Public keys: Diffie–Hellman and RSA

The Cold War. A man walks down an airport corridor with a briefcase chained to his wrist. Nothing in it is secret in itself: pages of random digits, next month’s keys for an embassy’s cipher machines. But without that briefcase the embassy falls silent. Couriers carried keys around the world by the thousand.

Every cipher we’ve met so far, from Caesar to the one-time pad and AES, works the same way: sender and receiver must hold the same key. Such ciphers are called symmetric. And they all share one headache: before you can encrypt, the key has to get there somehow. Secretly. And to send something secretly you need… a cipher with a key.

A vicious circle

This is the key distribution problem. For two people one meeting solves it. But picture a network where everyone must talk to everyone in private. Ten people need 45 different keys; a thousand need 499,500; a billion internet users would need about half a quintillion. And every one of those keys has to be delivered by hand.

Now picture yourself visiting your bank’s website for the first time. You’ve never met the bank, no courier has called, and your whole conversation runs from the first byte over other people’s wires: café Wi-Fi, your provider, a dozen internet nodes. How do you agree on a secret key when strangers hear every word?

Here’s a thought experiment that suggests it isn’t hopeless. Alice puts a letter in a box, snaps her padlock on it and sends it to Bob. Bob can’t open it, but he adds his own padlock and sends it back. Alice removes her padlock and sends it again. Now only Bob’s padlock is on the box: he opens it and reads. The box passed through the postman’s hands three times and was never open. And nobody exchanged keys!

Diffie–Hellman: mixing paints

In 1976 Whitfield Diffie and Martin Hellman of Stanford published a paper called “New Directions in Cryptography”. In it was a way for two people to agree on a shared secret while talking only in front of witnesses. Their colleague Ralph Merkle came up with an important part of the ideas.

It’s easiest to understand with paint. Mixing paint has just the property we need: mixing is easy, while separating a mix back into its colours is practically impossible.

1. Alice and Bob openly agree on a common paint, say yellow. Everyone sees it.
2. Each picks a secret paint and shows it to no one.
3. Each mixes the common paint with their secret one and sends the mix to the other, in the open.
4. Each adds their own secret paint to the mix they received.

Now both have the same colour: common + Alice’s secret + Bob’s secret, only mixed in a different order. Eve, eavesdropping, saw the yellow and both mixes. Mixing those together won’t do: her pot has two portions of yellow. And she can’t extract a secret out of a mix.

Diffie and Hellman actually mixed numbers, not paint. The common “paint” is two public numbers: a large prime p and a number g. Alice’s secret is a number a. To “mix” is to compute A = g^a mod p: raise g to the power a and take the remainder after dividing by p. We met remainders in the Caesar cipher: the same counting “round the clock”.

Bob receives A and raises it to his power b: A^b = g^ab. Alice does the same with B = g^b: B^a = g^ba. It’s the same number, the shared secret. To get it, Eve must find a from A = g^a mod p. This is called the discrete logarithm problem, and for primes hundreds of digits long nobody knows how to solve it in less than astronomical time.

A letterbox with a slot: RSA

Diffie and Hellman described one more idea but couldn’t find a way to build it. Let everyone have two keys: one public, one private. The public one encrypts, the private one decrypts. Like a letterbox with a slot: any passer-by can drop a letter in, but only the owner of the key can take letters out. You could print the public key in a newspaper: it can’t read anything.

A year later, in 1977, three researchers at MIT built such a letterbox: Ron Rivest, Adi Shamir and Leonard Adleman. The cipher is named after their initials: RSA. Here’s the recipe:

1. Pick two large primes p and q. They are the core secret.
2. Multiply them: n = p · q. This number is public.
3. Compute φ(n) = (p − 1)(q − 1), Euler’s function. It’s secret again: without p and q you can’t get it.
4. Choose e, a number sharing no factor with φ(n). The pair (n, e) is the public key.
5. Find d such that e · d leaves remainder 1 when divided by φ(n). That’s the private key.

To encrypt: the message is a number m (smaller than n), and the cipher is c = m^e mod n. To decrypt: m = c^d mod n. Raising to e and to d are two turns of a key that undo each other.

So where’s the protection? To find d you need φ(n), and for that you need p and q. Eve knows n. So she has to factor n. For n = 143 that takes a minute: 143 = 11 · 13. For a 600-digit n, nobody knows how to do it within the lifetime of the universe.

Easy to multiply, hard to factor

Multiplying two hundred-digit numbers takes a few minutes with a pencil and a microsecond on a computer. The reverse, finding the factors from the product, is another matter. You can try divisors, you can use clever methods, but for large numbers every known approach takes unimaginably long. A task that’s easy one way and hard the other is called a one-way function; RSA also has a “trapdoor”, the knowledge of p and q, which makes the way back easy.

Computers and algorithms have grown stronger since. In 2020 RSA-250, a 250-digit number, was factored; it took about 2,700 years of computer time. That’s why RSA keys today use an n of 2048 bits (617 digits) or more. The only known threat to that length is a large quantum computer: in 1994 Peter Shor found a fast factoring algorithm for one. No such machine exists yet, but people are already preparing: in 2024 the US approved its first post-quantum cryptography standards.

Signatures

A key pair has a second use, just as important. If you “encrypt” a message with the private key, s = m^d mod n, then anyone can “decrypt” it with the public one, s^e mod n. That gives no secrecy, but it proves authorship: only the owner of d could have produced that s. That’s a digital signature. In practice you sign not the message itself but its hash from the last lesson, which is why the hash must be free of collisions.

In real life the two inventions work together. When your browser opens a site over HTTPS, it uses a Diffie–Hellman exchange (usually the elliptic-curve version) to agree on a secret key with the server, and the server’s signature proves it really is your bank and not an impostor. After that the data is encrypted with a fast symmetric cipher such as AES. All of this in a fraction of a second, in front of witnesses, with not a single courier.

What to take with you

• Symmetric ciphers need a shared key, and it has to be delivered secretly. That’s the key distribution problem.
• Diffie–Hellman (1976): two people agree on a secret in the open. Mixing (powers modulo p) is easy; unmixing (the discrete logarithm) is hard.
• RSA (1977): n = p · q, φ = (p − 1)(q − 1), e is public, d is such that e · d leaves remainder 1 modulo φ. Cipher c = m^e mod n, decryption m = c^d mod n.
• RSA holds as long as n can’t be factored. At 617 digits that’s beyond any computer that exists.
• A signature is the same thing in reverse: sign with the private key, check with the public one.

You now hold the codebreaker’s whole toolkit, from counting letters to factoring numbers. All that’s left is to see it at work on real cases, from a plot against a queen to the ciphers of a serial killer. Next: famous ciphers →