All programs in this directory reproduce the walkthrough
traces, floating-point vs. exact-integer divergence cases,
Coppersmith RSA (\(e=3\))
small-root recovery, subset-sum knapsack attacks, and
empirical LLL scaling plots in
../lattice-reduction.md.
Files
lll.c: C11 implementation comparing corrected incrementaldoubleGSO LLL against exact__int128integer LLL (Cohen Algorithm 2.6.7 / de Weger). Prints the 2D Gauss/Lagrange trace, 3D LLL trace, 3D high-normdoubleprecision-loss counterexample, and a deterministic 640-basis dimension/\(\delta\) sweep (results/lll_sweep.csv).coppersmith_knapsack.py: Pure-Python arbitrary-precision exact integer LLL verifying the 3D trace, Lagarias–Odlyzko (1985) vs. CJLOSS (1992) subset-sum attacks, univariate Coppersmith RSA (\(e=3\)) partial-message recovery on a 511-bit modulus,doublevs. exact divergence at \(N^2 \sim 2^{128}\), Goldstein–Mayer HNF root Hermite factors (results/gm_rhf.csv), and GSA + Core-SVP BKZ block-size estimates for ML-KEM.plot_lattice.py: Generates../lll-bench-metrics.svgfromresults/lll_sweep.csvandresults/gm_rhf.csv.run.sh: End-to-end build, sanitizer verification (-fsanitize=address,undefined), execution, and figure generation.
Environment & Dependencies
- Tested on Linux x86_64 (AMD EPYC 9754, 2 vCPU, Linux
6.8.0-90), GCC 13.3.0, Python 3.12.3,
sympy,matplotlib 3.11.2. - No timing measurements are relied upon; all experiments track deterministic, clock-independent metrics (swaps, size reductions, orthogonality defect, root Hermite factor, Howgrave–Graham norm margin, and exact root recovery).
Build and Run
BUILD_DIR=$(mktemp -d) bash run.shOr run components individually:
B=$(mktemp -d)
gcc -O2 -Wall -Wextra -std=c11 -o "$B/lll" lll.c -lm
gcc -O1 -g -fsanitize=address,undefined -fno-sanitize-recover=all -Wall -Wextra -std=c11 -o "$B/lll_san" lll.c -lm
"$B/lll_san" "$B/san.csv" > /dev/null
"$B/lll" results/lll_sweep.csv > results/lll_c.txt
python3 -u coppersmith_knapsack.py > results/python_attacks.txt
python3 plot_lattice.py
rm -rf "$B"源码下载
本文相关源码已整理,共 4 个文件。