L = { a₁·b₁ + a₂·b₂ + ... + aₙ·bₙ | aᵢ ∈ ℤ }

Determinant: det(L) = |det(B)| where B is the basis matrix
Gaussian heuristic: shortest vector ≈ √(n/(2πe)) · det(L)^(1/n)

undefined

undefined

from fpylll import IntegerMatrix, LLL

n = 4
A = IntegerMatrix(n, n)

---

undefined

Rule of thumb: start with LLL, increase to BKZ if needed. BKZ block size 20-40 is usually sufficient for CTF.

---

undefined

**Parameters**:
- `X`: upper bound on the root
- `beta`: N = p^beta (beta=1.0 for modular root of N itself; beta=0.5 for root mod unknown factor p ≈ √N)
- `epsilon`: smaller = better results but slower (try 1/30 to 1/100)

undefined

undefined

undefined

undefined

undefined

---

undefined

# Build lattice
B = 2^(q.nbits() - known_bits)  # bound on unknown part
M = matrix(QQ, n + 2, n + 2)

for i in range(n):
    r_i, s_i, h_i, a_i = signatures[i]
    t_i = Integer(inverse_mod(s_i, q) * r_i % q)
    u_i = Integer(inverse_mod(s_i, q) * h_i % q)

    M[i, i] = q
    M[n, i] = t_i
    M[n+1, i] = u_i - a_i  # a_i = known nonce bits

M[n, n] = B / q
M[n+1, n+1] = B

# LLL reduction
L = M.LLL()

# Find row containing the private key x
for row in L:
    x_candidate = Integer(row[n] * q / B) % q
    # Verify x_candidate against one signature
    if verify_private_key(x_candidate, signatures[0], q):
        return x_candidate

return None

undefined

def ecdsa_reused_nonce(r, s1, s2, h1, h2, q):
    """Recover private key when nonce k is reused."""
    # s1 - s2 = k⁻¹(h1 - h2) mod q  (since r is same)
    k = ((h1 - h2) * inverse_mod(s1 - s2, q)) % q
    x = ((s1 * k - h1) * inverse_mod(r, q)) % q
    return x, k

undefined

# Build lattice (Lagarias-Odlyzko style)
N = ceil(sqrt(n) / 2)  # scaling factor
M = matrix(ZZ, n + 1, n + 1)

for i in range(n):
    M[i, i] = 1
    M[i, n] = N * weights[i]
M[n, n] = N * target

# Alternative: CJLOSS embedding
M2 = matrix(ZZ, n + 1, n + 2)
for i in range(n):
    M2[i, i] = 1
    M2[i, n + 1] = N * weights[i]
M2[n, n] = 1
M2[n, n + 1] = N * (-target)

L = M2.LLL()

# Look for short vector with entries in {0, 1, -1}
for row in L:
    if all(v in (0, 1) for v in row[:n]):
        solution = list(row[:n])
        if sum(solution[i] * weights[i] for i in range(n)) == target:
            return solution

return None

---

undefined

H = matrix(ZZ, N, N)
for i in range(N):
    for j in range(N):
        H[i, j] = h[(j - i) % N]

M = block_matrix([
    [q * identity_matrix(N), zero_matrix(N)],
    [H, identity_matrix(N)]
])

L = M.LLL()

# Short vector in reduced basis = (f, g) private key
for row in L:
    f = vector(row[:N])
    g = vector(row[N:])
    if f.norm() < q and g.norm() < q:
        return f, g

return None

---

1. Express the cryptographic problem as:
   "Find small x such that f(x) ≡ 0 (mod N)"
   or "Find x close to target t in some lattice L"

2. Choose lattice type:
   ├─ Polynomial lattice → Coppersmith-style
   ├─ Modular lattice → HNP-style CVP
   └─ Knapsack lattice → subset sum / CJLOSS

3. Determine dimensions:
   └─ More dimensions = better approximation but slower

4. Set scaling factors:
   └─ Balance the rows so short vector has roughly equal entries
   └─ Common: multiply by N/X where X is the root bound

5. Apply reduction:
   ├─ LLL first (fast, usually sufficient)
   └─ BKZ if LLL fails (increase block size: 20, 30, 40)

6. Extract solution:
   └─ Check reduced basis rows for valid solutions

undefined

# Augment matrix
M = matrix(ZZ, n + 1, m + 1)
for i in range(n):
    for j in range(m):
        M[i, j] = basis_matrix[i, j]
    M[i, m] = 0

for j in range(m):
    M[n, j] = target[j]
M[n, m] = scale  # scaling factor (try 1, then adjust)

L = M.LLL()

# Look for row with last entry = ±scale
for row in L:
    if abs(row[m]) == scale:
        return vector(target) - vector(row[:m]) * (row[m] // abs(row[m]))

return None

undefined

Lattice approach needed — which construction?
│
├─ RSA-related?
│  ├─ Small unknown part of message → Coppersmith univariate
│  │  └─ Check: unknown_bits < n_bits / e
│  ├─ Partial factor knowledge → Coppersmith mod p
│  │  └─ Use beta=0.5, X=2^unknown_bits
│  ├─ Small private exponent d → Boneh-Durfee
│  │  └─ Check: d < N^0.292
│  └─ Multiple related equations → multivariate Coppersmith
│
├─ DSA/ECDSA-related?
│  ├─ Reused nonce → direct algebraic recovery (no lattice needed)
│  ├─ Partial nonce leakage → HNP → CVP lattice
│  │  └─ Need enough signatures: n ≥ q_bits / leaked_bits
│  └─ Nonce bias → statistical HNP → larger lattice
│
├─ Knapsack / subset sum?
│  ├─ Low density (d < 0.9408) → CJLOSS lattice attack
│  ├─ High density → lattice attack unlikely to work
│  └─ Super-increasing → greedy algorithm (no lattice needed)
│
├─ LCG / PRNG?
│  ├─ Full outputs known → algebraic recovery (no lattice)
│  ├─ Truncated outputs → CVP on recurrence lattice
│  └─ Unknown modulus → use GCD of output differences
│
├─ NTRU?
│  └─ Build circulant lattice → LLL/BKZ for short key vector
│
└─ Custom problem?
   ├─ Express as "find small root of polynomial mod N" → Coppersmith
   ├─ Express as "find lattice point close to target" → CVP
   ├─ Express as "find short vector in lattice" → SVP / LLL
   └─ If none fit → probably not a lattice problem