Public Keys
Secret Writing: A History of Codes, Ciphers and Codebreaking
Course 1 · Chapter 11 · Public Keys
Chapter 10 ended on the hardest problem in the whole story: how do two people who have never met agree on a secret key without anyone else learning it? For about two thousand years the only answer was "carry it there". In the 1970s a different answer appeared, and it turned out that it had been found twice, once in public and once in secret.
The Key Distribution Problem
Every cipher so far in this course, from the scytale of Chapter 2 to the pads of Chapter 10, is symmetric: the same secret locks and unlocks the message. That means the secret must travel to the other end first, by courier, diplomatic bag or codebook delivery. Armies and governments could afford this. A bank with thousands of customers, or a stranger shopping online, could not.
The question that cracked it open sounds almost like a riddle: can two people talk entirely in public, with every word overheard, and still end up sharing a secret that the listener cannot work out?
Two Everyday Pictures
You do not need algebra to see the idea. Two pictures do the work.
The paint-mixing picture. Alice and Bob agree in public on a common colour, say yellow. Each secretly picks a private colour and mixes it with the yellow. They swap the mixtures in public. Each then adds their own private colour to the mixture they received. Both end up with the same final blend: yellow plus Alice's colour plus Bob's colour. A watcher sees the yellow and the two mixtures, but un-mixing paint is practically impossible, so the watcher cannot recover the private colours or the final blend.
The padlock picture. Bob makes thousands of identical open padlocks and leaves them at the post office for anyone to take. He keeps the one key. Alice takes a padlock, puts her message in a box, snaps the lock shut and posts it. Anyone can lock the box; only Bob can open it. Alice and Bob never met and never exchanged a secret.
| Picture | Public part | Private part | Real scheme it stands for |
|---|---|---|---|
| Paint mixing | Starting colour and the two mixtures | Each person's own colour | Diffie-Hellman key exchange |
| Padlock | The open padlock | The key that opens it | Public-key encryption such as RSA |
Diffie and Hellman, 1976
In 1976 Whitfield Diffie and Martin Hellman published a paper that described exactly this kind of public agreement, using arithmetic in place of paint. It rests on a one-way function: something easy to do and extremely hard to undo. Multiplying is easy; given only the answer, finding the pieces is hard when the numbers are huge. Repeated multiplication on a "clock" (remainders after division) behaves the same way: easy to compute forward, with no known shortcut backwards when the numbers are large.
Their paper also posed the padlock idea in general form, a system with a public key for locking and a private key for unlocking, but did not supply a working example. That came the next year.
Ron Rivest, Adi Shamir and Leonard Adleman (1977): RSA, a practical public-key scheme named from their initials.
James Ellis, Clifford Cocks and Malcolm Williamson (early 1970s): GCHQ researchers reported to have reached the same ideas earlier, in secret.
Phil Zimmermann (1991): released PGP, putting public-key encryption in ordinary hands.
RSA, 1977
Rivest, Shamir and Adleman built the padlock. Their scheme starts by multiplying two large prime numbers together. The product is made public as part of the lock; the two primes stay secret and are the key to the unlock. Anyone can lock with the public product, but undoing it without the primes needs the product to be split back into its factors, and for numbers hundreds of digits long no one knows a fast way to do that.
Here is a toy version small enough to do by hand. The numbers below are far too small to be safe; they only show the shape.
Anyone who knew the primes 3 and 11 could work out the private key at once. The whole security of the real thing is that, for huge numbers, finding the primes from the product is not feasible with known methods.
The Secret Twin Discovery
In the late 1990s it became public that the same ideas had already been found inside the British signals intelligence agency, GCHQ. The usual account is that James Ellis worked out in the early 1970s that a lock without a shared secret was logically possible, that Clifford Cocks then found a practical method very like RSA, and that Malcolm Williamson found a method like Diffie-Hellman. Because the work was classified, none of them could publish, and the discoveries stayed private for over twenty years. The agency is said to have lacked the computing power to make the schemes practical at the time, and did not see their commercial future.
It is a rare clean case of simultaneous invention with one half hidden. Compare it with the Polish and British Enigma stories in Chapters 8 and 9: secrecy protected the codebreaking advantage, but it also meant the inventors received no recognition until long afterwards.
Why It Changed the Internet
Public-key methods solved key distribution, and that is what makes a secure web page possible. When your browser shows a padlock, it has used a public-key method to agree a fresh secret with a server it has never met, and then switched to a fast symmetric cipher for the bulk of the traffic. The same idea gives digital signatures: lock something with your private key and anyone can check it with your public key, which proves it came from you. For the engineering, see Cryptography Fundamentals and HTTPS/TLS Fundamentals, which pick up exactly where this chapter stops.
| Older world | Public-key world |
|---|---|
| Secret must be delivered in advance (courier, pads, codebooks) | Strangers can agree a secret in public |
| One key per pair of people, so a huge number of keys | One public key per person is enough |
| Sealed letters and signatures vouch for identity | Digital signatures vouch for identity |
| Strong cipher work needed government-scale resources | Strong cipher software runs on a home computer |
The Crypto Wars
Once strong encryption was available to everyone, governments faced the opposite worry to the one in Chapter 10: now the other side's messages, and criminals' messages, might become unreadable too. In the 1990s this became known as the crypto wars. In the United States, strong cryptographic software was treated as a kind of munition, so exporting it was restricted, and for a time products sold abroad used deliberately weakened keys. A proposed government-designed encryption chip with a built-in way for authorities to recover keys met fierce opposition from privacy and industry groups. Meanwhile, PGP spread by people simply copying it, and its author faced a long investigation before it ended.
The argument has not gone away. It returns whenever a government asks for a lawful way into encrypted messages, and technologists reply that a deliberate weakness for one party is a weakness for everyone. The debate is a political and technical one, and reasonable people disagree, so this course only records that it exists.
Show the worked answer
3, then 3 x 3 = 9 which leaves 2, then 2 x 3 = 6, then 6 x 3 = 18 which leaves 4, then 4 x 3 = 12 which leaves 5, then 5 x 3 = 15 which leaves 1. So the remainders for powers 1 to 6 are 3, 2, 6, 4, 5, 1.
(a) The power that gives 5 is 5. (b) Power 7 starts the pattern again: 1 x 3 = 3, so the remainder is 3.
Going forward is quick. Going backwards means searching the table. With a table of six entries that is trivial; with a number hundreds of digits long, the table would be impossibly large. That gap is what public-key schemes live on.
Where This Leaves the Secret Writer
Notice how the theme of the course has shifted. For centuries the contest was between cipher makers and codebreakers over clever alphabets and machines. Public keys moved the battle: the mathematics is now public and excellent, and attackers look instead for flaws in software, mistakes by users, stolen keys and weak random numbers. The last chapter turns back to the oldest kind of puzzle, messages that no one has yet been able to read.
Exercises
A small number-version of the paint-mixing exchange. The public numbers are 23 and 5. Alice's private number is 3 and Bob's is 4. Alice sends Bob the remainder (after dividing by 23) of 5 to the power 3. Bob sends Alice the remainder (after dividing by 23) of 5 to the power 4. Work out both messages, then show that each person, using their own private number, gets the same shared secret.
Use the toy RSA numbers from the chapter: public numbers 33 and 3, private number 7. (a) Lock the message number 2: raise it to the power 3 and take the remainder after dividing by 33. (b) Unlock your answer by raising it to the power 7 and taking the remainder after dividing by 33, and check that you get 2 back. (Hint: 8 times 8 is 64, which leaves 31 after dividing by 33, and 31 is the same as minus 2 on this clock.)
(a) A public number is 391, made by multiplying two primes. Find them by trial division (try dividing by 3, 5, 7, 11, 13, 17 and so on), and note how many tries you needed. (b) Explain in two or three sentences why this approach would be hopeless for a number with hundreds of digits. (c) In the padlock picture, say which thing is the public key, which is the private key, and which of the four requirements from Chapter 10's table the padlock idea removes.
Quick Reference
- Symmetric: one shared secret, which must be delivered first
- Public key: a lock anyone may use; only the key holder can open
- Diffie-Hellman: strangers agree a secret in public (paint mixing)
- RSA: lock built from the product of two secret primes
- One-way function: easy forward, practically impossible backward
- Digital signature: lock with the private key, check with the public key
- Check: dates, names, the GCHQ account and the crypto wars details
Next chapter: Unsolved and Hidden in Plain Sight, the open puzzles, how to make your own, and where to go next.