Breaking RSA by factoring a small modulus

The attack surface is one number

Everything in an RSA public key is published: the exponent e and the modulus n. The private exponent d is not published, but it is not independent either — it is a function of e and $\varphi (n)$, and $\varphi (n)$ is a function of the two primes hiding inside n. So the whole security of RSA reduces to one question: can the attacker split n back into p and q? If yes, everything else is arithmetic that a ten-line program finishes before you release the key.

Worked example — recovering a plaintext from a 9-bit modulus

A ciphertext C = 105 is captured on its way to the holder of the public key {e = 7, n = 403}. Recover the message.

Step 1 — factor the modulus. Trial-divide 403 by successive integers up to $\sqrt{403}\approx 20.1$. The candidates 2, 3, 5, 7 and 11 all fail; 13 divides. So $403=13\cdot 31$, and both factors are prime. Twelve divisions, done by hand in under a minute.

Step 2 — compute the totient. $\varphi (403)=(13-1)(31-1)=12\cdot 30=360$.

Step 3 — invert the public exponent. We need d with $7d\equiv 1(\mathrm{mod}360)$. Extended Euclid on (7, 360) gives d = 103. Verify it before going further: $7\cdot 103=721$, and $721=2\cdot 360+1$. So $7\cdot 103\equiv 1(\mathrm{mod}360)$ — the inverse is right.

Step 4 — decrypt. $M=105^{103}\mathrm{mod}403=79$.

Step 5 — verify by re-encrypting. Never hand in an unverified answer when the check is one line: $79^7\mathrm{mod}403=105$, which is the ciphertext we started from. The plaintext is M = 79.

Four ways to attack RSA

The textbook groups the attacks into four classes, and you should be able to name all four:

1. Brute force — try every possible private key. Defeated by using a large key space, and of no practical interest.
2. Mathematical attacks — determine d by attacking the number theory. Three routes, and all three are equivalent in effort to factoring: factor n into p and q (what we just did); determine $\varphi (n)$ directly without factoring, which is provably as hard as factoring; or determine d directly, which is at least as hard as factoring. Because all roads lead back to it, the performance of factoring algorithms is the benchmark for RSA security.
3. Timing attacks — a ciphertext-only side-channel attack that recovers d one bit at a time, starting from the leftmost, by observing that square-and-multiply performs an extra modular multiplication on a 1 bit and that some of those multiplications are recognisably slow. It does not touch the mathematics at all; it attacks the implementation. Three countermeasures: constant exponentiation time (costs performance), a random delay (defeated by collecting more samples if the noise is too small), and blinding — multiply the ciphertext by $r^e\mathrm{mod}n$ before exponentiating and by $r^{-1}$ afterwards, at a 2–10% penalty.
4. Chosen-ciphertext attacks — exploit properties of the RSA function by getting a victim to decrypt attacker-chosen values.

Why 403 dies and 2048 bits does not

Trial division on n costs about $\sqrt{n}$ steps, so a modulus of b bits costs roughly $2^{b/2}$ divisions. Our 9-bit modulus takes 12; the 32-bit one in the second exercise takes 46,348; a 2048-bit modulus would take about $2^{1024}$, which is not a large number of steps so much as a number of steps that will not happen. Real attacks use far better algorithms than trial division, and the record is empirical rather than rhetorical: a 129-digit modulus fell in April 1994, a 232-digit one in December 2009, and a 250-digit (829-bit) one in February 2020. Note what improved between those dates — both raw computing power and the algorithms, the quadratic sieve giving way to the general number field sieve, which factored a larger number than RSA-129 at roughly a fifth of the effort. Keys therefore weaken with time on two fronts at once, which is why current NIST guidance puts the floor at 2048 bits and the 5th edition's more relaxed line about 1024 bits should not be repeated in an answer today.