RSA 两个线性 hint 都是 p、q 的小系数组合:枚举 ≤211 的系数让一边系数抵消,差值即素因子倍数,gcd 直接分解 n
crypto/rsa · verified
一句话结论
当两个 hint 形如 hint1 = x1·p + y1·q - C1、hint2 = x2·p + y2·q - C2(系数、常数都较小且已知常量偏移)时,先补回常数得到 S1 = x1·p + y1·q、S2 = x2·p + y2·q,再在小范围里枚举整数 i, j:一旦 i·y1 == j·y2,i·S1 - j·S2 = p·(i·x1 - j·x2) 就是 p 的倍数,gcd(i·S1 - j·S2, n) 直接给出 p。
原理
- 两个线性式的 gcd 直觉不成立,配对系数才成立:
S1、S2各自都不是 p 的倍数(都含 q 项),所以直接gcd(S1 - S2, n)通常为 1。要让差值只含 p,必须让 q 的系数相消:i·y1 - j·y2 = 0。 - 小系数让枚举可行:题中
x1,y1,x2,y2落在[0, 211)/[0, 2514)这类小范围,i, j也只需枚举到同量级(本题 211×211 次),命中条件是两个小整数互成比例(i/j = y2/y1),在 4 万组配对里必然出现。 - 差值即因子倍数:命中后
i·S1 - j·S2 = (i·x1 - j·x2)·p,是 p 的整数倍且远小于n,所以gcd(差值, n)等于 p(偶尔因同时整除 q 而得到 n,换个配对即可);拿到 p 后q = n//p,常规d = e^{-1} mod φ解密。 - 常数偏移必须先补回:
hint里减掉的0x114、0x514是公开常量,忘记加回去会让方程的 p/q 系数组合被常数污染,差值不再整除 p。
触发条件
- 已知
n、e、密文c,并泄露至少两个 p、q 的线性组合(系数小、常数已知)。 - 系数范围足够小,可对
i, j做O(K²)枚举(K 约几百)。 - 密文对应的明文短于
n(常规 RSA 解密前提)。
利用步骤
- 从题目输出里抓
n、c、两个 hint,以及 hint 定义里的常数偏移。 - 还原
S1 = hint1 + C1、S2 = hint2 + C2。 - 双重循环枚举
i, j ∈ [1, K],计算g = gcd(i*S1 - j*S2, n);1 < g < n且g为素数时即命中p。 q = n//g,d = inverse(e, (p-1)*(q-1)),m = pow(c, d, n),long_to_bytes(m)。
PoC
from math import gcd
from Crypto.Util.number import inverse, long_to_bytes, isPrime
K = 211
for i in range(1, K):
for j in range(1, K):
g = gcd(i * (hint1 + C1) - j * (hint2 + C2), n)
if 1 < g < n and isPrime(g):
p, q = g, n // g
d = inverse(65537, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)).decode())
raise SystemExit
上面的 g 命中判据要收紧为 isPrime(g):差值有时同时含 p 与 q 的更高次幂,gcd 会返回合数,此时换下一组 (i, j)。
变体与关联
- 三变量/多 hint:可先对两两 hint 做批量 gcd,或把
i·y1 - j·y2的配对方程当成整数线性方程组求小解(LLL),避免平方枚举。 - 系数带噪声:差值不再精确整除 p,需改用近似 GCD 或格约减(把
i·S1 - j·S2当短向量)。 - 与「多 hint 同余同一素因子 → 直接 gcd 差值」的卡相比:那张卡靠残差相同,本卡靠系数配平,题目给的是
x·p + y·q型而非s ≡ r (mod p)型。 - 与「hint 泄露 p+q / p-q」类卡相比:本卡两个 hint 都不是 p+q 或 p-q 的干净形式,必须先解系数。
检测与防御
- 不要泄露 p、q 的任何线性组合,哪怕是「加了小随机系数」的版本;只要系数范围可控即可被枚举配平。
- hint 若要发布,应保证其中一个系数足够大(接近 p 的量级)或引入秘密乘数,使配平枚举不可行。
- 出题侧自检:拿
gcd(i*S1 - j*S2, n)对小系数网格扫一遍,确认不出现素因子。