a tour of RSA attacks — algoatson.github.io

Nobody breaks RSA by factoring a well-formed 2048-bit modulus. They break the deployment: an exponent chosen for speed, two keys that share a number, a prime generated badly, a few bits leaked. Each of these is a CTF staple and a real-world incident. Here's the field guide — match the symptom to the attack.

target

scheme: textbook RSA — c = m^e mod n, m = c^d mod n
premise: the maths is fine; the parameters aren't
goal: recover m or d without factoring a sound n

small public exponent#

With e = 3 and no padding, if the message is short enough that m^3 < n, the modulus never wraps and the ciphertext is just a perfect cube:

c = m^{3} mod n, m^{3} < n ⟹ m = \sqrt[3]{c}

Take the integer cube root, done. And Håstad's broadcast: the same m sent to e recipients with different moduli n_1..n_e lets you CRT the c_i together into m^e mod (n_1·…·n_e); since m^e is smaller than that product, an integer e-th root recovers m. Padding (OAEP) is what stops both.

common modulus#

Two users, same n, different coprime exponents e_1, e_2, same message. Extended Euclid gives integers a, b with a·e_1 + b·e_2 = 1, and then:

c_{1}^{a} c_{2}^{b} \equiv m^{a e_{1} + b e_{2}} = m^{1} = m (\mod n)

(one of a, b is negative — use the modular inverse of that ciphertext). No factoring; sharing a modulus across users simply breaks confidentiality.

small private exponent — Wiener#

Someone shrank d to make decryption fast. If $d < \frac{1}{3} n^{1 / 4}$ , then e/n is close enough to k/d that k/d appears as a convergent of the continued fraction expansion of e/n — walk the convergents, test each as a candidate d, and recover the private key directly. Boneh–Durfee pushes the bound to $d < n^{0.292}$ with lattices.

primes chosen badly#

The modulus is only as strong as its prime generation:

Close primes → Fermat. If |p − q| is small, write $n = a^{2} - b^{2} = (a - b) (a + b)$ and search a upward from $⌈ \sqrt{n} ⌉$ until $a^{2} - n$ is a perfect square. A few iterations factor n.
Shared primes → batch GCD. Across many keys generated with poor entropy, two moduli may share a prime. Then $gcd (n_{1}, n_{2}) = p$ factors both instantly — a single GCD, no factoring. (This has been found at scale in real Internet-wide key surveys.)
Smooth p−1 → Pollard's p−1. If p−1 has only small factors, Pollard's method peels p off cheaply.

partial knowledge — Coppersmith#

If you leak part of a secret, lattices finish the job. Coppersmith's method finds small roots of a modular polynomial, which means: known high bits of p → factor n; a stereotyped message with a small unknown part → recover m; known high bits of d → recover d. The tool is LLL lattice reduction; the lesson is that "only a few bits leaked" is often equivalent to "all of them."

diagnose, then one-line it

txt

e == 3 and short m         -> cube root c
same n, two e's            -> common modulus (gcd of exponents)
d tiny                     -> Wiener (continued fractions of e/n)
p ~ q                      -> Fermat
gcd(n_i, n_j) != 1         -> shared prime, both keys fall
high bits of p known       -> Coppersmith / LLL
segfault{textbook_rsa_is_a_museum_of_footguns}

doing it right#

Always pad. OAEP for encryption, PSS for signatures — this alone kills the small-e, broadcast, and most stereotyped-message attacks.
e = 65537, full-size random d. No tiny exponents on either side.
Independent, well-seeded primes of equal-ish but not-too-close size, from a CSPRNG — never reuse a modulus or a prime across keys.

Every break here is the same story: the algorithm assumes a generic, padded instance, and a deployment quietly violated one assumption. When you see RSA in a challenge, you're not factoring — you're hunting for which assumption they broke. The math then takes a handful of lines, and the ones above cover most of them.