A Padlock You Can Post Publicly

Every cipher before the 1970s had the same hole, and it was not in the cipher.

However good your encryption, both parties needed the same key, which meant the key had to get from one to the other. Diplomats carried codebooks in locked bags. Banks sent couriers. Militaries printed key material for months in advance and distributed it physically, and anyone who intercepted that shipment had everything, retrospectively and prospectively. The strength of the lock was never the binding constraint; the delivery of the key was.

Public-key cryptography removes the delivery.

The idea is best held as an object. You make a large number of padlocks that can be snapped shut by anyone and opened only by your key. You post them everywhere: hand them to strangers, nail them to noticeboards, publish them in a newspaper. Anyone who wants to send you something locks it with one of your padlocks and sends the box. They cannot open it afterwards and neither can anybody watching. Only you can.

Nothing secret ever travels. That is the whole achievement.

Making the padlock out of arithmetic needs a trapdoor: a one-way function with a shortcut available to whoever holds extra information. Modular exponentiation does it. Raising to a power mod a large number is cheap, undoing it is believed hard, and knowing the two primes that built the modulus makes it easy again. Chapter one supplied the wrapping that keeps it cheap, chapter two supplied the gap that keeps it secret, and this is the two used together.

Whitfield Diffie and Martin Hellman published the idea in 1976. Ron Rivest, Adi Shamir and Leonard Adleman built a working system the following year, and RSA is their initials.

The credit is genuinely shared, though, and the sharing is unusual.

James Ellis at GCHQ had the concept in 1970, Clifford Cocks had essentially RSA in 1973, and Malcolm Williamson had what became Diffie-Hellman key exchange in 1974. All of it was classified. None of them could publish, none received credit in their working lives, and the work was declassified only in 1997. Cocks' paper is a few pages and he has said he did it in an evening.

The honest summary is that they got there first and it made no difference to the world. A result nobody can act on is not yet a contribution, which is an uncomfortable thing to say about three people who were simply obeying the rules of their employment.

One last thing, because the padlock metaphor leaks in exactly one place and it is the place everything actually goes wrong.

A padlock proves nothing about who made it. If an attacker can replace the padlock you published with one of their own, they receive everything, read it, re-lock it with your real padlock and pass it on, and both parties see a secure connection and notice nothing. The arithmetic is untouched. The assumption that failed was that the key you received is the key that was sent.

Certificates and the authorities who sign them exist to close that hole, and they are the component that keeps failing: authorities compromised, certificates issued in error, trust chains that nobody audits. The mathematics in this book has held for fifty years. The part built out of institutions and trust has not, which is roughly what anyone who had read the rest of this library would have predicted.