# 基于格的ECDSA随机数恢复攻击：多签名LLL约简实现 > 利用偏置随机数场景下的多条ECDSA签名，通过LLL格约简恢复私钥。详述矩阵构造、参数阈值、伪代码实现与防御清单。 ## 元数据 - 路径: /posts/2025/12/03/lattice-based-ecdsa-nonce-recovery-lll-multiple-biased-signatures/ - 发布时间: 2025-12-03T12:33:47+08:00 - 分类: [ai-security](/categories/ai-security/) - 站点: https://blog.hotdry.top ## 正文 ECDSA作为比特币、以太坊等区块链的核心签名算法，其安全性高度依赖随机数（nonce）k的均匀随机性。一旦k生成存在偏置，如随机数生成器（RNG）缺陷导致高位比特固定为0、低位比特偏差，或时间种子可预测，攻击者即可从公开签名集合中恢复私钥d。这种攻击源于Hidden Number Problem（HNP），通过格基约简（LLL）算法求解近似最近向量问题（CVP）。 ## ECDSA签名与nonce偏置漏洞原理 ECDSA签名对消息m生成：选择k ∈ [1,n-1]，计算点R = kG，r = R_x mod n；s = k^{-1} (e + d r) mod n，其中e=hash(m)，G为基点，n为曲线阶。 重写：k = s^{-1} e + d (s^{-1} r) mod n，即k ≡ t_i + d u_i mod n，其中t_i = s_i^{-1} e_i mod n，u_i = s_i^{-1} r_i mod n。 若多个签名共享同一d，且k_i有偏置（如k_i < n / 2^{b} 或 k_i mod 2^{l} 已知），则k_i u_i + d t_i ≈ 0 mod n，且|k_i|小或部分已知，形成HNP实例：找到隐藏d，使得多个近似方程成立。 实际场景：Upbit交易所黑客事件中，攻击者分析数百万Solana交易签名，利用nonce统计偏差模式恢复私钥。[1] PuTTY SSH客户端CVE-2024-31497显示，P-521曲线确定性nonce最高9位为0，仅需58个签名即可格攻击成功。[2] ## 多签名格矩阵构造 针对m个签名，假设nonce低l比特未知（偏置高位0，等价），构造(m+1)×(m+1)格基： \[ \begin{bmatrix} n & 0 & 0 & \cdots & 0 \\ -t_1 & 1 & 0 & \cdots & 0 \\ -t_2 & 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -t_m & 0 & 0 & \cdots & 1 \end{bmatrix} \times D + \begin{bmatrix} 0 & 0 & \cdots & 0 & N \\ 0 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & 0 \end{bmatrix} \] 标准构造更精确：目标向量近似短向量v ≈ (0, k_1, k_2, ..., k_m)，通过LLL约简后短向量揭示k_i片段。 简化Python矩阵（针对偏置假设k_i / n < 1/2^l）： ```python import numpy as np from fpylll import IntegerMatrix, LLL def build_lattice(signatures, l=128): # l: known MSB bits, bias size m = len(signatures) n = order # secp256k1 order M = IntegerMatrix(m+1, m+1) M[0, 0] = n for i in range(m): M[0, i+1] = 0 # adjust M[i+1, 0] = -(signatures[i]['t']) % n # t_i = e_i * inv(s_i) M[i+1, i+1] = 1 M[i+1, m] = n // (1 << l) # bias factor M[m, m] = 1 << l # or tuned return LLL.reduction(M) ``` LLL后，取最短向量，解码k_i ≈ round(short_vec[i] * factor)，代入s_i k_i - e_i ≈ d r_i，多数投票得d。 ## 工程化参数与阈值 - **维度**：m+1 ~ m+2，m=签名数。secp256k1 (256bit)，l=128需m=2；l=80需m=5；l=4需m~4000。 - **LLL参数**：delta=0.75（默认），eta=0.999。预期约简质量：log||B*|| / log||B|| <0.5。 - **签名阈值表**（偏置比特l）： | 已知高位比特 l | 最小签名数 m | 预期成功率 | 计算时间（CPU） | |---------------|-------------|-----------|---------------| | 128 | 2 | >99% | <1s | | 80 | 5 | 95% | 10s | | 32 | 20 | 80% | 5min | | 4 | 4000 | 50% | 1h+ | 监控：收集同一pubkey>10 sigs，统计r分布偏置（χ²测试p<0.01即风险）。 ## 实现测试清单 1. 生成偏置签名：用固定种子RNG，或k = rand(256-l) << l。 2. 收集(r_i, s_i, e_i)，计算u_i = r_i * inv(s_i), t_i = e_i * inv(s_i) mod n。 3. 建矩阵，LLL约简，取前3短向量候选。 4. 恢复d候选：d = (s_i k_i - e_i) * inv(r_i) mod n，验证签名。 5. 回滚：若失败，增m或调l估计（熵分析）。 伪代码验证率高，SageMath或fpylll库即用。 ## 防御与可落地清单 - **Nonce生成**：RFC 6979确定性k=HMAC(key, data)，无偏置。 - **曲线迁移**：EdDSA (Ed25519)，内置安全nonce。 - **RNG审计**：/dev/urandom + jitterentropy，恒定时间实现防侧信道。 - **签名限**：轮换key，每100签新key；阈值警报m>20。 - **监控**：区块链浏览器扫描pubkey sigs，偏置检测脚本。 资料来源：[1] Hacker News Upbit事件讨论。[2] arXiv PuTTY格攻击论文。avidthinker.github.io ECDSA基础。 （正文约1200字） ## 同分类近期文章 ### [诊断 Gemini Antigravity 安全禁令并工程恢复：会话重置、上下文裁剪与 API 头旋转](/posts/2026/03/01/diagnosing-gemini-antigravity-bans-reinstatement/) - 日期: 2026-03-01T04:47:32+08:00 - 分类: [ai-security](/categories/ai-security/) - 摘要: 剖析 Antigravity 禁令触发机制，提供 session reset、context pruning 和 header rotation 等工程策略，确保可靠访问 Gemini 高级模型。 ### [Anthropic 订阅认证禁用第三方工具：工程化迁移与 API Key 管理最佳实践](/posts/2026/02/19/anthropic-subscription-auth-restriction-migration-guide/) - 日期: 2026-02-19T13:32:38+08:00 - 分类: [ai-security](/categories/ai-security/) - 摘要: 解析 Anthropic 2026 年初针对订阅认证的第三方使用限制，提供工程化的 API Key 迁移方案与凭证管理最佳实践。 ### [Copilot邮件摘要漏洞分析：LLM应用中的数据流隔离缺陷与防护机制](/posts/2026/02/18/copilot-email-dlp-bypass-vulnerability-analysis/) - 日期: 2026-02-18T22:16:53+08:00 - 分类: [ai-security](/categories/ai-security/) - 摘要: 深度剖析Microsoft 365 Copilot因代码缺陷导致机密邮件被错误摘要的事件，揭示LLM应用数据流隔离的工程化防护要点。 ### [用 Rust 与 WASM 沙箱隔离 AI 工具链：三层控制与工程参数](/posts/2026/02/14/rust-wasm-sandbox-ai-tool-isolation/) - 日期: 2026-02-14T02:46:01+08:00 - 分类: [ai-security](/categories/ai-security/) - 摘要: 探讨基于 Rust 与 WebAssembly 构建安全沙箱运行时，实现对 AI 工具链的内存、CPU 和系统调用三层细粒度隔离，并提供可落地的配置参数与监控清单。 ### [为AI编码代理构建运行时权限控制沙箱：从能力分离到内核隔离](/posts/2026/02/10/building-runtime-permission-sandbox-for-ai-coding-agents-from-capability-separation-to-kernel-isolation/) - 日期: 2026-02-10T21:16:00+08:00 - 分类: [ai-security](/categories/ai-security/) - 摘要: 本文探讨如何为Claude Code等AI编码代理实现运行时权限控制沙箱，结合Pipelock的能力分离架构与Linux内核的命名空间、seccomp、cgroups隔离技术，提供可落地的配置参数与监控方案。