# 通过 LLL 格约简从偏置 nonce 的多签名中恢复 ECDSA 私钥：实用阈值与实现 > 偏置 nonce 签名下的格基攻击恢复私钥阈值：P-521 仅需 58 个签名；给出 LLL 矩阵构造、参数调优与监控要点。 ## 元数据 - 路径: /posts/2025/12/03/ecdsa-lattice-nonce-recovery-biased-signatures/ - 发布时间: 2025-12-03T12:48:20+08:00 - 分类: [ai-security](/categories/ai-security/) - 站点: https://blog.hotdry.top ## 正文 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 熵 < 预期。 ### 可落地参数与清单 **实现参数**： 1. 收集 ≥阈值签名（同公钥）。 2. 验证偏置：Z 测试单比特，Rayleigh 多比特（α=2^{-32}）。 3. 矩阵构造：t_i = r_i * s_i^{-1} mod q, b_i = hash(m_i) * s_i^{-1} mod q。 4. LLL：δ=0.99（BKZ 备选），目标向量 (0,...,0,1)。 5. 后处理：枚举短向量 ±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% 置信。 攻击风险：区块链/SSH 公钥易采集，偏置 RNG（如弱 PRNG）常见。防护首选 EdDSA（内置确定 nonce），或 RFC 6979 + 恒时实现。 **资料来源**：Hacker News 前页讨论、avidthinker.github.io ECDSA 详解、arXiv:2509.09331（PuTTY 58 签攻击）、CNBlogs/ECDSA 格实战代码、Upbit 事件分析。（约 950 字） ## 同分类近期文章 ### [诊断 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隔离技术，提供可落地的配置参数与监控方案。