Elliptic Curve Cryptography: the group law on a curve

Table of Contents

Public-key cryptography — the geometry underneath

Take a smooth cubic curve. Its points can be added with nothing more than a ruler: draw a line, find where it meets the curve again, reflect. That one geometric rule, repeated, builds a group where multiplication is easy but undoing it — finding how many times a point was added to itself — is computationally hopeless. Every TLS handshake, Bitcoin signature, and passkey login rests on that asymmetry.

The one-sentence idea. A private key is just a number d. The public key is the point Q = dG, computed by adding a fixed generator point G to itself d times. Going forward takes microseconds even for a 256-bit d; going backward, recovering d from Q, is the elliptic curve discrete logarithm problem, and no known algorithm does it in feasible time.

1 — The curve: a cubic with a symmetry

An elliptic curve over the real numbers is the set of points satisfying a short Weierstrass equation, plus one extra point at infinity that will act as the identity. Two things matter about the shape: it is symmetric about the x-axis (if (x, y) is on the curve, so is (x, −y)), and it must be smooth — no cusps or self-crossings — which is exactly what the discriminant condition below guarantees.

The curvey2=x3+ax+b
Smoothness condition4a3+27b2≠0When this quantity is 0 the curve pinches into a cusp or a node, the chord-and-tangent rule breaks down there, and the cryptography fails with it — singular curves have easy discrete logs.
The curve used in this stepy2=x3−2x+24a3+27b2=4(−8)+27(4)=−32+108=76≠0
the curve x-axis: mirror line of the symmetry

Figure 1. Drag the sliders below: the curve reshapes live. With a discriminant above zero the cubic has one real root and the curve is a single connected loop-with-a-tail; push it negative and a separate oval splits off on the left. Find a combination where the discriminant hits exactly 0 and watch the curve pinch — that is a singular curve, and it is excluded.

Figure 1: a = −2.0, b = 2.0 (smooth, one component)

76.04a³ + 27b²
SmoothCurve status
1Connected components

How to read this

  • Symmetry: the upper and lower halves are mirror images. Reflection across the x-axis will become negation in the group.
  • The point at infinity, written 𝒪, is not drawn — it sits “at the end of every vertical line” and acts as zero: P + 𝒪 = P.
  • Real curves are for intuition only. Real cryptography uses the same equation over a finite field, where the curve becomes a scatter of discrete points (Step 3) — but the addition rule is identical.

2 — Point addition: the chord-and-tangent rule

Here is the whole group law in one picture. A line meets a cubic in at most three points. So: draw the line through P and Q; it must hit the curve at a third point, call it R′; reflect R′ across the x-axis and define that to be P + Q. Reflection is what makes the operation associative and gives every point an inverse — the reflected point is −P, and P + (−P) is the vertical-line case, defined to be 𝒪.

Slope of the chordm=yQ−yPxQ−xP
Sum, x-coordinatexR=m2−xP−xQThis comes from substituting the line into the cubic: the three roots of the resulting equation sum to m², and two of them are already known.
Sum, y-coordinateyR=m(xP−xR)−yP
Doubling (P = Q): tangent slopem=3xP2+a2yPWhen the two points merge, the chord becomes the tangent — implicit differentiation of the curve equation. Everything else is unchanged.
P Q R′: third intersection R = P + Q: reflection of R′ chord through P and Q

Figure 2. Slide P and Q along the upper half of the curve. The gold chord always meets the curve a third time at R′, and the dashed vertical drops from R′ to its mirror image R = P + Q. Push Q onto P and the chord swings into the tangent — that limiting case is point doubling, 2P. Note that R lands on the lower half here: sums wander all over the curve, which is exactly what makes repeated addition look random.

Figure 2: P = (−1.20, 1.63), Q = (1.00, 1.00)

−0.29Slope m of chord or tangent
(0.28, 1.21)R′: third intersection
(0.28, −1.21)R = P + Q

How to read this

  • Closure: the sum of two curve points is always another curve point — the reflection step is what guarantees it.
  • Inverses: reflect P to get −P. The line through them is vertical, never meets the curve a third time in the plane, and the sum is defined as 𝒪.
  • Why a group matters: closure, identity, inverses, and associativity mean we can do arithmetic with points exactly as with numbers — the next step exploits this.

3 — Scalar multiplication: the one-way street

Now move the same equation to a finite field, where real cryptography lives. Work modulo the prime p = 17 on the curve below. The “curve” is now just 18 scattered points plus 𝒪, a group of order n = 19, which is prime, so every non-identity point generates the whole group. Fix the generator G = (5, 1). Scalar multiplication means adding G to itself k times, and the efficient way is double-and-add: read k in binary, double the running point for each bit, and add G whenever a bit is 1. A 256-bit private key needs only about 256 doublings and at most 256 additions — never 2256 additions.

The finite-field curvey2≡x3+2x+2(mod17)
Scalar multiplicationkG=∑i=1kGAddition is the chord-and-tangent rule of Step 2, with every coordinate reduced mod 17 and divisions replaced by modular inverses.
Worked check: G really is on the curve12=153+2·5+2=137≡1(mod17)
curve points mod 17 G = (5, 1) kG: current multiple hop from (j−1)G to jG

Figure 3. Each hop adds one more G. The landing points jump around the grid with no visible pattern: 2G = (6, 3) sits next to G, but 7G = (0, 6) is across the plot and 13G = (16, 4) is in the far corner. At k = 19 the walk returns to the point at infinity, and the cycle restarts: 19G = 𝒪, 20G = G. Given only the final point, nothing about the path is recoverable by looking.

Figure 3: k = 13, kG = (16, 4)

(16, 4)kG
1101k in binary
3 doubles, 2 addsDouble-and-add cost

How to read this

  • Forward is cheap: double-and-add costs about one doubling per bit of k, roughly 256 point operations for a real 256-bit key.
  • The walk fills the group: because 19 is prime, the multiples of G visit all 18 affine points before reaching 𝒪. Real curves are chosen the same way, with a large prime-order subgroup.
  • No shortcuts in the picture: consecutive multiples are unrelated as positions. That visual randomness is the discrete logarithm problem, coming in Step 6.

4 — Key exchange: ECDH

Diffie–Hellman needs an operation that commutes: a(bG) must equal b(aG). Scalar multiplication does exactly that, because both are just (ab)G. Alice picks a secret a and publishes A = aG; Bob picks a secret b and publishes B = bG. Alice computes aB, Bob computes bA, and both hold the same point — while an eavesdropper who sees G, A, and B cannot combine them without solving a discrete log.

The shared point, both waysaB=a(bG)=(ab)G=b(aG)=bA
Default values, checkeda=3A=3G=(10,6)b=5B=5G=(9,16)aB=15G=(3,16)=bA
A = aG: Alice’s public key B = bG: Bob’s public key shared point abG

Figure 4. Only A and B ever travel over the wire. Each side privately multiplies the other’s public point by its own secret and lands on the same teal point. In practice the x-coordinate of that point (here 3) is hashed into a symmetric session key — the point itself is never used as the key directly.

Figure 4: a = 3, b = 5, shared point (3, 16)

(10, 6)A = aG (public)
(9, 16)B = bG (public)
(3, 16)Shared point abG
3Shared x: fed to a key derivation hash

Why the eavesdropper loses. From A = aG alone, recovering a is a discrete log. Combining A and B directly into abG without knowing either secret is the computational Diffie–Hellman problem — believed just as hard on a well-chosen curve.

5 — Signatures: ECDSA

A signature proves “the holder of d signed this message” without revealing d. The signer commits to a one-time secret k by publishing the x-coordinate of kG, then mixes that commitment with the message hash and the private key. Verification recombines the public key Q = dG with the signature in a way that reconstructs the commitment point — but only if the signature really was built from d.

SetupQ=dGe=hash of the message, reduced modn
Signr=xkGmodns=k−1(e+dr)modnThe signature is the pair (r, s). If k is ever reused for two different messages, d can be solved for algebraically — this exact failure emptied wallets and once broke a games console’s signing key.
Verifyw=s−1modnu1=ewmodnu2=rwmodnX=u1G+u2QAccept exactly when the x-coordinate of X, reduced mod n, equals r. Substituting the signing equation shows X = kG, so an honest signature always passes — and producing one that passes, without d, requires forging that reconstruction.
Default signature, fully checkedd=4Q=4G=(3,1)k=6kG=(16,13)r=16e+dr=13+4·16=77≡1(mod19)k−1=16since6·16=96≡1(mod19)s=16·1=16w=s−1=6since16·6=96≡1(mod19)u1=13·6=78≡2(mod19)u2=16·6=96≡1(mod19)X=2G+1Q=(16,13)=kGThe x-coordinate of X is 16, which equals r: the signature verifies.
Q = dG: public key kG: signer’s commitment X = u₁G + u₂Q: verifier’s reconstruction

Figure 5. At the defaults the blue reconstruction lands exactly on the orange commitment point — the two markers coincide, drawn slightly offset so both stay visible. Change any of d, k, or the message hash and the algebra re-runs live: X tracks kG every time, because verification is the signing equation rearranged. What the verifier never learns is d or k themselves.

Figure 5: d = 4, k = 6, e = 13, signature (r, s) = (16, 16), valid

(3, 1)Q = dG (public key)
(16, 16)Signature (r, s)
u₁ = 2, u₂ = 1Verification scalars
(16, 13)X: x mod 19 = r, valid

How to read this

  • r binds the signature to k, s binds it to both the message (through e) and the key (through d). Tampering with the message changes e, the reconstruction X moves, and the check fails.
  • Some slider settings are invalid by design: if r or s comes out 0 the signature must be discarded and a fresh k chosen — the readouts say so when it happens.
  • Deterministic nonces (RFC 6979) derive k from the message and key, removing the reuse failure mode entirely; Ed25519 builds this in.

6 — Why the discrete log is hard

Everything above is public except one problem: given G and Q = dG, find d. On the toy curve an attacker can simply walk the multiples of G until the target appears — try it below; on average the target turns up halfway through the group. The devastating fact is how that walk scales. The best known generic attack, Pollard’s rho method, needs about the square root of the group order — for a 256-bit curve that is still roughly 2128 point operations, and unlike factoring there is no subexponential index-calculus attack: elliptic curves offer no smooth structure for it to exploit. Quantum computers are the exception — Shor’s algorithm solves this problem in polynomial time, which is why post-quantum schemes exist — but classically, the gap below is the whole story.

multiples already tried target point Q match found

Figure 6. The attacker computes G, 2G, 3G, … and compares each against the target. On this 19-point group the search ends within 18 tries — and is utterly hopeless as a method once the group has 2256 points, because the same walk would need about 2255 tries by brute force, or 2128 with the best generic shortcut.

Figure 6: secret d = 11, attacker has tried 6 guesses: not found

6 of 18Multiples checked
Not yetTarget found?
6 nsTime at a billion guesses per second
Security levelECC key sizeComparable RSA key sizeBest generic attack on ECC
80 bits160 bits1024 bitsabout 2⁸⁰ point operations
112 bits224 bits2048 bitsabout 2¹¹² point operations
128 bits256 bits3072 bitsabout 2¹²⁸ point operations
192 bits384 bits7680 bitsabout 2¹⁹² point operations
256 bits521 bits15360 bitsabout 2²⁵⁶ point operations

Put the 128-bit row in time units: 2128 is about 3.4 × 1038. At a trillion point operations per second — far beyond any single machine — the search runs about 3.4 × 1026 seconds, roughly 1.1 × 1019 years, against a universe about 1.4 × 1010 years old. That is why a 256-bit elliptic curve key, small enough to fit in a sentence, protects traffic that a 3072-bit RSA key is needed to match.

The honest caveats. The hardness is a well-tested belief, not a proof — no one has proven the discrete logarithm is hard on any curve. It holds only for carefully chosen curves (large prime-order group, no special structure), correct implementations, and secret scalars that stay secret. And a large fault-tolerant quantum computer running Shor’s algorithm would end it — the one attack that does not care how big the group is.

Curves used here: y² = x³ − 2x + 2 over the reals for the geometry, and y² = x³ + 2x + 2 over the field mod 17 (group order 19, generator G = (5, 1)) for everything cryptographic. Real deployments use standardized curves such as P-256 and Curve25519 with group orders near 2²⁵⁶, identical rules, vastly larger groups. Key-size comparisons follow NIST SP 800-57.