两条签名,一把私钥

admin 2026-11-16 19:30:45 网络安全文章 来源:ZONE.CI 全球网 0 阅读模式

两条签名,一把私钥

原创

利刃信安
利刃信安

利刃信安

2026年11月16日 09:30
北京

去阅读

两条签名,一把私钥

一台签名验签服务器,先后对两条消息各签了一次名。攻击者既拿不到私钥,也进不了密钥容器,手里只有两组 DER 编码的签名值和两条明文。

按常理,这什么也做不了。

但如果这两次签名用的随机数满足 某种潜在关联,私钥就会从这两组数字里被直接算出来——不需要解离散对数。

01 / 核 心

一行方程

SM2 的签名过程可以写成四行:

e = SM3(Z\_A ‖ M)

(x₁, y₁) = [k]G

r = (e + x₁) mod n

s = (1 + d)⁻¹ · (k − r·d) mod n

其中 d 是私钥,k 是每次签名都必须重新选取的随机数,n 是基点 G 的阶。

把 s 的式子两边乘 (1+d),再移项:

s(1 + d) = k − r·d

k = s + d(s + r)

记 A = (r + s) mod n,就得到万能方程:

k = s + d · A

验签端则是:

K′ = [s]G + (r + s)P

x(K′) ≡ r − e (mod n)

签名把 k 藏进 (r, s),验签把 k 还原出来再核对 x 坐标。私钥恢复攻击做的事,是用第二条方程把 k 或 d 逼出来。

关 键 认 知

一组签名,只给一条一次方程,未知量却是两个:k 和 d。所以单靠一组签名,既求不出 d,也求不出 k。所有私钥恢复题,本质都是在补一条关于 k 的独立信息。

这也是为什么“随机数复用”如此致命:它免费送第二条方程。

02 / 单 签 名

必须先泄露一个

只有一条方程时,必须再知道 k 或 d 其中一个。

C1:已知 k,反解私钥

由 k = s + dA 直接移项:

d = (k − s) · (s + r)⁻¹ mod n

这就是很多工具里“已知 k、r、s 求 d”的功能由来。

C2:已知 d,反推随机数

万能方程不需要求逆,直接算:

k = s + d · (r + s) mod n

对应“已知 d、r、s 求 k”。

如果两条都不知道,就回到椭圆曲线离散对数问题。这不是公式能绕过去的。

03 / 同 k

一次复用,等于交出私钥

两条签名使用同一个 k,消息不同,写下两条万能方程:

k = s₁ + d · A₁

k = s₂ + d · A₂

相减,k 被消掉:

0 = (s₁ − s₂) + d(A₁ − A₂)

d = (s₂ − s₁) · [(s₁ − s₂) + (r₁ − r₂)]⁻¹ mod n

这是 C3。

如果两条消息的 e 已知,还能把 r 差换成 e 差。同 k 意味着 x₁ 相同,而 r = e + x₁,所以:

r₁ − r₂ ≡ e₁ − e₂ (mod n)

d = (s₂ − s₁) · [(s₁ − s₂) + (e₁ − e₂)]⁻¹ mod n

这是 C4。

04 / 取 反

常见考点

这是最容易误判的一类。条件不是 k₂ = k₁,而是:

k₂ ≡ −k₁ (mod n)

把两条万能方程相加,k 被消掉:

s₁ + s₂ + d(A₁ + A₂) ≡ 0

d = −(s₁ + s₂) · [(s₁ + s₂) + (r₁ + r₂)]⁻¹ mod n

最 容 易 误 判 的 一 点

很多人看到 k₂ = n − k₁,第一反应是“那 r 应该一样吧”。同一消息时,r 确实相同;不同消息时,r 不同。但推导只用了 k₂ = −k₁,从头到尾没有假设 r₁ = r₂。r 是否相等,只是消息是否相同的副产品。。

05 / 线 性 结 构

k 一旦可表达,就不再随机

从“相等”推广到“成比例、仿射、任意线性组合”,解法完全一样:把 kᵢ = sᵢ + d·Aᵢ 代入约束,未知量只剩 d,解一次方程。

C6:仿射关系 k₂ = a·k₁ + b

s₂ + dA₂ = a(s₁ + dA₁) + b

d = (a·s₁ + b − s₂) · [(s₂ + r₂) − a(s₁ + r₁)]⁻¹ mod n

C7:每条签名各套一个仿射掩码

kᵢ = aᵢk + bᵢ,先由两条方程消去隐藏的 k,再解 d:

Δ = a₂A₁ − a₁A₂

d = [a₁(s₂ − b₂) − a₂(s₁ − b₁)] · Δ⁻¹ mod n

k = [A₁(s₂ − b₂) − A₂(s₁ − b₁)] · Δ⁻¹ mod n

C8:任意线性组合 Σcᵢkᵢ = c₀

d = (c₀ − Σcᵢsᵢ) · (ΣcᵢAᵢ)⁻¹ mod n

两条、三条、m 条都一样,条数只增加求和项,不改变结构。

注意:这里的“线性”指 k 与 d、e 或公开量之间存在代数线性关系。用 SM3 做密钥派生、把输出当 k,是另一回事——哈希不是线性函数。

06 / 跨 用 户 与 派 生

只要 k 能被表达

C9:跨用户同 k

两个不同私钥的用户复用了同一个 k。如果已知 d₁:

k = s₁ + d₁A₁

d₂ = (k − s₂) · A₂⁻¹ mod n

C10:k 与私钥线性相关

k = αd + β,且 α、β 已知:

s + dA = αd + β

d = (β − s) · (s + r − α)⁻¹ mod n

C11:k 由公开量线性生成

kᵢ = αuᵢ + β,u 可以是消息杂凑、计数器、时间戳。三条签名两两相减,先消 β,再消 α,最后解 d。u 公开并不可怕,可怕的是 k 与 u 之间是线性关系。

C12:k 同时依赖 d 与 e

k = αd + βe + γ:

s + dA = αd + βe + γ

d = (βe + γ − s) · (s + r − α)⁻¹ mod n

C13:点关系 K₂ = K₁ + P

因为 P = [d]G,点加法等价于标量加法:

k₂ = k₁ + d

s₂ + dA₂ = s₁ + dA₁ + d

d = (s₁ − s₂) · [(s₂ + r₂) − (s₁ + r₁) − 1]⁻¹ mod n

看起来是新的类型,翻译成标量后仍然是 C6 的一个特例:a = 1,b = d。

08 / 速 查 表

15 个用例,一张表

Aᵢ = rᵢ + sᵢ mod n,所有逆元都在模 n 下取。

单 签 名

C1  已知 k

d = (k − s)(s + r)⁻¹

C2  已知 d

k = s + d(r + s)

同 k

C3  同 k,同私钥

d = (s₂ − s₁)[(s₁ − s₂) + (r₁ − r₂)]⁻¹

C4  同 k,知 e

d = (s₂ − s₁)[(s₁ − s₂) + (e₁ − e₂)]⁻¹

C5  k₂ = n − k₁

d = −(s₁ + s₂)[(s₁ + s₂) + (r₁ + r₂)]⁻¹

线 性 结 构

C6  k₂ = a·k₁ + b

d = (a·s₁ + b − s₂)[(s₂ + r₂) − a(s₁ + r₁)]⁻¹

C7  kᵢ = aᵢk + bᵢ

d = [a₁(s₂ − b₂) − a₂(s₁ − b₁)]·Δ⁻¹
Δ = a₂A₁ − a₁A₂

C8  Σcᵢkᵢ = c₀

d = (c₀ − Σcᵢsᵢ)(ΣcᵢAᵢ)⁻¹

跨 用 户 与 派 生

C9  跨用户同 k

k = s₁ + d₁A₁;d₂ = (k − s₂)A₂⁻¹

C10  k = αd + β

d = (β − s)(s + r − α)⁻¹

C11  kᵢ = αuᵢ + β

两两相减消 β、α 后解 d

C12  k = αd + βe + γ

d = (βe + γ − s)(s + r − α)⁻¹

点 关 系 与 验 签

C13  K₂ = K₁ + P

d = (s₁ − s₂)[(s₂ + r₂) − (s₁ + r₁) − 1]⁻¹

C14  验签恒等式

[s]G + (r + s)P = [k]G;x(K) = r − e

C15  公钥恢复

P = (s + r)⁻¹(K − [s]G);K.x = r − e

09 / 防 守

写给实现者

如果你在写签名服务,下面每一条都比背公式重要。

01  k 必须来自合规的硬件密码模块,均匀落在 [1, n−1],明确拒绝 0 和 n。

02  绝不重用 k;绝不把 k 设成时间戳、计数器、消息杂凑的直接函数,或与 d 做线性组合。

03  需要确定性签名时,使用经过评审的方案,不要自己发明“哈希一下当随机数”。

04  签名服务记录并检测重复 r。r 相同意味着 k 相同或互为相反数,C3 和 C5 都会命中;发现即告警并轮换密钥。

05  签名后做一次自验签;日志、调试接口、故障转储里不能出现 k。

06  把本文 15 组向量加入回归测试,确保实现不会产生可预测的 k。

SM2 算法本身没有被攻破。被攻破的,是“随机数必须随机”这个实现假设。

结 语

15 个公式,最后都收敛到同一行:

k = s + d · A

所谓私钥恢复,不是解离散对数,而是找到第二条关于 k 的方程。约束是相等、相反数、仿射、线性组合、跨用户共享、私钥派生、点关系时,都能化成一次方程;约束不足时,仍然只能面对离散对数。

k 一旦有结构,d 就只是一次除法。

下次看到两组签名,先别急着套公式。问三个问题:

① 两次的 k 相同吗?
② k 之间存在代数关系吗?
③ r 与 e 的差告诉了我什么?


评论:0   参与:  0