lattice-crypto-attacks

A lattice-based cryptanalysis playbook aimed at CTF challenges and cryptanalysis research, gathering the techniques where an attack succeeds by finding a short or close vector in a well-constructed lattice. A quick application guide maps problem types to methods: RSA small roots to Coppersmith, RSA small private exponent to Boneh-Durfee, DSA/ECDSA nonce bias to the Hidden Number Problem via CVP, knapsack ciphers to low-density attacks, truncated LCG output and subset-sum to LLL and CVP, and NTRU key recovery to lattice reduction. Fundamentals are covered first: a lattice as all integer combinations of basis vectors, the Shortest and Closest Vector Problems (SVP and CVP), and quality metrics including the determinant and the Gaussian heuristic for estimating the shortest vector. The LLL algorithm produces a reduced, nearly orthogonal basis with an approximately short first vector in polynomial time, and BKZ trades exponential time in its block size for higher-quality reduction; a rule of thumb starts with LLL and moves to BKZ with block size 20 to 40 for CTF work. Usage is shown in both SageMath (M.LLL() and M.BKZ(block_size)) and Python's fpylll. Coppersmith's method is developed for the univariate case using SageMath's small_roots, with its X, beta, and epsilon parameters and the X less than N^(1/d) bound, a stereotyped-message RSA attack, partial key exposure recovering a factor p from known MSBs with beta=0.5, and multivariate Coppersmith and Howgrave-Graham underpinning Boneh-Durfee for small d. The Hidden Number Problem section recovers DSA/ECDSA private keys from biased nonces by reducing to CVP, with an example lattice construction, a table of practical bias sources and how many signatures each needs, and the reused-nonce special case. Knapsack and subset-sum coverage introduces the low-density attack with its density below 0.9408 threshold. Emphasis throughout is on constructing the correct attack lattice, with the right dimensions and scaling factors, where general approaches often go wrong.