批量 RSA 模数两两 gcd:共享素因子直接分解并恢复明文
ctf/crypto · verified
一句话结论
同时给出多组 RSA 模数时,只需两两计算 gcd:任意一对非互素的模数立刻暴露 1024 位共享素因子,分解两组模数、求私钥、解密即可;二十组模数只需 190 次大数除法,是批量 RSA 题的第一动作。
原理
- RSA 模数本应互素:每个
n = p*q由独立随机素数生成;两个独立生成的 1024 位素数相同的概率约为 2^-1024,实际上不可能。 - 共享因子即分解:若
gcd(n_i, n_j) = p > 1,则p同时整除两个模数,q_i = n_i / p、q_j = n_j / p,两组模数同时被分解。 - 根因是生成侧随机源失败:熵池未初始化、种子硬编码、同一进程连续生成多对密钥时 RNG 状态未更新,都会导致跨密钥的素因子复用。
- 解密流程是标准的:
phi=(p-1)(q-1)、d=e^-1 mod phi、m=c^d mod n;最后用pow(m,e,n)==c回环验证。 - 为什么先做 gcd:成本 O(k²) 次大数除法,远低于 Wiener、因子库查询、Coppersmith 等尝试;看到“多组 n/c 并列”就应先跑 gcd。
触发条件
- 题目/附件同时给出多组 RSA 模数(同指数或不同指数均可)。
- 其中至少两组的模数共享素因子(生成侧 RNG 缺陷、密钥批量生成、跨批次复用)。
- 攻击者能运行大整数 gcd 与模幂运算(Python/gmpy2 即可)。
- 每组密文对应可解密的目标(相同或不同明文均可,共享因子的两组都能解)。
利用步骤
- 解析所有
n(和对应的c、e),确认位长与分组。 - 对所有模数对跑
gcd(n_i, n_j);非 1 即命中,记录公因子位长并做素性检验。 - 用公因子分解命中对:
q_i = n_i // p,断言p*q_i == n_i。 - 对每组计算
phi、d,解出m,按字节长度还原明文。 - 用
pow(m, e, n) == c回环验证;多组结果互相印证。 - 若 gcd 全部为 1,再排查小因子、Wiener、素数幂、Fermat 近邻素数等其他缺陷,避免只盯一种。
PoC
from math import gcd
ns = [int(x) for x in open("moduli.txt")]
for i in range(len(ns)):
for j in range(i + 1, len(ns)):
g = gcd(ns[i], ns[j])
if g != 1:
print("shared factor:", i, j, g.bit_length())
# 命中 (4, 17) 后
p = gcd(ns[4], ns[17])
q4, q17 = ns[4] // p, ns[17] // p
assert p * q4 == ns[4] and p * q17 == ns[17]
phi = (p - 1) * (q4 - 1)
d = pow(e, -1, phi)
m = pow(cs[4], d, ns[4])
plain = m.to_bytes((m.bit_length() + 7) // 8, "big")
assert pow(m, e, ns[4]) == cs[4]
原文实测:二十组 2048 位模数中仅 (4,17) 共享 1024 位素因子,其余 378 对互素;解出 flag{abdcbe5fd94e23b3de429223ab9c2fdf}。
变体与关联
- 跨批次变体:不同批次/不同年份的密钥台账中复用同一素数,三组密钥可同时失效(同篇 OTA 题中三个批次共享 512 位素数)。
- 混合缺陷变体:同一题可同时存在共享素因子与小指数广播,两条路径应分别走通并交叉验证。
- 排除项:小因子试除、Wiener 连分数(
d过小)、模数为素数幂;这些都不命中时再考虑共享因子。 - 关联卡片:[[crypto-rsa-fermat-close-prime-factorization]](近邻素数)、[[crypto-rsa-pollard-pminus1-smooth-prime]](p-1 光滑)、[[crypto-rsa-common-modulus]](共模攻击)。
- 边界:只有一组模数时 gcd 无从比较;共享因子必须真实存在,不能靠猜测;强随机源生成的密钥不会命中。
检测与防御
- CTF 验证:分解后必须回环
pow(m,e,n)==c;多组明文可读性互相印证。 - 密钥生成审计:对一批公钥做两两 gcd 与熵源检查;禁止硬编码种子、共享 RNG 状态、在 fork 后复用随机数。
- 工程防御:使用系统 CSPRNG(
secrets/os.urandom/HSM);每对密钥独立生成并做自检;密钥台账定期做共享因子扫描。 - 检测信号:批量公钥中出现非互素对;密钥生成时间/进程高度集中;不同批次密钥共享素因子。