RSA 共模攻击
crypto/rsa · draft
一句话结论
同一明文用同一模数 n、不同互素指数 e1/e2 加密两次时,攻击者无需私钥即可通过扩展欧几里得算法恢复明文。
原理
已知 c1 = m^e1 mod n、c2 = m^e2 mod n,且 gcd(e1,e2)=1,可求 a,b 使 a*e1 + b*e2 = 1,于是 m = c1^a * c2^b mod n。负指数用模逆处理。
触发条件
- 相同模数
n被复用; - 两个公钥指数互素;
- 攻击者拿到两份密文。
利用步骤
- 确认两份密文使用同一
n; - 计算
gcd(e1,e2),确认互素; - 用扩展欧几里得求
a,b; - 处理负指数并计算明文。
PoC
from math import gcd
def egcd(a,b):
if b == 0: return (a,1,0)
g,x,y = egcd(b, a % b)
return (g, y, x - (a//b)*y)
g,a,b = egcd(e1,e2)
m = pow(c1,a,n) * pow(c2,b,n) % n
变体与关联
- 变体:低指数广播攻击、Related Message 攻击;
- 关联:RSA 填充与实现缺陷。
检测与防御
- 检测:证书/公钥复用同一模数;
- 防御:每次生成独立密钥、避免模数复用。