Elliptic curves: the maths in your pocket
This is the equation y2 = x3 − 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 the previous chapter. 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.
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: you just try them all. But the curve in your ID card has roughly 2384 points. That number has 116 digits. No one tries that many, not even a supercomputer, not even in a billion years.
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.
Why curves and not just RSA
| RSA (prime numbers) | Elliptic curves | |
|---|---|---|
| Equally secure at | a 3072-bit key | a 256-bit key |
| 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's why the world is switching over: the newest Belgian ID cards use a curve (named P-384), older cards still use RSA. The padlock in your browser negotiates its key with a curve. Bitcoin addresses are points on a curve.
The rule for a and b. While sliding, you saw that some settings give a kink or a loop. Mathematically: if 4a3 + 27b2 = 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 it's exactly this game that protects your ID card.