RSA Attacks

Exploit common RSA vulnerabilities in CTF challenges.

RSA Basics Review

from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime, inverse

# RSA Parameters:
# n = p * q (modulus)
# e (public exponent, commonly 65537)
# d = inverse(e, phi) where phi = (p-1)*(q-1)
# c = m^e mod n (encryption)
# m = c^d mod n (decryption)

def rsa_encrypt(m: int, e: int, n: int) -> int:
    return pow(m, e, n)

def rsa_decrypt(c: int, d: int, n: int) -> int:
    return pow(c, d, n)

def compute_private_key(p: int, q: int, e: int) -> int:
    """Compute private exponent d from factors."""
    phi = (p - 1) * (q - 1)
    d = inverse(e, phi)
    return d

Small e Attack (e=3, no padding)

import gmpy2

def small_e_attack(c: int, e: int = 3) -> int:
    """If m^e < n, we can just take the eth root."""
    m, exact = gmpy2.iroot(c, e)
    if exact:
        return int(m)
    return None

# Example
e = 3
m = 12345678
n = 10**100  # Large n
c = pow(m, e, n)  # c = m^3 because m^3 < n

recovered = small_e_attack(c, e)
print(f"Recovered: {recovered}")

Hastad's Broadcast Attack

from sympy.ntheory.modular import crt

def hastad_broadcast(ciphertexts: list, moduli: list, e: int = 3) -> int:
    """When same message sent to e recipients with same e.

    Given c1 = m^e mod n1, c2 = m^e mod n2, c3 = m^e mod n3
    Use CRT to find m^e, then take eth root.
    """
    # Chinese Remainder Theorem
    m_e, _ = crt(moduli, ciphertexts)
    m, exact = gmpy2.iroot(m_e, e)
    if exact:
        return int(m)
    return None

# Example with e=3
n1, n2, n3 = getPrime(512), getPrime(512), getPrime(512)
m = bytes_to_long(b"secret message")
c1 = pow(m, 3, n1)
c2 = pow(m, 3, n2)
c3 = pow(m, 3, n3)

recovered = hastad_broadcast([c1, c2, c3], [n1, n2, n3], 3)
print(long_to_bytes(recovered))

Common Modulus Attack

from math import gcd

def common_modulus_attack(c1: int, c2: int, e1: int, e2: int, n: int) -> int:
    """When same message encrypted with two different public exponents but same n.

    If gcd(e1, e2) = 1, we can recover m.
    """
    def extended_gcd(a, b):
        if a == 0:
            return b, 0, 1
        gcd_val, x1, y1 = extended_gcd(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd_val, x, y

    g, a, b = extended_gcd(e1, e2)
    if g != 1:
        return None

    # m = c1^a * c2^b mod n
    if a < 0:
        c1 = inverse(c1, n)
        a = -a
    if b < 0:
        c2 = inverse(c2, n)
        b = -b

    m = (pow(c1, a, n) * pow(c2, b, n)) % n
    return m

Wiener's Attack (Small d)

def continued_fraction(n: int, d: int) -> list:
    """Compute continued fraction expansion of n/d."""
    cf = []
    while d:
        cf.append(n // d)
        n, d = d, n % d
    return cf

def convergents(cf: list) -> list:
    """Get convergents from continued fraction."""
    convs = []
    for i in range(len(cf)):
        if i == 0:
            n, d = cf[0], 1
        elif i == 1:
            n = cf[0] * cf[1] + 1
            d = cf[1]
        else:
            n = cf[i] * convs[-1][0] + convs[-2][0]
            d = cf[i] * convs[-1][1] + convs[-2][1]
        convs.append((n, d))
    return convs

def wieners_attack(e: int, n: int) -> int:
    """Recover d when d < n^0.25 / 3."""
    cf = continued_fraction(e, n)
    convs = convergents(cf)

    for k, d in convs:
        if k == 0:
            continue

        # Check if d is correct
        phi_candidate = (e * d - 1) // k
        if (e * d - 1) % k != 0:
            continue

        # phi = (p-1)(q-1) = n - p - q + 1
        # p + q = n - phi + 1
        # Check if we can factor n
        b = n - phi_candidate + 1
        discriminant = b * b - 4 * n

        if discriminant >= 0:
            sqrt_disc = gmpy2.isqrt(discriminant)
            if sqrt_disc * sqrt_disc == discriminant:
                p = (b + sqrt_disc) // 2
                if n % p == 0:
                    return d

    return None

# Example
# When d is small, Wiener's attack can recover it

Fermat Factorization

import gmpy2

def fermat_factor(n: int) -> tuple:
    """Factor n when p and q are close (|p - q| small)."""
    a = gmpy2.isqrt(n)
    if a * a == n:
        return int(a), int(a)

    a += 1
    b2 = a * a - n

    while not gmpy2.is_square(b2):
        a += 1
        b2 = a * a - n

    b = gmpy2.isqrt(b2)
    p = int(a + b)
    q = int(a - b)

    return p, q

# Example: Close primes
p = getPrime(256)
q = p + 2 * getPrime(32)  # q close to p
n = p * q

recovered_p, recovered_q = fermat_factor(n)
print(f"Factored: {recovered_p} * {recovered_q}")

Pollard's p-1 Attack

from math import gcd

def pollard_p1(n: int, B: int = 100000) -> int:
    """Factor n when p-1 is B-smooth."""
    a = 2

    for j in range(2, B + 1):
        a = pow(a, j, n)
        d = gcd(a - 1, n)
        if 1 < d < n:
            return d

    return None

# Example: Works when p-1 has only small factors
# p = 2 * 3 * 5 * 7 * 11 * 13 + 1  # p-1 is 13-smooth

Shared Prime Attack

from math import gcd

def shared_prime_attack(n1: int, n2: int) -> tuple:
    """Find shared prime between two moduli."""
    p = gcd(n1, n2)
    if p > 1 and p < n1 and p < n2:
        q1 = n1 // p
        q2 = n2 // p
        return p, q1, q2
    return None

# If two RSA keys share a prime, both are broken

Franklin-Reiter Related Message Attack

from sympy import symbols, gcd as poly_gcd, Poly

def franklin_reiter(c1: int, c2: int, e: int, n: int, a: int = 1, b: int = 1) -> int:
    """When m2 = a*m1 + b (linear relation), recover m1.

    Requires gcd of polynomials.
    """
    x = symbols('x')
    # f1 = x^e - c1
    # f2 = (ax + b)^e - c2
    # gcd gives us the linear factor (x - m1)

    f1 = Poly(x**e - c1, x, domain='ZZ')
    f2 = Poly((a*x + b)**e - c2, x, domain='ZZ')

    # Compute GCD in Zn (simplified - actual implementation more complex)
    # This is conceptual; real implementation needs polynomial GCD mod n

    return None  # Placeholder - use specialized libraries

# Coppersmith's short pad attack is similar but for small padding differences

RSA-CRT Fault Attack

def crt_fault_attack(signature_good: int, signature_faulty: int, message: int, e: int, n: int) -> int:
    """Recover p from faulty CRT signature.

    If signature computed with fault in one CRT component,
    we can factor n.
    """
    # s_good^e = m mod n
    # s_faulty^e != m mod n, but s_faulty^e = m mod p OR mod q

    diff = pow(signature_good, e, n) - pow(signature_faulty, e, n)
    p = gcd(diff, n)

    if 1 < p < n:
        return p
    return None