RSA
RSA has been in use since 1977 and still signs most web certificates. The mathematics has held up: the best attack is still factoring the modulus, and the largest public factorisation is 829 bits. The failures have come from how it is used: missing padding, faulty hardware, and keys generated without enough randomness.
- Rests on
- The RSA problem, taking e-th roots modulo N = pq, which is no harder than factoring N
- Standards
- PKCS #1 v2.2 (RFC 8017); FIPS 186-5 for signatures; SP 800-56B for key establishment
- Sizes
- RSA-2048: 256-byte modulus and signature; RSA-3072: 384 bytes
- Best known attack
- The number field sieve; the largest public factorisation is RSA-250, 829 bits, in 2020
- Quantum
- Broken by Shor's algorithm
The scheme
Pick two large primes p and q and publish their product N together with an exponent e, almost always 65537. The private exponent d satisfies ed ≡ 1 mod (p − 1)(q − 1), and computing it needs p and q. Then for every m mod N,
Encryption raises to e, and so does signature verification. Decryption and signing raise to d. Recovering m from me mod N without d is the RSA problem. Factoring N solves it, and nothing substantially better than factoring is known.
Here is a key with 64-bit primes, generated and checked by the code that builds this page. That makes a 128-bit modulus, small enough to read and far too small to use:
- p, q
- 12017517957161568679, 18416108616170145109
- N = pq
- 221315915995862605756138350697499441011
- e
- 65537
- d = e−1 mod (p−1)(q−1)
- 67697944183729155392880397401730174217
The message m = 162636732814686403448117886186516556018 encrypts to c = me mod N = 152083984479829913375860482820873108877, and cd mod N gives m back.
The CRT speedup
The private-key holder knows p and q, and can compute cd modulo each separately, with the smaller exponents dp = d mod (p − 1) = 9878873955538434029 and dq = d mod (q − 1) = 5527052510359805669. The Chinese remainder theorem then combines the two halves into the answer mod N. Each half is an exponentiation with numbers half the size, so the whole takes about a quarter of the work, and nearly every implementation does it this way. On the key above both routes give the same m, as the build checks.
The speedup has a cost that is not arithmetic: the two halves are separate secrets, and an error in one of them, as the fault attack below shows, gives the factorisation away.
Why padding is not optional
The bare operation m ↦ me, "textbook RSA", has structure an attacker can use. It is deterministic, so equal messages give equal ciphertexts. It is also multiplicative: (m1m2)d = m1d m2d mod N. With the key above, the signatures on m1 = 169635402868690145007025520585269636032 and m2 = 180069909498339022707975475649847430267 multiply to 219949365838898887615636389138238068962, which verifies as a valid signature on m1m2 mod N = 76542379048537193462564054111097885405, a message the key holder never signed.
Padding destroys that structure. RSA-PSS for signatures and RSA-OAEP for encryption, both in PKCS #1 v2.2, hash and randomise the message before exponentiation, and come with security proofs in the random-oracle model. The older PKCS #1 v1.5 encryption padding does not, and Bleichenbacher showed in 1998 that a server revealing only whether a ciphertext's padding was valid lets an attacker decrypt any ciphertext with about a million queries. Variants of that attack have recurred in TLS implementations ever since, which is one reason TLS 1.3 dropped RSA key transport altogether.
Faults in CRT signing
Boneh, DeMillo and Lipton observed in 1997 that one faulty CRT signature is enough to factor N. Suppose a glitch, from voltage, heat or a deliberate laser pulse, corrupts only the half computed mod q. The faulty signature s′ is still correct mod p and wrong mod q, so s′e − h is divisible by p and not by q, and
The build signs h = 170353258798061478120892406166625372696 twice with the key above. The correct signature is 107498222148844492028097394686158116556. The second run adds one to the half mod q, and the result is 148222457455667009917425936892490253663. That fails verification, and the gcd above comes out as 12017517957161568679, which is p.
The defence is to verify every signature before releasing it, which costs one cheap exponentiation by e, or to randomise the computation. Smartcards and HSMs are expected to do this.
Sizes and the quantum question
RSA-2048 is conventionally rated at about 112 bits of classical security and RSA-3072 at 128, against the number field sieve, which is subexponential. That is why RSA keys are so much larger than elliptic-curve keys of the same strength. Shor's algorithm factors N in polynomial time on a large enough quantum computer, so RSA is on the same retirement path as elliptic-curve cryptography. NIST IR 8547 proposes deprecating 112-bit-security RSA after 2030 and disallowing RSA entirely after 2035, in favour of ML-DSA and ML-KEM.
Primary sources
- R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM 21 (1978)
- K. Moriarty, B. Kaliski, J. Jonsson and A. Rusch, RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2 (2016)
- D. Bleichenbacher, "Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1", CRYPTO 1998
- D. Boneh, R. A. DeMillo and R. J. Lipton, "On the importance of checking cryptographic protocols for faults", EUROCRYPT 1997
- N. Heninger, Z. Durumeric, E. Wustrow and J. A. Halderman, "Mining your Ps and Qs: detection of widespread weak keys in network devices", USENIX Security 2012
- A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, "Ron was wrong, Whit is right" (2012)
- NIST IR 8547 (initial public draft), Transition to Post-Quantum Cryptography Standards (2024)