What is RSA, who invented it, and what mathematical "hard problem" underlies its security?
RSA is the original public-key encryption / signature algorithm, named after Rivest, Shamir, and Adleman (MIT, 1977). Its security rests on the difficulty of factoring large integers — specifically the product n = p·q of two large primes.
Big picture of the algorithm:
| Step | What happens |
|---|---|
| Key gen | Pick two huge primes p, q. Compute n = p·q, φ(n) = (p−1)(q−1). Pick e (commonly 65537). Compute d = e⁻¹ mod φ(n). |
| Public key | (n, e) |
| Private key | (n, d) (or in CRT form: p, q, dp, dq, qinv for speed) |
| Encrypt | c = m^e mod n |
| Decrypt | m = c^d mod n |
The security argument: an attacker who knew p and q could compute d and decrypt. But factoring n (with n ~ 3072 bits in modern use) is infeasible with classical computers.
Historical credit: like Diffie-Hellman, Clifford Cocks at GCHQ invented essentially the same scheme in 1973, four years earlier — but classified. R-S-A get the public credit.
Recommended key sizes (2024):
| RSA key size | Equivalent symmetric strength |
|---|---|
| 2048 bits | ~112 bits — minimum acceptable, NIST says retire by 2030 |
| 3072 bits | ~128 bits — current recommendation |
| 4096 bits | ~140 bits — common for high-value cases |
| 15360 bits | ~256 bits — overkill, slow |
Tip: OpenSSL gives you all of this in one line: openssl genrsa -aes256 -out private.pem 4096. The PEM file (-----BEGIN RSA PRIVATE KEY----- etc.) is what backs nearly every Linux server's HTTPS, SSH, and S/MIME.