zee-cpu/ECDSA-Bazooka

# ECDSA Nonce-Bias 恢复工具 [](https://github.com/zee-cpu/ECDSA-Bazooka/actions/workflows/ci.yml) 给定一组来自同一私钥的真实 ECDSA 签名，且其 nonce (`k`) 存在某种统计偏差（MSB、LSB 或弱/软偏差），该工具可检测出 偏差并恢复私钥。核心方法：通过对签名对应用 主元消去法技巧，在代数上消除私钥 `d`，将其转化为仅剩一个小未知数的 Hidden Number Problem，并使用格规约（LLL/BKZ）结合 Kannan CVP-to-SVP 嵌入进行求解。 ## 快速开始 ``` mkdir -p build && cd build && cmake .. -DCMAKE_BUILD_TYPE=Release && make -j$(nproc) cd .. ./build/unit_tests # <1s, run after every change python3 scripts/generate_mock_signatures.py --count 500 --bias msb --bias-bits 12 \ --output /tmp/test.txt --seed 1 # prints the ground-truth key to stdout ./build/ecdsa_nonce_recovery -i /tmp/test.txt -q ``` 完整的 CLI/flag 参考及前置依赖包 列表，请参见 `COMMANDS.md`。 ## 当前能力 恢复情况取决于泄露深度 L（存在偏差的高位或低位数量），适用于 MSB 和 LSB 偏差： - **L >= 5 位：可稳健恢复并验证。** 强偏差（L >= 7） 在几秒钟内即可通过普通的 LLL 解决；L = 5-6 则需要使用针对性的 BKZ 计算（耗时几十秒 到几分钟不等）。 - **L = 4 位：尽力而为。** 可以恢复，但这恰好处于 block-30 BKZ 规约在 256 位下可解决的边缘，因此需要几分钟 以及两次独立的维度尝试。目前测试种子均能成功恢复；但并不能保证 适用于所有密钥。 - **L <= 3 位：实际中无法实现。** L = 3 在维度 >= 450 时需要 block_size >= 40 （每次尝试 > 15 分钟，且不保证收敛）；L = 2 在可行的成本下无法收敛；L = 1 则完全不在考虑范围内（ 该情况下真正的 Fourier / Bleichenbacher 攻击需要数百万个同密钥 签名——参见 De Mulder et al. CHES 2013, Osaki & Kunihiro SAC 2024, Aranha et al. CCS 2020——这是钱包的链上历史记录无法提供的）。 - **Modulo/Extended-HNP 偏差**：尚未实现（`detect_modulo_bias` 为 占位桩代码）。 对于弱偏差情况，请设置一个宽裕的 `--max-time`（例如 `-t 400`）：L = 4-6 BKZ 过程受到时间预算限制，如果剩余时间不足，它将被跳过。 ## 并发 格规约**在设计上为串行执行**。独立的试验看似 可以并行化，但 fplll 并不是线程安全的，无法进行并发规约（其 LLL 包装器会改变进程全局的 MPFR 精度，并且 BKZ 会在内部调用 LLL）， 因此同时运行两个任务会导致竞争和崩溃。我们曾构建过线程化版本，但也因为此原因 被撤销。实现并行化的唯一安全方式是进程 （`fork`）隔离，即每个 worker 对应一个 fplll 实例——而不是线程。 如果设置了 `ECDSA_FPLLL_STRATEGY` 环境变量，fplll 将通过该变量定位其 BKZ 剪枝策略 文件，否则将使用标准的安装前缀路径。即使 没有它，恢复工作依然可以进行（退回到较慢的未剪枝枚举），因此它只是 一种优化手段，而不是硬性依赖。 ## 测试 ``` ./build/unit_tests # fast (<1s): math, transforms, validation, ECC edge cases ctest -R ecc_differential # local ECC vs the trusted `ecdsa` library (edge + random) ctest -R e2e_recovery # slow (~5min): real recovery against real ground truth ``` CI (`.github/workflows/ci.yml`) 会在每次 push/PR 时运行：包含警告门控的 Release 构建、单元 + 差异测试、ASan/UBSan 检查，以及一个受时间限制的 端到端恢复冒烟测试。可以通过 `cmake --preset asan` 在本地进行 Sanitizer 构建。 ## 文件位置 - `src/lattice_solver.cpp` -- 核心恢复引擎（主元消去法 + Kannan 嵌入）。在修改之前，请阅读 `build_boneh_venkatesan_basis` 上方的注释。 - `src/bias_profiler.cpp` -- 偏差检测；`shrink_test_sweep` 是 MSB 和 LSB 检测共用的核心。 - `src/recovery_engine.cpp` -- 调度（LATTICE 与 FALLBACK）、 候选验证、重试逻辑。 - `src/verifier.cpp` -- 真正独立的 ECDSA 验证。 - `src/secp256k1.cpp` -- EC 原语。 - `tests/unit_tests.cpp` / `tests/e2e_recovery_test.sh` -- 上述两个 测试套件。 ## 更多背景信息 - `COMMANDS.md` -- 完整的 CLI 参考和构建前置条件。 ## 许可证 在 MIT 许可证下发布。参见 [`LICENSE`](LICENSE)。

标签：Bash脚本, ECDSA, LLL算法, 密码学, 密钥恢复, 手动系统调用, 数论, 格密码分析, 逆向工具