Public-Key Cryptography and the Padlock Idea

The answer to the key-distribution problem is due to Whitfield Diffie, Martin Hellman and Ralph Merkle in 1976, and to Ron Rivest, Adi Shamir and Leonard Adleman in 1977. It is called public-key cryptography, or asymmetric cryptography, and the core idea can be explained completely before a single number appears.

01.The padlock

Bob manufactures padlocks. They are ordinary padlocks with one property worth noticing: you can snap one shut with your bare hands, but opening it requires a small key, and Bob keeps the only copy of that key in a safe at home.

Bob now does something that sounds reckless. He mails out copies of his padlock, hanging open, to anybody who might ever want to write to him. He puts a stack of them in the lobby of his building. He posts one to Eve, because he does not mind. What he never sends anybody is the key.

Alice wants to send Bob something private. She picks up one of Bob's padlocks, puts her message in a box, snaps the padlock shut on the hasp, and posts the box.

Eve intercepts the box in transit. She has a padlock of her own, identical to the one on the box, and it does her no good at all. She can snap her padlock shut as many times as she likes. What she cannot do is open one, because opening needs the key, and the key never left Bob's safe.

Bob receives the box, takes his key out of the safe, opens the padlock, and reads the message.

02.What just happened

Look at what this arrangement achieved. Alice and Bob never met. They never agreed on anything in advance. Everything Bob sent out was public and Eve has a copy of it. And yet Alice sent Bob a message that only Bob can read.

The asymmetry is the whole trick. Locking and unlocking are different operations requiring different things. Locking needs only the padlock, which is public. Unlocking needs the key, which is private.

The vocabulary follows directly:

The public key is the padlock. Bob gives it away freely, to anybody, including his adversaries. Publishing it costs him nothing.

The private key is the key in the safe. Bob generates it, keeps it, and never transmits it anywhere.

Encryption is snapping the padlock shut. Anybody can do it.

Decryption is opening the padlock with the key. Only Bob can do it.

The pair together is called a key pair, and the defining property is that the public key can be derived from the private key but not the other way around.

03.The diagram

The arrow at the top is the part that would have looked like a mistake before 1976. Bob is broadcasting a piece of his key material to the entire world, his adversary included, and the scheme is still secure.

04.Signatures, running the same machine backwards

The same key pair does a second job that turns out to matter just as much.

Suppose Bob does not want to hide anything. He wants to publish a software update and let everybody confirm it really came from him. He performs an operation on the update using his private key, producing a short string called a signature, and publishes update and signature together.

Anybody with Bob's public key can check that the signature matches the update. Nobody without the private key can produce a signature that passes that check.

This is a digital signature, and it is what makes software updates, website certificates and code-signing work. Encryption protects secrecy. Signatures protect authenticity, meaning you know who wrote something and that nobody altered it in transit. Both are built from the same asymmetric key pair, used in opposite directions.

This distinction is worth holding on to, because when the NIST standards appear later in this chapter there are two of them for exactly this reason. ML-KEM does the key-establishment job. ML-DSA does the signature job.

05.The gap that remains

Padlocks are physical objects, and physical objects are hard to open because of steel and geometry. There is no steel on the Internet. There are only numbers being sent between machines, and any operation Bob can perform, Eve can also perform, because she has the same kind of computer.

So the padlock story is not yet a cryptosystem. It is a specification for one. It tells us what we need to find: an arithmetic operation that is easy to do forwards, effectively impossible to undo backwards, and yet easy to undo if you happen to hold a particular secret.

Making that precise is the next note.