RSA

2026-05-09/更新于 2026-08-22

加解密原理

RSA 的安全性完全依赖于逆向分解 $n$ 极难的特性。它利用了三个关键参数：

模数 $n$ ：由两个大素数 $p, q$ 相乘得到。
公钥指数 $e$ ：通常是一个固定的质数（如 65537）
私钥指数 $d$ ：满足 $e d \equiv 1 (\mod ϕ)$ 的逆元，其中 $ϕ = (p - 1) (q - 1)$ 。

由明文 $m$ 通过 $c = m^{e} (\mod n)$ 得到密文 $c$ 。RSA 是非对称加密，由密文 $c$ 通过 $m = c^{d} (\mod n)$ 还原明文 $m$ 。公钥是 $(n, e)$ ，私钥是 $(n, d)$ 。明文 $m$ 必须小于模数 $n$ ，否则会导致几乎无法恢复的信息截断。

假设有一个大于模数的明文 $m_{b i g}$ ，加密再解密后得到的是 $m_{b i g} mod n$ 。但疑问来了：加密算法 $c = m^{e} (\mod n)$ 中的 $m^{e}$ 几乎必定大于 $n$ ，就不怕发生信息截断吗？

事实上，只要参数 $e, ϕ (n)$ 互素， $m, c$ 二者必定是双射关系，即通过一方的值一定能寻找到唯一的另一方，下面给出证明。

使用反证法。假设有两个在 $(0, n - 1)$ 之间的不同明文 $m_{1}, m_{2}$ 经过 $e$ 次方后得到了同一个密文 $c$ ：

m_{1}^{e} \equiv c (\mod n), m_{2}^{e} \equiv c (\mod n)

对这两个等式同时进行 $d$ 次方，其中 $d$ 是 $e$ 在模 $ϕ (n) = (p - 1) (q - 1)$ 下的逆元：

m_{1}^{e d} \equiv c^{d} (\mod n), m_{2}^{e d} \equiv c^{d} (\mod n)

这里先引入欧拉定理。在模 $n$ 环上，让一个和 $n$ 互素的数 $m$ 不断自乘（即 $m^{i}$ ），其结果具有周期性。每当 $i$ 落入 $ϕ (n)$ 的倍数时，结果就会回到 $1$ ，即

m^{k \cdot ϕ (n)} \equiv 1 (\mod n), k = 0, 1, 2, \dots

当模数为质数 $p$ 时，欧拉函数 $ϕ (p) = (p - 1)$ 。此时欧拉定理退化为费马小定理：

a^{p - 1} \equiv 1 (\mod p)

其中 $gcd (a, p) = 1$ ，即 $a$ 不是 $p$ 的倍数。

回到原证明。由 $d$ 的定义 $e \cdot d \equiv 1 (\mod ϕ (n))$ ， $e d = 1 + k \cdot ϕ (n)$ 。代入回 $m^{e d}$ ：

m^{e d} = m \cdot m^{k \cdot ϕ (n)} \equiv m \cdot 1 = m (\mod n)

最终得到的是

m_{1} \equiv c^{d} (\mod n), m_{2} \equiv c^{d} (\mod n)

$c^{d} mod n$ 在 $(0, n - 1)$ 内是唯一的，因此有

m_{1} \equiv m_{2} (\mod n)

而 $m_{1}, m_{2} \in (0, n - 1)$ ，于是 $m_{1} = m_{2}$ 。

我们开始假设的是 $m_{1} \neq m_{2}$ ，矛盾了，因此原命题成立。

由此我们就证明了 $f (m) = m^{e} (\mod n)$ 是一个双射映射，且只要 $gcd (e, ϕ (n))$ 成立，私钥 $d$ 就必然存在，使得每个 $c$ 都能找到属于自己的，唯一的 $m$ 。

攻击面

参数不当

如果 RSA 体制的参数（如 $p, q, n, e, d$ ）选择不当，就会导致可能的漏洞。

质数 $p, q$ ：
- $p, q$ 过小。这是最直接的缺陷，可以通过分解大素数的网站 http://www.factordb.com 来直接分解 $n$ 得到 $p, q$ 。如果 $p, q$ 都是 512 位及以上，那基本就不用想了。
- $p, q$ 相差过小，精确来说，当 $| p - q | \leq n^{1 / 4}$ 时，费马分解法大概就能生效。
- $p, q$ 相差过大，不过做题中这种情况几乎没有。
- $p - 1$ 或 $p + 1$ 光滑（即质数 $p$ 在减去 1 或加上 1 后，所有质因子都很小），使用 Pollard’s $p - 1$ 算法 或 Williams’s $p + 1$ 算法，能够高效攻击。
上述的所有漏洞都可以调用 yafu 工具进行攻击。
公钥指数 $e$ ：
- $e$ 过小（如 $e = 3$ ），此时若是同一明文 $m$ 被加密多次，就是小加密指数广播攻击。
- Rabin 加密（ $e = 2$ 的特例）
- $e$ 与 $ϕ (n)$ 不互质，结合 AMM 算法实现攻击。
私钥指数 $d$ ：
- $d$ 过小（ $d < \frac{1}{3} n^{1 / 4}$ ），维纳攻击，以及 Boneh Durfee 攻击。

数据泄露

有些题目会泄露 $p, q$ 的中间值或高低位。

CRT 数据泄露，即 $d p, d q$ 泄露。
中间值泄露，如 $p + q$ 、 $p^{2} + q^{2}$ 、 $a p + b q$ 等等。需要灵活使用数论定理。
高低位泄露，使用 Coppersmith 和格密码处理。

过程失误

加密过程导致加密体制易受攻击。

共模攻击。两段及以上密文使用了同样的 $n$ 但不同的 $e$ ，此时可以使用扩展欧几里得算法。
小明文攻击。明文和 $e$ 都很小，直接对 $c$ 开方就能破解。
Oracle 交互，缩小明文范围来破解。

RSA 相关的攻击题目非常非常非常多…

OpenSSL 和公私钥文件

OpenSSL 是一个开源、跨平台的密码学工具包和开源软件库，包括加密算法库、协议库以及终端的命令行工具。在密码学方面，它可以实现对称加密（AES/SM4/DES）和非对称加密（RSA/ECC）等的加解密。简而言之，密码学的算法应用由 OpenSSL 落地。对于其实现的 RSA 加密，我们可以在终端执行以下命令：

openssl genrsa -out private.pem 2048 生成一个 2048 位的私钥文件
openssl rsa -in private.pem -pubout -out public.pem 从私钥文件提取公钥
openssl rsautl -encrypt -pubin -inkey public.pem -in file.txt -out file.enc 用公钥加密文件，在新版本的 OpenSSL 中，用 pkeyutl 替代 rsautl
openssl rsautl -decrypt -inkey private.pem -in file.enc -out file.dec 对应的解密

私钥文件

在终端执行命令 openssl rsa -in private.pem -text -noout，假设私钥文件完好，OpenSSL 会输出 modulus ( $n$ )，publicExponent ( $e$ )，privateExponent ( $d$ )，prime1 ( $p$ )，prime2 ( $q$ )，exponent1 ( $d (\mod p - 1)$ )，exponent2 ( $d (\mod q - 1)$ )，coefficient ( $q^{- 1} (\mod p)$ )

后三个参数用于加速解密。有关损坏的 .pem 文件，可以参考 https://blog.csdn.net/mxiaomi/article/details/51672547?sharetype = blog&shareId = 51672547&sharerefer = APP&sharesource = m0_73106878&sharefrom = link 提取部分参数，这属于数据泄露的问题。

公钥文件

执行 openssl rsa -pubin -in public.pem -text -noout，OpenSSL 会输出公钥文件包含的 $(n, e)$ 。如：

Public-Key: (512 bit)
Modulus:
    00:db:14:6d:70:bb:03:de:1f:ac:bc:10:e8:2a:59:
    ef:31:4a:3c:9f:13:ad:74:a5:a4:fc:bc:f1:72:42:
    ad:05:eb:78:1b:c8:f1:23:08:00:ba:22:97:11:16:
    e8:10:84:6e:02:18:fa:07:bd:af:63:09:85:89:3a:
    6c:27:d2:45:cd
Exponent: 65537 (0x10001)

剔除冒号和换行：

raw = """
00:db:14:6d:70:bb:03:de:1f:ac:bc:10:e8:2a:59:
ef:31:4a:3c:9f:13:ad:74:a5:a4:fc:bc:f1:72:42:
ad:05:eb:78:1b:c8:f1:23:08:00:ba:22:97:11:16:
e8:10:84:6e:02:18:fa:07:bd:af:63:09:85:89:3a:
6c:27:d2:45:cd
"""
n = raw.replace("\n", "").replace(":", "")
print(int(n, 16))

# 11474139889515860937094439001627058287359193788837184470918095463493180583872828620539844407240396269998313764108592663301050312411598240277126521860277709

攻击思路

正常解密

已知 $p, q, e, c$ ，最普通的情况：

from Crypto.Util.number import *
p = 
q = 
e = 65537
c = 
n = p*q
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))

(矩阵的)快速幂算法

顺便说一下快速幂算法。对于 pow(c, d, n)，如果我们先去算 $c^{d}$ ，再模 $n$ ，那么计算机在第一步就数据溢出了。快速幂算法是高效且必要的，具体逻辑：

根据模运算的性质， $a \times b (\mod m) = [a (\mod m) \times b (\mod m)] (\mod m)$ 。也就是说，模运算可以动态参与乘法运算。因此，先了解基本快速幂。

为了更好地理解，我们可以把指数用二进制的眼光看待。就比如 $2^{11}$ ，把指数写成二进制是 $2^{1011}$ ，也即 $2^{8} \cdot 2^{2} \cdot 2^{1}$ 。我们创建一个变量 res 用来记录结果，并初始化其为 $1$ 。二进制的权值为 $2$ ，也就是每进一位（exp // 2），这一位对应的幂相较于前一位的幂是翻倍的（base = base * base），且增长与指数位无关。因为就算该位（exp & 1）的幂不能被 res 记录（二进制位为 $0$ ），也要适配下一位的权值。在这个基础上每一步都加上模运算，就得到了快速模取幂算法：

def fast_pow(base, exp, mod):
    res = 1
    # 防止底数太大
    base = base % mod
    while exp > 0:
        if exp & 1 == 1:
            res = (res * base) % mod
        base = (base * base) % mod
        exp = exp // 2
    return res

还有矩阵版的快速幂，它和实数版差不多，常用于计算递推数列的指定项，可把时间复杂度压缩到 $O (\log n)$ 。以斐波那契数列 $F_{n} = F_{n - 1} + F_{n - 2}$ 为例，它可以写成矩阵形式：

(\begin{matrix} F_{n + 1} \\ F_{n} \end{matrix}) = (\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix}) (\begin{matrix} F_{n} \\ F_{n - 1} \end{matrix})

消项，得到矩阵版的通项公式：

(\begin{matrix} F_{n} \\ F_{n - 1} \end{matrix}) = {(\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix})}^{n - 1} (\begin{matrix} F_{1} \\ F_{0} \end{matrix})

核心思想是一致的，只不过带模版的矩阵乘法需要自己写。

def matrix_multiply_mod(A, B, mod):
    C = [[0, 0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
    return C

def matrix_fast_mod(base, exp, mod):
    # 初始化为单位矩阵，用于存储结果
    res = [[1, 0], [0, 1]]
    # 接下来几乎和实数版一致
    while exp > 0:
        if exp & 1 == 1:
            # 矩阵乘法
            res = matrix_multiply_mod(res, base, mod)
        # 更新 base，适配权重
        base = matrix_multiply_mod(base, base, mod)
        exp = exp // 2
    return res

# 求斐波那契数列第 n 项模 mod 后的值
def find_val(n, mod):
    if n == 1 or n == 2:
        return 1
    A = [[1, 1], [1, 0]] # 通项公式里的矩阵
	# 计算 A 的 n-1 次方
    A_final = matrix_fast_mod(A, n-1, mod)
    return A_final[0][0]

最终调用 find_val(n, mod)，得到斐波那契数列第 n 项模 mod 后的值。

dp 泄露

已知 $n, e, d p, c$ ，写一下数学推导：

$d p = d (\mod p - 1)$ ，展开后有 $d = d p + k_{1} (p - 1)$

$e, d$ 满足 $e d \equiv 1 (\mod ϕ (n))$ ，展开代入后有 $e d = k_{2} \cdot (p - 1) \cdot (q - 1) + 1$

将 $d = d p + k_{1} (p - 1)$ 代入，整理一下，得到 $e k_{1} (p - 1) + e \cdot d p = k_{2} (p - 1) (q - 1) + 1$

两边同模 $(p - 1)$ ， $e k_{1} (p - 1)$ 和 $k_{2} (p - 1) (q - 1)$ 是 $(p - 1)$ 的倍数，化为 $0$ ，得到：

e \cdot d p \equiv 1 (\mod p - 1)

化为普通代数式： $e \cdot d p - 1 = k (p - 1)$

等号左边都是已知的。关于 $k$ 的范围，由于 $d p = d (\mod p - 1)$ ，即 $d p < p - 1$ ，有以下不等式：

k = \frac{e \cdot d p - 1}{p - 1} < \frac{e \cdot d p}{p - 1} < \frac{e (p - 1)}{p - 1} = e

即 $k < e$ ，而 $e = 65537$ ，是可以爆破的。所以有以下脚本：

from Crypto.Util.number import *
n = 
e = 65537
dp = 
c = 
def find_p(n, e, dp):
    for k in range(1, e):
        if (e*dp - 1) % k == 0:
            p = (e*dp - 1) // k + 1
            if n % p == 0:
                return p
p = find_p(n, e, dp)
q = n // p
d = pow(e, -1, (p-1)*(q-1))
m = pow(c, d, n)
print(long_to_bytes(m))

dp, dq 泄露 & CRT 加速

有 $p, q, d p, d q, c$ 的情况。没有公钥指数 $e$ ，私钥指数 $d$ 也不易得。这个时候可以先尝试常见的 $e$ 值（如 3、5、17、257、65537 等），不行再去正经写。数学推导：

根据 $d p$ 的定义 $d p = d (\mod p - 1)$ ，得到 $d p = d + k (p - 1)$

于是 $c^{d p} \equiv c^{d + k (p - 1)} \equiv c^{d} \cdot (c^{p - 1})^{k} (\mod p)$

提出 $c^{p - 1} (\mod p)$ ，由费马小定理，有 $c^{p - 1} \equiv 1 (\mod p)$

代入， $c^{d p} \equiv c^{d} \equiv m (\mod p)$ ，同理可证 $c^{d q} \equiv m (\mod q)$

使用 CRT 合并求解 $m$ 即可。sage 脚本：

# sage
from Crypto.Util.number import *
p = 
q = 
dp = 
dq = 
c = 
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
m = crt([m1, m2], [p, q])
print(long_to_bytes(m))

事实上这就是 CRT 加速 RSA 的原理。

(ex)CRT & (ex)GCD

接下来讲一下普通 CRT。

假设我们有 $k$ 个同余方程，所有模数 $m_{i}$ 两两互质：

x \equiv a_{1} (\mod m_{1}), x \equiv a_{2} (\mod m_{2}), \dots, x \equiv a_{k} (\mod m_{k})

我们的目标是构造出一个 $x$ ，使得其满足以上的所有条件。假设 $x = X_{1} + X_{2} + \dots + X_{k}$ ，那么如果每个 $X_{i}$ 满足对 $m_{i}$ 的模为 $a_{i}$ ，对除 $m_{i}$ 以外的 $m$ 模为 0，那么就有：

x \equiv X_{1} + X_{2} + \dots + X_{k} \equiv a_{i} (\mod m_{i})

接下来如何寻找 $X_{i}$ 呢？首先要满足 $X_{i}$ 对除 $m_{i}$ 以外的 $m$ 模为 0。对于这个特性，记 $M = \prod_{i = 1}^{n} m_{i}$ ，只需让 $M_{i} = \frac{M}{m_{i}}$ 成为 $X_{i}$ 的因数。因为 $M_{i}$ 是除 $m_{i}$ 外所有 $m$ 的乘积，所以带有 $M_{i}$ 的 $X_{i}$ 模上其它 $m$ ，结果一定是 $0$ 。

因此 $X_{i}$ 的结构初步定为 $C \cdot M_{i}$ ， $C$ 是未知量。此时看第二个特性，要让 $X_{i}$ 模 $m_{i}$ 的结果是 $a_{i}$ 。回想模逆元的定义，此时 $X_{i} = C \cdot M_{i}$ 。由于 $m_{i}$ 两两互质，所以由 $M_{i} = \frac{M}{m_{i}}$ 得到的 $M_{i}$ 一定与 $m_{i}$ 互质。故一定存在 $t_{i}$ ，满足 $t_{i} \cdot M_{i} \equiv 1 (\mod m_{i})$ 。要想让等式右边变成 $a_{i}$ ，只需两边同乘 $a_{i}$ 即可。故未知数 $C = t_{i} \cdot a_{i}$ ，即

X_{i} = t_{i} \cdot a_{i} \cdot M_{i}

其中 ti = pow(Mi, -1, mi)。最后对 $M$ 取模，得到：

x = \sum_{i = 1}^{k} t_{i} \cdot a_{i} \cdot M_{i} (\mod M)

对于 $m_{i}$ 两两不互素的情况，就需要使用 exCRT 来处理。提取出同余方程组的前两个方程

x \equiv a_{1} (\mod m_{1}), x \equiv a_{2} (\mod m_{2})

为例，改写成普通的代数式：

x = a_{1} + k_{1} m_{1}, x = a_{2} + k_{2} m_{2}

消去 $x$ ，移项得到

m_{1} k_{1} - m_{2} k_{2} = a_{2} - a_{1}

将 $k$ 视为未知数，就得到了二元一次方程 $A x + B y = C$ 。其中 $A = m_{1}, B = - m_{2}, C = a_{2} - a_{1}, x = k_{1} . y = k_{2}$ 。由贝祖定理（我更喜欢它的另一个名字，裴蜀定理），令 $d = gcd (A, B)$ 。如果 $d$ 整除 $C$ ，那么方程 $A x + B y = C$ 有整数解。这里引出第一个判定条件，只有 (a2-a1) % gcd(m1,m2) == 0，方程才有整数解。在开始下一步之前，先讲一下扩展欧几里得算法。

$d = gcd (A, B)$ ，通过 exGCD，可以求出满足 $A x + B y = d$ 的一组特解 $(x, y)$ 。

先由 GCD 求出它们的最小公倍数。 $gcd (a, b) = gcd (b, a mod b)$ ，直到后者为 $0$ 时，返回 $gcd (x, 0) = x$ 。假设 $A = 18, B = 7$ ，演示一下 exGCD 的过程：

$18 \div 7 = 2 \dots 4$ ，余数 $4 = 18 - 7 \times 2$ 。记 $R_{1} = 4$ ， $R_{1} = A - 2 B$ 。
$7 \div 4 = 1 \dots 3$ ，余数 $3 = 7 - 4 \times 1$ 。记 $R_{2} = 3$ ， $R_{2} = B - R_{1}$ 。
$4 \div 3 = 1 \dots 1$ ，余数 $1 = 4 - 3 \times 1$ 。得到 $1 = R_{1} - R_{2}$ 。
上一步余数为 $1$ ，导致此式的余数一定为 $0$ 。exGCD 从余数为 $0$ 的上一式（即 3 式）开始递归代入。

将 $R_{2} = B - R_{1}$ 代入 $1 = R_{1} - R_{2}$ ，得到 $1 = 2 R_{1} - B$ 。再将 $R_{1} = A - 2 B$ 代入，得到 $1 = 2 A - 5 B$ 。由此我们便可以得到一组特解 $(2, - 5)$ 。因此，exGCD 可以用递归思想来写。当 $b = 0$ 时，说明等式变为了 $a \cdot x + 0 \cdot y = a$ ，此时取 $x = 1, y = 0$ ，并且公约数就是 $a$ 。假设递归调用的 exGCD 已经为我们返回了下一级方程

b \cdot x + (a mod b) \cdot y = gcd

的已知特解 $(x_{n e x t}, y_{n e x t})$ ，根据除式规则， $a mod b = a - b \cdot (a / / b)$ 。做代换，得到

b \cdot x_{n e x t} + [a - b \cdot (a / / b)] \cdot y_{n e x t} = gcd

拆括号后化简合并，有

a \cdot (y_{n e x t}) + b \cdot [x_{n e x t} - (a / / b) \cdot y_{n e x t}] = gcd

对比目标等式 $a x + b y = gcd$ ，容易发现：

x = y_{n e x t}, y = x_{n e x t} - (a / / b) \cdot y_{n e x t}

于是得到递归返回值。通用代码如下：

def exGCD(a, b):
    if b == 0:
        return a, 1, 0
    else:
        gcd, x_next, y_next = exGCD(b, a % b)
        x = y_next
        y = x_next - (a//b) * y_next
        return gcd, x, y

继续说之前的 exCRT 问题。对于 $m_{1} k_{1} - m_{2} k_{2} = a_{2} - a_{1}$ ，我们现在可以求出一组满足 $m_{1} \cdot u + m_{2} \cdot v = d$ 的特解 $(u, v)$ 。为了把右边凑成 $(a_{2} - a_{1})$ ，左右两边同乘 $\frac{a_{2} - a_{1}}{d}$ ，即

m_{1} \cdot (u \cdot \frac{a_{2} - a_{1}}{d}) + m_{2} \cdot (v \cdot \frac{a_{2} - a_{1}}{d}) = a_{2} - a_{1}

得到 $k_{1}$ 的特解：

k_{1} = u \cdot \frac{a_{2} - a_{1}}{d}

要同时满足两个同余方程，新模数需要是两个原模数的最小公倍数。即 $M = lcm (m_{1}, m_{2})$ ，这个等式也等于 $\frac{m_{1} m_{2}}{d}$ 。由此，我们就完美地把两个同余方程合并成了一个新方程：

x \equiv (a_{1} + k_{1} m_{1}) (\mod M)

设定 $a_{n e w} = a_{1} + k_{1} m_{1}$ ， $m_{n e w} = M$ ，不断使用 exGCD，就能合并到只剩一个方程，这就是 exCRT。

共模攻击

两段及以上相同明文加密使用了同样的 $n$ 但不同的 $e$ ，得到的密文可以被轻易破解，要求 $gcd (e_{1}, e_{2}) = 1$ 。

由裴蜀定理，存在整数 $s_{1}, s_{2}$ ，使 $s_{1} e_{1} + s_{2} e_{2} = 1$ 。考虑这样一个特殊的式子：

c_{1}^{s_{1}} \cdot c_{2}^{s_{2}} (\mod n)

代入 RSA 加密式 $c = m^{e} (\mod n)$ ：

c_{1}^{s_{1}} \cdot c_{2}^{s_{2}} = m^{e_{1} s_{1}} \cdot m^{e_{2} s_{2}} = m^{e_{1} s_{1} + e_{2} s_{2}} = m^{1} = m (\mod n)

所以那个特殊的式子就等于 $m$ 。但是 $s_{1}, s_{2}$ 必然一正一负，假设 $s_{2} < 0$ ，那么 $c_{2}^{s_{2}} = (c_{2}^{- 1})^{- s_{2}} (\mod n)$ 。

$c_{2}^{- 1}$ 就是 $c_{2}$ 关于 $n$ 的模逆元，c2_inverse = pow(c2, -1, n)。最终得到 $m = c_{1}^{s_{1}} \cdot (c_{2}^{- 1})^{- s_{2}} (\mod n)$ 。听起来有点反直觉的是，如果连 $e$ 也相同，攻击者反而什么也解不出来了，因为得到的是多个完全相同的方程，退化成了最基本的 RSA。

脚本：

n = 
e1 = 
e2 = 
c1 = 
c2 = 
# 调用之前的 exGCD
gcd, s1, s2 = exGCD(e1, e2)
if s1 < 0:
    s1, s2 = s2, s1
c2_inverse = pow(c2, -1, n)
m = (pow(c1, s1, n) * pow(c2_inverse, -s2, n)) % n

低加密指数广播攻击

和共模攻击很像，这里是相同明文使用同样的 $e$ 但不同的 $n$ ，且公钥指数非常小。

正式的 RSA 加密要求 $m < n$ ，否则在 $k$ 不定的情况下，几乎无法由 $m = m_{0} + k n$ 恢复原始信息。

假设 $e = 3$ ，攻击者截获了三份密文 $c$ 和模数 $n$ ，就有：

c_{1} \equiv m^{3} (\mod n_{1}), c_{2} \equiv m^{3} (\mod n_{2}), c_{3} \equiv m^{3} (\mod n_{3})

能够得到特解 $X$ 满足 $X = m^{3} (\mod n_{1} n_{2} n_{3})$ ，最终得到 $m = \sqrt[3]{X}$ 。脚本：

# sage
e = 3
c1 = 
c2 = 
c3 = 
n1 = 
n2 = 
n3 = 
x = crt([c1, n1], [c2, n2], [c3, n3]) % (n1*n2*n3)
# 这里不要直接用 pow 函数开方
m = x.nth_root(3)

为什么叫 低加密指数攻击？因为当 $e = 65537$ 时，要想获取完整信息，就要使 $m^{65537} < n^{k}$ ，其中 $k$ 是截获消息的条数。此时就只能寄希望于有一组 $n$ 共享了大素数，即 共模质数攻击，但实际上概率也极低。

多项式的 CRT

假设上述被加密的不再是明文 $m$ ，而是明文的线性组合 $M_{i} = a_{i} \cdot m + b_{i}$ ，那么我们有以下的同余方程：

\begin{matrix} (a_{1} \cdot m + b_{1})^{3} - c_{1} \equiv 0 (\mod n_{1}) \\ (a_{2} \cdot m + b_{2})^{3} - c_{2} \equiv 0 (\mod n_{2}) \\ (a_{3} \cdot m + b_{3})^{3} - c_{3} \equiv 0 (\mod n_{3}) \end{matrix}

由于各 $M_{i}$ 不相同了，所以不能简单地 CRT 后线性还原。

展开，等号左边的多项式可以化作标准形式 $A m^{3} + B m^{2} + C m + D$ 的形式。化作首一多项式，把未知量替换为 $x$ ，就有

\begin{matrix} f_{1} (x) = x^{3} + A_{1} x^{2} + B_{1} x + C_{1} (\mod n_{1}) \\ f_{2} (x) = x^{3} + A_{2} x^{2} + B_{2} x + C_{2} (\mod n_{2}) \\ f_{3} (x) = x^{3} + A_{3} x^{2} + B_{3} x + C_{3} (\mod n_{3}) \end{matrix}

解 $x^{2}$ 的全局系数 $A$ ： $A \equiv A_{1} (\mod n_{1})$ , $A \equiv A_{2} (\mod n_{2})$ , $A \equiv A_{3} (\mod n_{3})$

解 $x$ 的全局系数 $B$ ： $B \equiv B_{1} (\mod n_{1})$ , $B \equiv B_{2} (\mod n_{2})$ , $B \equiv B_{3} (\mod n_{3})$

解常数项的全局系数 $C$ ： $C \equiv C_{1} (\mod n_{1})$ , $C \equiv C_{2} (\mod n_{2})$ , $C \equiv C_{3} (\mod n_{3})$

把求出的 $A, B, C$ 重新拼装，就得到了在全局模数 $N = n_{1} n_{2} n_{3}$ 下的新多项式 $F (x) = x^{3} + A x^{2} + B x + C \equiv 0 (\mod N)$ 。

由 Coppersmith 定理，能找到的小根上界 $X \approx N^{1 / 3} \approx n$ ，从而可以还原 $m$ 。参考脚本：

# sage
from Crypto.Util.number import *

n = []
a = []
b = []
c = []
e = 3
assert len(a + b + c + n) == 12

R1.<x> = PolynomialRing(Zmod(n[0]))
R2.<x> = PolynomialRing(Zmod(n[1]))
R3.<x> = PolynomialRing(Zmod(n[2]))

f1 = ((a[0]*R1.gen() + b[0])^e - c[0]).monic()
f2 = ((a[1]*R2.gen() + b[1])^e - c[1]).monic()
f3 = ((a[2]*R3.gen() + b[2])^e - c[2]).monic()

coeffs = []
# 合并 x^0, x^1, x^2, x^3 的系数
for i in range(e + 1):
    coeff = crt([int(f1[i]), int(f2[i]), int(f3[i])], [n1, n2, n3])
    coeffs.append(coeff)
    
prod = lambda ls: 1 if not ls else ls[0] * prod(ls[1:])
R.<x> = PolynomialRing(Zmod(prod(n)))
f = sum(x^i*coeff for i, coeff in enumerate(coeffs))
roots = f.small_roots()

if roots:
    print(long_to_bytes(int(roots[0])))

Franklin-Reiter 相关消息攻击

当两个明文之间存在已知的线性关系，并且被相同的公钥 $(n, e)$ 加密时，攻击者就能直接还原出明文。

举个例子。假如 m1 = b"0123456789abcd"，有 14 字节。为了填充到 16 字节，使用 pad() 函数之后，m2 = b"0123456789abcd\x02\x02"。那么此时二者之间就具有线性关系：

m_{2} = 2^{16} \times m_{1} + (2^{8} \times 2 + 2^{0} \times 2) (\mod n)

虽然这个攻击理论上对任何 $e$ 都成立，但算法的复杂度为 $O (e \log^{2} n)$ 。因此在实战中，通常针对较小的 $e$ 。对于有线性关系的明文 $m_{2} = a \times m_{1} + b$ ，我们先在未知数 $x$ 上构造两个定义在环 $Z_{N} [x]$ 上的多项式：

f_{1} (x) = x^{e} - c_{1} (\mod n)

f_{2} (x) = (a \cdot x + b)^{e} - c_{2} (\mod n)

易知 $x = m_{1}$ 是两个多项式的一个公共根，那么 $(x - m_{1})$ 必定是 $f_{1} (x), f_{2} (x)$ 的公因式，也即 $gcd (f_{1} (x), f_{2} (x)) = x - m_{1} (\mod n)$ ，求出这个最大公因式就能得到明文 $m_{1}$ 。

多项式的 GCD

思想基本和普通 GCD 一致，只不过在多项式环上进行：

def poly_gcd(f1, f2):
    while f2:
        f2 = f2.monic()
        f1, f2 = f2, f1 % f2
    return f1.monic()

Franklin-Reiter 相关消息攻击的脚本：

# sage
from Crypto.Util.number import *

n = 
e = 
a = 
b = 
c1 = 
c2 = 

R.<x> = PolynomialRing(Zmod(n))
f1 = x^e - c1
f2 = (a*x + b)^e - c2

def poly_gcd(f1, f2):
    while f2:
        f2 = f2.monic()
        f1, f2 = f2, f1 % f2
    return f1.monic()

g = poly_gcd(f1, f2)
if g.degree() == 1:
    # m1 就是(x - m1)的常数项取负
    m1 = int(-g[0])
    m2 = (a*m1 + b) % n
    print(f"m1 = {long_to_bytes(m1)}")
    print(f"m2 = {long_to_bytes(m2)}")

维纳攻击

维纳攻击的主要利用点是私钥指数 $d$ 过小。这个攻击成功的前提条件是：

$p < q < 2 p$ ，即 $p, q$ 大小相近，这一点是默认满足的。
私钥 $d$ 满足 $d < \frac{1}{3} N^{1 / 4}$

前面提到当 $p, q$ 差距过小时，费马分解法能直接分解 $n$ ，具体的范围是 $| p - q | \leq n^{1 / 4}$ 。在 RSA-2048 中， $p, q$ 的大小又都是 1024 位，看起来有点反直觉，好像费马分解法的应用范围很广。事实上，对于 $p, q$ ，取值区间的大小是 $2^{1023}$ ，而危险区是 $2^{512}$ ，落入危险区的概率是 $\frac{2^{512}}{2^{1023}} = \frac{1}{2^{511}}$ ，非常小，在标准 RSA 中可以认为是不可能的。

说回维纳攻击。公钥 $e$ 和私钥 $d$ 的关系是 $e d \equiv 1 (\mod ϕ (n))$ 。化作标准代数式并且两边同除以 $d \cdot ϕ (n)$ ，就可以得到：

\frac{e}{ϕ (n)} = \frac{k}{d} + \frac{1}{d \cdot ϕ (n)}

$ϕ (n) \approx n$ ，于是 $\frac{e}{n} - \frac{k}{d} \approx \frac{1}{d \cdot ϕ (n)}$ ，且等号右边极小。这里引入勒让德定理：如果一个已知数 $x$ 与一个未知分数 $\frac{a}{b}$ 间的距离 $| x - \frac{a}{b} |$ 满足 $| x - \frac{a}{b} | < \frac{1}{2 b^{2}}$ ，那么 $\frac{a}{b}$ 必定是 $x$ 的连分数展开中的一个渐进分数。Wiener 发现当私钥 $d < \frac{1}{3} N^{1 / 4}$ 时， $\frac{e}{n}$ 和 $\frac{k}{d}$ 满足勒让德定理。

推导：

| \frac{e}{n} - \frac{k}{d} | = | \frac{e d - k n}{n d} |

由 $e d = 1 + k ϕ (n)$ ，有

| \frac{e d - k n}{n d} | = | \frac{1 + k ϕ (n) - k n}{n d} | = | \frac{1 - k (n - ϕ (n))}{n d} |

把 $ϕ (n) = p q - p - q + 1$ 展开，绝对值内变号，得到

| \frac{k (p + q - 1) - 1}{n d} | < | \frac{k (p + q - 1)}{n d} |

根据维纳攻击的适用条件 $p < q < 2 p$ ，有 $p + q - 1 < 3 p - 1 < 3 p < 3 \sqrt{n}$

带入这个放缩，同时也不要忘了原始式子。得到

| \frac{e}{n} - \frac{k}{d} | < \frac{3 k \sqrt{n}}{n d} = \frac{3}{\sqrt{n}} \cdot \frac{k}{d}

RSA 公钥指数 $e$ 的基本要求就是 $1 < e < ϕ (n)$ ，且 $gcd (e, ϕ (n)) = 1$ 。于是

k = \frac{e d - 1}{ϕ (n)} < \frac{e d}{ϕ (n)} < \frac{ϕ (n) d}{ϕ (n)} = d

$k < d$ ， $\frac{k}{d} < 1$ 。于是 $\frac{3}{\sqrt{n}} \cdot \frac{k}{d} < \frac{3}{\sqrt{n}}$ 。这样，我们就把式子放缩到了极致：

| \frac{e}{n} - \frac{k}{d} | < \frac{3}{\sqrt{n}}

代入勒让德定理的要求：

\frac{3}{\sqrt{n}} < \frac{1}{2 d^{2}}

得到 $d$ 能被攻击的范围是 $d < \frac{1}{\sqrt{6}} n^{1 / 4}$ （好像不是很准？）

连分数展开

实现连分数展开，通常指把一个实数 $x$ 表示成以下形式：

x = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{a_{3} + \dots}}}

它是欧几里得算法的变体。对于任何实数 $x$ ：

取 $a_{i} = ⌊ x ⌋$ ，即 $x$ 的整数部分。
$f = x - a_{i}$ ， $x$ 的小数部分。
如果 $f \neq 0$ （即此时 $x$ 不是整数），则令 $x = 1 / f$ ，回到第一步，直到 $f = 0$ 。

对于 $\frac{k}{d}$ 这样的有理数，展开是有限的。使用上面的算法，得到的是一个连分数序列 $[a_{0}, a_{1}, a_{2}, \dots, a_{i}]$ 。想通过这样的序列还原渐进分数 $\frac{N_{i}}{D_{i}}$ ，有以下递推规则：

第 0 项：分子 $N_{0} = a_{0}$ ，分母 $D_{0} = 1$
第 1 项：分子 $N_{1} = a_{0} \cdot a_{1} + 1$ ，分母 $D_{1} = a_{1}$
第 2 项及以后：分子 $N_{i} = a_{i} \cdot N_{i - 1} + N_{i - 2}$ ，分母 $D_{i} = a_{i} \cdot D_{i - 1} + D_{i - 2}$

由于寻找 $d$ 的过程需要遍历，使用之前提到的快速幂也没有必要了，迭代就可以。需要注意的是，开头提到的标准展开方法受限于浮点数误差，需要改用辗转相除法来避免偏移。下面是脚本：

def continued_fraction(a, b):
    res = []
    while b != 0:
        # 求商和余数
        quotient = a // b
        reminder = a % b
        res.append(quotient)
        # 辗转相除法的换位
        a = b
        b = reminder
    return res

在得到连分数序列后，要想方便地得到各渐进分数，可以假设出 $i = - 1, - 2$ 两项。这样对于任意 $i \geq 0$ ，都有上面的递推方程。这两项辅助项的值分别是

N_{- 1} = 1, N_{- 2} = 0 D_{- 1} = 0, D_{- 2} = 1

再根据递推方程写脚本：

def traverse_list(ls):
    # 初始定义两个辅助项
    n_last1, n_last2 = 1, 0
    d_last1, d_last2 = 0, 1
    res = []
    for a in ls:
        # 按递推公式计算
        n = a * n_last1 + n_last2
        d = a * d_last1 + d_last2
        res.append((n, d))
        # 迭代
        n_last2 = n_last1
        n_last1 = n
        d_last2 = d_last1
        d_last1 = d
    return res

初代的脚本没有检验步骤。对于得到的每一组 $(k, d)$ ，都要经过以下检验步骤：

检测分子是否为 0，也即是否是第一层展开。是的话就筛除。
由 $e d = 1 + k ϕ (n)$ ，有 $ϕ (n) = \frac{e d - 1}{k}$ ，这个值必须是整数。
在 $ϕ_{g u e s s} (n)$ 为整数的前提下，对于质数 $p, q$ ，有方程 $p q = n, p + q = n - ϕ (n) + 1$ 。根据韦达定理， $p, q$ 必定是方程 $x^{2} - (p + q) x + p q = 0$ 的两个根，也即 $x^{2} - (n - ϕ (n) + 1) x + n = 0$ 的根。计算方程的判别式 $Δ = b^{2} - 4 a c$ ，验证 $Δ$ 是否为完全平方数。若是，则解出 $p, q$ ，得到结果。

由上面的分析，得到完整的维纳攻击脚本：

import math

e = 
n = 

def wiener_attack(e, n):
    k_last1, k_last2 = 1, 0
    d_last1, d_last2 = 0, 1
    r0, r1 = e, n
    while r1 != 0:
        q = r0 // r1
        r0, r1 = r1, r0 % r1
        k = q * k_last1 + k_last2
        d = q * d_last1 + d_last2
        k_last2, k_last1 = k_last1, k
        d_last2, d_last1 = d_last1, d
        if k == 0:
            continue
        if (e*d - 1) % k != 0:
            continue
        phi = (e*d - 1) // k
        a = 1
        b = n - phi + 1
        c = n
        delta = b*b - 4*a*c
        if delta >= 0:
            s = math.isqrt(delta)
            if s*s == delta:
                if (b + s) % 2 == 0:
                    p = (b + s) // 2
                    q = (b - s) // 2
                    if p * q == n:
                        return d, p, q
    return None, None, None

res = wiener_attack(e, n)
if res[0] is not None:
    d, p, q = res
    print(f"p = {p}")
    print(f"q = {q}")
else:
    print("没有找到解")

当公钥指数 $e$ 很大时， $d$ 就很小。这时候可以试试维纳攻击能不能生效。

Boneh-Durfee 攻击

维纳攻击还有一个使用格密码的版本，称为 Boneh-Durfee 攻击。当加密者使用同一模数 $n$ ，不同公钥指数 $e_{i}$ 加密时，若 $d$ 落入攻击范围，则可以通过 Boneh-Durfee 攻击直接得到 $p, q$ 。其中 $d$ 的受攻击范围随着 $e_{i}$ 的数目上升。当只有一个低加密指数时， $d < n^{0.292}$ 。加密指数的数目提升到两个和三个时，指数位提升至 $5 / 14 (0.357)$ 和 $2 / 5 (0.4)$ 。理论上当加密指数的数量足够多，攻击范围可以提升到 $d < n$ 。

这种攻击依赖于 coppersmith 算法，脚本放在 coppersmith 那一篇 blog 里了。