AI摘要
攻击场景
CTF 中常见一类题型：给出多组 RSA 公钥 $(n_1, e_1), (n_2, e_2), \dots$ 及其对应密文 $c_1, c_2, \dots$，但题目不直接提供素数 $p, q$。如果运气好（或者说题目设计如此），其中某两个 $n$ 共享了同一个素数因子，则可以通过求最大公约数直接分解 $n$，进而解密。
此类攻击不需要大数分解的复杂算法，仅需一行 gcd 即可击穿 RSA 的安全性基石。
数学原理
问题形式化
设存在两组合法 RSA 密钥：
$$ \begin{aligned} n_1 &= p_1 \times q \\ n_2 &= p_2 \times q \end{aligned} $$
其中 $q$ 是两个 $n$ 共享的素数因子，$p_1 \neq p_2$ 为各自独有的素数。
利用 gcd 提取共享因子
由于 $q$ 同时整除 $n_1$ 和 $n_2$，根据最大公约数的定义：
$$ \gcd(n_1, n_2) = q $$
数学保证：若两个整数的质因数分解中各包含同一个素数 $q$，则该素数必然出现在 $\gcd$ 的结果中。当两个 $n$ 仅共享一个素数因子时（这是最常见的情况），$\gcd$ 精确地返回该因子。
更严格地，设 $n_i$ 的质因数集合为 $P_i$，则：
$$ \gcd(n_1, n_2) = \prod_{p \in P_1 \cap P_2} p^{\min(\alpha_p, \beta_p)} $$
其中 $\alpha_p, \beta_p$ 分别为 $p$ 在 $n_1, n_2$ 中的指数。RSA 模数 $n = p \times q$ 中每个素数的指数均为 $1$，故 $\gcd(n_1, n_2)$ 恰好等于它们共享的素数集合的乘积。若仅共享一个素数，$\gcd$ 就直接等于该素数。
得到 $q$ 之后
一旦通过 $\gcd$ 获得 $q$，另一半因子唾手可得：
$$ p_1 = \frac{n_1}{q}, \quad p_2 = \frac{n_2}{q} $$
之后按标准 RSA 解密流程即可恢复明文：
$$ \begin{aligned} \varphi(n_1) &= (p_1 - 1)(q - 1) \\ d_1 &\equiv e_1^{-1} \pmod{\varphi(n_1)} \\ m &\equiv c_1^{d_1} \pmod{n_1} \end{aligned} $$
现实成因：随机数生成器缺陷
共享素数攻击并非纯理论构造，在现实世界中确有案例：
- 2012 年 Lenstra 等人公开发表论文，扫描了互联网上约 710 万个 TLS 证书，发现约 0.2% 的证书（约 12700 个）共享了至少一个素数因子。根本原因是嵌入式设备（路由器、防火墙、IPMI 卡）在启动阶段的熵池不足，导致随机数生成器产生相同的"随机"素数。
- 低熵环境下，设备在首次启动时
/dev/urandom尚未积累足够的熵，而此时openssl genrsa已被调用，最终导致多个设备独立生成密钥时碰撞出相同素数。
对于 CTF 题目而言，共享素数是一种主动设计的考点，考察选手对 $\gcd$ 和 RSA 因子分解关系的理解。
实现细节
暴力二重循环的改进
原始脚本 muchN pqec.py 使用双重 for 循环比较所有 $n$ 对：
for i in n:
for j in n:
if (i != j):
pub_p = gp.gcdext(i, j)
if (pub_p[0] != 1) and (i > j):
...该写法的缺陷：
- 每一对 $(n_i, n_j)$ 比较了两次（一次 $i < j$，一次 $i > j$），条件
i > j用于去重； - 使用
gcdext而非gcd——gcdext返回 $(g, x, y)$ 三元组（扩展欧几里得），但我们只需要 $g$，用gcd更直接、更快； - 自比较 $i = j$ 会被
i <> j（Python 2 的不等号写法）过滤，无实际意义但仍需判断。
优化思路：只需对索引 $i < j$ 的每一对计算 $\gcd$，一旦发现 $\gcd \neq 1$ 即找到共享因子。
完整攻击脚本
以下为适配 Python 3 + gmpy2 的完整实现：
关键函数说明
| 函数 | 作用 | 时间复杂度 |
|---|---|---|
gmpy2.gcd(a, b) | 计算最大公约数 | $O(\log \min(a, b))$ |
gmpy2.invert(e, phi) | 求模逆元$e^{-1} \bmod \varphi(n)$ | $O(\log \varphi(n))$ |
pow(c, d, n) | 模幂运算（内置快速幂） | $O(\log d)$ |
整体复杂度来自双重循环：对于 $k$ 个 $n$，需计算 $C(k, 2) = \frac{k(k-1)}{2}$ 次 $\gcd$。通常 CTF 题目中 $k$ 不超过几十，完全可以接受。
不依赖 gmpy2 的备选方案
若环境无法安装 gmpy2，可使用 Python 内置的 math.gcd（Python 3.5+）：
import math
g = math.gcd(n_list[i], n_list[j])
if g != 1:
# 找到共享因子math.gcd 纯整数实现即可处理数百位的 crypro 级大数。gmpy2.gcd 在大规模批量计算时具有速度优势，但单次 $\gcd$ 差异不显著。
典型 CTF 题面特征
识别此类题型的方法：
- 题目给出多个 $n$（通常数量为 5~30 个）；
- 附件包含
n列表与对应c列表，$e$ 通常为统一值（如 65537）； - 有时会在文本中暗示"某某某的密钥生成器出了问题"或"这些公钥之间有什么联系"；
- 直接尝试对每个 $n$ 做小素数试除耗时过长（RSA-1024 以上不可行），提示另有蹊径。
攻击的本质
共享素数攻击暴露了 RSA 的一个根本脆弱点：安全性完全依赖于大整数分解的难度，而 $\gcd$ 则是绕过分解的捷径。如果 $n$ 能被任何公开信息轻易分解——无论是其他 $n$ 的 $\gcd$，还是有漏洞的随机生成——RSA 体系当即崩溃。
这与其他基于因子分解的攻击（Pollard's $p-1$、William's $p+1$、Fermat 分解等）不同，共享素数攻击不需要对 $n$ 本身做任何数学运算，只依赖于数据集内 $n$ 之间的关联。它本质上是供应链/多密钥环境下的信息泄露，而非单密钥的数学破译。
总结
- 当两个 RSA 模数 $n_1, n_2$ 共享同一个素数 $q$，$\gcd(n_1, n_2) = q$；
- 获得 $q$ 后可通过除法得到完整因子分解，进而解密；
- 现实世界中间件设备因熵不足曾批量出现此漏洞；
- CTF 中检测只需对所有 $n$ 对做 $\gcd$ 验证，找到 $\gcd \neq 1$ 即突破；
- 优先使用
gmpy2.gcd，无第三方库时可用math.gcd替代。
参考资料
- Lenstra, A. K., Hughes, J. P., Augier, M., Bos, J. W., Kleinjung, T., & Wachter, C. (2012). Ron was wrong, Whit is right. Cryptology ePrint Archive, Report 2012/064. https://eprint.iacr.org/2012/064
- Heninger, N., Durumeric, Z., Wustrow, E., & Halderman, J. A. (2012). Mining Your Ps and Qs: Detection of Widespread Weak Keys in Network Devices. USENIX Security Symposium.
- Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press. Chapter 8.
- GMP Library Documentation
- gmpy2 Documentation
- Python
math.gcd— 3.5+
