What is an elliptic curve, really?

An elliptic curve is every point (x, y) that satisfies one equation:

y² = x³ + a·x + b

Pick two numbers a and b and you get a curve. Because the left side is y squared, the curve is a mirror image of itself above and below the horizontal axis: if (x, y) is on it, so is (x, −y). Depending on a and b, it's either one smooth swoop or a swoop plus a separate oval.

Here's the surprising part. You can add points on the curve, and the answer is another point on the curve. The rule:

1. Draw a straight line through the two points, P and Q. On these curves, that line almost always hits the curve at exactly one more spot.
2. Flip that third spot to the other side of the horizontal axis. The flipped point is P + Q.

Two special cases complete the rule. To add a point to itself, use the line that just touches the curve there, the tangent. And when the line is perfectly vertical, as it is for P and −P, it never comes back down. Mathematicians add one extra, imaginary "point at infinity" for vertical lines to hit. It plays the role of zero: P + (−P) = 0, and P + 0 = P.

It's a small miracle that this rule behaves like real addition. It doesn't matter which order you add things in, or how you group them: (P + Q) + R always equals P + (Q + R). That last fact is not at all obvious from the picture, and proving it takes some real work. But it's what makes everything else possible.

Now do what we did on the clock: start at a point G and keep adding it. G, then G + G = 2G, then 3G, and so on. Writing kG for "G added to itself k times" gives us our forward step. Using the same doubling shortcut as before, even an astronomically large k takes only a few hundred doublings and additions.

On the smooth curve above, though, the points drift in a fairly orderly way, and the numbers turn into ever-messier fractions. Cryptography needs something more scrambled, with whole numbers only. So we put the curve on a clock.

Keep the same equation, but do every calculation mod p for a prime p, exactly like the clocks in Chapter 1. Now x and y can only be whole numbers from 0 to p − 1, and the curve stops being a curve. It becomes a scatter of dots. Division still works, because on a prime-sized clock every number except 0 has a partner it multiplies with to make 1. The same add-two-points formulas keep working, dot to dot.

See how kG jumps around with no pattern a human could spot? That's our one-way function. Given G and k, finding kG is quick. Given G and the point kG, finding k is the elliptic curve discrete logarithm problem. On a well-chosen curve, the best known methods take roughly as many steps as the square root of the number of points. Notice the mirror symmetry, too: every dot at height y has a twin at p − y, the clock version of flipping across the axis.

How many dots are there? Always roughly p: a theorem by Helmut Hasse says the count is within 2√p of p + 1. So a curve on a gigantic clock has a gigantic number of points, and walking it backward becomes hopeless.

P-256 is exactly this, scaled up. Its clock size is a prime with 78 digits, chosen with a special binary shape so that computers can do the wraparound quickly. Its number of points is another prime, also about 10⁷⁷, so the best known attacks need around 2¹²⁸ steps. Its a is −3, a common choice that makes the doubling formula faster. And its b is a seemingly random 78-digit number.

You don't have to take any of this on faith. The toy below holds P-256's real numbers and does the arithmetic in your browser.

So where did that b come from? Not from a person typing digits. According to the standard, it was produced by feeding a 20-byte seed into a hash function, a kind of digital blender. Here is P-256's seed:

c49d3608 86e70493 6a6678e1 139d26b7 819f7e90

Why would anyone make a curve from a blended seed? Because a few special kinds of curves are known to be weak, and a dishonest designer might try to slip one in. Chapter 3 shows how a seed is supposed to prove nobody did that, and we'll blend P-256's seed into P-256's b right here in the browser. Then comes the real question of this case: where did the seed come from?