RSA
The first practical public-key cryptosystem — one key encrypts, a different key decrypts, and you can publish the encrypting key in the phone book.
Why This Matters
Diffie and Hellman had described public-key cryptography as a goal in 1976; RSA was the first concrete construction that achieved it. The same key pair can be used both ways — encrypt with the public key and only the holder of the private key can decrypt; sign with the private key and anyone with the public key can verify. That single mathematical object simultaneously solved key distribution, authentication, and non-repudiation. Every TLS certificate, every code-signing chain, every signed software update is descended from this 1977 paper.
Rivest, Shamir, and Adleman were MIT researchers reading Diffie-Hellman's paper in 1976 and trying to find a working public-key construction. After dozens of failed attempts, Rivest had the key insight one Passover night in April 1977 after a glass of wine: use the multiplicative inverse d of the encrypting exponent e modulo φ(n). The MIT memo went out August 1977; Martin Gardner's Scientific American column in 1977 popularised it with a $100 challenge cipher (factored in 1994 by 600 volunteers). RSA Data Security was founded in 1982; the patent expired in 2000.
Pick two large primes p and q (each ~1024 bits for RSA-2048). Compute n = p·q and φ(n) = (p−1)(q−1). Choose a public exponent e coprime to φ(n) — almost always 65537. Compute the private exponent d ≡ e−1 mod φ(n).
Public key is (n, e); private key is (n, d). To encrypt message m: c = me mod n. To decrypt: m = cd mod n. The math works because of Euler's theorem: med ≡ m mod n for any m coprime to n. Recovering d from the public key requires factoring n, which is believed to be classically infeasible for 2048-bit moduli.
Security rests on the integer factorisation problem. The largest RSA modulus publicly factored is RSA-250 (829 bits, 2020), using ~2700 core-years on a CADO-NFS cluster. RSA-2048 is estimated at ~109 times harder. However: Shor's quantum algorithm factors n in polynomial time, so a sufficiently large quantum computer breaks RSA entirely. NIST's post-quantum standardisation (CRYSTALS-Kyber, ML-KEM) is the planned replacement. RSA also has dangerous implementation pitfalls: textbook RSA leaks small messages and is malleable; production systems must use OAEP padding for encryption and PSS for signatures.
| Where | How RSA is Used |
|---|---|
| TLS / HTTPS certificates | Most certificate authorities still issue RSA-2048 leaf certificates; ECDSA is gaining share |
| Code signing | Microsoft Authenticode, Apple notarisation, Debian package signing all use RSA |
| PGP / GPG | Default keypair for encrypted email and signed Git commits |
| SSH host keys | ssh-rsa remains the most common key type, though ed25519 is now preferred |
| JWT signatures | RS256 is the default for many OAuth / OIDC implementations |
| Era | Modern · 1977 |
| Status | In daily use; NIST is preparing a post-quantum migration (RSA breaks under Shor's algorithm on a sufficiently large quantum computer) |
| Origin | Ron Rivest, Adi Shamir, Leonard Adleman (MIT, 1977); Clifford Cocks (GCHQ, 1973, classified) |
| Year | 1977 |
| Type | Public-key encryption & digital signature (asymmetric) |
| Modern Role | TLS certificates, code signing, PGP/GPG, SSH host keys, JWT signatures, document signing |