Elliptic Curve Cryptography: the group law on a curve
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 curve | |
|---|---|
| Smoothness condition | When 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 step |
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.
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 chord | |
|---|---|
| Sum, x-coordinate | This 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-coordinate | |
| Doubling (P = Q): tangent slope | When the two points merge, the chord becomes the tangent — implicit differentiation of the curve equation. Everything else is unchanged. |
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.
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 curve | |
|---|---|
| Scalar multiplication | Addition 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 curve |
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.
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 ways | |
|---|---|
| Default values, checked |
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.
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.
| Setup | |
|---|---|
| Sign | The 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. |
| Verify | Accept 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 checked | The x-coordinate of X is 16, which equals r: the signature verifies. |
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.
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.
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.
| Security level | ECC key size | Comparable RSA key size | Best generic attack on ECC |
|---|---|---|---|
| 80 bits | 160 bits | 1024 bits | about 2⁸⁰ point operations |
| 112 bits | 224 bits | 2048 bits | about 2¹¹² point operations |
| 128 bits | 256 bits | 3072 bits | about 2¹²⁸ point operations |
| 192 bits | 384 bits | 7680 bits | about 2¹⁹² point operations |
| 256 bits | 521 bits | 15360 bits | about 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.
