题型判断#

如果一道题同时给出：

1. 同一条曲线上的公钥
2. 两条不同消息
3. 两条不同签名
4. 但两个签名的 r 完全一样

那第一反应基本就应该是：

1
ECDSA 重复 nonce

因为在 ECDSA 里，r 本质上是由临时随机数 k 推出来的。 同一个私钥下，如果两次签名用了同一个 k，最明显的特征就是 r 一样。

为什么重复 nonce 会直接出事#

ECDSA 的核心式子是：

1
s = k^{-1}(z + r*d) mod n

这里：

1. d 是私钥
2. k 是临时随机数
3. z 是消息哈希
4. n 是曲线阶

如果两条不同消息共用了同一个 k，那就会出现：

1
s1 = k^{-1}(z1 + r*d) mod n
2
s2 = k^{-1}(z2 + r*d) mod n

两式相减之后，d 会被消掉，直接变成一个关于 k 的一次式。

最核心的恢复公式#

先恢复随机数：

1
k = (z1 - z2) * (s1 - s2)^{-1} mod n

再恢复私钥：

1
d = (s1*k - z1) * r^{-1} mod n

这就是这类题最常见的两步走。

我做这类题的顺序#

1
先看 r 是否重复
2
-> 如果重复，直接怀疑 nonce 复用
3
-> 用两组 (z, s) 算出 k
4
-> 再把私钥 d 代出来
5
-> 最后给目标消息重新签名

这种题一般不需要去碰离散对数，也不需要碰更复杂的椭圆曲线攻击，关键只是签名者把临时随机数用坏了。

目标消息为什么也能签#

一旦私钥恢复出来，后面的事情就和“正常签名”没有区别了。

对目标消息：

1. 先做同样的哈希
2. 得到 z_target
3. 再用恢复出来的 d 和 k 计算新的 s_target

最后提交：

1
(r, s_target)

就能得到目标消息对应的合法签名。

常见坑点#

复现骨架#

下面这类骨架就足够把题做出来：

1
from hashlib import sha256
2

3
n = <curve_order>
4

5

6
def inv(x):
7
    return pow(x, -1, n)
8

9

10
k = ((z1 - z2) * inv(s1 - s2)) % n
11
d = ((s1 * k - z1) * inv(r)) % n
12

13
z_target = int.from_bytes(sha256(target_message).digest(), "big")
14
s_target = (inv(k) * (z_target + r * d)) % n

如果是交互题，最后把原来的 r 和新算出来的 s_target 交上去就行。

总结#

这类题的重点根本不在“怎么伪造管理员身份”，而在于签名者自己把 nonce 管理坏了。

一句话总结就是：

1
同一个 k -> 同一个 r -> k 可恢复 -> 私钥可恢复 -> 任意消息可伪造签名

所以以后看到 ECDSA 题里 r 重复，真的要立刻警觉起来，这往往已经不是“有点危险”，而是“基本可以直接拿下”了。