How a curve keeps a secret

Every time your browser opens a page over HTTPS, it agrees on a secret key with a server it may never have talked to before. They do it in public: anyone on the network can record every byte that passes between them, and still the key stays theirs. Very often, what makes that possible is a curve.

Not a metaphorical one. A specific curve, drawn by an equation you could have met at school, with one odd twist: a rule for “adding” two of its points to get a third. That addition is quick to do and, as far as anyone knows, practically impossible to run backwards. In this essay we’ll build the trick up from nothing, one figure at a time.

Each figure can be handled: drag the points, move the sliders, spin the shapes. A ghost cursor demonstrates what to try and steps aside the moment you take over. Every figure also has a reset button, so nothing you do can break it.

A curve with a rule

The curves in this story are the solutions of one family of equations:

Choose two numbers a and b, and every point (x, y) that makes both sides equal belongs to the curve. These are called elliptic curves. The name is inherited from an old problem, measuring the length of an arc of an ellipse, and that is the last we’ll hear of ellipses: these curves don’t look like one.

Because y only appears squared, if (x, y) is on the curve then so is (x, −y): every elliptic curve is symmetric about the horizontal axis. Depending on a and b it comes in one piece, or in two: an egg-shaped loop beside an endless arm. Both are allowed.

What isn’t allowed is the moment in between. Set a = −3 and b = 2 and the loop touches the arm, so the curve crosses itself; at a = 0, b = 0 it grows a sharp point. At such points the construction we’re about to learn stops working, and both happen exactly when 4a³ + 27b² = 0. Cryptographers rule those curves out, and the figure turns hot when you land on one. From here on we’ll use one well-behaved curve, y² = x³ − 3x + 6.

Adding two points

Here is the rule that makes these curves special. Take two points on the curve, P and Q, and draw the straight line through them. Because the equation is a cubic, a line that crosses the curve twice will, apart from exceptions we’ll deal with shortly, cross it exactly once more. Call that third point R and reflect it across the horizontal axis. The reflection is what we call P + Q.

It’s a strange thing to call addition, and nothing about it should feel obvious yet. One thing you can check straight away: the line through P and Q is the same as the line through Q and P, so P + Q = Q + P.

The picture turns into arithmetic without much effort. If the line has slope λ, the sum has coordinates

Subtraction, multiplication and one division, nothing more. That will matter later, when we throw the picture away and keep only the arithmetic.

What about P + P? There is no single line through a point and itself, but if you slide Q onto P in the figure above, the line settles into a position anyway: the tangent, which just grazes the curve at P. So that is the line we use. Its slope comes from the curve’s derivative, λ = (3x_P² + a) / 2y_P, and the rest of the recipe stays the same.

Now drag P down to the spot where the curve crosses the horizontal axis. The tangent there is vertical, and a vertical line never meets the curve a third time. The rule has a hole in it.

The point at infinity

The same hole appears whenever Q is the mirror image of P: the line through them is vertical too, and there is no third point. To patch it we add one extra point to the curve, called O, the point at infinity, and declare that every vertical line passes through it.

That can sound like cheating, so here is a way to see it. Squash the entire plane into a disc, so that everything infinitely far away lands on its rim. Straight lines become arcs running from one side of the rim to the opposite side, and every vertical line runs to the very top and the very bottom. The two arms of the curve head there as well. Now agree that the top and the bottom of the rim are the same point. That point is O.

As Q approaches P’s mirror image, the third point slides off towards the top of the disc, and it arrives at O exactly when the line becomes vertical. So the rule always has an answer. And O behaves just like zero: adding it to a point changes nothing, P + O = P, and adding a point to its mirror image gives O. That is why the mirror image of P is written −P.

Brackets don’t matter

One more property is needed, and it’s the surprising one. If you add three points, does it matter which pair you add first? Is (P + Q) + R the same point as P + (Q + R)? There’s no obvious reason it should be. The two sides are built from four different lines.

And yet they always land in the same place. This property is called associativity, and it holds on every elliptic curve. Proving it takes either pages of algebra or some genuinely deep geometry (look up the Cayley–Bacharach theorem if you’re curious). A set with an addition like this, with a zero, negatives and associativity, is what mathematicians call a group. For us, it means a long sum of points has one answer however it’s bracketed.

Multiplying by a whole number

Once you can add, you can add a point to itself again and again: 2P = P + P, 3P = 2P + P, and so on. Adding P to itself n times is written nP and called scalar multiplication. Here is P = (1, 2), a point with whole-number coordinates on our curve, multiplied by n.

The multiples don’t march along the curve in order; they leap about, and their coordinates get messy fast. 2P is a tidy (−2, −2), but 3P is already (25/9, −118/27). Underneath there is a hidden order. On the real curve, multiplying by n is secretly like turning a dial n times as far, and a function called the elliptic logarithm can read the dial back off a point. Keep that in mind: it’s a weakness we will need to get rid of.

To compute nP for a large n you don’t need n − 1 additions. Write n in binary and read its digits from the left. Start with P; for each following digit, double what you have, and if the digit is 1, add P. This is called double-and-add.

Doubling makes the jumps grow exponentially. For a 256-bit number, which is around 10⁷⁷, double-and-add needs at most 255 doublings and 255 additions: a few hundred operations instead of a count of additions with 77 digits. Multiplying is easy. Hold on to that, because it is half of the trapdoor.

Clock arithmetic

Real numbers are a poor fit for cryptography. Computers can’t store them exactly, and the smooth geometry gives away too much: as the dial above suggests, there are ways to read off how many times a point was added. So we keep the equation and change the numbers.

Instead of all real numbers we use only the whole numbers 0, 1, 2, …, p − 1 for some prime p, and whenever a result passes p we wrap around, like the hours on a clock face. This is arithmetic modulo p. Addition, subtraction and multiplication work as usual. Division works too, as long as p is prime: dividing by q means multiplying by the number q⁻¹ for which q · q⁻¹ leaves remainder 1. With p = 97, for instance, 13⁻¹ = 15, because 13 · 15 = 195 = 2 · 97 + 1.

Here is the same curve, y² = x³ − 3x + 6, with all the arithmetic done modulo 97.

The curve has become a scatter of 106 points. It doesn’t look like a curve at all, but it keeps the old symmetry: whenever (x, y) is on it, so is (x, p − y), which is −y in clock arithmetic. So the scatter is mirrored about the line y = p/2. Add the point at infinity and there are 107 points in total. That happens to be a prime, which will be convenient. The count always stays close to p: Hasse’s theorem guarantees it is within 2√p of p + 1.

Since point addition was only ever arithmetic, it still works. Surprisingly, the picture survives as well. The line through P and Q becomes the set of points with y = λx + c, modulo 97. Drawn on the grid, that is a straight line which leaves through the top edge and comes straight back in through the bottom, again and again.

Follow the wrapped line and you’ll find it meets the curve at exactly three points, P, Q and R, just like a line on the real curve (a tangent counts its point twice). The panel works through the same formula as before, with every division turned into a multiplication by an inverse.

If leaving through the top really is the same as entering at the bottom, the honest thing to do is glue those edges together. That makes a tube. The left and right edges wrap around too, so bend the tube until its ends meet, and the grid becomes the surface of a doughnut, a torus. The wrapped line turns into a single unbroken loop.

The trapdoor

Now we can state the problem that keeps the secret. Everyone agrees on a curve and a starting point G. You pick a secret number n and publish Q = nG. Given G and Q, can anyone find n?

On our small curve, easily. Try n = 1, 2, 3, … until nG lands on Q. There are only 107 possibilities, and the computer below gets there in seconds even at a leisurely pace.

Real curves use the same equation with a prime p about 2²⁵⁶ in size and a similar number of points: roughly 1.2 × 10⁷⁷, a number with 78 digits. That is within a few powers of ten of the usual estimate for the number of atoms in the observable universe, around 10⁸⁰. Computing nG takes double-and-add a few hundred steps. Trying every n at a billion tries a second would take about 3.7 × 10⁶⁰ years. The universe is about 1.4 × 10¹⁰ years old.

There are cleverer attacks than counting. The best general method known, Pollard’s rho, needs roughly the square root of the number of points: around 2¹²⁸, or 3.4 × 10³⁸ steps. Give a billion computers a billion steps per second each and that still takes about 10¹³ years, nearly 800 times the age of the universe. This is the elliptic-curve discrete logarithm problem. Its hardness is a well-tested belief rather than a theorem, and decades of work haven’t dented it for well-chosen curves. The one known threat is a large quantum computer running Shor’s algorithm, which is why post-quantum methods are now being deployed alongside elliptic curves.

Two secrets, one point

With a trapdoor in hand, key exchange is almost an anticlimax. Alice and Bob agree, in public, on a curve and a point G. Alice picks a secret number a and publishes A = aG. Bob picks a secret b and publishes B = bG. An eavesdropper, traditionally called Eve, sees G, A and B.

Then Alice takes Bob’s public point and multiplies it by her own secret, computing aB = a(bG). Bob does the same with hers: bA = b(aG). Each is just G added to itself ab times, and since addition doesn’t care about order or brackets, both arrive at the same point, abG.

Alice and Bob now share a point that Eve could only find by solving the trapdoor. Run its x-coordinate through a hash function and it becomes the key for the rest of the conversation. This is elliptic-curve Diffie–Hellman, ECDH, and a version of it runs inside most of the secure connections your browser makes.

A real curve

Production curves are the same thing with very large numbers. Here is P-256, standardised by NIST and among the most widely deployed curves in the world. (For key exchange, browsers more often pick X25519, built on Curve25519, which uses a differently shaped equation and the same ideas.)

That string of 64 hexadecimal digits is the whole private key. Everything else on the card is public, printed in the standard for anyone to read.

Where it breaks

The mathematics has held up well. The failures happen around it.

Elliptic curves also make digital signatures. In ECDSA, the most widely used scheme, every signature needs a fresh secret random number k, called a nonce: used once, then thrown away. A signature on a message whose hash is z is a pair of numbers (r, s), where r is the x-coordinate of kG and s = (z + rd) / k, all modulo the number of points n, and d is the private key.

Sign two different messages with the same k and both signatures carry the same r, which anyone can notice. Subtract one equation for s from the other and k falls out; with k known, d follows in one more line.

This isn’t hypothetical. In December 2010, at the 27th Chaos Communication Congress, the fail0verflow group showed that the code Sony used to sign PlayStation 3 software reused the same supposedly random nonce for every signature. From two signatures they computed the private key, the one that decides what code the console will trust. No curve was broken. A random number simply wasn’t random.

Most real failures look like that: nonces reused or subtly biased, points accepted without checking that they lie on the curve, secrets leaking through timing. Modern defences mostly take those choices away from people. RFC 6979 derives the nonce deterministically from the key and the message, and Ed25519 signatures do the same by design. For anyone writing software the advice is the dull one: use a well-reviewed library and let it handle the curve.

Somewhere beneath this page, while you were reading, your browser did one of these exchanges. It picked a secret, multiplied a point, and agreed on a key with a stranger in full view. Nothing was hidden. Some sums are simply easy to do and hard to undo.