RSA

Rivest, Shamir and Adleman developed RSA at MIT in 1977, following the public-key research of Diffie and Hellman. Their construction was publicly described in 1977 and published in Communications of the ACM in 1978. Clifford Cocks had found a related construction at GCHQ in 1973, but that work remained classified until 1997.

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⁻¹ mod φ(n).

Public key is (n, e); private key is (n, d). To encrypt message m: c = m^e mod n. To decrypt: m = c^d mod n. The math works because of Euler's theorem: m^ed ≡ m mod n for any m coprime to n. Factoring n lets an attacker compute a private exponent. The Chinese remainder theorem extends this correctness argument to all message representatives from 0 to n−1, not only those coprime to n.

Factoring the modulus breaks RSA, but general RSA inversion has not been proved equivalent to factoring. Security claims must also specify the encoding and attack model: textbook RSA is deterministic and malleable. RFC 8017 defines schemes such as RSA-OAEP for encryption and RSA-PSS for signatures and recommends using a key pair for one scheme. A sufficiently capable quantum computer running Shor's algorithm would break RSA. NIST finalized ML-KEM for key establishment and ML-DSA and SLH-DSA for signatures in 2024; these serve different roles rather than providing one universal RSA replacement.