ctf-crypto-ecc

Files (1)

• SKILL.md

SKILL.md (first lines)

# CTF Crypto — Elliptic Curve Attacks

Smart's attack, ECDSA nonce reuse, Pohlig-Hellman, invalid/singular curves, Ed25519 torsion.

## Install

```bash
sage --version   # SageMath required
pip install ecdsa pycryptodome --break-system-packages
```

---

## Phase 1: Detect Vulnerability

```python
# SageMath — check if curve is anomalous (Smart's attack):
E = EllipticCurve(GF(p), [a, b])
n = E.order()
print(f"p = {p}")
print(f"order n = {n}")
print(f"Anomalous (n==p): {n == p}")      # → Smart's attack
print(f"p-1 smooth: factor(p-1)")          # → Pohlig-Hellman
print(f"discriminant: {E.discriminant()}") # → 0 = singular

# Check for small subgroup factors (Pohlig-Hellman):
for factor, exp in factor(n):
    print(f"  {factor}^{exp}")
# If largest prime factor is small → Pohlig-Hellman
```

---

## Phase 2: Smart's Attack (Anomalous Curves)

```python
# When: E.order() == p
# Solves ECDLP in O(1) via p-adic lifting

def smart_attack(p, a, b, Gx, Gy, Qx, Qy):
    """Smart's attack: ECDLP on anomalous curve E(GF(p)) where #E = p."""
    E = EllipticCurve(GF(p), [a, b])
    G = E(Gx, Gy)
    Q = E(Qx, Qy)
    
    # Automatic (Sage handles anomalous internally):
    try:
        secret = G.discrete_log(Q)
        return secret
    except:
        pass
    
    # Manual p-adic lift:
    Qp = pAdicField(p, 2)
    Ep = EllipticCurve(Qp, [a, b])
    
    for gp in Ep.lift_x(ZZ(Gx), all=True):
        for qp_pt in Ep.lift_x(ZZ(Qx), all=True):
            try:
                pG = p * gp
                pQ = p * qp_pt
                x_G = ZZ(pG[0] / pG[1]) / p
                x_Q = ZZ(pQ[0] / pQ[1]) / p
                k = ZZ(x_Q / x_G) % p
                if E(Gx, Gy) * k == E(Qx, Qy):
                    return k
            except (ZeroDivisionError, ValueError):
                continue
    return None

# Usage:
secret = smart_attack(p, a, b, Gx, Gy, Qx, Qy)
print(f"Secret key: {secret}")
```

---

## Phase 3: Pohlig-Hellman (Smooth Order)

```python
# When: E.order() factors into small primes
# Solve DLP in each subgroup, combine with CRT

from sympy.ntheory.residues import n_order
from sympy.ntheory.modular import crt

def pohlig_hellman_ec(G, Q, n, E):
    """Pohlig-Hellman on E(GF(p)) with smooth order n."""
    factors = list(factor(n))
    residues = []
    moduli = []
    
    for q, e in factors:
        q_e = q**e
        # Subgroup generator:
        Gi = (n // q_e) * G
        Qi = (n // q_e) * Q
        
        # DLP in subgroup of order q^e:
        x = 0
        gamma = Gi
        for i in range(e):
            h = (q**(e - 1 - i)) * Qi
            # Brute-force in small subgroup:
            for k in range(q):
                if k * gamma == h:
                    x = (x + k * q**i) % q_e
                    Qi = Qi - k * (q**i * G)
                    break
        
        residues.append(int(x))
        moduli.append(int(q_e))
    
    # CRT combination:
    secret, _ = crt(moduli, residues)
    return secret

# In SageMath (automatic):
secret = G.discrete_log(Q)  # Sage uses Pohlig-Hellman automatically for smooth orders

From Yoraexe/ceobe, MIT.

More from Yoraexe/ceobe