Rivest, Shamir, Adleman and RSA

Abstract

Diffie and Hellman proved in 1976 that public-key cryptography was possible, but their paper contained no practical way to do it. The scheme that made it real came a year later from three young MIT researchers: Ron Rivest, Adi Shamir, and Leonard Adleman, after months of failed attempts and one sleepless night following a Passover seder in April 1977. RSA (encrypt with a public key, decrypt with a private one, security resting on the difficulty of factoring large numbers) became the workhorse of internet commerce: every early SSL handshake, most digital signatures, the padlock in the browser. The trio earned the 2002 Turing Award, built one of the first crypto companies, and each went on to a second landmark career. The algorithm’s own story (a $100 magazine challenge cracked by 600 internet volunteers, a secret British precursor, and an NSA payment scandal) is a compressed history of the crypto wars.

Ron Rivest and Adi Shamir on stage at CRYPTO 2017; Len Adleman was scheduled to join by video. Image: M. B., Jr., CC BY-SA 3.0, via Wikimedia Commons.

One Night in April 1977

Diffie and Hellman’s New Directions in Cryptography (1976) defined the goal: a trapdoor one-way function, easy to compute, infeasible to invert without a secret. Finding one was left as an exercise. At MIT, computer scientists Ron Rivest (b. 1947) and Adi Shamir (b. 1952, Israel) generated candidate schemes, and mathematician Leonard Adleman (b. 1945) shot them down, a division of labor that killed dozens of attempts over roughly a year.

The breakthrough came the night after a Passover seder in April 1977. Rivest, unable to sleep, worked through the idea on a couch with a math textbook: raise the message to a power modulo the product of two large primes. Multiplying the primes is trivial; recovering them from the product is (as far as anyone can tell after five decades) computationally infeasible at scale, factoring is the trapdoor. By dawn he had most of the paper. Adleman, who judged his contribution the smallest, had to be persuaded to be listed as an author, third, hence R-S-A. The result was published as “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” in Communications of the ACM, February 1978. Crucially, RSA did both things at once: encryption (anyone can lock a message only you can open) and digital signatures (you can sign so anyone can verify), the primitive behind public key cryptography’s entire application stack.

Squeamish Ossifrage: The $100 Challenge

Before the paper even appeared, Martin Gardner described the scheme in his Mathematical Games column in Scientific American, August 1977, probably the most consequential popular-science column in cryptographic history. Readers mailed MIT thousands of requests for the technical memo. The column included a challenge: a message encrypted with a 129-digit modulus (RSA-129), a $100 prize, and Rivest’s estimate that factoring it would take on the order of 40 quadrillion years.

It took seventeen. In April 1994, a team led by Derek Atkins, Michael Graff, Arjen Lenstra, and Paul Leyland factored RSA-129 using about 1,600 machines volunteered by ~600 people over the internet, one of the first great distributed-computing efforts. The plaintext: “THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE.” The episode fixed the industry’s understanding that RSA security is a moving target indexed to compute and algorithms: key sizes marched from 512 bits to today’s 2,048–4,096, the successor RSA Factoring Challenge ran until 2007 (largest number factored to date: RSA-250, in 2020), and Shor’s algorithm stands as the reason NIST spent the 2020s standardizing post-quantum replacements.

The Secret Precursor at GCHQ

RSA was invented first, just not publicly. In 1973, mathematician Clifford Cocks at Britain’s GCHQ, building on James Ellis’s idea of “non-secret encryption,” wrote an internal memo describing what is essentially the RSA scheme. GCHQ judged it impractical with 1970s hardware, classified it, and said nothing for a quarter century; the documents were declassified only in 1997. The MIT trio invented RSA independently, and, decisively for history, published it. The lesson recurs throughout computing: credit and consequence flow to the open publication, not the locked safe (see Computer Science Firsts).

RSA the Company

In 1982 the three founded RSA Data Security to license the algorithm (MIT held U.S. Patent 4,405,829, granted 1983, the patent, and the export-control regime around it, made RSA a central artifact of the 1990s crypto wars; see Phil Zimmermann and PGP). Its BSAFE libraries shipped inside Netscape’s SSL-era software, and the annual RSA Conference became the security industry’s main stage. The patent was released to the public domain in September 2000, two weeks before expiry. EMC bought RSA Security in 2006 for $2.1 billion.

The company’s darkest chapter surfaced in December 2013, when Reuters reported that the NSA had secretly paid RSA Security $10 million in 2004 to make Dual_EC_DRBG (a random-number generator with a suspected NSA backdoor) the default in BSAFE. RSA disputed aspects of the story but advised customers to abandon the generator. That a firm named for the founders of open academic cryptography had shipped a backdoored default became the crypto community’s standing parable about trust (see Edward Snowden and the NSA). By then the founders were long gone from operations; the scandal stained the brand, not the men or the mathematics.

Three Second Acts

The 2002 Turing Award citation covers RSA, but each founder built a further legacy:

Ron Rivest (MIT, still) designed a string of workhorse primitives (MD5, RC4, the RC ciphers) plus ring signatures, and became a leading scientist of election integrity, co-authoring foundational work on risk-limiting audits and end-to-end verifiable voting.
Adi Shamir (Weizmann Institute) may be the most inventive cryptanalyst alive: Shamir secret sharing (1979), breaking the Merkle–Hellman knapsack cryptosystem, co-inventing differential cryptanalysis (with Eli Biham), the technique that, it later emerged, IBM and NSA had known and kept quiet in the 1970s, plus identity-based cryptography and side-channel attacks.
Leonard Adleman (USC) founded DNA computing: his 1994 Science paper solved a small Hamiltonian-path instance with molecules in a test tube, opening molecular computation as a field. He also supervised Fred Cohen’s 1980s dissertation on self-replicating programs and suggested the name that stuck: “computer virus” (see Cybersecurity: The Invisible War).

⚠️ Dead End: The Knapsack Rival

RSA had a same-generation competitor: the Merkle–Hellman knapsack cryptosystem (1978), which was faster and, many then believed, at least as secure. Shamir broke it in 1982 (a polynomial-time attack, demonstrated to applause at the CRYPTO conference) and follow-on work by Brickell and others demolished the knapsack family entirely. The episode shaped modern cryptographic culture: security claims must survive public attack by the best adversaries, and a system’s speed is irrelevant if its hard problem isn’t hard. Factoring, whatever its fate against quantum computers, has survived five decades of the world’s best mathematicians trying; the knapsack lasted four years. It remains the canonical warning against betting infrastructure on young hardness assumptions.