RSA, or the Passover night that locked the internet
Ron Rivest did not plan to solve one of computing’s most stubborn open problems that April in 1977. He had spent the evening at a Passover seder in Cambridge, Massachusetts — wine and company both plentiful — and when he got home, unable to sleep, he picked up a math textbook and lay on the couch. By morning, he had most of the paper written.
The problem had been sitting, half-solved, at MIT for nearly a year. Rivest, Adi Shamir, and Leonard Adleman were working on a challenge that Whitfield Diffie and Martin Hellman had posed the year before: given that two strangers can agree on a shared secret over an open channel, could anyone encrypt a message that only one specific person could read — using nothing but a publicly posted key? Diffie and Hellman had shown the concept was coherent. They hadn’t shown the mechanism. For nearly twelve months, Rivest and Shamir had been proposing candidate one-way functions while Adleman played skeptic, picking each one apart.
What Rivest understood on the couch is elegant enough to state in a sentence: multiplying two large prime numbers together is fast; factoring their product back into the original primes is, for numbers of sufficient size, computationally brutal. The product becomes the public key — anyone can use it to encrypt. The two primes are the private key — only someone who knows them can decrypt. There is no known shortcut to get from the product back to its factors. Rivest sent the draft to his collaborators the next morning. Their paper, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, appeared in February 1978 in the Communications of the ACM, though Martin Gardner had already given it a Scientific American column in August 1977 — which, as it happened, permanently voided the algorithm’s international patent protection.
The story has a second act, though the audience didn’t get to hear it until December 18, 1997. Clifford Cocks, a Cambridge-trained mathematician, had joined Britain’s signals intelligence agency GCHQ in September 1973. Within weeks, his mentor Nick Patterson showed him a classified memo by James H. Ellis describing the theoretical possibility of “non-secret encryption” — the same idea Diffie and Hellman would publish four years later. Cocks recognized that prime factorization was exactly the mechanism Ellis was missing. He wrote it up in a note titled “Note on Non-Secret Encryption” dated November 20, 1973. GCHQ classified it, judging the algorithm too expensive for the hardware of the era. It sat there, undisclosed, for 24 years.
RSA gave public-key cryptography something it had previously lacked: a working implementation. Before it, two parties who had never met could not exchange a secret without first exchanging a secret — the key distribution problem that had bedeviled every cipher since Caesar. After it, a browser and a web server on opposite sides of the planet could negotiate an encrypted session in milliseconds, with no prior arrangement. That negotiation underlies HTTPS, PGP, digital signatures, and essentially every secure transaction on the modern internet.
Every time a padlock icon appears in a browser bar, it runs on Rivest’s insomnia.
Sources
- RSA cryptosystem — Wikipedia — the April 1977 breakthrough, Martin Gardner’s 1977 Scientific American column, patent history, and publication details.
- Clifford Cocks — Wikipedia — GCHQ’s independent 1973 discovery, the November 20, 1973 internal note, and the declassification date of December 18, 1997.
- In conversation with Clifford Cocks — Chalkdust Magazine — Cocks’s account of Nick Patterson introducing him to the problem and his recognition that prime factorization was the solution.