椭圆曲线签名的安全性分析：从 ECDLP 到 HNP、EC-HNP 与 EHNP

Scope. 本文从 ECDSA 方程构造 bounded-nonce-error 的 HNP/CVP instance，再说明 EC-HNP、EHNP 与真实 signer leakage 的适用边界。

ECDLP security assumption 是曲线层基线。wallet and signing implementations 若泄漏 nonce 的偏置、部分位或 side-channel trace，攻击目标会转化为多条共享私钥的近似模线性关系。^{1 2 3 4}

Threat Model：曲线层与 Signer 泄漏

ECDLP security assumption 给出的基线

把基线写清很重要。对阶为 \(n\) 的群，给定生成元 \(G\) 与公钥

\[ P = dG, \]

如果敌手只能把公钥当作黑盒群元素来观察，那么它需要恢复私钥 \(d\)。这就是 ECDLP 的基本形状。曲线参数选择、群阶、实现是否避免小子群或 invalid-curve 问题，这些都属于 curve-level security。

ECDSA 敌手还可能收集签名 \((r_i,s_i)\)、消息哈希 \(z_i\)、时间、功耗、窗口访存或故障执行结果。此时需要判断这些观测能否约束 nonce，并进一步恢复 \(d\)。

实现泄漏与协议误用如何改变问题类型

这里至少要分三层：

• 曲线层：ECDLP、群阶、cofactor、点验证、invalid-curve / twist 安全
• 实现层：nonce 生成、partial nonce leakage、wNAF trace、cache timing、power trace、fault injection
• 协议层：签名接口复用、跨域消息处理、错误的 deterministic nonce 上下文、重复签名状态

格攻击恢复 ECDSA 私钥通常利用实现泄漏或协议误用，并不直接否定曲线层 ECDLP 假设。

从 ECDSA signing equation 到 hidden-number style relation

最小 ECDSA signing equation

设私钥为 \(d\)，公钥为 \(P=dG\)。对消息哈希 \(z\)，签名者取 nonce \(k\)，计算

\[ R = kG, \qquad r = x(R) \bmod n, \]

再定义

\[ s = k^{-1}(z + rd) \bmod n. \]

把这个式子乘回去，可得

\[ sk \equiv z + rd \pmod n. \]

或者写成

\[ rd - sk + z \equiv 0 \pmod n. \]

这一步已经暴露了 ECDSA 的脆弱面：nonce \(k\) 和私钥 \(d\) 在同一个模方程里线性耦合。

把 nonce 泄漏改写成线性约束

如果攻击者完全知道某次签名的 \(k\)，那么

\[ d \equiv (sk - z) r^{-1} \pmod n, \]

私钥会被立即恢复。对 nonce bias and partial nonce leakage，把 nonce 写成

\[ k_i = \hat{k}_i + \delta_i, \]

其中 \(\hat{k}_i\) 是攻击者已知或可猜测的部分，\(\delta_i\) 是较小的未知误差项。代回签名方程得

\[ s_i(\hat{k}_i + \delta_i) \equiv z_i + r_i d \pmod n, \]

整理为

\[ r_i d - s_i \delta_i \equiv s_i \hat{k}_i - z_i \pmod n. \]

一旦 \(\delta_i\) 的范围足够小，或者样本足够多，这组关系就会变成典型的 hidden-number style linear constraints。攻击者可以利用部分已知的 nonce 结构，把私钥恢复转化为格约化或最近向量类问题。

这个转化解释了为什么 ECDSA 对 nonce 异常敏感：签名等式本身就把 secret key 和 ephemeral nonce 放进了同一条可线性化的约束里。

从 bounded error 到一个 CVP 格基

为了看清“可线性化”怎样变成格问题，先把每条 ECDSA 方程乘以 \(s_i^{-1}\)：

\[ a_i = r_i s_i^{-1} \bmod n, \qquad b_i = z_i s_i^{-1} \bmod n. \]

若泄漏模型给出

\[ k_i = \hat{k}_i + \varepsilon_i, \qquad |\varepsilon_i| < B, \]

再令 \(c_i=b_i-\hat{k}_i\)，就存在整数 \(q_i\) 使

\[ a_i d+c_i-q_i n=\varepsilon_i. \]

这里应把 \(c_i\) 和误差都理解为居中的整数代表元；若跨越模 \(n\) 的边界，\(q_i\) 会吸收对应的整倍数。取缩放因子

\[ W=\left\lceil \frac{n}{B}\right\rceil, \]

考虑下面这个行格基：

\[ L= \begin{pmatrix} Wn & 0 & \cdots & 0 & 0\\ 0 & Wn & \cdots & 0 & 0\\ \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & \cdots & Wn & 0\\ Wa_1 & Wa_2 & \cdots & Wa_m & 1 \end{pmatrix}. \]

整数系数 \((-q_1,\ldots,-q_m,d)\) 生成格向量

\[ v=\bigl(W(a_1d-q_1n),\ldots,W(a_md-q_mn),d\bigr). \]

对目标向量

\[ t=(-Wc_1,\ldots,-Wc_m,0), \]

二者之差恰为

\[ v-t=(W\varepsilon_1,\ldots,W\varepsilon_m,d). \]

由于 \(WB\) 与 \(n\) 同量级，前 \(m\) 个坐标被压进一个受控范围；求 \(t\) 附近的格向量时，最后一个坐标会直接给出私钥候选 \(d\)。这只是便于展示结构的 CVP 嵌入。实际成功率还取决于样本数、泄漏位数、误差分布、居中取值是否处理正确，以及所用约化和枚举算法。已知低位时通常还要先做模缩放；各样本误差界不同或带分类噪声时，EHNP 会使用逐坐标权重、不等式约束或额外嵌入，不能照搬同一个格基。

一个小整数例子可以核对坐标。取 \(n=101\)、\(d=37\)、\(B=4\)，令

\[ (a_1,a_2,a_3)=(7,19,43),\quad (c_1,c_2,c_3)=(46,1,26),\quad (q_1,q_2,q_3)=(3,7,16). \]

逐项计算 \(a_i d+c_i-q_i n\)，得到 \((2,-3,1)\)，确实满足误差界。此时 \(W=26\)，由上述格基产生的 \(v\) 与目标 \(t\) 之差为

\[ v-t=(52,-78,26,37) =26(2,-3,1)\mathbin{\|}37. \]

前三个坐标记录缩放后的 nonce 误差，最后一个坐标保留私钥候选。真实攻击会用远大于 101 的群阶和更多签名样本；这个例子只验证嵌入的代数接线。

HNP、EC-HNP 与 EHNP 的区别

HNP：带近似信息的 hidden number

HNP 的抽象轮廓是：有一个隐藏标量 \(\alpha\)，攻击者观察到若干形如

\[ t_i \alpha + b_i \approx a_i \]

的约束，其中“近似”来自高位、低位、区间或某种可控误差。HNP 本身不要求这些量来自椭圆曲线签名；它只是说，若同一个 hidden number 在多条近似线性关系里反复出现，就可能被恢复。

EC-HNP：把约束放回椭圆曲线签名接口

EC-HNP 把 HNP 的抽象关系落回 ECDSA 或相关 elliptic-curve 签名接口。此时 hidden number 是和签名方程直接耦合的私钥或 nonce 相关量。攻击者观测到：

• 签名样本 \((r_i, s_i)\)
• 消息哈希 \(z_i\)
• 某种关于 nonce 的偏置信息或部分位信息

于是 HNP 的近似线性关系由 ECDSA signing equation 系统地产生；EC-HNP 这个名称强调的正是其椭圆曲线签名来源。

EHNP：泄漏模型变丰富时会发生什么

EHNP 常用来表示 extended hidden number problem 视角，允许泄漏模型包含比“某些高位或低位已知”更复杂的不规则信息，例如：

• windowed multiplication 泄漏出的局部窗口信息
• wNAF trace 暗示的 signed-digit 模式
• 带噪声的 side-channel 分类结果
• 非连续 bit positions 的偏置信息

HNP、EC-HNP 与 EHNP 不能压成一个宽泛的“lattice attack”标签。攻击者能看到什么、误差边界有多小、样本需求有多少，以及恢复步骤如何建模，都会随泄漏模型变化。

把攻击前提映射到真实的 Web3 签名环境

nonce bias 与弱随机数

最经典的一类问题是 nonce 分布不均匀。假设 signer 的随机数生成器有偏置，或者某些高位在统计上更容易落到固定模式，那么攻击者就可能从链上或日志里收集大批签名样本，进而构造 HNP 类约束。Biased Nonce Sense 之所以有杀伤力，正因为这类攻击不要求侧信道探针，只要求大规模可观测签名样本。³

这类风险更像运维和实现事故：

• 弱 RNG
• 随机源复用
• 虚拟化环境里熵不足
• 多租户 signer 共享状态

partial nonce leakage 与 side-channel trace

另一类攻击更贴近硬件钱包、HSM 和远程 signer。此时攻击者未必能完整读出 nonce，但可以从 cache timing、power analysis、EM trace 或分支行为中得到部分信息。只要这些信息足以把 \(k_i\) 压成“已知部分 + 小误差项”的形式，就会自然进入 EC-HNP 或 EHNP。

典型泄漏接口包括：

• 标量乘中的窗口访存模式
• 非 constant-time 条件分支
• wNAF trace 暴露的 signed-digit 模式
• 异常处理路径泄漏出的重试或归约信息

Return of the Hidden Number Problem 把这些底层 side-channel observations 与高层私钥恢复直接连了起来。²

fault injection、重放与接口误用

fault injection 不一定总会落到 HNP 类问题，但它经常会扩大泄漏面。例如：

• 让某些乘法或模约减步骤跳过
• 让 deterministic nonce 的输入上下文不完整
• 诱导 signer 重复使用部分内部状态

这些情况有些属于协议误用，有些属于实现缺陷，修复路径也不同。修曲线参数解决不了 deterministic nonce 上下文拼接错误；增加测试样本也无法修复一个会在故障下注入重复状态的签名服务。

在 Web3 语境里，可以把这些环境粗分为三类：

• 本地钱包：风险集中在设备侧信道、浏览器扩展接口和签名请求隔离
• 硬件钱包 / HSM：风险集中在物理侧信道、fault model 和标量乘实现
• 后端 signer / 托管服务：风险集中在随机数、并发、状态复用、日志和 API 域分离

曲线层安全、实现泄漏与协议误用要分开看

把这三层放在一张表里，会比口号更清楚。

层级	核心问题	典型失败模式	解决路径
曲线层	ECDLP 是否足够强、点验证是否完备	小子群、invalid-curve、参数选择错误	选对曲线与群参数，做输入点验证
实现层	nonce 和标量乘是否泄漏	nonce bias、partial nonce leakage、cache/power/EM leakage、wNAF trace	constant-time、signer isolation、侧信道加固
协议层	接口是否在正确上下文中使用	域分离错误、deterministic nonce 上下文缺失、重放与状态复用	API 边界、域分离、状态管理与审计

很多争论卡住，是因为一方把所有问题归为“曲线不安全”，另一方又只责怪实现。曲线层安全定义代数基线，实现泄漏与协议误用共同构成实际攻击面。

工程实现对接

RFC6979 与 deterministic nonce

RFC6979 的价值，在于把 ECDSA nonce 生成从“依赖外部随机源每次都不出错”收紧到一个 deterministic procedure。它显著降低了弱随机数和重复 nonce 的风险，但不意味着攻击面彻底消失。

RFC6979 解决的是：

• 低质量随机数导致的 nonce bias
• 签名服务偶发重复 nonce
• 由熵源质量波动带来的灾难性故障

它不直接解决的是：

• side-channel 泄漏出的 partial nonce 信息
• fault injection 打断正常执行
• 跨协议或跨上下文错误复用签名输入

constant-time、wNAF 与 signer isolation

如果实现仍在标量乘、窗口选择、条件分支和异常路径上泄漏行为模式，那么 deterministic nonce 依然可能被 EHNP 类模型利用。工程上更实在的要求是：

• 标量乘和模运算保持 constant-time
• 尽量避免将 wNAF、窗口表访问和异常分支暴露成可测 side-channel
• 将 signer 放在最小可见接口后面，减少外部对签名过程的观测面
• 对硬件设备单独建立 power / EM / fault model，避免套用软件系统假设

审计时该检查什么

如果把这篇压成一份 audit checklist，我会优先看下面几项：

• nonce 生成是否严格符合 RFC6979 或对应规范
• 是否存在重复状态、并发复用或错误缓存导致的 nonce correlation
• 标量乘实现是否 constant-time，窗口访存是否可被外部观测
• 是否存在可形成 partial nonce leakage 的日志、debug、telemetry 或错误处理路径
• wallet and signing implementations 是否把消息域、链 ID、账户上下文与 deterministic nonce 输入正确绑定
• 是否有硬件钱包、HSM、远程 signer 各自独立的 threat model 与 side-channel 假设

审计重点应落在系统是否持续制造“同一个 secret scalar 出现在许多条近似线性关系里”的条件，而非论文里某一组格参数的复杂程度。

总结

ECDLP 仍然是椭圆曲线签名安全性的基线。对 ECDSA 而言，一旦 nonce 偏置、部分泄漏或 side-channel 进入系统，攻击问题会从离散对数转化为 hidden-number style relation。

判断框架可以压成两个问题：曲线层是否给出足够强的代数基线；signer 实现是否持续泄漏了绕开该基线的信息。前者约束理论求解难度，后者决定现实攻击面。

下一篇进入 pairing-friendly curves 时，这个框架仍然有效。曲线类型会改变协议接口，但不会取消一个事实：实际安全性永远是 algebraic assumption、implementation boundary 和 protocol discipline 的交集。