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: 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 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 2.3 Python (fpylll) 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 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. 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) 4.3 Partial Key Exposure (Factor p) Known MSBs of p: p = p known + x where x is small. 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 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) + xr) mod q If partial bits of k are known: reduces to CVP on a lattice. 5.2 Attack Setup 5.3 Practical Nonce Bias Sources Source Leaked Bits Required Signatures MSB bias (always 0) 1 bit ~100 signatures k generated with wrong length Variable ~50 signatures Timing side channel 1 4 bits 20 100 signatures Insecure PRNG Many Few Reused nonce (k₁ = k₂) All 2 signatures For reused nonce (simplest case): 6. KNAPSACK / SUBSET SUM ATTACKS 6.1 Low Density Attack Knapsack: given weights a₁,...,aₙ and target S, find x₁,...,xₙ ∈ {0,1} such that Σxᵢaᵢ = S. Density d = n / max(log₂ aᵢ). If d < 0.9408, lattice attack works. 7. NTRU CRYPTANALYSIS 7.1 NTRU Lattice 8. CONSTRUCTING ATTACK LATTICES — METHODOLOGY 8.1 General Recipe 8.2 Embedding Technique (CVP → SVP) Transform CVP into SVP by embedding the target into the lattice: 8.3 Dimension Selection Guide Problem Typical Dimension Notes Coppersmith univariate (degree d) d × m where m ≈ 1/ε Larger m = smaller root bound HNP with n signatures n + 2 n ≥ known bits ratio × q bits Knapsack with n weights n + 1 or n + 2 Depends on density LCG with n outputs n + 1 More outputs = easier Boneh Durfee (m+1)(m+2)/2 m = parameter depth 9. DECISION TREE 10. COMMON PITFALLS Pitfall Symptom Fix Root bound too large small roots() returns empty Reduce X, increase epsilon, verify bound satisfies Coppersmith criterion Wrong scaling LLL finds irrelevant short vector Scale columns so target vector has balanced entries Insufficient dimension Solution not in reduced basis Increase m parameter (more shift polynomials) Wrong beta Coppersmith doesn't find factor beta=0.5 for half size factor, beta=1.0 for full modulus Too few signatures (HNP) Lattice attack fails Collect more signatures with nonce bias BKZ block size too small Solution not short enough Increase block size (try 25, 30, 40) Integer overflow SageMath crashes Use ZZ ring explicitly, avoid mixing QQ and ZZ

lattice-crypto-attacks