ctf-crypto-rsa

Files (1)

• SKILL.md

SKILL.md (first lines)

# CTF Crypto — RSA Attacks

Complete RSA attack toolkit: cube root, Wiener, Hastad, Pollard, Fermat, batch GCD, Manger oracle, signature forgery.

## Install

```bash
pip install pycryptodome gmpy2 sympy owiener --break-system-packages
# SageMath for Coppersmith:
# apt-get install -y sagemath
```

---

## Phase 1: Small Public Exponent (Cube Root)

```python
import gmpy2

def small_e_attack(c, e):
    """Works when m^e < n (no modular wrap)."""
    m, exact = gmpy2.iroot(c, e)
    if exact:
        return int(m)
    return None

m = small_e_attack(c, e=3)
if m:
    print(bytes.fromhex(hex(m)[2:]))
```

---

## Phase 2: Common Modulus Attack

```python
from math import gcd

def common_modulus_attack(c1, c2, e1, e2, n):
    """Same n, same message, different coprime exponents."""
    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

    g, a, b = extended_gcd(e1, e2)
    assert g == 1
    if a < 0:
        c1 = pow(c1, -1, n); a = -a
    if b < 0:
        c2 = pow(c2, -1, n); b = -b
    return (pow(c1, a, n) * pow(c2, b, n)) % n

m = common_modulus_attack(c1, c2, e1, e2, n)
print(bytes.fromhex(hex(m)[2:]))
```

---

## Phase 3: Wiener's Attack (Small Private Exponent)

```python
import owiener  # pip install owiener

d = owiener.attack(e, n)
if d:
    m = pow(c, d, n)
    print(bytes.fromhex(hex(m)[2:]))
else:
    print("Wiener failed — d not small enough")

# Manual implementation:
def wiener_attack(e, n):
    def continued_fraction(num, den):
        cf = []
        while den:
            q, r = divmod(num, den)
            cf.append(q)
            num, den = den, r
        return cf

    def convergents(cf):
        h0, h1 = 0, 1
        k0, k1 = 1, 0
        for a in cf:
            h0, h1 = h1, a * h1 + h0
            k0, k1 = k1, a * k1 + k0
            yield h1, k1

    from math import isqrt
    for k, d in convergents(continued_fraction(e, n)):
        if k == 0: continue
        if (e * d - 1) % k != 0: continue
        phi = (e * d - 1) // k
        s = n - phi + 1
        disc = s * s - 4 * n
        if disc < 0: continue
        t = isqrt(disc)
        if t * t == disc:
            return d
    return None
```

---

## Phase 4: Pollard's p-1 Factorization

```python
from math import gcd

def pollard_p1(n, B=100000):
    """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, n // d
    return None

From Yoraexe/ceobe, MIT.

More from Yoraexe/ceobe