Rsa Attack Techniques

SKILL: RSA Attack Techniques — Expert Cryptanalysis Playbook

AI LOAD INSTRUCTION: Expert RSA attack techniques for CTF and authorized security assessments. Covers factorization attacks, small exponent exploits, lattice-based approaches (Wiener/Boneh-Durfee/Coppersmith), broadcast attacks, common modulus, padding oracles, and fault attacks. Base models often suggest attacks that don't match the given parameters or miss the correct attack selection based on what's known.

0. RELATED ROUTING

• lattice-crypto-attacks for deep lattice theory behind Coppersmith/Boneh-Durfee
• hash-attack-techniques when RSA signature forgery involves hash weaknesses
• symmetric-cipher-attacks when RSA protects a symmetric key (hybrid encryption)

Advanced Reference

Also load RSA_ATTACK_CATALOG.md when you need:

• Detailed SageMath/Python implementation for each attack
• Step-by-step mathematical derivation
• Edge cases and failure conditions per attack

Quick attack selection

---

1. FACTORIZATION ATTACKS

1.1 Direct Factorization (Small n)

from sympy import factorint

n = 0x...  # small modulus
factors = factorint(n)
p, q = list(factors.keys())

When: n < ~512 bits, or known to be in factordb.

1.2 Fermat's Factorization

Works when p and q are close together: |p - q| is small.

from gmpy2 import isqrt, is_square

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

1.3 Pollard's p-1

Works when p-1 has only small prime factors (B-smooth).

from gmpy2 import gcd

def pollard_p1(n, B=2**20):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
    d = gcd(a - 1, n)
    if 1 < d < n:
        return d
    return None

1.4 Batch GCD (Multiple n share a factor)

from math import gcd
from functools import reduce

def batch_gcd(moduli):
    """Find shared factors among multiple RSA moduli."""
    product = reduce(lambda a, b: a * b, moduli)
    results = {}
    for i, n in enumerate(moduli):
        remainder = product // n
        g = gcd(n, remainder)
        if g != 1 and g != n:
            results[i] = (g, n // g)
    return results

---

2. SMALL EXPONENT ATTACKS

2.1 Cube Root Attack (e = 3, small m)

If m^e < n (no modular reduction occurred), simply take the e-th root.

from gmpy2 import iroot

c = 0x...  # ciphertext
e = 3
m, exact = iroot(c, e)
if exact:
    print(f"Plaintext: {bytes.fromhex(hex(m)[2:])}")

2.2 Hastad Broadcast Attack

Same message encrypted with same small e under different moduli (n₁, n₂, ..., nₑ).

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

# e = 3, three ciphertexts under three different n
n_list = [n1, n2, n3]
c_list = [c1, c2, c3]

# CRT: find x such that x ≡ ci (mod ni) for all i
r, M = crt(n_list, c_list)
m, exact = iroot(r, 3)
assert exact

2.3 Related Message Attack (Franklin-Reiter)

Two messages related by a known linear function: m₂ = a·m₁ + b. Same n and e.

# SageMath
def franklin_reiter(n, e, c1, c2, a, b):
    R.<x> = PolynomialRing(Zmod(n))
    f1 = x^e - c1
    f2 = (a*x + b)^e - c2
    return Integer(n - gcd(f1, f2).coefficients()[0])

---

3. LARGE e / SMALL d ATTACKS

3.1 Wiener's Attack (Continued Fractions)

When d < n^(1/4) / 3, the continued fraction expansion of e/n reveals d.

def wiener_attack(e, n):
    """Recover d when d is small via continued fractions."""
    cf = continued_fraction(e, n)
    convergents = get_convergents(cf)

    for k, d in convergents:
        if k == 0:
            continue
        phi_candidate = (e * d - 1) // k
        # phi(n) = n - p - q + 1 → p + q = n - phi + 1
        s = n - phi_candidate + 1
        # p, q are roots of x^2 - s*x + n = 0
        discriminant = s * s - 4 * n
        if discriminant >= 0:
            from gmpy2 import isqrt, is_square
            if is_square(discriminant):
                return d
    return None

def continued_fraction(a, b):
    cf = []
    while b:
        cf.append(a // b)
        a, b = b, a % b
    return cf

def get_convergents(cf):
    convergents = []
    h_prev, h_curr = 0, 1
    k_prev, k_curr = 1, 0
    for a in cf:
        h_prev, h_curr = h_curr, a * h_curr + h_prev
        k_prev, k_curr = k_curr, a * k_curr + k_prev
        convergents.append((h_curr, k_curr))
    return convergents

3.2 Boneh-Durfee Attack (Lattice-Based)

Extends Wiener: works when d < n^0.292. Uses lattice reduction (LLL/BKZ).

Use SageMath implementation — see lattice-crypto-attacks for theory.

---

4. COPPERSMITH'S METHOD

4.1 Stereotyped Message

Known portion of plaintext, unknown part is small.

# SageMath
n = ...
e = 3
c = ...
known_prefix = b"flag{" + b"\x00" * 27  # known prefix, unknown suffix
known_int = int.from_bytes(known_prefix, 'big')

R.<x> = PolynomialRing(Zmod(n))
f = (known_int + x)^e - c
roots = f.small_roots(X=2^(27*8), beta=1.0)
if roots:
    m = known_int + int(roots[0])
    print(bytes.fromhex(hex(m)[2:]))

4.2 Partial Key Exposure

Known MSB or LSB of p → recover full p via Coppersmith.

# SageMath — known MSB of p
p_msb = ...  # known upper bits of p
R.<x> = PolynomialRing(Zmod(n))
f = p_msb + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
if roots:
    p = p_msb + int(roots[0])
    q = n // p

---

5. COMMON MODULUS ATTACK

Two ciphertexts of same message under same n but different e₁, e₂ where gcd(e₁, e₂) = 1.

from gmpy2 import gcd, invert

def common_modulus(n, e1, e2, c1, c2):
    """Recover m when same message encrypted with two different e under same n."""
    assert gcd(e1, e2) == 1
    _, s1, s2 = extended_gcd(e1, e2)  # s1*e1 + s2*e2 = 1

    if s1 < 0:
        c1 = invert(c1, n)
        s1 = -s1
    if s2 < 0:
        c2 = invert(c2, n)
        s2 = -s2

    m = (pow(c1, s1, n) * pow(c2, s2, n)) % n
    return m

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x, y = extended_gcd(b % a, a)
    return g, y - (b // a) * x, x

---

6. ORACLE ATTACKS

6.1 LSB Oracle (Parity Oracle)

An oracle reveals whether decrypted message is even or odd.

from gmpy2 import mpz

def lsb_oracle_attack(n, e, c, oracle_func):
    """Decrypt using LSB (parity) oracle. oracle_func(c) returns m%2."""
    from fractions import Fraction
    lo, hi = Fraction(0), Fraction(n)

    for _ in range(n.bit_length()):
        c = (c * pow(2, e, n)) % n  # multiply plaintext by 2
        if oracle_func(c) == 0:
            hi = (lo + hi) / 2
        else:
            lo = (lo + hi) / 2

    return int(hi)

6.2 Bleichenbacher (PKCS#1 v1.5 Padding Oracle)

Given a padding validity oracle (valid/invalid PKCS#1 v1.5), iteratively narrow down the plaintext range.

Complexity: O(2^16) oracle queries per byte on average.

Target: TLS implementations returning different errors for valid/invalid padding.

6.3 Manger's Attack (PKCS#1 OAEP)

Similar to Bleichenbacher but for OAEP padding. Exploits oracle that distinguishes whether the first byte after unpadding is 0x00.

---

7. RSA-CRT FAULT ATTACK

If RSA-CRT signing produces a faulty signature (fault in one CRT half):

def rsa_crt_fault(n, e, correct_sig, faulty_sig, msg):
    """Factor n from one correct and one faulty CRT signature."""
    from math import gcd
    diff = pow(correct_sig, e, n) - pow(faulty_sig, e, n)
    p = gcd(diff % n, n)
    if 1 < p < n:
        q = n // p
        return p, q
    return None

# Even simpler: only faulty signature needed if message is known
def rsa_crt_fault_simple(n, e, faulty_sig, msg):
    p = gcd(pow(faulty_sig, e, n) - msg, n)
    if 1 < p < n:
        return p, n // p
    return None

---

8. DECISION TREE

RSA challenge — what information do you have?
│
├─ Have n and it's small (< 512 bits)?
│  └─ Factor directly: factordb.com → yafu → msieve
│
├─ Have multiple n values?
│  └─ Batch GCD — shared factors?
│     ├─ Yes → factor all that share factors
│     └─ No → analyze each n individually
│
├─ Know e?
│  ├─ e = 3 (or small)?
│  │  ├─ Single ciphertext, small message → cube root
│  │  ├─ Multiple ciphertexts, different n → Hastad broadcast
│  │  ├─ Two related messages → Franklin-Reiter
│  │  └─ Partial plaintext known → Coppersmith
│  │
│  ├─ e is very large?
│  │  └─ d is likely small → Wiener → Boneh-Durfee
│  │
│  └─ Same n, two different e values?
│     └─ Common modulus attack (Bezout coefficients)
│
├─ Know partial factorization info?
│  ├─ Know some bits of p → Coppersmith partial key
│  ├─ p-1 is B-smooth → Pollard p-1
│  └─ p ≈ q (close primes) → Fermat factorization
│
├─ Have an oracle?
│  ├─ Parity oracle (LSB) → LSB oracle attack
│  ├─ Padding validity oracle (PKCS#1 v1.5) → Bleichenbacher
│  └─ OAEP oracle → Manger's attack
│
├─ Have faulty signature?
│  └─ RSA-CRT fault → factor n from faulty sig
│
├─ Know e·d relationship?
│  └─ e·d ≡ 1 mod φ(n) → factor n from (e,d,n)
│
└─ None of the above?
   ├─ Check factordb for known factorization
   ├─ Try Pollard rho for medium-size n
   ├─ Look for implementation flaws (weak PRNG for key generation)
   └─ Consider side-channel if physical access available

---

9. TOOLS

RsaCtfTool Quick Commands

# From public key
python3 RsaCtfTool.py --publickey pub.pem -n --private

# From parameters
python3 RsaCtfTool.py -n $N -e $E --uncipher $C

# Try all attacks
python3 RsaCtfTool.py --publickey pub.pem --uncipherfile flag.enc --attack all

Decrypt After Factoring

from Crypto.PublicKey import RSA
from gmpy2 import invert

p, q = ...  # factored
n = p * q
e = 65537
phi = (p - 1) * (q - 1)
d = int(invert(e, phi))

c = ...  # ciphertext as integer
m = pow(c, d, n)
plaintext = m.to_bytes((m.bit_length() + 7) // 8, 'big')
print(plaintext)

RSA Attack Catalog — Detailed Implementations & Mathematics

AI LOAD INSTRUCTION: Load this when you need full mathematical derivations, complete SageMath/Python implementations, and edge-case handling for each RSA attack. Assumes the main SKILL.md is already loaded for attack selection and decision trees.

---

1. FACTORIZATION METHODS — DETAILED

1.1 Trial Division

def trial_division(n, limit=10**6):
    """Factor n by trial division up to limit."""
    factors = []
    d = 2
    while d * d <= n and d <= limit:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

1.2 Pollard's Rho

from math import gcd
from random import randint

def pollard_rho(n):
    """Pollard's rho factorization."""
    if n % 2 == 0:
        return 2
    x = randint(2, n - 1)
    y = x
    c = randint(1, n - 1)
    d = 1
    while d == 1:
        x = (x * x + c) % n
        y = (y * y + c) % n
        y = (y * y + c) % n
        d = gcd(abs(x - y), n)
    return d if d != n else None

1.3 Williams' p+1

Works when p+1 is smooth (complement to Pollard's p-1).

def williams_pp1(n, B=10**6):
    """Williams p+1 factorization."""
    from sympy import nextprime
    
    for A in range(3, 20):
        v = A
        p = 2
        while p < B:
            e = 1
            pe = p
            while pe * p <= B:
                pe *= p
                e += 1
            # Lucas chain multiplication
            v = lucas_chain(v, pe, n)
            p = nextprime(p)
        
        g = gcd(v - 2, n)
        if 1 < g < n:
            return g
    return None

1.4 Quadratic Sieve (Concept)

For n in range 10^30 to 10^100. Use yafu or msieve for implementation.

Algorithm outline:
1. Choose factor base of small primes
2. Sieve for B-smooth values of Q(x) = (x + ⌈√n⌉)² - n
3. Collect enough smooth relations (≥ factor base size + 1)
4. Linear algebra over GF(2) to find subset product = perfect square
5. Compute gcd(x² - y², n) to find factor

---

2. SMALL EXPONENT ATTACKS — DETAILED

2.1 Cube Root with Padding Search

When m^e slightly exceeds n (wraps around a few times):

from gmpy2 import iroot, mpz

def cube_root_with_wrap(c, e, n, max_k=10000):
    """Try c + k*n for small k, check if perfect e-th root."""
    for k in range(max_k):
        m, exact = iroot(mpz(c + k * n), e)
        if exact:
            return int(m)
    return None

2.2 Hastad with Linear Padding

When messages have linear padding: mᵢ = a·m + bᵢ (different padding per recipient).

# SageMath
def hastad_linear_padding(n_list, c_list, e, a_list, b_list):
    """Hastad attack with linear padding: m_i = a_i * m + b_i."""
    assert len(n_list) == e
    
    # Build polynomial for CRT
    N = product(n_list)
    R.<x> = PolynomialRing(Zmod(N))
    
    g = 0
    for i in range(e):
        Ni = N // n_list[i]
        ti = inverse_mod(Ni, n_list[i])
        fi = (a_list[i] * x + b_list[i])^e - c_list[i]
        g += fi * Ni * ti
    
    g = g.monic()
    roots = g.small_roots()
    if roots:
        return int(roots[0])
    return None

2.3 Coppersmith's Short Pad Attack

Two encryptions of same message with different short random padding (r₁, r₂):

# SageMath
def short_pad_attack(n, e, c1, c2, pad_bits):
    """Recover message when same message has short random padding."""
    R.<x, y> = PolynomialRing(Zmod(n))
    
    # m1 = m * 2^pad_bits + r1, m2 = m * 2^pad_bits + r2
    # Let y = r1 - r2 (difference of padding)
    g1 = x^e - c1
    g2 = (x + y)^e - c2
    
    # Resultant eliminates x, leaving univariate in y
    res = g1.resultant(g2, x)
    
    Ry.<yy> = PolynomialRing(Zmod(n))
    res_uni = Ry(res.polynomial(y))
    roots = res_uni.small_roots(X=2^pad_bits)
    
    if roots:
        diff = int(roots[0])
        # Now solve for x with known y = diff
        # ...

---

3. WIENER'S ATTACK — COMPLETE IMPLEMENTATION

def wiener_full(e, n):
    """Full Wiener's attack implementation with validation."""
    from gmpy2 import isqrt, is_square, mpz
    
    cf = []
    a, b = e, n
    while b:
        cf.append(a // b)
        a, b = b, a % b
    
    # Generate convergents
    p_prev, p_curr = 0, 1
    q_prev, q_curr = 1, 0
    
    for a_i in cf:
        p_prev, p_curr = p_curr, a_i * p_curr + p_prev
        q_prev, q_curr = q_curr, a_i * q_curr + q_prev
        
        k, d = p_curr, q_curr
        
        if k == 0:
            continue
        
        # Check if (e*d - 1) / k is integer (= phi(n))
        if (e * d - 1) % k != 0:
            continue
        
        phi = (e * d - 1) // k
        
        # p + q = n - phi + 1
        # p * q = n
        s = n - phi + 1
        discriminant = mpz(s * s - 4 * n)
        
        if discriminant < 0:
            continue
        
        if is_square(discriminant):
            sqrt_disc = isqrt(discriminant)
            p = (s + sqrt_disc) // 2
            q = (s - sqrt_disc) // 2
            if p * q == n:
                return d, int(p), int(q)
    
    return None

---

4. BONEH-DURFEE — SAGE IMPLEMENTATION

# SageMath
def boneh_durfee(n, e, delta=0.292, m=4):
    """
    Boneh-Durfee attack for small d: d < n^delta.
    Based on: e*d = 1 + k*(n+1-p-q) = 1 + k*(n+1-s) where s = p+q.
    Rewrite: 1 + k*(n+1) ≡ k*s (mod e)
    """
    A = Integer((n + 1) // 2)
    P.<x, y> = PolynomialRing(ZZ)
    f = 1 + x * (A + y)
    
    X = Integer(2 * floor(n^delta))
    Y = Integer(floor(n^0.5))
    
    # Build lattice for Coppersmith-type method
    t = m + 1
    shifts = []
    
    for k in range(m + 1):
        for i in range(m - k + 1):
            g = x^i * f^k * e^(m - k)
            shifts.append(g)
    
    for k in range(1, t + 1):
        for i in range(k):
            g = y^i * f^k * e^(m - k)  
            shifts.append(g)
    
    # Construct lattice matrix and apply LLL
    # ... (full lattice construction omitted for brevity)
    # Use standard Coppersmith multivariate implementation
    
    # After LLL: extract small root (x0, y0)
    # k = x0, s = 2*(A + y0)
    # p = (s + sqrt(s^2 - 4n)) / 2

---

5. LSB ORACLE ATTACK — COMPLETE

from gmpy2 import mpz, invert
from decimal import Decimal, getcontext

def lsb_oracle_full(n, e, c, oracle):
    """
    Full LSB oracle attack.
    oracle(c) → returns LSB of decrypt(c), i.e., m mod 2.
    """
    getcontext().prec = n.bit_length() + 100
    
    lo = Decimal(0)
    hi = Decimal(n)
    
    two_e = pow(2, e, n)
    multiplier = mpz(1)
    
    for i in range(n.bit_length()):
        multiplier = (multiplier * two_e) % n
        test_c = (c * multiplier) % n
        
        lsb = oracle(int(test_c))
        
        mid = (lo + hi) / 2
        if lsb == 0:
            hi = mid
        else:
            lo = mid
    
    return int(hi)

---

6. BLEICHENBACHER ATTACK — ALGORITHM OUTLINE

Input: oracle O(c) = 1 if PKCS-conformant, 0 otherwise
       n, e (public key), c₀ (target ciphertext)

Step 1: Blinding
  Find s₀ such that O(c₀ · s₀ᵉ mod n) = 1
  Set c ← c₀ · s₀ᵉ mod n

Step 2a: Starting search
  Find smallest s₁ ≥ ⌈n/(3B)⌉ such that O(c · s₁ᵉ mod n) = 1
  where B = 2^(8*(k-2)), k = byte length of n

Step 2b: Searching with one interval
  If M = {[a, b]}, find smallest s ≥ 2(b·sᵢ₋₁ - 2B)/n
  such that O(c · sᵉ mod n) = 1

Step 3: Narrowing intervals
  For each (s, [a,b]) in M × {s}:
    r_min = ⌈(a·s - 3B + 1) / n⌉
    r_max = ⌊(b·s - 2B) / n⌋
    For r in [r_min, r_max]:
      Update interval: [max(a, ⌈(2B + r·n)/s⌉), min(b, ⌊(3B - 1 + r·n)/s⌋)]

Step 4: Check
  If M = {[a, a]}: m = a (done!)
  Else: go to Step 2

---

7. RSA-CRT FAULT — MATHEMATICAL DERIVATION

RSA-CRT computation:
  sp = m^d mod p     (computed correctly)
  sq = m^d mod q     (fault injected here → s̃q ≠ sq)
  
  Correct: s = CRT(sp, sq) = sp + p · (((sq - sp) · p⁻¹) mod q)
  Faulty:  s̃ = CRT(sp, s̃q) = sp + p · (((s̃q - sp) · p⁻¹) mod q)

Verification:
  s^e ≡ m (mod p)   ← correct (sp was correct)
  s̃^e ≡ m (mod p)   ← correct (sp was correct)
  
  s^e ≡ m (mod q)   ← correct
  s̃^e ≢ m (mod q)   ← wrong (s̃q was faulty)

Therefore:
  s̃^e - m ≡ 0 (mod p)   but   s̃^e - m ≢ 0 (mod q)
  
  ⟹ gcd(s̃^e - m, n) = p

from math import gcd

def rsa_crt_factor(n, e, m, faulty_sig):
    """Factor n from a single faulty CRT signature."""
    diff = (pow(faulty_sig, e, n) - m) % n
    p = gcd(diff, n)
    if 1 < p < n:
        return p, n // p
    return None

---

8. MULTI-PRIME RSA

When n = p · q · r (three or more primes):

from sympy import factorint
from functools import reduce

def multi_prime_decrypt(n, e, c):
    factors = factorint(n)
    primes = list(factors.keys())
    
    # Euler's totient for multi-prime
    phi = reduce(lambda a, p: a * (p - 1), primes, 1)
    
    d = pow(e, -1, phi)
    m = pow(c, d, n)
    return m

---

9. KNOWN e·d → FACTOR n

from random import randint
from math import gcd

def factor_from_ed(n, e, d):
    """Factor n given e and d such that e·d ≡ 1 (mod φ(n))."""
    k = e * d - 1
    
    while True:
        g = randint(2, n - 2)
        t = k
        
        while t % 2 == 0:
            t //= 2
            x = pow(g, t, n)
            
            if x > 1 and gcd(x - 1, n) > 1:
                p = gcd(x - 1, n)
                if p != n:
                    return p, n // p

---

10. ATTACK CONDITIONS SUMMARY