/lattice-crypto-attacks

name: lattice-crypto-attacks
description: >-
  Lattice-based cryptanalysis playbook. Use when attacking RSA via Coppersmith
  small roots, recovering DSA/ECDSA nonces from bias, solving knapsack
  problems, or applying LLL/BKZ reduction to cryptographic constructions.

SKILL: Lattice-Based Cryptanalysis — Expert Attack Playbook

> **AI LOAD INSTRUCTION**: Expert lattice techniques for CTF and cryptanalysis. Covers LLL/BKZ reduction, Coppersmith's method (univariate and multivariate), Hidden Number Problem for DSA/ECDSA nonce recovery, knapsack attacks, and NTRU analysis. Base models often fail to construct the correct attack lattice (wrong dimensions, missing scaling factors) or misapply Coppersmith bounds.

0. RELATED ROUTING

• [rsa-attack-techniques](../rsa-attack-techniques/SKILL.md) for RSA-specific attacks that use lattice methods (Coppersmith, Boneh-Durfee)
• [symmetric-cipher-attacks](../symmetric-cipher-attacks/SKILL.md) for LCG state recovery via lattice
• [classical-cipher-analysis](../classical-cipher-analysis/SKILL.md) when lattice methods apply to classical cipher analysis

Quick application guide

| Problem Type | Lattice Technique | Key Parameter | |---|---|---| | RSA small roots | Coppersmith (LLL on polynomial lattice) | Root bound X < N^(1/e) | | RSA small d | Boneh-Durfee (multivariate Coppersmith) | d < N^0.292 | | DSA/ECDSA nonce bias | Hidden Number Problem → CVP | Bias bits known | | Knapsack cipher | Low-density lattice attack | Density < 0.9408 | | LCG truncated output | CVP on recurrence lattice | Unknown bits per output | | Subset sum | LLL reduction on knapsack lattice | Element size vs count | | NTRU key recovery | Lattice reduction on NTRU lattice | Dimension and key size |

---

1. LATTICE FUNDAMENTALS

1.1 Definitions

A **lattice** L is the set of all integer linear combinations of basis vectors:

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

where b₁, ..., bₙ are linearly independent vectors in ℝᵐ.

**Key problems**:

• **SVP** (Shortest Vector Problem): Find the shortest non-zero vector in L
• **CVP** (Closest Vector Problem): Given target t, find v ∈ L closest to t
• **SVP is NP-hard** in general, but LLL finds an approximately short vector in polynomial time

1.2 Lattice Quality Metrics

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

---

2. LLL ALGORITHM

2.1 What LLL Does

Takes a lattice basis B and produces a **reduced basis** B' where:

• Vectors are nearly orthogonal
• First vector is approximately short (within 2^((n-1)/2) factor of SVP)
• Runs in polynomial time: O(n^5 · d · log³ B) where d = dimension, B = max entry size

2.2 SageMath Usage

# SageMath
M = matrix(ZZ, [
    [1, 0, 0, large_value_1],
    [0, 1, 0, large_value_2],
    [0, 0, 1, large_value_3],
    [0, 0, 0, modulus],
])

L = M.LLL()
# Short vectors in L reveal the solution
short_vector = L[0]  # first row is typically shortest

2.3 Python (fpylll)

from fpylll import IntegerMatrix, LLL

n = 4
A = IntegerMatrix(n, n)
# Fill matrix A...
A[0] = (1, 0, 0, large_value_1)
A[1] = (0, 1, 0, large_value_2)
A[2] = (0, 0, 1, large_value_3)
A[3] = (0, 0, 0, modulus)

LLL.reduction(A)
print(A[0])  # shortest vector

---

3. BKZ (BLOCK KORKINE-ZOLOTAREV)

3.1 Comparison with LLL

| Property | LLL | BKZ-β | |---|---|---| | Quality | 2^((n-1)/2) approximation | 2^(n/(β-1)) approximation | | Speed | Polynomial | Exponential in β | | Block size | Fixed (2) | Configurable β | | Best for | Quick reduction | High-quality reduction |

3.2 Usage

# SageMath
M = matrix(ZZ, [...])
L = M.BKZ(block_size=20)  # β = 20

# fpylll
from fpylll import BKZ
BKZ.reduction(A, BKZ.Param(block_size=20))

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

---

4. COPPERSMITH'S METHOD

4.1 Univariate Case

Given f(x) ≡ 0 (mod N) with small root |x₀| < X, find x₀.

**Bound**: X < N^(1/d) where d = degree of f.

# SageMath — built-in small_roots
N = ...
R.<x> = PolynomialRing(Zmod(N))
f = x^3 + a*x^2 + b*x + c  # known polynomial
roots = f.small_roots(X=2^100, beta=1.0, epsilon=1/30)

**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)

4.2 Stereotyped Message Attack (RSA)

# SageMath
n, e, c = ...  # RSA parameters
known_msb = ...  # known upper portion of message

R.<x> = PolynomialRing(Zmod(n))
f = (known_msb + x)^e - c

# x represents the unknown lower bits
X = 2^(unknown_bit_count)
roots = f.small_roots(X=X, beta=1.0)
if roots:
    m = known_msb + int(roots[0])

4.3 Partial Key Exposure (Factor p)

Known MSBs of p: `p = p_known + x` where x is small.

# SageMath
n = ...
p_known = ...  # known upper bits of p

R.<x> = PolynomialRing(Zmod(n))
f = p_known + x
roots = f.small_roots(X=2^unknown_bits, beta=0.5)
# beta=0.5 because p ≈ √n
if roots:
    p = p_known + int(roots[0])
    q = n // p

4.4 Multivariate Coppersmith (Howgrave-Graham)

For f(x, y) ≡ 0 (mod N):

• No polynomial-time algorithm guaranteed
• Heuristic methods work in practice
• Used in Boneh-Durfee for RSA small d

# SageMath — Boneh-Durfee
# e*d ≡ 1 (mod phi) where phi = (p-1)(q-1)
# Rewrite: e*d = 1 + k*((n+1) - (p+q))
# Let x = k, y = (p+q), both small relative to n

R.<x, y> = PolynomialRing(ZZ)
A = (n + 1) // 2
f = 1 + x * (A + y)  # mod e

# Build shift polynomials and construct lattice
# Apply LLL to find small (x₀, y₀)

---

5. HIDDEN NUMBER PROBLEM (HNP) — DSA/ECDSA NONCE RECOVERY

5.1 Problem Statement

Given: signatures (rᵢ, sᵢ) where nonces kᵢ have known bias (leaked MSBs or LSBs).

DSA equation: `s = k⁻¹(H(m) + xr) mod q`

Rearranged: `k = s⁻¹(H(m) + x