Elliptic curves: the maths in your pocket

This is the equation y² = x³ − x + 1. Draw it, and you get a curved line — an elliptic curve. That sounds like something from a math textbook you'd never think about again. But this exact kind of line sits in the chip of your ID card, behind the padlock in your browser, and underneath Bitcoin. In this chapter you're going to click on it and see why.

Words you might need

Curve: Simply a curved line on a graph: every point (x, y) for which an equation holds true. A parabola is a curve. This is a slightly more interesting one.
Adding points: This is the strange idea. On this curve you can "add" two points together and get a third point on the same curve. Not by adding up the coordinates, but with a drawing rule: draw a line through the two points, see where it crosses the curve a third time, and mirror that point across the x-axis. Done: that's P + Q.
Doubling: P + P. You only have one point, so you take the tangent line — the line that just touches the curve at P — and do the same trick.
Clock arithmetic (modulo): Working with only whole numbers from 0 up to a limit, where you start back at 0 once you pass the limit. You know this from chapter 6, where it was the engine under Diffie–Hellman. Here you'll see what it does to a graph.

Click on the curve

Everything happens in your browser. Nothing is sent to the server.

Click somewhere on the line. That's P. Click a second time for Q. The demo draws the line, finds the third intersection, mirrors it, and shows P + Q.
Click Clear, pick one point and press Double. Then keep clicking Add P again: 3·P, 4·P, 5·P… the points jump all over the curve.
Slide a and b. The shape changes — sometimes the line splits into two pieces. Find the setting where it gets a kink: that one's unusable, and the demo says why.
Press Clock arithmetic (modulo 97). Same equation, only whole numbers now. See what's left of the line. Pick a dot and add points again.

a =

b =

What you just saw

On the smooth line you could still sort of "feel" where you were. After adding three times you're roughly there, after four times roughly there. But the moment you switched to clock arithmetic, the line fell apart into a cloud of dots with no pattern at all. And the addition still worked — same formulas, same rules — only now the result jumps back and forth across the plane.

Now the whole secret. Say I pick a point P and add it to itself 1,000,000 times. A computer can do that blazingly fast — there's a trick that makes it take only about thirty steps. I give you P and the end point. Can you work out that it was 1,000,000 times? On the dot cloud with 97, sure: there are only about a hundred points, and you just try them all. But the curve in your ID card has roughly 2³⁸⁴ points. That number has 116 digits. No one tries that many, not even a supercomputer, not even in a billion years.

Trying them all isn't even the smartest attack, by the way. There is a shortcut, found by John Pollard in 1978, that needs roughly the square root of the number of points: about 2¹⁹² steps. That number still has 58 digits, and nobody gets there either. Cryptographers always count with the best shortcut they know, never with trying everything. That will matter in a moment.

That's the private key: the number of times. The public key is the end point. Anyone may see the end point; no one can count backwards. Exactly the open padlock from the previous chapter — but with a graph instead of prime numbers.

How many dots? You'd think: modulo 97, so 97 points. It doesn't work like that. In clock arithmetic the demo counts them for you. With a = −1 and b = 1 there happen to be exactly 97, plus the point at infinity: 98. Go back to the smooth line, move a or b and switch again: now you get, say, 80, 106 or 117. You can't guess the number, but it's never far from 97. Helmut Hasse proved in 1933 that it always stays within 2√p of p + 1; for 97 that means between 79 and 117. For P-384 the number of points is known exactly, and it is itself a prime number. That's no accident: the curve was picked for it.

Why curves and not just RSA

	RSA (prime numbers)	Elliptic curves
Equally secure at	a 3072-bit key	a 256-bit key
Best known attack takes	about 2¹²⁸ steps	about 2¹²⁸ steps
That's	a number with 925 digits	a number with 78 digits
Fits on a chip card?	barely	easily
Invented in	1977	1985, by Neal Koblitz and Victor Miller, independently of each other

Twelve-times-shorter keys for the same security. That doesn't mean RSA is badly built. "Equally secure" means: the best attack we know takes the same number of steps on both sides. Against RSA, attackers have had a clever tool since the early 1990s, the number field sieve, which factors far faster than trying everything. Against a well-chosen curve nobody has found anything like it; Pollard's shortcut is still the best there is. So RSA has to use bigger numbers to give the attacker the same amount of work.

That's why the world is switching over: the newest Belgian ID cards use a curve (named P-384), older cards still use RSA. P-384 sits one step above the table: about 2¹⁹² steps. With RSA you would need 7,680 bits for that, a number with 2,312 digits. The padlock in your browser negotiates its key with a curve. Your Bitcoin key is a point on a curve, and the address you hand out is the fingerprint of that point (see chapter 3).

The rule for a and b. While sliding, you saw that some settings give a kink or a loop. Mathematically: if 4a³ + 27b² = 0, the curve is "degenerate" and the addition stops working everywhere. Cryptographers pick a and b with great care — and they publish them, so that anyone can check there's no hidden weakness tucked away in there. That distrust is a field in its own right.

This is math: a group

What you just did — "adding" points with a drawing rule — has all the properties of ordinary addition. It's associative: (P + Q) + R = P + (Q + R), even though you can't see that right away. There's a "zero" (the point at infinity, which you ran into when the line went vertical). Every point has an opposite (its mirror image). Mathematicians call a set with an operation like that a group. That's the opening chapter of abstract algebra, the field where you learn that numbers, rotations of a cube, and points on a curve are, deep down, playing the same game. It's in the first year of every university math programme.

And that game reaches much further than secret codes. The moves of a Rubik's cube form a group, with more than 43 quintillion positions. Chemists sort molecules by their symmetry group and use it to predict which light a molecule can absorb. There are exactly 230 kinds of symmetry a crystal can have; they were counted out in 1891, with group theory. Physicists build their description of the smallest particles, the Standard Model, on groups. And the QR code on a concert ticket still scans with a corner torn off, thanks to algebra on a finite set of numbers, just like here. Cryptography is only one corner of that world.

Mind you: the group itself doesn't make your ID card secure. Groups are everywhere, and most of them are useless for secrets. Clock arithmetic with ordinary addition is a group too, and there you count back with a single division. The security hangs on one question about this one group that nobody has found a fast answer to: how many times was P added? That it looks hard is not a proof. It's an assumption that has held up for more than forty years.

Notice, by the way, what you did not need here. To understand why RSA is hard to run backwards, you first have to know something about prime numbers and factoring, and that is a subject in itself. Here a line crossing a curve was enough. Cryptographers therefore often say that for a beginner curves are in fact easier to grasp than RSA: the difficulty is not hidden in the mathematics underneath, it is lying on the table. That you read chapter 7.1 first and this chapter afterwards is historical order, then, not order of difficulty.