The Math That Made Public-Key Crypto Work

Multiply two 300-digit primes. The product has 600 digits. Hand it to someone and ask them to recover the primes; the best known classical algorithm, the general number field sieve, takes time growing roughly as exp(c · (log n)^(1/3) · (log log n)^(2/3)). For a 2048-bit modulus that is, on current hardware, longer than the age of the universe.

This gap — multiplication is easy, factoring is hard — is the foundation of RSA. Ron Rivest, Adi Shamir, and Leonard Adleman published it in April 1977 at MIT. Pick large primes p and q, set n = pq, choose an exponent e coprime to (p−1)(q−1), and compute d such that ed ≡ 1 mod (p−1)(q−1). The pair (n, e) is public; d is private. Encryption is m^e mod n; decryption is c^d mod n. Both work via Euler's theorem on the multiplicative group of integers mod n.

What the cryptosystem does not have is a proof that factoring is hard. RSA's security is conjectural. It is consistent with the rest of mathematics that someone could publish a polynomial-time factoring algorithm tomorrow and the entire global PKI would need replacing.

A strange historical wrinkle: an equivalent scheme had been worked out in 1973 at GCHQ, the British signals intelligence agency, by Clifford Cocks. It was classified until 1997. Whitfield Diffie and Martin Hellman had published the public-key concept itself in 1976 with no idea about the GCHQ work.

The other shadow over RSA is Peter Shor. In 1994 he showed that a quantum computer of sufficient size can factor in polynomial time. No such machine exists at scale, but every encrypted message recorded today is decryptable on the day one does. "Harvest now, decrypt later" is not theoretical to agencies that store ciphertext.