【密码学百科】RSA 从原理到攻击：教科书 RSA 为什么不安全

1977 年，罗纳德·里维斯特（Ron Rivest）、阿迪·沙米尔（Adi Shamir）与伦纳德·阿德曼（Leonard Adleman）在麻省理工学院发表了一种新的公钥加密方案，以三人姓氏首字母命名为 RSA。这是人类第一个同时可用于加密与数字签名的公钥密码体制，也是至今工业界部署最广泛的非对称算法之一。然而，教科书中那段简洁优美的数学公式只描绘了 RSA 的骨架；真实世界里，从密钥生成的每一个比特到填充方案的每一个字节，都暗藏着精巧的攻击面。本文将从最基础的密钥生成出发，逐步展示教科书 RSA 为何不安全，以及工程实践如何在数十年的攻防博弈中一步步堵住漏洞。

一、RSA 密钥生成

RSA 的安全性建立在大整数分解问题（Integer Factorization Problem）之上：给定两个大素数 p 和 q 的乘积 n = p·q，在已知 n 的情况下恢复 p、q 在计算上是不可行的。密钥生成的每一步都直接决定了这一假设能否成立。

选取大素数 p 和 q。 现代标准要求 p 和 q 各自的位长为密钥长度的一半。若密钥长度为 2048 比特，则 p 和 q 各为 1024 比特的素数。生成过程通常是在密码学安全的随机数发生器（CSPRNG）中连续采样奇数，然后对每个候选数执行 Miller-Rabin 素性测试，重复足够多轮以将误判概率压至可忽略的水平。

工程上还会对 p 和 q 施加额外限制。首先，|p − q| 必须足够大，否则费马因式分解法（Fermat factorization）能在极短时间内分解 n。其次，p − 1 和 q − 1 不应含有过小的因子，否则 Pollard 的 p − 1 算法可以轻松分解 n。满足此条件的素数常被称为”安全素数”（safe prime），即 p 和 q 的形式为 p = 2p’ + 1，其中 p’ 同样是素数。虽然并非所有标准都要求使用安全素数，但 FIPS 186-5 和许多密码库将其作为推荐实践。

选取公开指数 e。 公开指数 e 须满足 1 < e < λ(n) 且 gcd(e, λ(n)) = 1，其中 λ(n) = lcm(p − 1, q − 1) 是卡迈克尔函数（Carmichael function）。历史上曾使用 e = 3 以加速加密运算，但过小的 e 会引发后文将详述的 Håstad 攻击等一系列问题。当今的事实标准是 e = 65537（即 2^16 + 1），这是一个费马素数，其二进制表示仅含两个 1，使模幂运算只需 17 次平方加一次乘法，兼顾了效率与安全。

计算私钥指数 d。 私钥 d 是 e 对 λ(n) 的模逆元，即 d·e ≡ 1 (mod λ(n))。此值通过扩展欧几里得算法（Extended Euclidean Algorithm）在多项式时间内计算。d 的长度通常与 n 相当，约为 2048 比特。若 d 过短，则 Wiener 攻击或 Boneh-Durfee 攻击可以在多项式时间内恢复 d，这将在第六节详细讨论。

密钥长度建议。 2024 年，NIST 建议 RSA 密钥长度不低于 2048 比特以达到 112 比特的安全等级，而 3072 比特可达 128 比特安全等级。要达到 256 比特安全（对应 AES-256 的等级），RSA 密钥需要超过 15000 比特，这在性能上几乎不可接受，也正是 RSA 逐渐被椭圆曲线密码（ECC）替代的重要原因之一。

二、教科书 RSA

理解了密钥生成之后，我们先给出最原始的、未经任何修饰的 RSA 方案——即所谓”教科书 RSA”（Textbook RSA）。

加密。 设公钥为 (n, e)，明文消息 m 是一个满足 0 ≤ m < n 的整数。加密运算为：

c = m^e mod n

密文 c 同样是模 n 下的一个整数。

解密。 持有私钥 d 的接收者计算：

m = c^d mod n

正确性证明。 为什么解密能够恢复明文？根据欧拉定理（Euler’s theorem），若 gcd(m, n) = 1，则 m^φ(n) ≡ 1 (mod n)。因为 d·e ≡ 1 (mod λ(n))，存在整数 k 使得 d·e = 1 + k·λ(n)。于是：

c^d = (m^e)^d = m^(e·d) = m^(1 + k·λ(n)) = m · (m^λ(n))^k ≡ m · 1^k = m (mod n)

当 gcd(m, n) ≠ 1 时（即 m 恰好是 p 或 q 的倍数），可分别在模 p 和模 q 下验证等式成立，再由中国剩余定理（CRT）合并得到相同结论。需注意，此处使用 λ(n) = lcm(p−1, q−1) 比使用 φ(n) = (p−1)(q−1) 更为精确，因为 λ(n) 是满足 m^λ(n) ≡ 1 (mod n) 的最小正指数。

签名与验证。 教科书 RSA 的签名是加密的”镜像”操作：签名者用私钥 d 计算 σ = m^d mod n，验证者用公钥 e 检查 m ≡ σ^e (mod n)。

下面给出一个最小化的 Python 实现，仅用于演示原理，切勿将其用于任何生产环境：

import random
from math import gcd

def is_probable_prime(n, k=20):
    """Miller-Rabin 素性测试"""
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0:
        return False
    # 将 n-1 写成 2^r · d
    r, d = 0, n - 1
    while d % 2 == 0:
        r += 1
        d //= 2
    for _ in range(k):
        a = random.randrange(2, n - 1)
        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        for _ in range(r - 1):
            x = pow(x, 2, n)
            if x == n - 1:
                break
        else:
            return False
    return True

def gen_prime(bits):
    """生成指定位长的素数"""
    while True:
        p = random.getrandbits(bits) | (1 << (bits - 1)) | 1
        if is_probable_prime(p):
            return p

def extended_gcd(a, b):
    if a == 0:
        return b, 0, 1
    g, x1, y1 = extended_gcd(b % a, a)
    return g, y1 - (b // a) * x1, x1

def mod_inverse(e, phi):
    g, x, _ = extended_gcd(e % phi, phi)
    if g != 1:
        raise ValueError("模逆元不存在")
    return x % phi

def keygen(bits=2048):
    """教科书 RSA 密钥生成"""
    e = 65537
    while True:
        p = gen_prime(bits // 2)
        q = gen_prime(bits // 2)
        if p == q:
            continue
        lam = (p - 1) * (q - 1) // gcd(p - 1, q - 1)  # lcm(p-1, q-1)
        if gcd(e, lam) == 1:
            break
    n = p * q
    d = mod_inverse(e, lam)
    return (n, e), (n, d)

def encrypt(pub, m):
    n, e = pub
    return pow(m, e, n)

def decrypt(priv, c):
    n, d = priv
    return pow(c, d, n)

# 演示
pub, priv = keygen(512)  # 仅为演示，512 位极不安全
message = 42
ciphertext = encrypt(pub, message)
plaintext = decrypt(priv, ciphertext)
assert plaintext == message
print(f"明文: {message}, 密文: {ciphertext}, 解密: {plaintext}")

这段代码在数学上完全正确。但正如我们接下来将看到的那样，它在密码学意义上是彻底不安全的。

三、教科书 RSA 的致命缺陷

教科书 RSA 之所以被称为”教科书版本”，正是因为它仅存在于教科书之中，任何严肃的密码学实现都不会直接使用它。它至少存在以下几类根本性缺陷。

确定性加密——不满足 IND-CPA 安全。 相同的明文 m 在相同的公钥下总是产生相同的密文 c。这意味着攻击者可以通过观察密文是否重复来获取明文的统计信息。在实际场景中，假设一家银行使用教科书 RSA 加密转账金额，攻击者只需预先加密所有常见金额（如整百整千的数值），然后将截获的密文逐一比对，即可在毫秒级时间内推断每笔交易的金额。更严格地说，教科书 RSA 无法通过选择明文攻击下的不可区分性（IND-CPA）测试：攻击者只需选择两个明文 m0 和 m1，在收到挑战密文后自行加密 m0，若结果与挑战密文一致则明文为 m0，否则为 m1。攻击者的优势为 1，系统彻底崩塌。

乘法同态性——可锻造性。 教科书 RSA 具有乘法同态性质：若 c1 = m1^e mod n，c2 = m2^e mod n，则 c1·c2 mod n = (m1·m2)^e mod n。这意味着攻击者无需知道任何明文，即可将两段密文”融合”为一段新密文，其对应的明文恰为原始两段明文的乘积。这种可锻造性（malleability）在拍卖、电子投票等场景中是灾难性的。

更具体地说，假设攻击者拦截了密文 c = m^e mod n，想获取明文 m 但无法直接向解密预言机提交 c。攻击者可以选取任意 s，计算 c’ = s^e · c mod n，将 c’ 提交给解密预言机。预言机返回 m’ = c’^d mod n = s·m mod n，攻击者再计算 m = m’·s^(−1) mod n 即可恢复原始明文。这就是经典的”选择密文攻击”（Chosen-Ciphertext Attack, CCA）。

缺乏语义安全。 除了上述两点之外，教科书 RSA 对小消息空间完全无力抵抗穷举搜索。例如，若明文是一个 32 比特的社会保障号码，攻击者只需对 2^32 个可能值逐一加密并与密文比对。由于加密是确定性的，匹配成功即意味着解密成功。

四、Håstad 广播攻击

Håstad 广播攻击（Håstad’s broadcast attack）是最早被发现的针对低公开指数 RSA 的攻击之一。它的场景简单而实际：同一明文 m 被发送给多个接收者，每个接收者使用不同的模数 n_i 但相同的公开指数 e。

假设 e = 3，攻击者截获三段密文：

c1 = m^3 mod n1
c2 = m^3 mod n2
c3 = m^3 mod n3

由于 n1、n2、n3 两两互素（否则可直接通过 gcd 分解模数），中国剩余定理告诉我们可以唯一确定一个整数 C，使得：

C ≡ c1 (mod n1)
C ≡ c2 (mod n2)
C ≡ c3 (mod n3)
且 0 ≤ C < n1·n2·n3

因为 m < n_i 对每个 i 成立，所以 m^3 < n1·n2·n3。这意味着 C = m^3 在整数意义上成立（不涉及任何取模），攻击者只需对 C 计算整数立方根即可恢复 m。

更一般地，当公开指数为 e 时，攻击者需要截获 e 段密文即可发起攻击。这就是为什么现代实践中推荐 e = 65537 而非 e = 3 的重要原因——即使攻击者收集到了 65537 段密文，中国剩余定理重建后的整数也不等于 m^65537 在整数上的值（因为 m^65537 极为巨大）。当然，真正的防御手段是使用合适的填充方案，而非仅仅依赖较大的 e。

以下是 Håstad 攻击的 Python 演示：

from functools import reduce

def integer_cube_root(n):
    """牛顿法计算整数立方根"""
    if n < 0:
        return -integer_cube_root(-n)
    if n == 0:
        return 0
    x = 1 << ((n.bit_length() + 2) // 3)
    while True:
        y = (2 * x + n // (x * x)) // 3
        if y >= x:
            return x
        x = y

def crt(remainders, moduli):
    """中国剩余定理"""
    N = reduce(lambda a, b: a * b, moduli)
    result = 0
    for r_i, n_i in zip(remainders, moduli):
        N_i = N // n_i
        _, x, _ = extended_gcd(N_i % n_i, n_i)
        result += r_i * N_i * x
    return result % N

def hastad_attack(ciphertexts, moduli):
    """Håstad 广播攻击 (e=3)"""
    C = crt(ciphertexts, moduli)
    m = integer_cube_root(C)
    return m

# 演示：三个接收者，e=3
e = 3
keys = []
for _ in range(3):
    while True:
        p, q = gen_prime(256), gen_prime(256)
        lam = (p - 1) * (q - 1) // gcd(p - 1, q - 1)
        if gcd(e, lam) == 1:
            break
    n = p * q
    d = mod_inverse(e, lam)
    keys.append((n, e, d))

secret_message = 123456789
ciphertexts = [pow(secret_message, e, n_i) for n_i, _, _ in keys]
moduli = [n_i for n_i, _, _ in keys]

recovered = hastad_attack(ciphertexts, moduli)
assert recovered == secret_message
print(f"Håstad 攻击成功！恢复明文: {recovered}")

五、Bleichenbacher 攻击

1998 年，丹尼尔·布莱兴巴赫（Daniel Bleichenbacher）在 CRYPTO 会议上发表了一项震动密码学界的攻击。他证明了 PKCS#1 v1.5 填充方案存在填充预言机漏洞（padding oracle），攻击者可以通过自适应选择密文攻击（adaptive chosen-ciphertext attack）在大约一百万次查询内完全恢复明文。

PKCS#1 v1.5 填充格式。 在加密之前，明文 m 被编码为如下格式：

0x00 || 0x02 || [随机非零填充字节] || 0x00 || [明文数据]

其中随机填充字节至少 8 个，总长度等于密钥字节数（如 256 字节对应 2048 位密钥）。接收者在解密后检查最高两字节是否为 0x00 和 0x02，以及后续是否存在分隔符 0x00。

攻击原理。 Bleichenbacher 发现，许多 TLS 服务器在收到格式不正确的密文时会返回不同的错误消息——一种是”填充格式错误”，另一种是”解密后数据不合法”。这种差异构成了一个一比特的填充预言机。攻击者利用 RSA 的乘法同态性质，构造形如 c’ = (s^e · c) mod n 的变体密文并发送给服务器。如果服务器接受了填充格式（返回非填充错误），攻击者就知道 s·m mod n 的最高字节为 0x00 0x02，从而将 m 的可能范围缩小。通过二分搜索式的迭代，攻击者在大约 2^20（约一百万）次查询后即可精确恢复 m。

历史影响。 这一攻击直接促使 PKCS#1 v2.0 引入了 OAEP 填充方案。然而，由于向后兼容的压力，PKCS#1 v1.5 在 TLS 中存活了近二十年。2017 年，Hanno Böck、Juraj Somorovsky 和 Craig Young 发表了 ROBOT（Return Of Bleichenbacher’s Oracle Threat）攻击，证明包括 Facebook、PayPal 在内的大量知名网站仍然容易受到 Bleichenbacher 类攻击。他们在现代 TLS 栈中发现了各种微妙的侧信道——响应时间差异、错误码差异、甚至 TCP 连接重置行为的差异——都足以充当填充预言机。

这一事件深刻地告诉我们：密码学协议中的错误处理必须做到严格的常量时间（constant-time），且不能泄露任何关于解密结果的信息。TLS 1.3 最终彻底移除了 RSA 密钥传输机制，从协议层面根除了这一攻击面。

六、Coppersmith 方法

1996 年，唐·科波斯密斯（Don Coppersmith）基于格基归约（lattice basis reduction）技术提出了一种强大的方法，可以在多项式时间内找到模多项式的小根。这一方法在 RSA 分析中催生了一系列极具威力的攻击。

小消息攻击。 若明文 m 相对于模数 n 较小（例如 m < n^(1/e)），教科书 RSA 的密文 c = m^e 在整数上就已经等于 m^e（无需取模），直接开 e 次方根即可恢复明文。这实际上是 Håstad 攻击的一种退化情形。Coppersmith 方法更进一步：即使 m 稍大于 n^(1/e)，只要满足 m < n^(1/e) 的某个宽松上界，攻击者仍可通过构造关于 m 的格（lattice）并执行 LLL 算法来恢复 m。

部分密钥泄露攻击。 若攻击者通过侧信道获得了私钥 d 的部分比特（例如低位的一半），Coppersmith 方法可以在多项式时间内恢复完整的 d。具体而言，Boneh、Durfee 和 Frankel 在 1998 年证明，知道 d 的低 n/4 位即足以在多项式时间内分解 n。这对硬件实现中的侧信道防护提出了极高要求。

Boneh-Durfee 攻击（小私钥攻击）。 1999 年，Dan Boneh 和 Glenn Durfee 证明，当 d < n^0.292 时，可以在多项式时间内恢复 d。这改进了 Michael Wiener 在 1990 年提出的 d < n^0.25 的界限（Wiener 攻击基于连分数逼近）。Boneh-Durfee 攻击的核心思想是将恢复 d 的问题转化为在某个格上寻找短向量的问题，然后利用 LLL 或 BKZ 算法求解。

Franklin-Reiter 相关消息攻击。 若两段明文之间存在已知的线性关系 m2 = a·m1 + b（其中 a、b 已知），攻击者在截获两段对应密文后，可以利用多项式公因子分解在多项式时间内恢复两段明文。Coppersmith 方法将此推广到更一般的多项式关系。

这些攻击共同说明了一个主题：RSA 的安全性不仅依赖于大整数分解的困难性，还极度依赖于使用方式的正确性。密钥和消息中任何结构性的”短”特征，都可能被格方法精确捕获并利用。

七、RSA-OAEP 与 RSA-PSS

面对教科书 RSA 的种种缺陷，密码学家设计了两套标准化的填充方案：用于加密的 RSA-OAEP 和用于签名的 RSA-PSS。

RSA-OAEP（Optimal Asymmetric Encryption Padding）。 OAEP 由 Mihir Bellare 和 Phillip Rogaway 在 1994 年提出，后经 Fujisaki、Okamoto、Pointcheval 和 Stern 完善安全证明。其核心结构是一个双轮费斯妥网络（two-round Feistel network）：

1. 生成一个随机种子 r。
2. 计算 maskedDB = DB ⊕ G(r)，其中 DB 是填充后的明文数据块，G 是一个掩码生成函数（Mask Generation Function, MGF），通常基于 SHA-256 实现。
3. 计算 maskedSeed = r ⊕ H(maskedDB)，其中 H 是另一个哈希函数。
4. 将 0x00 || maskedSeed || maskedDB 作为编码后的消息，执行 RSA 加密。

这种结构引入了随机性（解决确定性问题），将明文均匀分散到整个模数空间（防止小消息攻击），并且使得任何对密文的修改都会以压倒性的概率导致解密失败（抵抗可锻造性）。在随机预言机模型（Random Oracle Model, ROM）下，RSA-OAEP 被证明满足 IND-CCA2 安全——这是公钥加密最强的标准安全定义。

PKCS#1 v2.2 将 RSA-OAEP 定义为推荐的加密方案，NIST SP 800-56B 也将其列为密钥传输的批准方法。

RSA-PSS（Probabilistic Signature Scheme）。 PSS 同样由 Bellare 和 Rogaway 提出，是一种概率签名方案。与传统的”哈希再签名”（hash-then-sign）不同，PSS 在签名过程中引入随机盐值（salt），使得同一消息的每次签名都不相同。其结构同样基于掩码生成函数：

1. 计算消息的哈希值 mHash = Hash(M)。
2. 生成随机盐值 salt。
3. 计算 H’ = Hash(padding || mHash || salt)。
4. 构造编码消息 EM，其中包含 maskedDB（由 salt 位置信息经 MGF(H’) 掩码后得到）和 H’。
5. 对 EM 执行 RSA 签名运算。

在 ROM 下，RSA-PSS 被证明是紧致安全的（tightly secure）：其安全性可直接归约到 RSA 问题本身，归约损失极小。这意味着 RSA-PSS 几乎能”完全利用”RSA 问题的困难性。FIPS 186-5 已将 RSA-PSS 列为唯一推荐的 RSA 签名方案，PKCS#1 v1.5 签名方案虽仍被允许用于遗留系统验证，但不再推荐用于新系统。

八、CRT 优化与故障攻击

CRT 加速。 直接计算 m = c^d mod n 需要对一个约 2048 位的指数执行模幂运算，开销巨大。利用中国剩余定理（CRT）可以将这一运算拆分为两个较小的模幂运算：

m_p = c^(d mod (p-1)) mod p
m_q = c^(d mod (q-1)) mod q

然后通过 CRT 合并：

m = CRT(m_p, m_q) = m_q + q · ((m_p - m_q) · q^(-1) mod p)

由于每个子运算的模数和指数都只有原来的一半大小，而模幂的计算量大致与指数长度的立方成正比，CRT 优化可以带来约四倍的加速。这就是为什么几乎所有 RSA 实现——从 OpenSSL 到硬件安全模块（HSM）——都使用 CRT 形式的私钥操作。

Bellcore 故障攻击。 1997 年，Boneh、DeMillo 和 Lipton 发现了 CRT-RSA 实现的一个惊人弱点：如果在计算 m_p 或 m_q 的过程中发生单比特计算错误（例如由宇宙射线、电压毛刺或激光注入引起），攻击者可以通过一次正确签名和一次错误签名直接分解 n。

具体地，假设 m_q 的计算正确而 m_p 的计算出错，得到错误的 m̃_p。则错误签名 σ̃ 满足：

σ̃^e ≡ m (mod q)  但  σ̃^e ≢ m (mod p)

因此 gcd(σ̃^e − m, n) = q，攻击者立即获得 q，进而分解 n。

对策。 防御故障攻击的标准做法是在输出签名之前进行验证：计算 σ^e mod n 并检查是否等于原始消息的编码。若不等则丢弃签名并重新计算。这一额外的模幂运算仅增加约百分之几的开销（因为 e = 65537 很小，验证很快），却能完全阻止故障攻击。此外，一些实现还会使用随机化技术（如 RSA 盲化，RSA blinding）来抵抗时序分析和功耗分析等侧信道攻击：在计算前将密文乘以一个随机因子 r^e，计算完成后再除以 r，使得每次运算的中间值都是随机的。

RSA 攻击谱系总览

回顾前文讨论的各类攻击，我们可以将 RSA 的攻击面整理为从数学层到协议层的完整谱系：

RSA 攻击谱系
│
├── 数学层攻击（Mathematical Attacks）
│   ├── 通用整数分解
│   │   ├── 数域筛法（GNFS） ─────────── 所有 RSA 变体（密钥长度不足时）
│   │   └── 量子分解（Shor 算法） ────── 所有 RSA 变体（量子计算机可用时）
│   ├── Coppersmith 方法 ─────────────── 低公开指数 + 部分信息泄露场景
│   │   └── 已知明文高位/低位时恢复完整明文
│   ├── Wiener 攻击 ──────────────────── d < n^(1/4)/3 的小私钥指数 RSA
│   └── Håstad 广播攻击 ──────────────── 教科书 RSA + 小 e + 多接收者广播
│
├── 实现层攻击（Implementation Attacks）
│   ├── 时序攻击（Timing Attack） ────── 非常量时间的模幂运算实现
│   ├── 功耗/电磁分析 ────────────────── 无掩码保护的硬件/嵌入式实现
│   ├── 故障注入攻击（Fault Attack） ── CRT-RSA 签名（无签名后验证时）
│   └── 缓存侧信道 ──────────────────── 使用查表的滑动窗口模幂实现
│
└── 协议层攻击（Protocol-Level Attacks）
    ├── Bleichenbacher 攻击 ──────────── PKCS#1 v1.5 填充的 RSA 加密
    │   └── ROBOT 攻击（2017） ────────── TLS 服务器中残存的 Bleichenbacher 预言机
    ├── 填充预言攻击 ─────────────────── 错误消息区分填充失败与解密失败的实现
    ├── 选择密文攻击（CCA） ──────────── 教科书 RSA（乘法同态性）
    └── Manger 攻击 ─────────────────── RSA-OAEP 的不当实现（泄露解码步骤信息）

梳理这张攻击谱系时，我常常感叹：RSA 的”脆弱”恰恰是密码学教育最宝贵的资产。没有任何一个单一原语像 RSA 这样，在数学层、实现层、协议层三个截然不同的维度上都拥有如此丰富的攻击案例。学习 Coppersmith 方法让你理解格约化；学习 Bleichenbacher 攻击让你理解填充方案为什么不能泄露一比特信息；学习 CRT 故障攻击让你理解为什么数学正确不等于实现安全。如果说现代密码分析是一门手艺，那么 RSA 就是每个学徒磨练技艺的第一块试金石——它教给你的不只是如何攻破一个方案，而是如何用攻击者的眼光审视整个系统。

从另一个视角看，RSA 堪称理解”数学优美性为何在密码学中可能是一把双刃剑”的罗塞塔石碑。RSA 之所以拥有如此丰富的攻击面，恰恰因为它的代数结构太”好”了——乘法同态性让选择密文攻击成为可能，公钥指数的数论性质催生了 Håstad 攻击和 Wiener 攻击，而模运算的平滑结构则为 Coppersmith 方法提供了格约化的切入点。对比之下，椭圆曲线上的离散对数问题几乎不存在类似的结构化攻击——不是因为 ECC 被研究得更少，而是因为椭圆曲线群缺乏整数环那种丰富的代数”把手”供攻击者抓取。这给密码学设计者一个深刻的教训：数学上越优美、结构越丰富的对象，往往给攻击者提供的工具也越多。现代密码学越来越倾向于选择”结构贫乏”的数学对象作为安全基础——从椭圆曲线到格，再到同源，每一代新原语的共同趋势是：刻意远离那些人类直觉上觉得”自然”的代数结构。

九、RSA 的未来

RSA 已经服役近半个世纪，其地位正在发生根本性的变化。

密钥长度的军备竞赛。 1999 年，512 位 RSA 被公开分解。2010 年，768 位 RSA 被分解（使用数域筛法，耗时约两年的集群计算时间）。2020 年，研究人员使用约 2700 个核心年的计算量分解了 829 位的 RSA 挑战数。目前普遍认为 1024 位 RSA 对国家级行为者已不安全，情报机构可能早已具备分解能力。2048 位在经典计算能力下预计至少安全到 2030 年代，但这一预测会随着算法改进和硬件发展而不断修正。值得注意的是，数域筛法的渐近复杂度为亚指数级，这意味着每增加一倍密钥长度，所需的破解时间远不止翻倍，但也远不如指数级增长那样令人安心。每次密钥长度的提升都伴随着显著的性能代价——RSA-4096 的签名速度约为 RSA-2048 的八分之一，而密钥生成时间可能长达数秒。

与椭圆曲线密码的性能对比。 在相同安全等级下，ECC 的密钥远短于 RSA：128 位安全对应 256 位 ECC 密钥，却需要 3072 位 RSA 密钥。这意味着 ECC 在带宽、存储和计算速度上全面优于 RSA。ECDSA 和 EdDSA 签名的生成和验证速度通常比同等安全级别的 RSA-PSS 快数倍至数十倍。在移动设备和物联网等资源受限的场景下，这种差距尤为显著。TLS 1.3 虽然仍支持 RSA 签名用于证书验证，但密钥协商已完全转向基于椭圆曲线的 ECDHE。

量子威胁。 1994 年，彼得·肖尔（Peter Shor）提出了一种量子算法，可以在量子计算机上以多项式时间分解大整数。这意味着一旦足够大规模的容错量子计算机（fault-tolerant quantum computer）问世，RSA 将被彻底击溃，无论密钥长度多大。当前的估计是，分解 2048 位 RSA 需要约 4000 个逻辑量子比特（对应数百万个物理量子比特），这超出了现有量子硬件的能力，但量子技术的进步速度可能比预期更快。

后量子迁移。 NIST 已于 2024 年正式发布了后量子密码标准（PQC），包括基于格的 ML-KEM（前称 CRYSTALS-Kyber）用于密钥封装和基于格的 ML-DSA（前称 CRYSTALS-Dilithium）用于数字签名。这些方案旨在抵抗量子计算攻击，同时在经典计算机上保持可接受的性能。各大科技公司和标准化组织正在推进从 RSA 和 ECC 向后量子密码的迁移计划。这一迁移并非一朝一夕之事——全球数十亿张数字证书、数以百万计的嵌入式设备和遗留系统都需要逐步更新。在过渡期间，混合方案（hybrid scheme）——同时使用传统算法和后量子算法——被广泛推荐以确保向前兼容。即便量子计算机尚未到来，“先存储后解密”（harvest now, decrypt later）的威胁已迫使各国政府将后量子迁移提上日程。

一个经常被忽视的观点是，RSA 的持续存在与其说是技术惯性，不如说是组织行为学的案例研究。2025 年的今天，仍然有大量系统在生成 4096 位的 RSA 密钥——尽管 256 位的 ECC 密钥在相同安全等级下体积只有前者的十六分之一、运算速度快一个数量级、带宽开销微乎其微。这种现象无法用技术原因解释，只能从组织和生态的角度理解：RSA 嵌入了无数的合规文件、采购规范、硬件安全模块的固件、以及工程师的肌肉记忆中。迁移密码算法的成本不在于写新代码，而在于修改每一份引用了旧算法的文档、通过每一项引用了旧算法的合规审计、以及说服每一位”RSA 用了四十年都没问题”的决策者。这是密码学领域最大的非技术挑战：密码学的进化速度远快于组织制度的进化速度。每一次密码学迁移——从 DES 到 AES、从 SHA-1 到 SHA-2、从 RSA 到 ECC、再到即将到来的后量子迁移——本质上都是同一个社会学问题的重演：技术社区早已达成共识，而部署惯性却需要十年甚至更久才能克服。

RSA 的故事是密码学演化的缩影：一个在理论上优美、在实践中复杂的方案，在攻防博弈中不断演化，最终在新的计算范式面前走向落幕。但它所带来的公钥密码学革命——密钥交换无需预共享秘密、数字签名可以被公开验证——这些根本性的思想突破将永远镌刻在信息安全的历史中。从最初教科书般简洁的数学公式，到填充方案的精心设计，再到侧信道防护的工程细节，RSA 的发展历程展现了密码学如何在纯数学、协议设计和系统工程三个层面上同时展开斗争。理解 RSA 的每一个细节，不仅是理解一个算法，更是理解密码学这门科学如何在理想与现实之间寻求平衡。

密码学百科系列 · 第 15 篇

← 上一篇：数论基础 | 系列目录 | 下一篇：Diffie-Hellman →