签名算法与nonce复用

本文适合

已经理解哈希、随机数和 ECC/RSA 基础，准备处理 DSA/ECDSA/Schnorr 签名伪造或私钥恢复题的学习者。学完你能：从签名列表中识别 nonce 重复、偏差、部分泄露或挑战绑定错误，并写出恢复 k、私钥或伪造签名的最小脚本。

一句话判断

DSA/ECDSA/Schnorr 这类签名一旦 nonce k 重复、可预测、偏小或部分泄露，签名公式会变成可解方程，私钥可能直接暴露。

题目中常见信号

多个签名 (r,s) 中 r 重复

说明：ECDSA/DSA nonce 复用

k 来自 random、时间或短 seed

说明：nonce 可预测

泄露 nonce 高位/低位

说明：HNP/格攻击

Schnorr 使用相同 commitment R

说明：nonce 复用

签名 hash 未绑定消息/公钥/上下文

说明：可重放或替换

验签接口接受用户给的公钥参数

说明：可能伪造或小子群攻击

核心概念

ECDSA 签名满足 s = k^-1(z + r*d) mod n。如果同一个 k 签了两条不同消息，两个方程相减即可求出 k，再求私钥 d。如果只泄露 nonce 的一部分，也能把问题转成 Hidden Number Problem，用格攻击恢复。

签名安全不只看算法名，还要看 nonce 生成、消息哈希、上下文绑定、参数校验和验签逻辑。

最小分析流程

1. 收集签名字段：消息、hash z、r、s、曲线阶 n 或 DSA 参数。
2. 查重复：按 r 或 commitment R 分组。
3. 检查 nonce 来源：源码里是否使用普通随机数、时间或可控 seed。
4. 对重复 nonce 直接恢复 k 和私钥。
5. 对部分泄露 nonce 转向 格密码与LLL入门 / 格攻击案例专题。
6. 用恢复出的私钥签目标消息，或验证伪造签名通过。

最小验证示例

from Crypto.Util.number import inverse

n = 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551
r = 123456789
s1 = 111111111
s2 = 222222222
z1 = 333333333
z2 = 444444444

k = ((z1 - z2) * inverse(s1 - s2, n)) % n
d = ((s1 * k - z1) * inverse(r, n)) % n
print("k =", k)
print("private d =", d)

真实题要先确认两条签名 r 相同且消息 hash 不同。恢复 d 后，用公钥 Q = dG 或重新签名验证。

常见利用 / 解题路线

路线总览：

• ECDSA/DSA 重复 nonce：重复 r，两式相减恢复 k,d。
• Schnorr 重复 nonce：同一 R 下两条挑战响应恢复 secret。
• 弱随机 nonce：枚举时间 seed 或小范围 k。
• 部分 nonce 泄露：构造 HNP 格，用 LLL/BKZ 求私钥。
• 签名绑定错误：签名没有覆盖消息、域名、用户或公钥，导致替换/重放。

常见失败原因

算出的私钥不对

排查动作：检查 z 是否需要截断到曲线阶 bit 长度

inverse 不存在

排查动作：s1 == s2 或模数不是正确的群阶

重复字段不是 r

排查动作：Schnorr 看 commitment，RSA 签名看 padding 和 hash

格攻击无结果

排查动作：nonce 泄露位数不够、样本太少或不等式界限写错

伪造签名不过

排查动作：检查 DER 编码、低 s 规范化、hash 算法和消息字节完全一致

迷你案例

题目给 20 条 ECDSA 签名，其中两条 r 完全相同。把两条消息分别做 SHA256 得到 z1,z2，代入公式恢复 k 和私钥 d。再用 d 对 admin=true 签名，提交后服务端验签通过返回 flag。

WP 要写出重复 r 的证据、恢复公式、验签通过结果，而不是只贴最终私钥。