六组模数两两共享素因子 + 同一明文被同一指数连乘两层:gcd 分解后必须按「后加密的先解」逆序解密(先 d_2 再 d_1)才能还原
ctf/crypto · verified
一句话结论
当题目给出 6 组 (n_i, e_i, c_i)、且每个 c 是「同一明文先 m^e mod n_a、再把结果当消息做一次 ^e mod n_b」的两层连乘,同时 n_a 与 n_b 又两两共享同一个素因子时,攻击分两步且顺序不能错:先用 gcd(n_a, n_b) 把这一对模数同时分解、分别求出两个私钥,然后先解第二层(用 n_b 的 d_b)再用第一层(n_a 的 d_a) 才能得到明文;顺序颠倒只会得到中间值。
原理
- 共享素因子使一对模数同时失效:
p = gcd(n_a, n_b),则q_a = n_a/p、q_b = n_b/p,两组的φ与私钥都能算出。六组模数排成三对,每对共享一个素数,于是三组明文全部可解;这是「密钥批量生成时随机源复用」的典型后果。 - 两层连乘让解密有严格顺序:加密是
c = (m^e mod n_1)^e mod n_2,等价于c = m^(e²) mod n_2与m^e mod n_1的嵌套。解密必须从最外层开始:先m_mid = c^(d_2) mod n_2(此时m_mid = m^e mod n_1),再m = m_mid^(d_1) mod n_1。若先做mod n_1,指数与被模数不匹配(c是mod n_2的结果,可能大于n_1),既解不对也可能直接得到乱码。 - 为什么两层的模数必须共享素因子:如果不共享,就只能拿到两个独立 RSA 的嵌套,缺少任一层私钥都无法推进;共享因子让「两个私钥」同时可得,双层才有意义。这也是本题设成三对(6 个模数)而不是两对的原因。
- 指数相同不代表可以合并:有人会想
e²与n_2组合直接解密,但gcd(e², φ(n_2))未必为 1,且明文空间受n_1限制;逐层解、逐层断言pow(m, e, n) == c才是稳妥做法。 - 解出的字节常常不是最终 flag:本题明文经过一次字符层变换(删字符 / 双写字符),需要按提示还原;这提示「RSA 解出可读串」不等于结束,要读注释与题面对明文做二次处理。
触发条件
- 题目给出偶数个(≥4)模数,且成对出现;两两
gcd不为 1。 - 每个
c都是「同一e连乘两层」得到,即加密脚本里能看到c = pow(pow(m, e, n1), e, n2)这种形态。 - 已知每对的
n_a, n_b, e, c;能跑大整数 gcd、模逆与模幂。 - 明文相对模数较小(flag 量级),
long_to_bytes后应为可打印串。
利用步骤
- 把所有模数配对(题目通常按
n1/n2、n3/n4、n5/n6给出),对每对算p = gcd(n_a, n_b);断言1 < p < n_a。 - 分解:
q_a = n_a // p、q_b = n_b // p,并断言p*q_a == n_a、p*q_b == n_b。 - 分别求
φ_a = (p-1)(q_a-1)、φ_b = (p-1)(q_b-1),再d_a = e^-1 mod φ_a、d_b = e^-1 mod φ_b(每对的e可能不同,逐对取)。 - 逆序解密:
mid = pow(c, d_b, n_b)然后m = pow(mid, d_a, n_a)。 - 回环校验:
pow(pow(m, e, n_a), e, n_b) == c,确认没有把顺序搞反(反序会校验失败)。 long_to_bytes(m)得到可读串;再按题面提示做字符层还原(删掉某个字符、把某个字符双写等)。- 三对分别执行,得到三段明文,按题面顺序拼接成最终 flag。
PoC
import gmpy2
from Crypto.Util.number import long_to_bytes
# 每对:(n_a, n_b, e, c),e 为连乘两层的同一个指数
pairs = [(n1, n2, e1, c1), (n3, n4, e2, c2), (n5, n6, e3, c3)]
for na, nb, e, c in pairs:
p = gmpy2.gcd(na, nb)
assert 1 < p < na, "该对不共享素因子"
qa, qb = na // p, nb // p
assert p * qa == na and p * qb == nb
da = int(gmpy2.invert(e, (p - 1) * (qa - 1)))
db = int(gmpy2.invert(e, (p - 1) * (qb - 1)))
mid = pow(c, db, nb) # 先解外层(第二个模数)
m = pow(mid, da, na) # 再解内层(第一个模数)
assert pow(pow(m, e, na), e, nb) == c # 顺序校验
print(long_to_bytes(m).decode(errors="replace"))
变体与关联
- 层数变体:三层连乘就再多一个
d按「后进先出」解;层数与模数对数量必须一致,否则拿不到全部私钥。 - 配对变体:共享因子可能不是整齐配对(
n1与n3共享、n2与n5共享),此时应先做全部两两gcd建图,再按「密文与哪两个模数相关」配对解密。 - 明文后处理变体:删字符、字符双写、按位置移位、再套一层古典密码;见 [[crypto-rsa-dp-leak-composite-modulus-power-coppersmith]](同篇的 Beaufort + 位置移位)。
- 关联:[[ctf-crypto-rsa-shared-prime-batch-gcd]](只做 gcd 分解与单层解密,本卡补「双层逆序」这一必要步骤);[[ctf-crypto-rsa-noncoprime-common-modulus-iroot-wiener-chain]](同一模数、指数不互素时的开根路线,与本卡「不同模数、共享因子」互补)。
检测与防御
- CTF 验证:解完必须回环
pow(pow(m,e,na),e,nb) == c;顺序错时回环必失败,这是最快的自检。 - 真实 RSA 防御:每对密钥独立生成、RSA 参数不复用;用
secrets/os.urandom等 CSPRNG;对批量公钥定期做两两 gcd 扫描(共享因子一旦出现,所有相关密钥同时失效)。 - 协议层:不要用「同一明文多模数连乘」构造密钥封装,指纹固定且可验证;使用标准 KEM(RSA-OAEP)或直接换 ECC。
- 检测信号:批量公钥存在非互素对;
c < n_a但按n_a解密得乱码(提示真实模数是配对的另一个);密文长度与两层模数都不匹配。