ECDSA 部分 nonce 泄露:k=h+l 线性关系用 LLL/CVP 恢复私钥
crypto/ecc · verified
一句话结论
若多个 ECDSA 签名的 k_i 只有低 X 位未知(k_i = h_i + l_i、0 <= l_i < X),或 k_i 之间存在已知线性关系,可把 s_i = k_i^{-1}(e_i + d*r_i) 改写为 t_i*d + u_i ≡ -l_i (mod n),构造 diag(n,...,n) + t 行 + u 行的格,用 LLL/CVP 求出短向量,从最后一位恢复私钥 d。
原理
- ECDSA:
s_i = k_i^{-1}(e_i + d*r_i) mod n,等价于k_i = e_i*s_i^{-1} + d*r_i*s_i^{-1} mod n。 - 记
T_i = r_i*s_i^{-1} mod n、A_i = e_i*s_i^{-1} mod n,则k_i = A_i + d*T_i mod n。 - 若
k_i = h_i + l_i,l_i < X,则l_i = A_i + d*T_i - h_i - y_i*n(某个整数y_i)。把u_i = A_i - h_i记入,得到u_i + d*T_i ≡ l_i (mod n)。 - 构造
(m+2) x (m+2)格:前m行diag(n),第m行前m列为T_i,第m+1行前m列为u_i;右下角分别为X/n与X。 - 格中存在短向量,其前
m个坐标对应l_i(或带符号),最后坐标与d相关;LLL 后按d ≈ row[m]*n/X提取候选,验证所有l_i是否落在[0,X)。 - 若
k_i之间是线性关系(k_i = a_i*k_0 + b_i),可先消元把未知量减少到一个,再用同样的格/HNP。
触发条件
- 多个 ECDSA 签名使用同一私钥,且每个
k_i的未知部分l_i有共同上界X(如低 128 位未知)。 - 已知每个
k_i的已知部分h_i或线性关系;消息哈希与签名可获取。 X相对n足够小,格维数/样本数足够(通常 3 个以上签名即可尝试)。- 有 LLL/BKZ/CVP 工具(Sage/fpylll)。
利用步骤
- 收集
m组(r_i,s_i,e_i,h_i),确认k_i = h_i + l_i、l_i < X。 - 计算
T_i = r_i*s_i^{-1} mod n、u_i = e_i*s_i^{-1} - h_i mod n。 - 按上述构造
(m+2)x(m+2)格,设置X与X/n。 - LLL/BKZ 约减,检查短向量;从最后坐标提取
d候选(注意符号/取模)。 - 用候选
d计算k_i = (A_i + d*T_i) mod n,检查是否都< X;若失败,增加样本/调整X/换向量。 - 用
d*G == Q或伪造签名验证私钥。
PoC
# Sage
n = 0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
X = 2**128
sigs = [{"r": ..., "s": ..., "e": ..., "h": ...}, ...]
m = len(sigs)
M = Matrix(QQ, m + 2, m + 2)
for i, sig in enumerate(sigs):
s_inv = pow(sig["s"], -1, n)
t = (sig["r"] * s_inv) % n
u = (sig["e"] * s_inv - sig["h"]) % n
M[i, i] = n
M[m, i] = t
M[m + 1, i] = u
M[m, m] = X / n
M[m + 1, m + 1] = X
M_lll = M.LLL()
for row in M_lll:
d = abs(int(row[m] * n / X))
if 0 < d < n:
ks = [(sigs[i]["e"] * pow(sigs[i]["s"], -1, n) + d * sigs[i]["r"] * pow(sigs[i]["s"], -1, n)) % n for i in range(m)]
if all(0 <= k < X for k in ks):
print("d =", d)
break
变体与关联
- 变体:
k_i之间满足k_i = a_i*k_0 + b_i时,先代入消元,再按单未知量 HNP 构造格。 - 变体:未知部分是高位而非低位时,把
h_i与l_i的角色互换,等式仍成立。 - 变体:样本带噪声/部分位错误时,用 CVP/BKZ 或枚举异常样本剔除。
- 关联:[[crypto-ecc-ecdsa-time-side-channel-hnp]](时间侧信道 HNP)、[[crypto-ecc-ecdsa-nonce-reuse-private-key-recovery]](完全复用)、[[crypto-prng-truncated-lcg-coppersmith-lattice-cvp]](格/CVP 方法)。
检测与防御
- 防御:使用 RFC6979/CSPRNG 生成 full-size nonce,不要截断/复用;签名实现不要泄露
k的高位/低位。 - 防御:对签名接口做速率限制,避免攻击者收集大量样本;使用 HSM 保护私钥与 nonce。
- 检测:签名日志中出现
k的部分位、固定高位、线性关系;大量签名样本被收集。 - 响应:发现 nonce 泄露后立即轮换私钥,审计历史签名是否可恢复,修复随机数生成。