BREAKING RSA IN CTFS: WIENER, FRANKLIN-REITER, AND BROADCAST ATTACKS

RSA is one of those algorithms that is elegant in theory and constantly broken in practice. The mathematical foundation is sound — factoring large numbers is hard. But RSA implementations are full of parameters you can get wrong, and CTF designers know exactly which parameters to abuse.

Wiener's Attack — Small Private Exponent

If the private exponent d is small (specifically, d < N^0.25 / 3), Wiener's attack recovers it directly from the public key (n, e) using continued fractions. From e*d ≡ 1 (mod phi(n)), we can write e*d = k*phi(n) + 1 for some integer k. This means e/n ≈ k/d. The fraction k/d appears as a convergent in the continued fraction expansion of e/n. How to spot it: the challenge gives you an unusually large e. Small d is sometimes hinted directly ("efficient decryption") or hidden in the numbers.

import owiener
from Crypto.Util.number import long_to_bytes

d = owiener.attack(e, n)
if d:
    pt = pow(ct, d, n)
    print(long_to_bytes(pt))

Hastad's Broadcast Attack — Small e, Multiple Recipients

If the same message m is encrypted to e different recipients with distinct moduli n_1 through n_e (with small e, typically e=3), recover m using CRT. You have c_i = m^e mod n_i for i=1..e. By CRT, compute M = m^e mod product of all n_i. Since m is smaller than each n_i, m^e equals M exactly as an integer. Take the e-th integer root.

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

r, _ = crt([n1, n2, n3], [c1, c2, c3])
m, exact = iroot(r, 3)
print(bytes.fromhex(hex(m)[2:]))

Franklin-Reiter Related Message Attack

If two messages m1 and m2 are related by a known linear function (m2 = a*m1 + b), and both are encrypted with the same key (n, e), you can recover both plaintexts. The attack exploits that gcd(f1(x), f2(x)) over Z_n[x] has a common root — the plaintext. With e=3 this is especially powerful. Spot it when a challenge mentions the plaintexts are "related" or differ by a known transformation.

Common Modulus Attack

If the same message is encrypted twice with the same modulus n but different exponents e1 and e2, and gcd(e1, e2) = 1, recover the plaintext using Bezout's identity: find a, b such that a*e1 + b*e2 = 1, then m = c1^a * c2^b mod n.

Low Public Exponent + Small Message

If e=3 and m is small enough that m^3 < n, then c = m^3 exactly as an integer — no modular reduction occurred. Take the cube root directly. Common in beginner CTFs.

Reading the Challenge

Most RSA CTF challenges telegraph their vulnerability. "Multiple recipients" = broadcast. "Two messages, one key" = Franklin-Reiter or common modulus. "Efficiency" or "small d" = Wiener. "e=3" = check if m is small. Learning to read these signals is half the battle. I write detailed writeups on Medium (@patrick.jane) and the RSA CTF GUI I built implements most of these attacks with a graphical interface.