A Method for Obtaining Digital Signatures and Public-Key Cryptosystems
A key you publish for the whole world to encrypt with — yet only you, holding its secret twin, can decrypt.
What if you could hand a complete stranger an open padlock — let them snap it shut on a box and mail it back — and only you, never them, could ever open it again?
The big idea
For all of history a code had one key: the same secret that scrambled a message also unscrambled it, so both sides had to share that secret first. RSA breaks the key in two. It builds a matched pair of keys where one locks and the other unlocks — and, crucially, knowing the locking key tells you nothing useful about the unlocking key.
So you can publish your locking key to the entire world. Anyone, even someone you have never met, can use it to encrypt a message that only you — the holder of the private unlocking key — can read. Run the pair the other way and you get a signature: you 'unlock' a document with your private key, and anyone can use your public key to confirm it could only have come from you.
How it came about
In 1976 Whitfield Diffie and Martin Hellman had announced the dream — a public key, a digital signature — but not a way to build one. At MIT, three young researchers took up the challenge: Ron Rivest and Adi Shamir kept proposing schemes, and Leonard Adleman, the number theorist of the group, kept breaking them. The story goes that after a Passover evening in April 1977, a sleepless Rivest worked out the idea that survived: hide the key behind the multiplication of two large primes.
They named it RSA, after their three surnames, and published it in 1978. Unknown to them, a mathematician named Clifford Cocks at Britain's secret signals agency, GCHQ, had found essentially the same method in 1973 — but it was classified until 1997, so the public credit, the patent, and the 2002 Turing Award went to Rivest, Shamir and Adleman.
Why it mattered
RSA is what made commerce and trust possible between strangers online. When your browser connects to a bank it has never spoken to before, public-key cryptography lets the two agree on secrets and verify identities in the open, in a fraction of a second. The same idea lets software prove it really came from its maker, and lets a document carry a signature no one can forge. For decades, RSA was the workhorse that did all of this — the quiet machinery under the padlock in your address bar.
A way to picture it
Think of a public mailbox with two different keys. One key — the public one — only locks the slot; you can hang copies of it everywhere, and anyone can drop in a letter and click it shut. The other key — the private one, which you alone keep — is the only thing that opens the box to take the letters out. Multiplying two large prime numbers together is the 'locking': quick and easy to do. Splitting the result back into those two primes is the 'opening' — and for big enough primes, that is so slow that even every computer on Earth, running for longer than the universe has existed, could not finish it.
Where it sits
RSA is the second act of the public-key story. Diffie and Hellman wrote the idea in 1976; RSA built the first working machine in 1978; and the line runs on to the elliptic-curve keys and digital signatures that, in this Library, authorize every transaction in Nakamoto's Bitcoin. Its security rests on a problem as old as Euclid — factoring whole numbers into primes — turned, for the first time, into a shield. The looming sequel is the quantum computer, which would dissolve that shield and is now pushing the world toward post-quantum codes.
An encryption method is presented with the novel property that publicly revealing an encryption key does not thereby reveal the corresponding decryption key. Couriers or other secure means are not needed to transmit keys, since a message can be enciphered using an encryption key publicly revealed by the intended recipient. Only he can decipher the message, since only he knows the corresponding decryption key.
A message can be "signed" using a privately held decryption key. Anyone can verify this signature using the corresponding publicly revealed encryption key. Signatures cannot be forged, and a signer cannot later deny the validity of his signature.
The era of "electronic mail" may soon be upon us; we must ensure that two important properties of the current "paper mail" system are preserved: (a) messages are private, and (b) messages can be signed.