ctf-crypto-advanced-math

Files (1)

• SKILL.md

SKILL.md (first lines)

# CTF Crypto — Advanced Mathematical Attacks

LLL, Coppersmith, isogenies, quaternion RSA, LWE, Manger oracle.

## Install

```bash
sage  # SageMath for lattice/number theory
pip install fpylll z3-solver --break-system-packages
```

---

## Phase 1: LLL Lattice Attack

```python
# Pattern: hints h_i = flag * p_i + noise (noise is small)
# LLL finds short vector → reveals p_i values

from sage.all import *

# Collect 3 server hints:
h1, h2, h3 = (hint1, hint2, hint3)  # from server

M = matrix(ZZ, [
    [1, 0, 0, h1],
    [0, 1, 0, h2],
    [0, 0, 1, h3],
    [0, 0, 0, -1]
])
reduced = M.LLL()
# Short vector: contains p1, p2, p3
# Recover flag: (h1 - noise) // p1
```

---

## Phase 2: Merkle-Hellman Knapsack via LLL

```python
from sage.all import *

def crack_knapsack(pubKey, encoded):
    """Crack Merkle-Hellman knapsack encryption via LLL."""
    nbit = len(pubKey)
    A = Matrix(ZZ, nbit + 1, nbit + 1)
    
    for i in range(nbit):
        A[i, i] = 1
        A[i, nbit] = pubKey[i]
    A[nbit, nbit] = -int(encoded)
    
    res = A.LLL()
    
    for row in res:
        if row[-1] == 0 and all(b in (0, 1) for b in row[:-1]):
            plaintext_bits = list(row[:-1])
            return bytes(int(''.join(map(str, plaintext_bits[i:i+8])), 2) 
                        for i in range(0, len(plaintext_bits)-7, 8))
    return None

# Usage:
flag = crack_knapsack(server_pubkey, server_ciphertext)
```

---

## Phase 3: Coppersmith — Partially Known Prime

```python
from sage.all import *

# Pattern: p = base + 10^k * x where base is known, x is small
# Condition: x < N^(1/e) ≈ N^0.25 for linear polynomial

def coppersmith_known_prefix(N, base, k):
    """Find small x where p = base + 10^k * x divides N."""
    R = PolynomialRing(Zmod(N), 'x')
    x = R.gen()
    
    inv_10k = int(pow(10**k, -1, N))
    f = x + int(base * inv_10k % N)  # Must be monic
    
    roots = f.small_roots(X=2**70, beta=0.5)
    if roots:
        x_val = int(roots[0])
        p = base + 10**k * x_val
        q = N // p
        if p * q == N:
            return p, q
    return None, None

p, q = coppersmith_known_prefix(N, known_base, k_value)
if p:
    phi = (p-1)*(q-1)
    d = pow(e, -1, phi)
    m = pow(ct, d, N)
```

---

## Phase 4: Pohlig-Hellman (Smooth Curve Order)

```python
from sage.all import *

# ECC with smooth order → Pohlig-Hellman DLP

def pohlig_hellman_ecc(G, P, E, n):
    """Solve discrete log P = d*G where E.order() is smooth."""
    factors = factor(n)
    partial_logs = []
    
    for (prime, exp) in factors:
        cofactor = n // (prime ** exp)
        G_sub = cofactor * G
        P_sub = cofactor * P
        
        d_sub = discrete_log(P_sub, G_sub, ord=prime**exp)

From Yoraexe/ceobe, MIT.

More from Yoraexe/ceobe