RSA共享素数攻击

## 攻击场景

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$ 对：

```python
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):
                ...
```

该写法的缺陷：

1. 每一对 $(n_i, n_j)$ 比较了两次（一次 $i < j$，一次 $i > j$），条件 `i > j` 用于去重；
2. 使用 `gcdext` 而非 `gcd`——`gcdext` 返回 $(g, x, y)$ 三元组（扩展欧几里得），但我们只需要 $g$，用 `gcd` 更直接、更快；
3. 自比较 $i = j$ 会被 `i <> j`（Python 2 的不等号写法）过滤，无实际意义但仍需判断。

优化思路：只需对索引 $i < j$ 的每一对计算 $\gcd$，一旦发现 $\gcd \neq 1$ 即找到共享因子。

### 完整攻击脚本

以下为适配 Python 3 + `gmpy2` 的完整实现：
[hide]

```python
import gmpy2
from Crypto.Util.number import long_to_bytes

# ========== 输入（题目给定） ==========
n_list = [
    1351234567890123456789012345678901234567890123456,
    2462345678901234567890123456789012345678901234567,
    # ... 更多 n 值
]
c_list = [
    9876543210987654321098765432109876543210987654321,
    7654321098765432109876543210987654321098765432109,
    # ... 对应密文
]
e = 65537

# ========== 寻找共享素数 ==========
def find_shared_prime(n_list):
    """在两两组合的 n 中寻找共享素数因子"""
    length = len(n_list)
    for i in range(length):
        for j in range(i + 1, length):
            g = gmpy2.gcd(n_list[i], n_list[j])
            if int(g) != 1:
                return i, j, int(g)
    return None, None, None

idx1, idx2, shared_q = find_shared_prime(n_list)

if shared_q is None:
    print("未找到共享素数因子")
    exit(1)

print(f"[+] 发现共享因子：n[{idx1}] 与 n[{idx2}] 共享素数 {shared_q}")

# ========== 分解 n ==========
n = n_list[idx1]
p = n // shared_q
q = shared_q

print(f"[+] n = {n}")
print(f"[+] p = {p}")
print(f"[+] q = {q}")
assert n == p * q, "分解失败"

# ========== 标准 RSA 解密 ==========
phi = (p - 1) * (q - 1)
d = int(gmpy2.invert(e, phi))
m = pow(c_list[idx1], d, n)

print(f"[+] 私钥 d = {d}")
print(f"[+] 明文: {long_to_bytes(m).decode()}")
```

[/hide]

### 关键函数说明

| 函数                   | 作用                              | 时间复杂度           |
| ---------------------- | --------------------------------- | -------------------- |
| `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+）：

```python
import math

g = math.gcd(n_list[i], n_list[j])
if g != 1:
    # 找到共享因子
```

`math.gcd` 纯整数实现即可处理数百位的 crypro 级大数。`gmpy2.gcd` 在大规模批量计算时具有速度优势，但单次 $\gcd$ 差异不显著。

## 典型 CTF 题面特征

识别此类题型的方法：

1. 题目给出多个 $n$（通常数量为 5~30 个）；
2. 附件包含 `n` 列表与对应 `c` 列表，$e$ 通常为统一值（如 65537）；
3. 有时会在文本中暗示"某某某的密钥生成器出了问题"或"这些公钥之间有什么联系"；
4. 直接尝试对每个 $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` 替代。

## 参考资料

1. 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
2. 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.
3. Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). *Handbook of Applied Cryptography*. CRC Press. Chapter 8.
4. [GMP Library Documentation](https://gmplib.org/manual/)
5. [gmpy2 Documentation](https://gmpy2.readthedocs.io/)
6. [Python `math.gcd` — 3.5+](https://docs.python.org/3/library/math.html#math.gcd)

AI摘要

文章介绍了RSA共享素数攻击：当多个公钥共享素数因子时，通过计算最大公约数（gcd）可快速分解模数。该攻击源于设备随机数生成器缺陷，在CTF中常见。文章详细讲解了原理、成因及Python实现。

攻击场景

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)} $$

得到 $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+

投币支持一下吧

END

👤 作者Monarchdos

📄 标题RSA共享素数攻击

🔗 地址https://ayfre.com/35.html

RSA共享素数攻击

攻击场景