RSA Attacks

c = (m^e) mod n

Small Exponent Attacks

Vulnerability

With very small public exponents

e = 3, 5, 17

No modular reduction occurs

m^e < n

The modular arithmetic becomes regular arithmetic

c = m^e

Which make easy to reverse the message

m = c^(1/e)

Check if m^e < n holds true

m_e = pow(message, e)
if m_e < modulus:
    print("Vulnerable to small exponent attack!")

Wiener's Attack

Vulnerability

Private exponent d is too small

d < (1/3) * N^(1/4)

• Compute continued fraction expansion of e/n

• For each convergent k/d, test if it's the correct private key

• Use relation: ed - 1 = k * φ(n) to find φ(n)

• Solve quadratic equation to find p and q

POC

import math

def is_vulnerable_to_wiener(e, n):
    """Check if potentially vulnerable to Wiener's attack"""
    threshold = (1/3) * (n ** 0.25)
    # Can't directly check d, but look for suspicious e/n ratios
    return e > n**0.5  # Heuristic: large e might indicate small d

def wieners_attack(e, n):
    """
    Implement Wiener's attack using continued fractions
    Returns: (p, q, d) if successful, None otherwise
    """
    from fractions import Fraction
    
    # Convert e/n to continued fraction
    convergents = continued_fraction_convergents(e, n)
    
    for k, d in convergents:
        if k == 0:
            continue
            
        # Check if this d works
        phi_n = (e * d - 1) // k
        
        # Solve quadratic: x² - (n - phi_n + 1)x + n = 0
        discriminant = (n - phi_n + 1) ** 2 - 4 * n
        
        if discriminant >= 0:
            sqrt_d = int(discriminant ** 0.5)
            if sqrt_d * sqrt_d == discriminant:
                p = ((n - phi_n + 1) + sqrt_d) // 2
                q = ((n - phi_n + 1) - sqrt_d) // 2
                
                if p * q == n:
                    return p, q, d
    
    return None

Boneh-Durfee Attack

Wiener's attack failed but d is still suspected to be small

Covers more cases than Wiener's N^0.25

d < N^0.292

Use lattice reduction (LLL algorithm)

POC

def boneh_durfee_attack(e, n, delta=0.292):

    # This requires advanced lattice reduction libraries (fpylll, sage)
    # Conceptual implementation:
    
    # 1. Set up lattice based on polynomial f(x,y) = 1 + x(n+1-e*y)
    # 2. Use LLL to find short vectors
    # 3. Extract small roots that give us d

Fermat's Factorization

Vulnerability

Prime factors p and q are close to each other

Use difference of squares

n = a² - b² = (a+b)(a-b)

Factor n by finding a and b

p = a+b, q = a-b

• Primes p and q are close: |p - q| is small

• Key generation used sequential or nearby primes

• n can be expressed as difference of squares efficiently

POC

import math

def fermats_factorization(n, max_iterations=100000):
    """
    Fermat's factorization method
    Returns: (p, q) if successful, None if failed
    """
    # Start with a = ceil(sqrt(n))
    a = int(math.ceil(math.sqrt(n)))
    
    for i in range(max_iterations):
        # Calculate b² = a² - n
        b_squared = a * a - n
        
        # Check if b² is a perfect square
        b = int(math.sqrt(b_squared))
        
        if b * b == b_squared:
            # Found factors!
            p = a + b
            q = a - b
            
            if p * q == n:
                return p, q
        
        a += 1
    
    return None

def is_vulnerable_to_fermat(n):
    """Check if n might be vulnerable to Fermat's attack"""
    sqrt_n = int(math.sqrt(n))
    
    # If sqrt(n) is very close to an integer, primes might be close
    if (sqrt_n + 1) ** 2 - n < sqrt_n:
        return True
    
    return False

1. Start with a = ⌈√n⌉

2. Compute b² = a² - n

3. Check if b² is a perfect square

4. If yes: p = a + b, q = a - b

5. If no: increment a and repeat

Pollard's p-1 Method

Vulnerability

Poor prime generation that produces smooth numbers

p-1

Use Fermat's Little Theorem to find factor p

gcd(a^(k!) - 1, n)

POC

import math
from math import gcd

def pollard_p_minus_1(n, B=1000):
    """
    Pollard's p-1 method
    B: smoothness bound
    Returns: non-trivial factor if found, None otherwise
    """
    # Choose random base
    a = 2
    
    # Compute a^(lcm(1,2,...,B)) mod n
    # We approximate lcm with product of prime powers
    
    # Generate primes up to B
    primes = sieve_of_eratosthenes(B)
    
    for p in primes:
        # Find highest power of p <= B
        power = int(math.log(B) / math.log(p))
        
        # Compute a = a^(p^power) mod n
        for _ in range(power):
            a = pow(a, p, n)
    
    # Compute gcd(a-1, n)
    factor = gcd(a - 1, n)
    
    if 1 < factor < n:
        return factor
    
    return None

def sieve_of_eratosthenes(limit):
    """Generate primes up to limit"""
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
    
    return [i for i in range(2, limit + 1) if sieve[i]]

1. Choose smoothness bound B

2. Compute a = 2^(lcm(1,2,...,B)) mod n

3. Calculate gcd(a-1, n)

4. If 1 < gcd < n, we found a factor

Pollard's Rho Method

Vulnerability

General factorization method

Attack: Use Floyd's cycle detection on pseudorandom sequence
Result: Find collision that reveals factor
Recovery: Factor n using birthday paradox principle

POC

def pollard_rho(n, x0=2, c=1):
    """
    Pollard's Rho algorithm
    Returns: non-trivial factor if found, None otherwise
    """
    if n % 2 == 0:
        return 2
    
    # Floyd's cycle detection
    x = x0
    y = x0
    
    while True:
        # Tortoise moves one step
        x = (x * x + c) % n
        
        # Hare moves two steps
        y = (y * y + c) % n
        y = (y * y + c) % n
        
        # Check for cycle
        factor = gcd(abs(x - y), n)
        
        if factor == 1:
            continue
        
        if factor == n:
            # Failure, try different parameters
            return pollard_rho(n, x0 + 1, c + 1)
        
        return factor

Broadcast Attacks (Hastad's Attack)

Vulnerability: Same message encrypted multiple times with different keys
Attack: Use Chinese Remainder Theorem to reconstruct original message
Result: Recover m^e, then take eth root
Recovery: m = (reconstructed_value)^(1/e)

When to Use

• Same plaintext encrypted under different RSA keys multiple times

• Small public exponent (e = 3, 5)

Mathematical Process

1. Collect k encryptions: (c₁, n₁), (c₂, n₂), ..., (cₖ, nₖ)

2. Use CRT to find m^e such that m^e ≡ cᵢ (mod nᵢ) for all i

3. Take the eth root: m = (m^e)^(1/e)