RSA 私钥 d 泄露后只换 e 不换 n:e·d−1 概率分解 N 并解新密文
crypto/rsa · verified
一句话结论
RSA 私钥指数 d1 泄露后,即使服务端“生成新密钥对”只换了 e2、仍沿用同一个模数 n1(同一对 p,q),也不安全:由 k = e1·d1 − 1 = 2^r·s,随机取 g 计算 g^s mod n 并反复平方,可用 gcd(x−1,n) 概率分解 n;得到 p,q 后求 φ(n),再用新公钥 e2 计算 d2 = e2^{-1} mod φ(n) 即可解密新密文。
原理
- RSA 关系:
e·d ≡ 1 (mod λ(n)),因此e·d − 1是λ(n)的倍数,也是φ(n)的倍数;写k = e·d − 1 = 2^r·s(s 为奇数)。 - 概率分解:对随机
g ∈ [2,n−2],计算x = g^s mod n。若x ≠ 1, n−1,则对x反复平方(最多 r 次),在某个x^{2^i}处gcd(x−1,n)会给出 p 或 q;这是 Miller-Rabin 分解思路的逆用。 - 为什么换 e 不换 n 不安全:
d1泄露等价于泄露φ(n)的倍数,进而分解 n;攻击者拿到 p,q 后,任何基于同一 n 的新公钥e2都能求出对应私钥d2,旧模数上的所有新密文都可解。 - 攻击步骤:分解 n →
φ=(p−1)(q−1)→d2=inverse(e2,φ)→m=pow(c,d2,n)→ long_to_bytes。 - 修复误区:只换 e、重新生成 d 但不换 p,q/n,等于没换密钥;必须重新生成模数(新 p,q)或直接弃用旧密钥对。
触发条件
- 攻击者已知旧模数
n、旧公钥指数e1、旧私钥指数d1(泄露/日志/内存/侧信道),以及新公钥e2和新密文c。 - 新密钥对复用了同一个
n(同一对 p,q),只换了e;e2与φ(n)互素。 - 目标未在 d 泄露后轮换模数/未撤销旧密钥;密文使用标准 RSA(无随机化/填充问题)。
- 计算资源足以做几次模幂/ gcd(分解概率算法通常很快)。
利用步骤
- 计算 k:
k = e1*d1 - 1;写k = 2^r * s(s 奇数)。 - 概率分解:循环随机取
g,x = pow(g, s, n);若x==1或x==n-1重试;否则对i in range(r):p = gcd(x-1,n),若1<p<n成功,否则x = x^2 mod n。 - 验证:
p*q == n;得到 p,q。 - 求新私钥:
φ=(p-1)*(q-1);d2 = inverse(e2, φ)。 - 解密:
m = pow(c, d2, n);long_to_bytes(m)得明文/flag。 - 若 e2 与 φ 不互素:需要先分解 φ 或求
λ(n),用扩展欧几里得处理;通常 e2 为质数且不整除 φ。
PoC
from math import gcd
from random import randrange
from Crypto.Util.number import long_to_bytes, inverse
n = ... # 旧模数
e1 = 65537
d1 = ... # 泄露的旧私钥指数
e2 = 6767671
c = ...
k = e1 * d1 - 1
s, r = k, 0
while s % 2 == 0:
s //= 2; r += 1
def factor_from_d(n, s, r):
while True:
g = randrange(2, n - 1)
x = pow(g, s, n)
if x in (1, n - 1):
continue
for _ in range(r):
p = gcd(x - 1, n)
if 1 < p < n:
return p, n // p
x = pow(x, 2, n)
p, q = factor_from_d(n, s, r)
assert p * q == n
phi = (p - 1) * (q - 1)
d2 = inverse(e2, phi)
m = pow(c, d2, n)
print(long_to_bytes(m))
原文在给定 n,e1,d1,e2,c 下成功分解并解出 flag;本卡不执行 PoC。
变体与关联
- 只泄露 d 的低位/高位:需要 Coppersmith/格方法补全,见 [[crypto-rsa-private-exponent-low-bits-partial-p]];本卡是完整 d 泄露。
- 泄露 φ(n)/λ(n):同样可分解 n 或直接求 d;与 d 泄露等价。
- 多把公钥同模数:若 e1,e2 共用 n 且 d1 泄露,全部可解;即使没有 d,共用模数的多把密钥也可能被 GCD/共模攻击。
- 关联:[[crypto-rsa-continued-fraction-lambda-factorization]](由 e·g/n 恢复 λ 并分解)、[[crypto-rsa-wiener-small-private-exponent-large-e]](小 d 攻击)、[[crypto-rsa-partial-e-coppersmith-hgs-multi-key-small-d]](同模数多密钥)。
- 边界:需要完整 d1 和同一 n;若服务端在 d 泄露后真正更换了 p,q/n,或使用 RSA-KEM/抗量子方案,本攻击不成立。
检测与防御
- 密钥轮换:d 泄露后必须重新生成 p,q 和 n,不能只换 e;撤销旧证书/密钥,通知依赖方。
- 最小暴露:私钥指数不出现在日志/内存转储/错误信息/侧信道可达位置;使用 HSM/TPM 保护私钥,常时算法。
- 密钥管理:定期轮换、分离密钥用途、监控同一 n 被多把 e 复用;对历史密文评估是否需重新加密。
- 检测:同一模数对应多个公钥指数、d 出现在日志/配置文件、异常的大数 gcd/模幂行为;证书透明度/密钥泄露监控。
- 响应:立即轮换模数与所有相关密钥,重新加密敏感数据,审计是否已被解密。