The RSA attack decision tree

RSA is the most over-represented topic in CTF crypto, and the reason is structural: it has a dozen well-known parameter mistakes, each with a clean, published attack. A challenge author picks one mistake, and your job is to read the parameters and name it. You are not being asked to break RSA. You are being asked to notice which way it was already broken.

The setup, so the notation below is unambiguous: n = p × q, encryption is c = m^e mod n, decryption is m = c^d mod n where d = e⁻¹ mod φ(n) and φ(n) = (p-1)(q-1). Every attack below either factors n, recovers d without factoring, or recovers m without recovering d.

Start here: look at e

The public exponent tells you which branch of the tree you are on before anything else does.

e = 3 (or any very small e)

Small e means the modular reduction may never have happened. If the message is short and unpadded, m^3 < n, so c is just the integer cube of m - take an exact integer cube root and you are done. No factoring, no key.

from gmpy2 import iroot          # or write your own binary-search nth root

m, exact = iroot(c, 3)
if exact:
    print(bytes.fromhex(format(int(m), 'x')))

# If it is not exact, the reduction did happen at least once. Try adding
# multiples of n back before rooting - k is usually small.
for k in range(1, 10000):
    m, exact = iroot(c + k * n, 3)
    if exact:
        print(k, bytes.fromhex(format(int(m), 'x')))
        break

e is huge (close to n)

A public exponent with hundreds of digits is a signal, not a coincidence. Since e·d ≡ 1 mod φ(n), a very large e implies a very small d, and small d is exactly what Wiener’s attack breaks. It works whenever d < n^(1/4) / 3: expand e/n as a continued fraction and test each convergent as a candidate k/d. Boneh-Durfee extends the bound to roughly d < n^0.292 using lattice reduction, at considerably more implementation cost.

Then look at n

n is small (under ~512 bits)

Just factor it. Under 256 bits, trial division and Pollard’s rho finish in seconds in a browser. Under 512 bits, a general-purpose siever will do it, and it is very likely already in FactorDB, which is worth checking before you spend any compute at all.

p and q are close together

If the primes were generated as nextprime(x) and nextprime(x + small), then n sits just under a perfect square and Fermat factorisation finds it almost immediately. Write n = a² - b² = (a-b)(a+b): start at a = ceil(sqrt(n)), increment, and test whether a² - n is a perfect square.

from math import isqrt

def fermat(n: int):
    a = isqrt(n)
    if a * a < n:
        a += 1
    while True:
        b2 = a * a - n
        b = isqrt(b2)
        if b * b == b2:
            return a - b, a + b
        a += 1

p - 1 has only small prime factors

Pollard’s p-1 exploits smoothness: compute a = 2^(B!) mod n for a bound B, then gcd(a - 1, n). If every prime factor of p - 1 is below B, that gcd is p. Its elliptic-curve cousin, ECM, does the same job for factors up to about 50 digits and is what you reach for when a modulus has one small-ish prime among large ones.

You have two moduli from the same challenge

Take gcd(n₁, n₂). If a generator reused a prime - which happens both in challenges and, famously, in the wild - the gcd is that shared prime and both moduli fall at once. It costs microseconds; always try it when you have more than one modulus.

Now look at what else you were given

Same message, several moduli, small e

Håstad’s broadcast attack. With e ciphertexts of the same m under pairwise-coprime moduli, the Chinese Remainder Theorem reconstructs m^e mod (n₁n₂...n_e). Because m^e is smaller than that product, the CRT result *is* the integer m^e, and an exact e-th root finishes it.

from sympy.ntheory.modular import crt
from gmpy2 import iroot

x, _ = crt([n1, n2, n3], [c1, c2, c3])
m, exact = iroot(int(x), 3)
assert exact

Same modulus, two different exponents

Common modulus attack. If gcd(e₁, e₂) = 1, the extended Euclidean algorithm gives u, v with u·e₁ + v·e₂ = 1, and then c₁^u · c₂^v ≡ m^(u·e₁ + v·e₂) ≡ m (mod n). One of u or v is negative, so you need the modular inverse of that ciphertext - which exists because it is coprime to n.

def common_modulus(c1, c2, e1, e2, n):
    g, u, v = extended_gcd(e1, e2)
    assert g == 1
    if u < 0:
        c1, u = pow(c1, -1, n), -u
    if v < 0:
        c2, v = pow(c2, -1, n), -v
    return (pow(c1, u, n) * pow(c2, v, n)) % n

Two ciphertexts of related messages, small e

Franklin-Reiter. If m₂ = f(m₁) for a known linear f - say the same message with a counter appended - then m₁ is a common root of x^e - c₁ and f(x)^e - c₂ over Z/nZ. Their polynomial GCD is linear in practice, and reading its root off gives m₁ directly.

You know part of the message or part of the key

Coppersmith. Lattice reduction finds small roots of polynomials modulo n. The stereotyped-message case recovers up to 1/e of the message bits when the rest is known; the partial-key-exposure case factors n given roughly half the bits of p. This is the attack that looks like magic and is really just LLL applied to a carefully chosen lattice basis.

If there is a server, look for an oracle

When the challenge is interactive, the parameters are usually fine and the *protocol* is the bug. Three patterns cover most of them.

• Parity / LSB oracle. A server that tells you whether a decryption is even or odd lets you binary-search the plaintext. Send c · 2^e, learn the low bit of 2m mod n, and halve the interval. log₂(n) queries, no factoring.
• Unpadded signing oracle (blinding). A server that signs anything except your target c still signs c · r^e. The signature is m·r, and dividing by r mod n recovers m. The oracle’s refusal is meaningless because RSA is multiplicatively homomorphic.
• PKCS#1 v1.5 padding oracle (Bleichenbacher). A server that distinguishes valid from invalid padding leaks that the plaintext lies in [2B, 3B). Iteratively multiply and narrow. It is chatty - thousands of queries - but it is the intended path when the only feedback is a padding error.

The tree, condensed

1. e = 3 and short message → integer cube root, then c + k·n.
2. e enormous → Wiener, then Boneh-Durfee.
3. n small → factor it; check FactorDB.
4. n ≈ square → Fermat.
5. Two moduli → gcd.
6. e ciphertexts, e moduli → Håstad + CRT.
7. One modulus, two exponents → common modulus.
8. Known message prefix or half of p → Coppersmith.
9. Interactive server → parity oracle, blinding, or Bleichenbacher.
10. None of the above → re-read the source; the mistake is somewhere in how the key was generated.

That last line is the honest one. When no standard attack fits, the answer is almost always in the generation code: a seeded RNG, a prime derived from a timestamp, φ computed wrong, a modulus that is a prime power. The tree above is not a substitute for reading the source - it is what you do *after* you have read it.