RSA 非互素指数共模攻击:gcdext 得 m^g 后加 n 开 g 次根恢复明文
ctf/crypto · verified
一句话结论
同一明文用同一模数 n、两个不互素的指数 e1/e2 加密时,扩展欧几里得只能得到 m^g mod n(g = gcd(e1,e2))而不是 m;对结果反复加 n 并开 g 次整数根,找到完全 g 次方即可恢复明文。本例先用 Wiener 从“大 e 小 d”恢复压缩包密码,再在重建的 docx 内用该变体解出 flag。
原理
- 共模攻击基础:
c1 = m^e1 mod n、c2 = m^e2 mod n;由扩展欧几里得求s1·e1 + s2·e2 = g = gcd(e1,e2),于是c1^s1 · c2^s2 ≡ m^g (mod n)。负指数用模逆/powmod处理。 - 当
g=1时直接得到m;当g>1时得到的是m^g mod n,即m^g - k·n对某个未知k。由于明文(如 flag)通常远小于n,m^g本身可能小于n,也可能被n回绕若干次。 - 恢复办法:令
v = m^g mod n,依次尝试v, v+n, v+2n, ...,对每个候选做g次整数开根;若存在精确整数根r且r^g == v + k·n,则r就是明文。g越大,m^g增长越快,通常只需少量k。 - 本例
e1=341=11×31、e2=209=11×19,g=11,因此共模计算后得到flag^11 mod n,再开 11 次根。 - Wiener 前置:RSA 参数文件中出现“e 与 n 同量级、d 很短”时,用
e/n连分数收敛恢复d(详见关联卡),得到下一层压缩包密码;这是多层 CTF 压缩包常见的“先解一层再拿下一层参数”结构。 - 包装层技巧:损坏的 zip 可用 WinRAR 修复;注释/备注常藏密码;docx 本质是 zip,缺
_rels/.rels等文件时从其他目录补齐后重新压缩并改后缀即可打开。
触发条件
- 两组密文使用相同模数
n、不同公钥指数e1/e2,且g = gcd(e1,e2) > 1(普通共模脚本会因指数不互素而失败)。 - 攻击者已知
n、e1、e2、c1、c2,并能进行大整数开根与模幂运算。 - 明文相对模数较小,
m^g的回绕次数k可枚举(通常 flag 级别足够小)。 - 前置层可能是“大 e 小 d”的 RSA(Wiener);需要先恢复上一层密码才能拿到共模参数。
利用步骤
- 修复损坏的压缩包(WinRAR“修复”),查看注释/备注得到第一层密码;解压出含 RSA 参数(
n、e、c,并提示d=short integer)的文本。 - 对第一层参数跑 Wiener:连分数展开
e/n,枚举收敛k/d,用(e·d−1) % k == 0求φ与p+q,判别式s²−4n为完全平方即恢复d,解出下一层压缩包密码。 - 解压第二层,识别其为 docx(zip 结构);缺失的
_rels/.rels等文件从第一层目录补齐,重新压缩并改后缀为.docx,用 Word 打开得到第二组 RSA 参数(m1=m2、e1、e2、n、c1、c2)。 - 计算
g, s1, s2 = gcdext(e1, e2),求v = c1^s1 · c2^s2 mod n,此时v = m^g mod n。 - 令
cand = v,循环:尝试整数g次根r;若r^g == cand则明文为r;否则cand += n继续。g次根可用gmpy2.iroot或整数二分。 - 把明文转字节;若字节序被反转(CTF 常见
[::-1]),反转后按 flag 格式校验。
PoC
import gmpy2
# e1=341, e2=209, gcd=11;c1/c2/n 为题目参数
g, s1, s2 = gmpy2.gcdext(e1, e2)
v = (pow(c1, int(s1), n) * pow(c2, int(s2), n)) % n # v = m^g mod n
cand = v
while True:
r, ok = gmpy2.iroot(cand, int(g))
if ok:
break
cand += n
pt = bytes.fromhex(hex(int(r))[2:])
print(pt[::-1]) # 本例反转后得到 flag
# 说明:若 g=1 则退化为普通共模攻击;g>1 时不能直接 long_to_bytes(v)。
# 前缀 "m1=m2=flag" 是关键前提;e1/e2 不互素时先算 gcd 再决定是否需要开根。
变体与关联
- 变体:
g=1的普通共模攻击,见 [[crypto-rsa-common-modulus]];g>1且k较大时,可结合明文格式/长度约束缩小枚举。 - 变体:低指数广播攻击也做“整数开根”,但模数不同,见 [[ctf-crypto-rsa-hastad-broadcast-e3-crt]]。
- 关联:[[crypto-rsa-wiener-small-private-exponent-large-e]](大 e 小 d 连分数恢复私钥)、[[crypto-rsa-e3-small-plaintext-integer-cube-root]](小指数直接开根)、[[ctf-misc-broken-docx-zip-mtime-thumbnail-stego]](docx/zip 结构修复思路)。
- 边界:
m^g的回绕次数随g与明文大小增长;若g很大或明文接近n,枚举k可能不可行。参数必须满足m1=m2(同一明文)且模数复用。
检测与防御
- 检测(CTF):看到两组密文同
n、指数不同,先算gcd(e1,e2);g>1时不要直接返回long_to_bytes(m),应转入开根流程;用iroot验证完全幂。 - 防御(真实 RSA):禁止复用模数;每次生成独立密钥;使用 RSA-OAEP 等带随机化的填充,使相同明文产生不同密文。
- 加固(工程):密钥生成后校验
gcd(e, φ)=1与d的规模;不要把“大 e 小 d”的私钥用于生产。