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,

(me)d ≡ m  (mod N) Raising to e and to d undo each other

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

gcd(s′e − h, N) = p One faulty signature on a known h factors N

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.

Shared primes

RSA's security needs p and q to be unpredictable. In 2012 two independent teams, Heninger, Durumeric, Wustrow and Halderman, and Lenstra and colleagues, collected millions of RSA public keys from the internet and computed pairwise gcds of the moduli. Many devices, mostly routers and embedded systems that generated keys at first boot with too little entropy, had produced moduli sharing one prime with another device. Heninger's team recovered private keys for 0.50% of the TLS hosts they scanned.

The attack is one line. The build generates two keys that share a prime, as such a device would:

N1
169539004447946207924492599901229771809
N2
164309505621721155053360814796316121253
gcd(N1, N2)
12040577098273738717

The gcd is the shared prime, and dividing it out gives the other two, 14080637752176601877 and 13646314813704258409: both keys are factored without any factoring. Computing a gcd takes microseconds at real sizes, and a product tree does all pairs in a large collection at once.

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

  1. R. L. Rivest, A. Shamir and L. Adleman, "A method for obtaining digital signatures and public-key cryptosystems", Communications of the ACM 21 (1978)
  2. K. Moriarty, B. Kaliski, J. Jonsson and A. Rusch, RFC 8017, PKCS #1: RSA Cryptography Specifications Version 2.2 (2016)
  3. D. Bleichenbacher, "Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1", CRYPTO 1998
  4. D. Boneh, R. A. DeMillo and R. J. Lipton, "On the importance of checking cryptographic protocols for faults", EUROCRYPT 1997
  5. 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
  6. A. K. Lenstra, J. P. Hughes, M. Augier, J. W. Bos, T. Kleinjung and C. Wachter, "Ron was wrong, Whit is right" (2012)
  7. NIST IR 8547 (initial public draft), Transition to Post-Quantum Cryptography Standards (2024)