RSA hint 值差值 GCD 分解:多组提示同余于同一素因子时直接取公因子
crypto/rsa · verified
一句话结论
题目给出多组 (a_i, b_i, s_i) 提示时,若这些 s_i 都同余于同一个素因子(例如都满足 s_i ≡ r (mod p)),则任意两组之差 s_i - s_j 都是 p 的倍数,直接计算 gcd(|s_i - s_j|, N) 即可恢复 p,随后按常规 RSA 求 d 解密。
原理
- 同余产生公因子:设 N=pq,若所有提示值满足
s_i ≡ r (mod p)(同一残差 r),则s_i - s_j ≡ 0 (mod p),即 p 整除每一对差值。 - GCD 提取:
gcd(|s_i - s_j|, N)在理想情况下等于 p(或 q);若得到 1,说明该对提示不同余或差值不含因子;若得到 N,说明差值同时是 p、q 的倍数,需要换一对。 - 与费马分解的关系:经典费马分解利用
a² - N = b²的平方差;本题是“提示值同余”的推广——只要提示值共享某个模 p 的不变量,差值就携带 p 的倍数,GCD 即可分解。 - 批量形式:有多组提示时,可对所有配对做 GCD,或先计算相邻差值/乘积树做批量 GCD;命中后立即用
q=N//p验证。 - 后续:恢复 p、q 后计算
φ=(p-1)(q-1)、d=e^{-1} mod φ,m=c^d mod N;若明文小于较小因子,也可用d_r=e^{-1} mod (r-1)简化。
触发条件
- RSA 模数 N 与多组提示值
s_i一并泄露;提示值由同一秘密因子派生,且共享模 p(或 q)的残差。 - 至少两组有效提示;提示数量越多,命中概率越高。
- 提示值未被随机噪声破坏(若有噪声需用近似 GCD/格方法)。
- 已知 e 与密文 c,拿到因子后可正常解密。
利用步骤
- 从 output.txt/附件中用正则提取所有
Hint i: a, b, s三元组。 - 对所有提示对计算
g = gcd(abs(s_i - s_j), N)。 - 检查
1 < g < N且N % g == 0;命中即得到 p(或 q)。 - 令
q = N // g,计算φ=(p-1)(q-1)、d=e^{-1} mod φ。 m = c^d mod N,long_to_bytes(m)得到 flag;若失败,换其他提示对或先做批量 GCD。- 若差值 GCD 全为 1/N,检查提示公式是否应使用和、积或带符号组合。
PoC
from itertools import combinations
from math import gcd
import re
from Crypto.Util.number import long_to_bytes, inverse
txt = open("output.txt").read()
hint_re = re.compile(r"Hint \d+:\s*(\d+)\s*,\s*(\d+)\s*,\s*(\d+)")
hints = [(int(m.group(1)), int(m.group(2)), int(m.group(3)))
for m in hint_re.finditer(txt)]
def find_factor_from_hints(hints):
for (i, (a1, b1, s1)), (j, (a2, b2, s2)) in combinations(list(enumerate(hints)), 2):
g = gcd(abs(s1 - s2), n)
if g != 1 and g != n:
return i, j, g
return None
i, j, p = find_factor_from_hints(hints)
q = n // p
d = inverse(e, (p - 1) * (q - 1))
print(long_to_bytes(pow(c, d, n)).decode())
原文在 18 组 hint 中由第 12、17 组差值得到 309 位因子 p,解密出:
ISCTF{M0dIFi3D_f3RM47_7H30r3m_I5_fUn_8U7_h4rD3r!}
变体与关联
- 组合方式变体:若提示满足
s_i ≡ -r (mod p),则用s_i + s_j;若提示带系数,先做线性组合再取 GCD。 - 噪声变体:提示值有随机误差时,
s_i - s_j不再是 p 的精确倍数,需用近似 GCD(AGCD)或格方法;见 [[ctf-crypto-agcd-sda-lattice-small-error-recovery]]。 - 关联:[[crypto-rsa-fermat-close-prime-factorization]](经典平方差)、[[crypto-rsa-shared-prime-batch-gcd]](多模数共享素因子)。
- 边界:提示值与 N 的因子无同余关系、或提示数量不足/全部被噪声污染时,GCD 路线失效。
检测与防御
- 检测:CTF 中 output 含大量
Hint i: a,b,s;对提示两两做 GCD 是否出现非平凡因子。 - 防御:不要向不可信方泄露同一秘密因子的多组派生值;密钥生成使用随机大素数,避免结构化提示。
- 加固:若业务必须提供 hint,加入随机化/盲化并限制查询次数;定期轮换密钥。