通过 LLL 格约简从偏置 nonce 的多签名中恢复 ECDSA 私钥：实用阈值与实现

ECDSA（椭圆曲线数字签名算法）广泛用于区块链、SSH 等场景，其安全性高度依赖签名过程中的临时随机数 nonce（k 值）。若 nonce 存在偏置（如高位比特全为 0、低熵或截断），攻击者可利用多个公开签名，通过 LLL（Lenstra-Lenstra-Lovász）格约简算法求解隐数问题（Hidden Number Problem, HNP），高效恢复私钥。这种攻击不需侧信道，仅需公网签名数据，已在 PuTTY P-521 等实现中实战验证。

攻击原理：从偏置 nonce 到 HNP

ECDSA 签名过程：对消息 m，选随机 k ∈ [1, q-1]（q 为曲线阶），计算 R = kG（G 为基点），r = R_x mod q，s = k^{-1} (hash (m) + d r) mod q（d 为私钥）。重排得：(hash (m) + d r) /s ≡ k mod q，即 t d + b ≡ k mod q（t = r/s, b = hash (m)/s）。

若多个签名共享同一私钥 d，且 k 偏置（如 PuTTY P-521 的 k <2^{512}，高 9 比特为 0），则每个签名提供一个近似方程。HNP 问题：给定多个 (t_i, b_i, k_i ≈0 高位)，求 d。LLL 通过构造格基，将短向量问题转化为 CVP（最近向量问题），约简后提取 d。

典型格矩阵（n 签名，假设 k 高 l 比特已知为 0）：

[ q  0   ...  0  ]
[ 0  q   ...  0  ]
[ ...             ]
[ t1 t2 ... tn  2^{l}/q ]
[ b1 b2 ... bn  0     ]

LLL 约简（δ=0.75）后，最短向量接近 (d, ..., 0)，Baby-step giant-step 或枚举恢复 d。SageMath 或 fpylll 库实现高效。

实用阈值与实例

阈值取决于偏置比特数（l）和曲线安全级别：

9 比特偏置（PuTTY P-521）：58 签名成功率 >50%，60 签名 100%。arXiv:2509.09331 验证，67s 内破密钥（USVPPredSieve 算法）。
80 比特固定前缀：5 签名（YubiKey 案例）。
128 比特：2 签名。
4 比特偏差：~4000 签名（NIST P-256）。
Upbit 黑客事件：数百万 Solana 签名中微妙偏置，韩专家指高阶数学攻击，仅需少量相关 nonce。

格维度 m ≈ n+2，运行时 O (m^3 log B)，B 为比特长。P-256 (n=20)：秒级；P-521 (n=60)：分钟级。监控：签名 r 值分布偏倚（χ² 检验），nonce 熵 < 预期。

可落地参数与清单

实现参数：

收集 ≥阈值签名（同公钥）。
验证偏置：Z 测试单比特，Rayleigh 多比特（α=2^{-32}）。
矩阵构造：t_i = r_i * s_i^{-1} mod q, b_i = hash (m_i) * s_i^{-1} mod q。
LLL：δ=0.99（BKZ 备选），目标向量 (0,...,0,1)。
后处理：枚举短向量 ±d，验证签名。

工程清单：

生成偏置签名：截断 RNG（如 SHA-512 未 mod q），PuTTY k_proto 复现。
防御阈值：

偏置比特签名数阈值防护

128 2 RFC 6979

80 5 全熵 RNG

9 (P521) 58 弃 P-521

4 4000 侧信道防护
监控：签名服务日志 r/s 统计，熵警报 >10% 偏置；轮换密钥 <1000 签。
回滚：检测偏置后，冻结密钥，通知用户；阈值：>50 签无偏置 99% 置信。

偏置比特	签名数阈值	防护
128	2	RFC 6979
80	5	全熵 RNG
9 (P521)	58	弃 P-521
4	4000	侧信道防护

攻击风险：区块链 / SSH 公钥易采集，偏置 RNG（如弱 PRNG）常见。防护首选 EdDSA（内置确定 nonce），或 RFC 6979 + 恒时实现。

资料来源：Hacker News 前页讨论、avidthinker.github.io ECDSA 详解、arXiv:2509.09331（PuTTY 58 签攻击）、CNBlogs/ECDSA 格实战代码、Upbit 事件分析。（约 950 字）