RSA Attacks

RSA itself is sound; what breaks in CTFs is the way it is used. Reused randomness, tiny exponents, structured plaintexts, leaked bits, or special-shaped primes each open a distinct mathematical door. This page is a working catalogue: how to recognise each weakness, the math behind it, and a runnable script.

If you have not yet internalised key generation, $\varphi(n)$, and the encryption/decryption relations, read RSA Basics first.

Which Attack? Decision Table

Read off what the challenge gives you and what looks abnormal.

Tooling and First Moves

Before any clever attack, try to factor $n$ outright.

from factordb.factordb import FactorDB

f = FactorDB(n)
f.connect()
print(f.get_factor_list())   # [] or fully/partially factored

Small Public Exponent (No Padding)

When $e$ is tiny (classically $e=3$) and the plaintext is short, encryption may not wrap around the modulus: if m^e < n, then $c = m^e$ over the integers and you recover $m$ with an integer $e$-th root.

from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

c = ...   # ciphertext
e = 3

m, exact = iroot(c, e)
if exact:
    print(long_to_bytes(int(m)))
else:
    print("Not a perfect e-th root: m^e wrapped the modulus or padding is present")

If it is not a perfect root, $m^e$ exceeded $n$. You can still recover $m$ if it wrapped by only a small factor $k$: try $\sqrt[e]{c + k n}$ for $k = 0, 1, 2, \dots$ until the root is exact.

Hastad Broadcast Attack

If the same message $m$ is sent to $e$ (or more) recipients with the same small exponent $e$ and pairwise-coprime moduli $n_1, \dots, n_e$, the Chinese Remainder Theorem reconstructs $m^e$ modulo $N = \prod n_i$. Because m^e < N, that combined value is $m^e$ over the integers, and a single $e$-th root finishes the job.

from sympy.ntheory.modular import crt
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes

e = 3
mods = [n1, n2, n3]
cts  = [c1, c2, c3]

M, _ = crt(mods, cts)          # M = m^e mod (n1*n2*n3)
m, exact = iroot(int(M), e)
assert exact
print(long_to_bytes(int(m)))

Common Modulus Attack

Two ciphertexts of the same plaintext under the same modulus $n$ but different, coprime exponents $e_1, e_2$ leak $m$ regardless of how large the exponents are. By Bezout, find $s, t$ with $s e_1 + t e_2 = 1$; then

One of $s, t$ is negative, so invert the corresponding ciphertext.

from math import gcd
from Crypto.Util.number import long_to_bytes

n, e1, e2, c1, c2 = ...
assert gcd(e1, e2) == 1

g, s, t = __import__("sympy").gcdex(e1, e2)   # s*e1 + t*e2 = 1
s, t = int(s), int(t)

if s < 0:
    c1 = pow(c1, -1, n); s = -s
if t < 0:
    c2 = pow(c2, -1, n); t = -t

m = (pow(c1, s, n) * pow(c2, t, n)) % n
print(long_to_bytes(m))

Wiener's Attack (Small $d$)

If the private exponent is small, d < \tfrac{1}{3} n^{1/4}, then $d$ appears as a denominator in the continued-fraction expansion of $e/n$. Each convergent $k/d$ is a candidate; the right one yields an integer $\varphi(n) = (ed-1)/k$ that recovers $p, q$.

from Crypto.Util.number import long_to_bytes

def wiener(e, n):
    # continued fraction of e/n
    cf, a, b = [], e, n
    while b:
        cf.append(a // b); a, b = b, a % b
    # convergents
    num0, num1, den0, den1 = 0, 1, 1, 0
    for q in cf:
        num0, num1 = num1, q * num1 + num0
        den0, den1 = den1, q * den1 + den0
        k, d = num0, den1
        if k == 0:
            continue
        if (e * d - 1) % k:
            continue
        phi = (e * d - 1) // k
        # solve x^2 - (n - phi + 1)x + n = 0 for integer roots p, q
        s = n - phi + 1
        disc = s * s - 4 * n
        if disc >= 0:
            t = __import__("gmpy2").isqrt(disc)
            if t * t == disc and (s + t) % 2 == 0:
                return d
    return None

d = wiener(e, n)
print("d =", d)

The library owiener (pip install owiener) does the same in one call. For the boundary case $n^{0.25} \le d \le n^{0.292}$, Wiener fails and you need Boneh-Durfee.

Boneh-Durfee (Small $d$, Lattice)

Boneh and Durfee extended the small-$d$ break up to

(the tight bound \delta < 1 - \tfrac{1}{\sqrt 2}), using Coppersmith's lattice method. The key relation $ed \equiv 1 \pmod{\varphi(n)}$ with $\varphi(n) = n + 1 - (p+q)$ becomes a small-root problem for the bivariate modular polynomial

where the small root encodes $k$ and $-(p+q)$. See the original Eurocrypt 1999 paper and the lattice attacks page.

# SageMath - uses the well-known boneh_durfee.sage helper
# https://github.com/mimoo/RSA-and-LLL-attacks
#
# Set the parameters and the lattice tuning knobs:
#   delta : target bound, d < n^delta  (try 0.26 -> 0.292)
#   m, t  : lattice dimension / shifts (raise if it fails, slower)
load("boneh_durfee.sage")

n = ...
e = ...
delta = 0.28
m = 4          # lattice parameter
t = int((1 - 2 * delta) * m)
X = int(floor(n ** delta))            # bound on k
Y = int(floor(2 * n ** 0.5))          # bound on p+q

d = boneh_durfee(n, e, delta, m, t, X, Y)
print("recovered d =", d)

Franklin-Reiter Related Message

If two plaintexts satisfy a known linear relation $m_2 = a\,m_1 + b \pmod n$ and are encrypted under the same $(n, e)$ with small $e$, then $m_1$ is a common root of

Their polynomial $\gcd$ is (with overwhelming probability) linear, $x - m_1$, revealing the message.

# SageMath
def franklin_reiter(n, e, c1, c2, a, b):
    P.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (a * x + b)^e - c2
    # monic gcd over Z/nZ
    g = g1
    h = g2
    while h != 0:
        g, h = h, g % h
    g = g.monic()
    return Integer(-g[0])     # root is the constant term of (x - m1)

m1 = franklin_reiter(n, e, c1, c2, a, b)
print(bytes.fromhex(hex(int(m1))[2:]))

The closely related Coppersmith short-pad attack handles the case where the relation is unknown but small (random short padding differs between two encryptions of the same message); it combines a Franklin-Reiter step with a Coppersmith resultant - see below.

Partial Key Exposure

Leaking only part of the private key is often enough.

• Low bits of $d$: Given roughly the bottom $n/4$ bits of $d$ and a small $e$, Boneh-Durfee-Frankel recovers the rest. With small $e$ you can also solve $ed \equiv 1 \pmod{e \cdot 2^{\ell}}$ style relations.
• High or low bits of $p$: If you know about half the bits of a prime, Coppersmith factors $n$. Write $p = p_{\text{known}} + x_0$ with \lvert x_0\rvert < n^{1/4} and find the small root of $f(x) = p_{\text{known}} + x \pmod p$.

# SageMath - factor n given the high bits of p (Coppersmith)
n = ...
p_high = ...          # the known most-significant bits of p, low bits zeroed
unknown_bits = ...    # number of unknown low bits of p

P.<x> = PolynomialRing(Zmod(n))
f = p_high + x
f = f.monic()
# small_roots needs: beta ~ 0.5 (root mod a divisor of size n^beta),
# X bounds the unknown part.
roots = f.small_roots(X=2**unknown_bits, beta=0.4)
if roots:
    p = int(p_high + roots[0])
    print("p =", p, "  divides n:", n % p == 0)

This is the practical core of Coppersmith for factoring; the lattice page explains the bound X < n^{\beta^2/\deg} that governs how many bits you need.

LSB / Parity Oracle

If a service decrypts attacker-chosen ciphertexts and leaks just the parity (or just whether the result is in the upper/lower half), you can binary-search the plaintext. Multiplying $c$ by $2^e$ encrypts $2m$; the oracle's answer tells you whether $2m$ wrapped the modulus, which is one bit of $m$ per query.

Each query halves the interval $[\text{lo}, \text{hi}]$ containing $m$; after $\lceil \log_2 n\rceil$ queries you have $m$ exactly.

from fractions import Fraction
from Crypto.Util.number import long_to_bytes

def lsb_oracle(c):
    """Return parity (0/1) of the decryption of c. Replace with the real oracle."""
    ...

n, e, c = ...
two_e = pow(2, e, n)
lo, hi = Fraction(0), Fraction(n)
ct = c
for _ in range(n.bit_length()):
    ct = (ct * two_e) % n
    mid = (lo + hi) / 2
    if lsb_oracle(ct) == 1:    # 2m wrapped -> m was in upper half
        lo = mid
    else:
        hi = mid
print(long_to_bytes(int(hi)))

Fermat Factorization (Close Primes)

If $p$ and $q$ are close, $n = a^2 - b^2 = (a-b)(a+b)$ with $a \approx \sqrt n$ and small $b$. Iterate $a = \lceil\sqrt n\rceil, \lceil\sqrt n\rceil + 1, \dots$ until $a^2 - n$ is a perfect square.

from gmpy2 import isqrt, is_square

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

p, q = fermat(n)
print("p =", p, "q =", q)

This converges in a handful of steps only when $\lvert p-q\rvert \lesssim n^{1/4}$. Wider gaps need a sieving variant or a different attack.

Shared Factor / Batch GCD

If many RSA keys are generated with a weak RNG, two moduli may share a prime. Then $\gcd(n_i, n_j) = p$ factors both instantly. Across a large key set, the bGCD / "Mining your Ps and Qs" product-tree algorithm finds all shared factors in near-linear time.

from math import gcd
from Crypto.Util.number import long_to_bytes

# pairwise GCD for a small batch
def pairwise_shared(moduli):
    found = {}
    for i in range(len(moduli)):
        for j in range(i + 1, len(moduli)):
            g = gcd(moduli[i], moduli[j])
            if g != 1:
                found[i] = g; found[j] = g
    return found

shared = pairwise_shared([n1, n2, n3])
# Given a shared prime p for modulus n with exponent e:
# q = n // p; d = pow(e, -1, (p-1)*(q-1)); m = pow(c, d, n)

For thousands of keys, use a product/remainder tree (the batch-gcd tool) instead of $O(k^2)$ pairwise GCDs.

Smooth $p-1$ (Pollard)

If $p - 1$ factors into only small primes (it is $B$-smooth), Pollard's $p-1$ method finds $p$. Compute $a = 2^{M} \bmod n$ where $M = \mathrm{lcm}(1, \dots, B)$; then $p \mid \gcd(a - 1, n)$.

from math import gcd
from Crypto.Util.number import isPrime
import sympy

def pollard_p_minus_1(n, B=10**6):
    a = 2
    for prime in sympy.primerange(2, B):
        pe = prime
        while pe * prime <= B:
            pe *= prime
        a = pow(a, pe, n)
        g = gcd(a - 1, n)
        if 1 < g < n:
            return g
    return None

p = pollard_p_minus_1(n)
print("p =", p)

The analogous Williams $p+1$ method targets smooth $p+1$. CTF challenges that "roll their own primes" (e.g. $p = 2 \cdot \prod(\text{small primes}) + 1$) are textbook targets.

Coppersmith: Stereotyped and Short-Pad

Coppersmith's method finds small roots of a polynomial modulo a divisor of $n$. Two classic RSA applications:

# SageMath - stereotyped message with e = 3
n = ...
e = 3
c = ...
m_known = ...            # known part, unknown low bits zeroed
unknown_bits = ...       # size of the unknown chunk

P.<x> = PolynomialRing(Zmod(n))
f = (m_known + x)^e - c
f = f.monic()
roots = f.small_roots(X=2**unknown_bits, beta=1.0, epsilon=1/30)
print("recovered low part:", roots)

For non-built-in cases (bivariate, custom shifts) use the well-known defund/coppersmith helper. The mechanics of small_roots, the lattice it builds, and the achievable bounds are covered on the lattice attacks page.

CRT Fault Attack (Bellcore)

RSA signing is often sped up with the CRT: compute $s_p = m^d \bmod p$ and $s_q = m^d \bmod q$, then recombine. If a hardware/software fault corrupts exactly one half (say $s_q$ is wrong, $s_p$ correct), the faulty signature $\hat s$ satisfies $\hat s^e \equiv m \pmod p$ but $\not\equiv m \pmod q$. Therefore

One faulty signature factors the modulus.

from math import gcd

# m : the signed message (already encoded), e, n public
# s_faulty : a signature produced with a fault injected in one CRT branch
p = gcd(pow(s_faulty, e, n) - m, n)
q = n // p
print("p =", p, "q =", q)

The defence (verify the signature, or use Shamir's trick before releasing it) is exactly what a vulnerable CTF service forgets to do.

Bleichenbacher $e=3$ Signature Forgery

PKCS#1 v1.5 signatures with $e=3$ are forgeable when the verifier parses the padding loosely (does not check that the hash sits flush against the modulus, i.e. accepts trailing garbage). The signature block is

If the verifier ignores the bytes after the hash, you can craft a number whose perfect cube reproduces a valid-looking prefix, with arbitrary low bytes - and a cube root is easy with $e=3$. No private key required.

from gmpy2 import iroot, mpz
import hashlib

# Build the "left-aligned" block: header + ASN.1 + H(m), then garbage to fill n.
def forge_e3(msg, modulus_bits, asn1_prefix):
    h = hashlib.sha256(msg).digest()
    block = b"\x00\x01\xff\xff\xff\x00" + asn1_prefix + h
    # left-align in the modulus, pad the rest with zero bits we are free to choose
    block += b"\x00" * ((modulus_bits // 8) - len(block))
    target = int.from_bytes(block, "big")
    # take the ceil cube root; the cube's high bytes match our crafted prefix
    root, _ = iroot(mpz(target), 3)
    forged = int(root) + 1
    return forged                      # forged^3 verifies under a sloppy parser

# Real exploits tune the trailing bytes so the cube's prefix matches exactly;
# see Hal Finney's "Bleichenbacher's RSA signature forgery based on implementation error".

See Hal Finney's classic write-up for the byte-exact construction.

Checklist

• Tried FactorDB and a quick factor(n) / ECM pass
• $e$ tiny and message short? cube root, then try $c + kn$
• Same $m$ across $\ge e$ moduli? Hastad + CRT
• Same $n$, two coprime exponents? common modulus (Bezout)
• $e$ huge / $d$ small? Wiener, then Boneh-Durfee up to $n^{0.292}$
• Known linear relation between two messages? Franklin-Reiter gcd
• Leaked bits of $p$ or $d$? Coppersmith small-roots
• Parity/range oracle available? binary-search with $c\cdot 2^e$
• $\lvert p-q\rvert$ small? Fermat
• Many keys from one source? batch GCD for shared primes
• $p-1$ smooth? Pollard $p-1$ (and try $p+1$)
• Known plaintext structure? Coppersmith stereotyped / short-pad
• CRT signing service that can glitch? Bellcore fault, one signature
• $e=3$ PKCS#1 v1.5 verifier that is loose? Bleichenbacher forgery

See Also

• RSA Basics - key generation, the math, and the embedded quick-attack notes.
• Lattice Attacks - LLL and Coppersmith mechanics underpinning Boneh-Durfee, partial-key, and stereotyped attacks.
• ECC Attacks - the elliptic-curve counterpart catalogue.
• Diffie-Hellman Attacks - discrete-log weaknesses in the other major asymmetric family.
• Asymmetric Cryptography - subsection index and quick selectors.

Last updated on Jun 15, 2026