Rsa Attack Techniques

# 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](./SKILL.md) is already loaded for attack selection and decision trees.

---

## 1. FACTORIZATION METHODS — DETAILED

### 1.1 Trial Division

```python
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

```python
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).

```python
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):

```python
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).

```python
# 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₂):

```python
# 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 = d