算法核心

选择两个大素数 $p, q$，令 $n = p \cdot q$，欧拉函数 $\varphi(n) = (p-1)(q-1)$。选取 $e$ 满足 $\gcd(e, \varphi(n)) = 1$，计算 $d \equiv e^{-1} \pmod{\varphi(n)}$。

• 公钥：$(n, e)$
• 私钥：$(n, d)$
• 加密：$c \equiv m^e \pmod{n}$
• 解密：$m \equiv c^d \pmod{n}$

正确性证明：

由 $ed \equiv 1 \pmod{\varphi(n)}$，存在整数 $k$ 使得 $ed = k\varphi(n) + 1$。

$$ c^d \equiv (m^e)^d \equiv m^{ed} \equiv m^{k\varphi(n) + 1} \equiv (m^{\varphi(n)})^k \cdot m \pmod{n} $$

根据欧拉定理，当 $\gcd(m, n) = 1$ 时 $m^{\varphi(n)} \equiv 1 \pmod{n}$，代入得 $c^d \equiv m \pmod{n}$。

若 $\gcd(m, n) \neq 1$（即 $m$ 是 $p$ 或 $q$ 的倍数），可通过中国剩余定理分别验证模 $p$ 和模 $q$ 下成立，RSA 解密在该情况下仍然正确¹。

欧拉函数 $\varphi(n)$： 小于 $n$ 且与 $n$ 互质的正整数个数。积性：$\gcd(a, b) = 1$ 时 $\varphi(ab) = \varphi(a)\varphi(b)$。

• 若 $p$ 为素数，$\varphi(p) = p - 1$
• 由积性：$\varphi(pq) = (p-1)(q-1)$
• 对于素数幂 $p^r$：$\varphi(p^r) = p^r - p^{r-1}$（区间 $[1, p^r]$ 中仅 $p, 2p, \dots, p^{r-1}p$ 共 $p^{r-1}$ 个数与 $p^r$ 不互素）

几个 $\varphi(n)$ 的变形：

模逆元： $d$ 满足 $e \cdot d \equiv 1 \pmod{\varphi(n)}$。可解性的充要条件是 $\gcd(e, \varphi(n)) = 1$——这正是密钥生成时选择 $e$ 的约束。求解使用扩展欧几里得算法（Extended Euclidean Algorithm），该算法在求出 $\gcd$ 的同时返回 Bézout 系数。

d = libnum.invmod(e, phi_n)        # libnum
d = int(gmpy2.invert(e, phi_n))    # gmpy2
d = pow(e, -1, phi_n)              # Python 3.8+

基础加解密模板：

import libnum

p = libnum.generate_prime(1024)
q = libnum.generate_prime(1024)
m = libnum.s2n('flag{test}')
n = p * q
phi_n = (p - 1) * (q - 1)
d = libnum.invmod(e, phi_n)
c = pow(m, e, n)
m = pow(c, d, n)
print(libnum.n2s(m))

N 的分解

当 $p, q$ 选择不当，$n$ 可被分解，RSA 安全性直接瓦解。

在线查询：factordb.com，常用的大数可能已有记录。

yafu 本地分解：

yafu-x64.exe factor(123456789)
yafu-x64.exe "factor(@)" -batchfile n.txt

$p, q$ 过于接近 — 费马分解：

对于任意奇数 $n = pq$，可表示为平方差：

$$ n = pq = \left(\frac{p+q}{2}\right)^2 - \left(\frac{p-q}{2}\right)^2 = a^2 - b^2 $$

其中 $a = \frac{p+q}{2}$，$b = \frac{p-q}{2}$。而 $a = \sqrt{n + b^2} \ge \sqrt{n}$。

当 $p, q$ 接近时，$b$ 很小，$a \approx \sqrt{n}$。从 $a = \lceil\sqrt{n}\rceil$ 开始递增，检查 $a^2 - n$ 是否为完全平方数。若 $a^2 - n = b^2$，则 $p = a+b$, $q = a-b$。

时间复杂度取决于 $|p-q|$：差值为 $O(n^{1/4})$ 时约需 $O(n^{1/4})$ 步，远优于试除法。

def fermat(n):
    a = gmpy2.iroot(n, 2)[0]
    while True:
        b2 = a * a - n
        b, ok = gmpy2.iroot(b2, 2)
        if ok:
            return int(a + b), int(a - b)
        a += 1

低加密指数

$e=3$ 且 $m^3 < n$ 时，模运算退化为普通整数运算：$c = m^3$（未发生取模回绕）。此时 $m = \sqrt[3]{c}$ 可直接在整数域求解。

若 $m^e \ge n$，则 $c = m^e - kn$（$k$ 为取模时减去的 $n$ 的倍数）。由于 $m < n$，$k < e \cdot n^{e-1}$ 通常很小——爆破 $k$ 即可：

$$ m = \sqrt[e]{c + k \cdot n} $$

# 场景一：m^e < n，直接开根
m = gmpy2.iroot(c, e)[0]

# 场景二：m^e >= n，爆破 k
k = 0
while True:
    m, ok = gmpy2.iroot(c + k * n, e)
    if ok:
        break
    k += 1

广播攻击 (Håstad)

相同 $m$、相同 $e$，使用不同 $n_i$ 加密得到多组 $(n_i, c_i)$。

攻击核心是 Håstad 定理：若 $n_i$ 两两互素且 $m < \min(n_i)$，则当密文数 $\ge e$ 时，可唯一确定 $m$。

构造同余方程组：

$$ \begin{cases} m^e \equiv c_1 \pmod{n_1} \\ m^e \equiv c_2 \pmod{n_2} \\ \quad\vdots \\ m^e \equiv c_k \pmod{n_k} \end{cases} $$

由中国剩余定理，存在唯一解 $M \equiv m^e \pmod{\prod n_i}$。因 $m^e < \prod n_i$（当 $k \ge e$ 且每个 $n_i$ 足够大时），$M = m^e$ 在整数域上成立，对 $M$ 开 $e$ 次根即得 $m$。

from functools import reduce

def crt(remainders, moduli):
    M = reduce(lambda x, y: x * y, moduli)
    x = 0
    for r, m in zip(remainders, moduli):
        Mi = M // m
        ti = gmpy2.invert(Mi, m)
        x += r * Mi * ti
    return x % M

m_e = crt(c_list, n_list)
m = gmpy2.iroot(m_e, e)[0]

共模攻击

同一 $n$ 下，用互素的两个 $e_1, e_2$ 加密同一 $m$ 得到 $c_1, c_2$。

由 Bézout 恒等式，$\gcd(e_1, e_2) = 1$ 意味着存在整数 $s, t$ 使：

$$ s \cdot e_1 + t \cdot e_2 = 1 $$

因此：

$$ c_1^s \cdot c_2^t \equiv (m^{e_1})^s \cdot (m^{e_2})^t \equiv m^{s e_1 + t e_2} \equiv m^1 \equiv m \pmod{n} $$

$s$ 或 $t$ 可能为负，此时需要对应的模逆元：$c^{-s} \equiv (c^{-1})^s \pmod{n}$。

_, s, t = gmpy2.gcdext(e1, e2)
m = (pow(c1, s, n) * pow(c2, t, n)) % n

若 $s$ 或 $t$ 为负，pow(c, -s, n) 等价于 pow(gmpy2.invert(c, n), s, n)。

共享素数

多个 $n$ 共用一个素因子：

q = gmpy2.gcd(n1, n2)
p1 = n1 // q
p2 = n2 // q

Wiener 攻击

当 $d$ 很小（$d < \frac{1}{3}n^{1/4}$）而 $e$ 相应很大时，Wiener 利用连分数展开恢复 $d$。

推导思路： 由 $ed \equiv 1 \pmod{\varphi(n)}$ 得 $ed - k\varphi(n) = 1$，两边除以 $d\varphi(n)$：

$$ \left|\frac{e}{\varphi(n)} - \frac{k}{d}\right| = \frac{1}{d\varphi(n)} $$

由于 $p, q$ 是大素数，$\varphi(n) = n - p - q + 1 \approx n$，因此：

$$ \left|\frac{e}{n} - \frac{k}{d}\right| \approx \frac{1}{d\varphi(n)} < \frac{1}{2d^2} $$

根据 Dirichlet 逼近定理，$\frac{k}{d}$ 必然是 $\frac{e}{n}$ 的连分数展开中的某个渐近分数。逐一检查每个渐近分数的分母 $d_i$ 是否满足 $e \cdot d_i \equiv 1 \pmod{\varphi(n)}$（等价于用 $d_i$ 解密一段已知明文验证）。

import owiener
d = owiener.attack(e, n)
if d:
    m = pow(c, d, n)

dp / dq 泄露

快速解密的一个常用优化（CRT-RSA）会计算 $dp = d \bmod (p-1)$ 和 $dq = d \bmod (q-1)$。一旦这些中间值泄露，即可攻破 RSA。

仅有 dp 泄露：

由定义 $dp \equiv d \pmod{p-1}$，两边同乘 $e$：

$$ dp \cdot e \equiv d \cdot e \equiv 1 \pmod{p-1} $$

因此存在整数 $k$ 使 $dp \cdot e - 1 = k(p-1)$。变形得 $p = \frac{dp \cdot e - 1}{k} + 1$。由于 $dp < p-1$，有 $k < e$，只需枚举 $k \in [1, e)$ 并验证 $n \bmod p = 0$：

for k in range(1, e):
    if (dp * e - 1) % k == 0:
        p = (dp * e - 1) // k + 1
        if n % p == 0:
            q = n // p
            break

同时有 dp, dq： 直接用 CRT 解密，无需计算 $d$：

由 $dp \equiv d \pmod{p-1}$ 知 $m \equiv c^{dp} \pmod{p}$（因为 $c^{dp} \equiv c^d \equiv m \pmod{p}$，其中 $c^d = c^{k(p-1) + dp}$ 且费马小定理消去 $c^{k(p-1)}$）。同理 $m \equiv c^{dq} \pmod{q}$。联立用 CRT 还原 $m \bmod n$：

inv_q = gmpy2.invert(q, p)
mp = pow(c, dp, p)
mq = pow(c, dq, q)
m = (((mp - mq) * inv_q) % p) * q + mq

$n = p^r$

$n$ 是单个素数的幂，无独立的 $q$。

$\varphi(p^r)$ 的推导： 区间 $[1, p^r]$ 中共 $p^r$ 个整数。与 $p^r$ 不互素的数必定是 $p$ 的倍数：$p, 2p, 3p, \dots, p^{r-1} \cdot p$，共 $p^{r-1}$ 个。因此：

$$ \varphi(p^r) = p^r - p^{r-1} = p^{r-1}(p-1) $$

这也是 $\varphi$ 函数积性在单素数幂场景的直接结果。

p = gmpy2.iroot(n, r)[0]
phi_n = p**r - p**(r-1)
d = gmpy2.invert(e, phi_n)
m = pow(c, d, n)

$e$ 与 $\varphi(n)$ 不互素

$\gcd(e, \varphi(n)) = t > 1$ 时，$e$ 在模 $\varphi(n)$ 下不存在逆元，无法按常规方式生成 $d$。此时将 $e$ 约去公因子：令 $e' = e/t$，则 $\gcd(e', \varphi(n)) = 1$，可求 $d'$ 满足 $e' \cdot d' \equiv 1 \pmod{\varphi(n)}$。

解密过程变为：

$$ c^{d'} \equiv m^{e \cdot d'} \equiv m^{t \cdot e' \cdot d'} \equiv m^t \pmod{n} $$

即解密得到 $m^t$，再在整数域上开 $t$ 次根恢复 $m$。前提是 $t$ 足够小且 $m^t < n$（否则需要枚举 $k$ 修正，类同低加密指数攻击）。

t = gmpy2.gcd(e, phi_n)
d = gmpy2.invert(e // t, phi_n)
m_t = pow(c, d, n)
m = gmpy2.iroot(m_t, t)[0]

已知 $e, d, n$ 恢复 $p, q$

同时拥有公钥和私钥时，可在不分解 $n$ 的情况下恢复 $p, q$。

原理： $ed - 1$ 是 $\varphi(n) = (p-1)(q-1)$ 的倍数。令 $ed - 1 = 2^s \cdot t$（$t$ 为奇数）。

考虑模 $n$ 下的乘法群 $\mathbb{Z}_n^*$。由 Carmichael 定理，对任意 $g \in \mathbb{Z}_n^*$ 有 $g^{\varphi(n)} \equiv 1 \pmod{n}$，因此 $g^{ed-1} \equiv 1 \pmod{n}$。

关键观察：$x^2 \equiv 1 \pmod{n}$ 在 $n = pq$ 时有四个平方根：$\pm 1, \pm x_0$（其中 $x_0 \equiv 1 \pmod{p}, x_0 \equiv -1 \pmod{q}$）。若随机选取 $g$ 并计算 $g^{t}, g^{2t}, g^{4t}, \dots, g^{2^s t}$，必有一项 $x$ 是非平凡的平方根（$x \not\equiv \pm 1$ 但 $x^2 \equiv 1$），此时 $\gcd(x-1, n)$ 必为 $p$ 或 $q$。

该算法成功的概率至少为 $1/2$（每次尝试失败后换一个 $g$ 即可）。

k = e * d - 1
while True:
    g = random.randint(2, n - 1)
    t = k
    while t % 2 == 0:
        t //= 2
        x = pow(g, t, n)
        if x > 1 and gmpy2.gcd(x - 1, n) > 1:
            p = gmpy2.gcd(x - 1, n)
            q = n // p
            return p, q

PEM 文件解析

from Crypto.PublicKey import RSA

with open('pubkey.pem', 'rb') as f:
    key = RSA.import_key(f.read())
    print(key.n, key.e)

# 私钥文件同理，额外包含 .d .p .q

其他攻击方向

• Coppersmith — $p$ 高位已知时，在 sage 中用 small_roots 求解
• Franklin-Reiter — 两条明文仅差已知固定值时，用 sage 求多项式 GCD
• Boneh-Durfee — Wiener 的增强版，$d < n^{0.292}$ 时适用
• 高位攻击 / 格基归约 — 利用 LLL 处理部分已知比特

参考文献

1. Rivest R L, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems [J]. Communications of the ACM, 1978.
2. Boneh D. Twenty Years of Attacks on the RSA Cryptosystem [J]. Notices of the AMS, 1999.
3. Wiener M J. Cryptanalysis of Short RSA Secret Exponents [J]. IEEE Trans. on Info. Theory, 1990.
4. Håstad J. Solving Simultaneous Modular Equations of Low Degree [J]. SIAM J. on Computing, 1988.