Crypto 方向 RSA 常见攻击手法

引言

RSA 是 CTF Crypto 方向出现频率最高的题目类型，原因很直接：它的安全性完全依赖于「大整数分解很难」这一个假设，而题目一旦把参数选得不标准，这个假设就立刻失效。出题人不会让你去分解一个正常的 2048 位模数，他会让 e 等于 3、让 p 和 q 只差几百、让两组密钥共享一个素因子、或者让私钥指数 d 小到可以用连分数逼近。

这类题有一个共同的特征：拿到 n、e、c 三个数之后，先不要写代码，先做一轮参数体检。看 e 是不是异常小或异常大，看 n 的位数是否与预期一致，看 n 能否被小素数整除，看是否同时给了多组参数。绝大多数的「RSA 攻击」在体检阶段就已经确定方向了，剩下的只是套用对应的数学工具。

本文与 Crypto 方向古典密码与现代密码 构成完整的一对：那篇讲对称密码与编码，这篇讲公钥体系。两者的攻击哲学其实是一致的，都是寻找「实现层面的退化」，只不过 RSA 的退化更多表现为数论参数的异常，而不是模式与随机数的误用。

按攻击目标划分，本文会依次覆盖四类问题：明文太小或指数太小（小公钥指数）、私钥太小（Wiener 与 Boneh-Durfee）、模数本身可分解（Fermat、Pollard p 减 1、共模）、以及结构泄漏（Coppersmith、非互素、随机数预测）。最后一节会回到真实工程，说明为什么生产系统不会遇到这些问题，以及 PKCS#1 v1.5 与 OAEP 的差别到底在哪。

目录

1. RSA 数学基础与 CTF 参数形态
2. 小公钥指数：直开方与 Håstad 广播攻击
3. 小私钥指数：Wiener 连分数与 Boneh-Durfee
4. 模数分解：Fermat 与 Pollard p 减 1
5. 共模攻击与多密钥泄漏
6. 已知高位与低位：Coppersmith 方法
7. 非互素、多素数与其他参数变体
8. 随机数预测与密钥恢复
9. 工具链与真实工程启示

1. RSA 数学基础与 CTF 参数形态

RSA 的全部数学就是三行。选两个大素数 p、q，令 n = p*q，φ(n) = (p-1)*(q-1)；选 e 与 φ(n) 互素，求 d = e^(-1) mod φ(n)；加密 c = m^e mod n，解密 m = c^d mod n。正确性来自欧拉定理：m^(e*d) = m^(1 + k*φ(n)) ≡ m (mod n)。

from Crypto.Util.number import getPrime, inverse

p, q = getPrime(1024), getPrime(1024)
n = p * q
phi = (p - 1) * (q - 1)
e = 65537
d = inverse(e, phi)
m = int.from_bytes(b"flag{example}", "big")
c = pow(m, e, n)
assert pow(c, d, n) == m          # 正常参数下加解密可逆

CTF 题目给的参数组合本身就是最强的提示。下面这张表是参数体检的第一轮筛查清单：

一个常被忽略的检查是「n 是不是完全平方数」以及「n 是否被小素数整除」。这两条用一行 gmpy2.is_square 与试除法就能排除，却能省下大量时间。

推导时反复用到的恒等式只有几个，记住它们比记住攻击名字更有用：

n - phi(n) + 1 = p + q                    # 从 n 与 phi 反推 p+q
(p - q)^2 = (p + q)^2 - 4*n               # 判别式，用于韦达定理求解
e*d - 1 = k * phi(n)                      # k 是小整数，通常 1 到 e 之间
m^(e*d) = m^(1 + k*phi(n)) ≡ m (mod n)    # 欧拉定理保证解密正确

这几行是所有分解类攻击的共同骨架：只要能拿到 p+q 或者 k，剩下的就是解一元二次方程。

2. 小公钥指数：直开方与 Håstad 广播攻击

当 e 很小且明文也很小时，m^e 可能还没有超过 n，此时模运算根本没起作用，密文就是明文的整数次幂，直接开方即可还原。

from gmpy2 import iroot

def low_exponent_root(c, e, n, rounds=200000):
    for k in range(rounds):              # 明文可能被叠加了若干轮 n
        root, exact = iroot(c + k * n, e)
        if exact:
            return int(root)
    return None

即使 m^e > n，只要溢出的倍数 k 不大，枚举 k 依然能在秒级内解出。这是 CTF 里 e 等于 3 的题目最常见的形态。

更强的变体是 Håstad 广播攻击：同一个明文 m 用三组不同的模数 n1, n2, n3 加密，且 e 都等于 3。由中国剩余定理可以把三个密文组合成一个模 n1*n2*n3 的同余式，而 m^3 < n1*n2*n3，于是组合结果就是 m^3 本身，开三次方即得明文。

from sympy.ntheory.modular import crt
from gmpy2 import iroot

M = crt([n1, n2, n3], [c1, c2, c3])[0]   # 组合出 m^3 mod n1*n2*n3
m = int(iroot(M, 3)[0])                   # 因为 m^3 小于模数，直接开方

防御结论非常明确：e 取 65537，且加密前必须做随机化填充（OAEP）。填充的核心作用是让 m 变成一个接近 n 量级、每次加密都不同的随机化大整数，从而同时消灭「值太小」和「相同明文产生相同密文」这两个前提。

相关消息攻击

与广播攻击同源的还有「相关消息攻击」（Franklin-Reiter）。当两条明文之间存在已知的线性关系 m2 = a*m1 + b，且用同一个 n、同一个小的 e 加密时，两个密文构成一个方程组，可以用多项式的最大公因式把 m1 求出来：

from sage.all import PolynomialRing, Zmod, gcd

P = PolynomialRing(Zmod(n), 'x')
x = P.gen()
f1 = x ^ e - c1
f2 = (a * x + b) ^ e - c2
g = gcd(f1, f2)                 # 两式相减后的公共根就是 m1
m1 = int(-g[0] / g[1])

这条攻击同样只在「无填充 + 小指数 + 已知线性关系」三个条件同时满足时成立，而 OAEP 的随机化会让 m2 = a*m1 + b 这个前提直接崩塌。

3. 小私钥指数：Wiener 连分数与 Boneh-Durfee

Wiener 攻击针对的是「为了加速解密而把 d 取得过小」的实现错误。当 d < n^0.25 / 3 时，e/n 的连分数展开的某个收敛子恰好就是 k/d。攻击流程是枚举所有收敛子，把每个候选当作 k/d，反推 φ(n) = (e*d - 1) / k，再用韦达定理求解 p、q。

from gmpy2 import isqrt

def wiener(e, n):
    # 枚举 e/n 的连分数收敛子 h/k，检验候选 d 是否成立
    cf, num, den = [], e, n
    while den:
        cf.append(num // den)
        num, den = den, num - (num // den) * den
    h0, h1, k0, k1 = 0, 1, 1, 0
    for a in cf:
        h0, h1 = h1, a * h1 + h0
        k0, k1 = k1, a * k1 + k0
        k, d = h1, k1
        if k == 0:
            continue
        if (e * d - 1) % k:              # φ(n) 必须是整数
            continue
        phi = (e * d - 1) // k
        s = n - phi + 1                  # p + q
        disc = s * s - 4 * n             # 判别式需为完全平方
        if disc >= 0 and isqrt(disc) ** 2 == disc:
            return (s + isqrt(disc)) // 2, (s - isqrt(disc)) // 2
    return None

Boneh-Durfee 把这个界推进到 d < n^0.292，代价是要构造二维格并做 LLL 约简，通常直接用 sage 实现或调用现成脚本。超过 0.292 之后就没有多项式时间的通用方法了，这也是为什么「d 取小一点加速解密」在实践中极其危险：常见的 d 缩减策略（例如只取一半比特）几乎必然落进可攻击区间。

工程启示

生产环境的正确做法是让库自己生成密钥，不要在 d 上做任何优化。RSA 解密的性能瓶颈应该用中国剩余定理（CRT 加速，把模幂拆到 p、q 上，约 4 倍提升）或直接迁移到椭圆曲线/Ed25519 来解决，而不是缩短私钥指数。

4. 模数分解：Fermat 与 Pollard p 减 1

如果 p 和 q 生成得不够独立，模数本身就会变得可分解。最常见的是两者数值接近：此时 n = p*q = ((p+q)/2)^2 - ((p-q)/2)^2，从 ceil(sqrt(n)) 开始往上试，几步之内就能找到。

from gmpy2 import isqrt, is_square

def fermat(n, limit=10_000_000):
    a = isqrt(n) + 1
    for _ in range(limit):
        b2 = a * a - n
        if is_square(b2):
            b = isqrt(b2)
            return int(a - b), int(a + b)
        a += 1
    return None

另一种退化是 p-1 只有小素因子（即 B 光滑）。此时对任意底数 a，a^(B!) ≡ 1 (mod p)，于是 gcd(a^(B!) - 1, n) 直接给出 p。这就是 Pollard p 减 1 算法。

from math import gcd

def pollard_pm1(n, B=100000):
    a = 2
    for j in range(2, B):
        a = pow(a, j, n)
        if j % 1000 == 0:                # 定期检查，避免全程空转
            g = gcd(a - 1, n)
            if 1 < g < n:
                return g
    return None

防御上只有一条：p 与 q 必须由密码学安全的随机源独立生成，且要求两者差值足够大（经验值是至少 2^512 量级）。任何「用固定种子生成素数」「用相邻素数」「用 p 减 1 光滑的素数做演示」的做法都只适合教学靶场。

已知 d 时如何分解 n

如果私钥指数 d 本身被泄露，题目往往不是让你直接解密，而是让你「用 d 分解 n」，因为这能证明私钥文件泄露的破坏力。思路是利用 e*d - 1 = k*phi(n) 这个关系，把 e*d - 1 写成 2^s * t 的形式，然后随机取底数 a，计算 a^t, a^(2t), ... 直到出现非平凡平方根：

from random import randrange
from math import gcd

def factor_with_d(n, e, d):
    k = e * d - 1
    s = 0
    while k % 2 == 0:                 # 提取因子 2
        k //= 2
        s += 1
    for _ in range(100):
        a = randrange(2, n - 1)
        x = pow(a, k, n)
        for _ in range(s):
            y = pow(x, 2, n)
            if y == 1 and x not in (1, n - 1):
                p = gcd(x - 1, n)
                if 1 < p < n:
                    return int(p), int(n // p)
            x = y
    return None

这条路径的工程含义是：d 与 p、q 是等价的秘密，泄露 d 不能只当作「一条消息被解出」，而应当按整份私钥泄露做应急响应与密钥轮换。

5. 共模攻击与多密钥泄漏

共模攻击利用的是「同一模数被两组密钥复用」。设 e1 与 e2 互素，由扩展欧几里得可以求出 s1*e1 + s2*e2 = 1，于是：

c1^s1 * c2^s2 = m^(e1*s1) * m^(e2*s2) = m^(e1*s1 + e2*s2) = m (mod n)

def common_modulus(n, e1, c1, e2, c2):
    # 扩展欧几里得求 s1*e1 + s2*e2 = 1
    old_r, r, old_s, s = e1, e2, 1, 0
    while r:
        q = old_r // r
        old_r, r = r, old_r - q * r
        old_s, s = s, old_s - q * s
    s1, s2 = old_s, (old_r - old_s * e1) // e2
    if s1 < 0:                           # 负指数要先求模逆
        c1, s1 = pow(c1, -1, n), -s1
    if s2 < 0:
        c2, s2 = pow(c2, -1, n), -s2
    return pow(c1, s1, n) * pow(c2, s2, n) % n

如果 gcd(e1, e2) = g > 1，同样的方法只能还原出 m^g，还需要再开 g 次方或结合其他条件。另一条相关路径是「多组模数共享素因子」：只要把任意两个 n 做一次 gcd，若结果不等于 1 也不等于 n，就直接拿到了公因子，进而分解两组密钥。这在真实世界出现过多次，根源都是随机数生成器熵不足。

防御上，模数绝不能复用，每组密钥必须独立生成；同时要监控并拒绝共享素因子的证书，这也是各种「RSA 密钥体检」工具做的事。

6. 已知高位与低位：Coppersmith 方法

Coppersmith 方法解决的是「已知部分比特」的问题：已知明文的高位，或者已知 p 的高位。它的数学基础是格约简（LLL），在 sage 里封装成了 small_roots，直接调用即可。

以「已知明文高位」为例：设 m = m_hi + x，其中 x 小于 n^(1/e)，构造多项式 f(x) = (m_hi + x)^e - c mod n，求它的小根：

n, e, c = ...                                 # 以下代码在 sage 环境执行
m_hi = 0x666c61677b0000000000000000          # 已知高位，低位未知
kbits = 64                                    # 未知低位比特数
P.<x> = PolynomialRing(Zmod(n))
f = (m_hi + x) ^ e - c
roots = f.small_roots(X=2 ^ kbits, beta=1)
m = m_hi + int(roots[0])

「已知 p 高位」是同一套方法的应用：把 p = p_hi + x 代入，构造以 x 为变量的多项式，因为 f(x) ≡ 0 mod p 而 p 是 n 的因子，small_roots 能在 x < n^0.25 的范围内把 p 找出来。

适用边界

Coppersmith 不是万能的，它的成功率取决于未知比特数与 n 的位数之比。经验值是：e 等于 3 时未知部分要小于 n^(1/3)，已知 p 高位时要小于 n^0.25。超过这个界，格约简就无法给出可用的短向量。防御结论同样简单：密钥生成必须使用完整熵的随机源，任何「为了可复现而固定部分比特」的做法都会直接打开这扇门。

7. 非互素、多素数与其他参数变体

除了上面几类主线，CTF 里还有一批「参数构造异常」的题目，处理方式各不相同。

第一种是 gcd(e, φ(n)) != 1。此时 e 在模 φ(n) 下没有逆，无法按标准流程求 d。常见处理是先求出 m^g（g 为公约数），再用枚举开方或结合明文格式约束求解。题目里如果 e 与 φ(n) 不互素，通常会额外给出提示，比如明文较短或已知前缀。

第二种是 p 与 q 不互素，极端情况是 p == q，此时 n 是完全平方数，isqrt(n) 直接给出 p。

第三种是多素数 RSA：n = p*q*r，此时 φ(n) = (p-1)*(q-1)*(r-1)。数学上完全成立，安全性略低于同长度的双素数版本，但只要三个素因子都足够大就没问题。题目特征往往是 n 的位数与通常的 1024 或 2048 不符。

第四种是给了 dp = d mod (p-1) 这类中间量。它同样可以用来分解 n：

def factor_with_dp(n, e, dp):
    for k in range(1, e):                # k 的实际取值范围很小
        if (e * dp - 1) % k:
            continue
        p = (e * dp - 1) // k + 1
        if 1 < p < n and n % p == 0:
            return int(p), int(n // p)
    return None

这些变体的共同教训是：RSA 的安全边界不只取决于位数，还取决于每一个中间量是否被泄露。真实系统里私钥文件包含 p、q、dp、dq、qinv，任何一项泄露都等价于私钥泄露，因此密钥存储的保护等级必须按「全部泄露」来设计。

8. 随机数预测与密钥恢复

有一类 RSA 题目不攻击算法本身，而是攻击生成密钥的随机数。最典型的是线性同余生成器（LCG）：x_{n+1} = (a*x_n + c) mod m。如果攻击者拿到连续三个输出，就能直接解出 a 与 c：

def lcg_recover(x0, x1, x2, m):
    a = (x2 - x1) * pow(x1 - x0, -1, m) % m    # 差分消去 c
    c = (x1 - a * x0) % m
    return a, c

如果模数 m 本身未知，则需要更多输出并用格方法求解：把连续输出写成关于 a、c、m 的多项式，构造格并做 LLL 约简，即可在若干组输出之后恢复全部参数。一旦 a、c、m 全部恢复，后续所有输出都可预测，包括被当作素数候选的数值。CTF 里常见的形态是「p、q 由 LCG 连续生成」或者「用 random 模块生成素数」。

Python 的 random 是 MT19937，状态空间只有 624 个 32 位字，泄露足够多的输出后可以用线性代数完整恢复内部状态：

from randcrack import RandCrack

rc = RandCrack()
for value in leaked:               # 需要 624 个完整的 32 位 getrandbits 输出
    rc.submit(value)
predicted_prime = rc.predict_getrandbits(1024)   # 预测下一个「素数候选」

这与对称密码那一篇里讲的 PRNG 问题是同一个根因：统计随机数生成器的输出序列在数学上是可逆的，而密码学安全的生成器（secrets、os.urandom、crypto/rand）刻意设计成不可预测。两者的区别不在「看起来随机不随机」，而在「给定足够输出能否反推内部状态」。

工程启示

密钥生成必须使用操作系统的 CSPRNG，并且应该直接调用标准库的密钥生成接口（cryptography 的 rsa.generate_private_key、OpenSSL 的 genrsa），而不是自己写「找素数」的循环。自实现密钥生成最常见的两个错误，一是随机源不是 CSPRNG，二是素数测试用了确定性不足的伪素性检验。

9. 工具链与真实工程启示

CTF 的 RSA 题目有相当成熟的工具生态，但理解原理比记住工具更重要，因为出题人往往会在标准手法上再加一层变形。

真实工程为什么不会遇到这些

回到生产系统，这些攻击之所以不成立，靠的是三条工程约束。其一，密钥由经过审计的库生成，e 固定 65537、p 与 q 独立随机、位数 2048 起步（新系统建议 3072，NIST 已计划 2030 年前淘汰 1024），d 不做任何缩减。其二，加密使用 OAEP 填充而不是裸 RSA，OAEP 引入随机性并保证明文长度接近模数，从根上消灭了「小指数直开方」与「相同明文相同密文」。

其三，也是历史教训最深的一条：PKCS#1 v1.5 填充对 Bleichenbacher 式攻击是脆弱的。1998 年提出的 Bleichenbacher 攻击指出，如果服务对「填充是否正确」给出可区分的响应（哪怕只是耗时差异），攻击者就能像 Padding Oracle 一样逐字节恢复明文。这就是为什么现代协议在必须兼容 v1.5 时要用常量时间实现并统一错误响应，而新设计一律使用 OAEP。认证与会话层的整体设计可以对照 认证与会话安全 ，工具链的完整梳理见 CTF 工具链与攻击视角下的防御 。

密钥长度与迁移节奏

长度选择上有一条现成的路线图：1024 位在 2010 年前后就已不推荐，NIST 计划在 2030 年前后全面停用；2048 位是当前最低线，3072 位对应约 128 位安全强度，是长期数据与新系统的合理选择。更值得提前规划的是后量子迁移：Shor 算法一旦有足够规模的量子计算机就能在多项式时间内分解 RSA 模数，因此「先收集、后解密」的威胁已经成立，需要长期保密的数据现在就应该评估混合密钥交换（经典算法与后量子算法并行）的部署成本。

一句话总结：RSA 本身没有破，破的永远是参数与填充。

权衡取舍

从投入产出看，参数体检（看 e、看 n、做 gcd、试小因子）应该永远排在第一位，它覆盖了绝大多数题目；格方法是进阶技能，值得投入时间但不要指望它解决所有问题。

常见坑清单

1. 拿到题目直接跑工具：先做参数体检，e 的大小、n 的位数、参数组数三个信息就能定方向。
2. 忘了试 k 轮叠加：小指数直开方时明文可能被叠加了若干次 n，不枚举 k 会误判为无解。
3. 共模攻击忘记处理负指数：s 为负数时必须先求模逆，否则代码直接抛异常或算出错误结果。
4. 把 gcd 检查漏掉：多组模数之间做一次 gcd，成本极低但命中率很高。
5. 误以为 e 大就是安全：e 接近 n 恰恰是小私钥指数的强信号，应该立刻上 Wiener。
6. 忽略 n 是完全平方：p 等于 q 的题目只需一次 isqrt，但很多人不会去试。
7. Coppersmith 越界使用：未知比特数超过 n^(1/e) 的界时 small_roots 会静默返回空列表。
8. 用 random 或自写 LCG 生成密钥：MT19937 与 LCG 都可预测，等价于私钥直接泄露。
9. 只看位数不看填充：2048 位模数配上裸 RSA 加密，照样会被小指数与 Bleichenbacher 类攻击打穿。
10. 把 CTF 手法用于未授权目标：这些技术的前提是靶场与竞赛环境，真实系统的正确动作是检测与修复。

小结

RSA 的攻击面可以概括成一句话：任何让「分解 n 很难」这个前提不成立的参数选择，都会立刻变成一个可解问题。e 太小让模运算失效，d 太小让连分数逼近成功，p 与 q 太接近让 Fermat 生效，随机数可预测让模数直接暴露，部分比特泄露让格方法有出手空间。把所有手法归到「前提失效」这一个框架下，记忆负担会小很多。

学习路径上，建议按这个顺序推进：先用纯 Python 实现小指数直开方与共模攻击，理解模运算的边界；然后实现 Wiener，把连分数与 RSA 参数之间的关系吃透；接着用 gmpy2 写 Fermat 与 Pollard p 减 1，建立对素数生成质量的直觉；最后再上手 sage 的 small_roots，把 Coppersmith 当作一个需要理解适用边界的黑盒来用。整个过程建议在本地生成参数、本地求解，不要连接任何外部服务。

最后回到工程：这套知识真正的价值在于反向指导密钥管理。选择 2048 位以上的模数、固定 e 等于 65537、使用 OAEP、用 CSPRNG 生成密钥、按「全部中间量都可能泄露」的标准保护私钥文件，这几条做到，本文列出的攻击手法就全部失效。这也是 CTF 与真实安全工作的关系：竞赛教你攻击如何成立，工程让你知道如何让它不成立。整体学习路线可以参考 CTF 竞赛全景与学习路径 。