The Story Behind RSA: The Invention That Secured the Internet (ft. Turing Award Winner Ron Rivest)

Ron Rivest joined MIT in 1974 at a time when cryptography had no formal theory, no security definitions, and no proofs. The Data Encryption Standard, developed with IBM's involvement, was not provably secure, and its short key size was a persistent controversy. Diffie and Hellman's 1976 paper New Directions in Cryptography introduced public key cryptography and digital signatures but largely posed an open problem rather than delivering a complete solution. Rivest, Adi Shamir, and Len Adleman worked at MIT's Laboratory for Computer Science with Shamir designing candidate ciphers and Adleman breaking them. RSA was the one scheme Adleman could not attack.

The idea for RSA came to Rivest on April 2, 1977, after a dinner at Shamir's house, while he was reading a number theory book by Dixon. The system's security rests on the fact that multiplying two large primes is easy but factoring the result is computationally hard. Factoring had been very sparsely studied at the time, with few algorithms beyond trial division, so the team's confidence in the hardness assumption was cautious rather than certain. To gauge what was known, Rivest met Martin Gardner in New York, and the RSA team helped Gardner write a Scientific American column featuring a 129-digit challenge number they estimated would take 140 quadrillion years to factor. That number was factored in 1994 using the number field sieve. The largest RSA challenge number factored to date is approximately 768 bits, and the challenge series extends to 2048 bits.

The NSA was concerned that strong academic cryptography would undermine its ability to monitor foreign adversaries and pushed back specifically on the encryption capability of RSA. Len Adleman declined an NSA research grant because it required subjecting all his papers to NSA review. When RSA was proposed as a digital signature standard, opposition arose from parties who objected to standardizing a scheme that could also encrypt. The DSA standard was proposed as an alternative specifically because it could only be used for signatures, reflecting NSA influence on NIST to suppress encryption capability. A patent dispute between RSA and Diffie-Hellman delayed standardization by six years, extending patent coverage to approximately 2003. DSA later evolved into ECDSA, which is widely used today including in blockchain systems.

Rivest found digital signatures more intellectually interesting than encryption because signatures were a genuinely new idea. The Goldwasser-Micali work in the early 1980s introduced formal security definitions and randomization into encryption, placing RSA security on firmer theoretical ground. There was no immediate enthusiasm for RSA within computer science academia after its initial publication. Hash functions were needed alongside digital signatures to make RSA signatures commercially viable, which led Rivest to design the MD family. He produced MD2, MD4, MD5, and MD6, abandoning MD3 because it was not secure. He describes the design process as highly ad hoc and not theoretically motivated. MD4 and MD5 were widely used but have since been replaced by NIST's SHA standards. Rivest says SHA-256 is a good hash function and notes its similarities to his MD family.

Dan Boneh states that digital signatures and collision-resistant hash functions are the two cryptographic primitives without which blockchain protocols could not function. Collision resistance means it is computationally hard to find two different messages that hash to the same output, even though the pigeonhole principle guarantees mathematically that many collisions exist. Hash functions underpin Merkle trees, which allow committing to large datasets and proving membership, and Merkle trees play an important role in hash-based SNARKs, making hash functions relevant to zero-knowledge proofs. Boneh notes that a collision-resistant hash function can compress the entire Bitcoin, Ethereum, or Solana blockchain to 256 bits.

Shor's algorithm, developed in 1994, poses a more concrete threat to RSA than a P equals NP result because it follows directly from accepted postulates of quantum mechanics and is therefore an engineering problem in principle rather than a mathematical unknown. The key open question is whether a quantum machine large enough to factor RSA-2048 can ever actually be built. Rivest openly states he wishes quantum computing engineers the worst of luck, while simultaneously endorsing NIST's quantum-resistant cryptography standards as a necessary precaution, arguing the world cannot bet its safety on hopes that a cryptographically relevant quantum machine is never built within the next ten to twenty years. He raises a caveat that new physics could introduce terms in the equations underlying Shor's algorithm that prevent it from functioning at scale.

On P versus NP, Rivest does not lose much sleep over the possibility, given fairly wide consensus that the two classes are probably not equal. Even if P were to equal NP, the threat to cryptography would only materialize if the resulting algorithm were practically efficient rather than merely polynomial in a theoretical sense. If P equals NP with a fast algorithm, all complexity-based cryptography would become impossible, leaving only information-theoretic schemes like the one-time pad. Rivest predicts the question should be resolved within a hundred years. RSA Data Security was founded around 1982 or 1983 and struggled until Jim Bidzos joined in 1986 and secured deals with Microsoft and IBM. The business only took off when the web arrived and online payment systems emerged, realizing the visions Diffie and Hellman had articulated years earlier.