ctf-crypto-exotic

Files (1)

• SKILL.md

SKILL.md (first lines)

# CTF Crypto — Exotic Schemes

Braid DH, tropical semiring, Paillier oracle, Hamming, ElGamal.

---

## Phase 1: Braid Group DH — Alexander Polynomial

```python
from sympy import symbols, Poly, factor, gcd

def alexander_polynomial(braid_word, n_strands):
    """
    Compute Alexander polynomial of braid closure (knot invariant).
    This is a homomorphism from braid group → Laurent polynomial ring.
    """
    t = symbols('t')
    # Burau representation (reduced):
    # Generator sigma_i maps to matrix with t at position (i,i)
    I = [[1 if i==j else 0 for j in range(n_strands-1)]
         for i in range(n_strands-1)]

    def burau_generator(k, n, t_var):
        """Reduced Burau matrix for sigma_k."""
        mat = [[1 if i==j else 0 for j in range(n-1)] for i in range(n-1)]
        if k > 0: mat[k-1][k-1] = 1; mat[k-1][k] = 1
        mat[k][k] = -t_var
        if k < n-2: mat[k+1][k] = t_var; mat[k+1][k+1] = 1
        return mat

    result = I
    for gen in braid_word:
        m = burau_generator(abs(gen)-1, n_strands, t if gen > 0 else 1/t)
        result = matmul_poly(result, m, t)

    return det_poly(result, t)

# Attack on braid DH:
# Public: braid B, elements aB, Ba
# Alexander polynomial alex(B) is invariant under conjugation
# But alex(aB) = alex(B)^k only if specific structure → coefficient attack
# Many braid DH schemes broken by:
# 1. Conjugacy length attack (CLA)
# 2. Length-based attack (statistical)
# 3. Super summit set enumeration for small braids

def length_based_attack(public_braid, target, max_steps=1000):
    """
    Braid conjugacy search: find a such that aB = target.
    Heuristic: minimize braid word length.
    """
    current = public_braid
    for _ in range(max_steps):
        if current == target:
            return True
        # Try all generators and their inverses
        for g in generators + inverse_generators:
            conjugated = g * current * g.inverse()
            if len(conjugated) < len(current):
                current = conjugated
                break
    return current == target
```

---

## Phase 2: Tropical Semiring Cryptography

```python
import numpy as np

def trop_add(a, b):
    """Tropical addition = min."""
    return min(a, b)

def trop_mul(a, b):
    """Tropical multiplication = classical addition."""
    return a + b

def trop_matmul(A, B):
    """Tropical matrix multiplication."""
    n = len(A)
    C = [[float('inf')] * n for _ in range(n)]
    for i in range(n):
        for k in range(n):
            for j in range(n):
                C[i][j] = trop_add(C[i][j], trop_mul(A[i][k], B[k][j]))
    return C

def trop_matpow(M, k):
    """Tropical matrix exponentiation."""
    n = len(M)
    result = [[0 if i==j else float('inf') for j in range(n)] for i in range(n)]
    for _ in range(k):
        result = trop_matmul(result, M)
    return result

# Tropical DH attack via residuation:
# Public: A^k (tropical matrix power), find k
# Key insight: tropical eigenvalue = min cycle mean in weighted graph
# Recover: A has eigenvalue lambda, A^k has eigenvalue k*lambda
# Count tropical eigenvalue ratio to recover k

def trop_eigenvalue(A):
    """Tropical eigenvalue via minimum cycle mean (Floyd-Warshall)."""
    n = len(A)
    # All-pairs shortest paths in tropical sense
    d = [row[:] for row in A]
    for m in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = trop_add(d[i][j], trop_mul(d[i][m], d[m][j]))
    # Minimum mean cycle:
    return min(d[i][i] for i in range(n)) / 1  # simplified

def tropical_dlog(A, B, max_k=10000):
    """Given A and A^k = B, find k by tropical DLP."""
    current = [[0 if i==j else float('inf') for j in range(len(A))] for i in range(len(A))]
    for k in range(max_k):

From Yoraexe/ceobe, MIT.

More from Yoraexe/ceobe