How can a lock be public?

For thousands of years, secret messages worked the same way. You and your friend agree on a key ahead of time, maybe a word or a codebook, and use it both to scramble and to unscramble. This is called symmetric encryption, because both sides hold the same key.

It has one big catch: you have to get the key to your friend first, without anyone else seeing it. That's fine if you can meet in a café. It's hopeless for the internet, where your phone talks to a bank's computer it has never met, over wires and radio that anyone might be listening to.

In 1976, Whitfield Diffie and Martin Hellman published a way around it, now called public-key cryptography. (British government cryptographers had found similar ideas a few years earlier, but kept them secret until 1997.) The trick depends on a special kind of math problem, one that is easy to do but hard to undo.

You already know one kind of math that wraps around: a clock. Four hours after 10 o'clock is 2 o'clock, not 14. Mathematicians call this arithmetic modulo 12, written mod 12: do the sum, then keep only the remainder after dividing by 12.

Now take a clock with a prime number of hours, say 23 (a prime), and do something stranger. Start at 1, and keep multiplying by the same number, wrapping around the clock each time. Watch where it lands.

Going forward is easy. Even on a clock with an enormous number of hours, a computer can find where k steps land almost instantly, using a shortcut called square-and-multiply. But look at the landing spots: they jump all over the place, with no obvious pattern. So now try going backward.

On a 23-hour clock you can find Nib's secret by hand. On a 1,009-hour clock it takes a computer a moment. Real systems use clocks with hundreds of digits. Clever algorithms beat trying every step, but for well-chosen sizes even the best known methods would take longer than the age of the universe.

That lopsidedness is called a one-way function: easy forward, practically impossible backward. Undoing this particular one is called the discrete logarithm problem, and a great deal of real cryptography stands on it.

Here's the Diffie–Hellman trick. Nib and Tansy want a shared secret, but Grub is listening to everything they say. They agree, out loud, on a clock size p and a multiplier g. Then each picks a secret number of steps and announces only where they landed. Each one then takes the other's landing spot and walks their own secret number of steps from there.

Why do they end up at the same spot? Nib walks a steps and then b more; Tansy walks b and then a. Either way it's a×b steps in total, because the order of multiplying doesn't matter. Grub knows the starting point and both landing spots, but to get the shared secret he would have to work backward from one of them: the discrete logarithm problem again.

The same idea gives us digital signatures, which are what the NIST curves were standardized for. You keep a secret number as your private key and publish its landing spot as your public key. With the secret, you can produce a signature on a message that anyone can check against your public key, but nobody can forge without the secret. Your browser checks digital signatures every time it shows a website's padlock icon.

Clocks work, but they need very big numbers to be safe. In 1985, Neal Koblitz and Victor Miller each suggested doing the same trick with the points on an elliptic curve instead of the hours on a clock. The backward problem on a good curve is much harder, so the numbers can be far smaller. By NIST's own guidance, a 256-bit curve key gives about the same protection as a 3,072-bit key for RSA, the older and better-known public-key system.

Smaller keys mean faster connections and less battery, which is why curves took over. One of the most widely used is called P-256. It is one of the five NIST prime curves at the heart of our mystery, and the next chapter shows what it actually is.