1977 年，罗纳德·里维斯特（Ron Rivest）、阿迪·沙米尔（Adi

Shamir）与伦纳德·阿德曼（Leonard

Adleman）在麻省理工学院发表了一种新的公钥加密方案，以三人姓氏首字母命名为

RSA。这是人类第一个同时可用于加密与数字签名的公钥密码体制，也是至今工业界部署最广泛的非对称算法之一。然而，教科书中那段简洁优美的数学公式只描绘了

RSA

的骨架；真实世界里，从密钥生成的每一个比特到填充方案的每一个字节，都暗藏着精巧的攻击面。本文将从最基础的密钥生成出发，逐步展示教科书

RSA

为何不安全，以及工程实践如何在数十年的攻防博弈中一步步堵住漏洞。

RSA

算法流程：密钥生成、加密与解密

先用一张图把本文的核心关系串起来。

flowchart TD

A[选 p q] --> B[计算 n 与 phi]

B --> C[选择 e]

C --> D[求私钥 d]

D --> E[加密与签名]

一、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）：

生成一个随机种子 r。

计算 maskedDB = DB ⊕ G(r)，其中 DB

是填充后的明文数据块，G 是一个掩码生成函数（Mask Generation

Function, MGF），通常基于 SHA-256 实现。

计算 maskedSeed = r ⊕ H(maskedDB)，其中 H

是另一个哈希函数。

将 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），使得同一消息的每次签名都不相同。其结构同样基于掩码生成函数：

计算消息的哈希值 mHash = Hash(M)。

生成随机盐值 salt。

计算 H’ = Hash(padding || mHash || salt)。

构造编码消息 EM，其中包含 maskedDB（由 salt 位置信息经

MGF(H’) 掩码后得到）和 H’。

对 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 的不当实现（泄露解码步骤信息）

攻击类别

代表性攻击

目标变体

核心利用点

主要对策

数学——分解

GNFS、Shor

所有 RSA

模数 n 的因子分解

增大密钥长度；迁移至后量子方案

数学——格方法

Coppersmith

低 e + 部分泄露

小根多项式求解

使用完整填充方案（OAEP）

数学——连分数

Wiener

小 d RSA

私钥指数过小

确保 d 足够大（标准密钥生成）

数学——CRT

Håstad 广播

教科书 RSA, e=3

中国剩余定理还原

随机化填充（OAEP）

实现——时序

Kocher 时序攻击

非恒定时间实现

模幂运算时间差异

常量时间实现 + RSA 盲化

实现——故障

Bellcore 攻击

CRT-RSA 签名

单故障暴露因子

签名后验证；冗余计算

协议——填充

Bleichenbacher

PKCS#1 v1.5 加密

填充有效性预言机

迁移至 RSA-OAEP；消除预言机

协议——残留

ROBOT

TLS + RSA 密钥传输

服务器残存的错误区分

TLS 1.3 移除 RSA 密钥传输

梳理这张攻击谱系时，我常常感叹：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

→

同主题继续阅读把当前热点继续串成多页阅读，而不是停在单篇消费。

2026-04-04 · cryptography

【密码学百科】填充方案：PKCS#1 v1.5、OAEP 与 PSS

填充看似简单，却是密码学安全的关键环节——从 PKCS#1 v1.5 的 Bleichenbacher 攻击到 OAEP 的双重哈希防御，本文深入解析填充方案为何如此重要

2026-04-04 · cryptography

【密码学百科】密码学简史：从凯撒密码到量子时代

从古典密码的替换与置换，到现代密码学的数学革命，再到后量子时代的全新挑战——一篇文章带你走完密码学三千年的演进之路

2026-04-12 · cryptography

【密码学百科】量子计算基础：量子比特、量子门与密码学的量子威胁

量子计算机对现有密码体系构成根本性威胁——本文从量子比特和量子门的基本概念出发，讲解量子并行性、量子纠缠、Deutsch-Jozsa 算法，为理解 Shor 和 Grover 算法对密码学的影响打下基础

2026-12-10 · cryptography / security

【国密算法与国密 TLS 系列】国密生态全景：GmSSL、铜锁、硬件密码机与合规落地

从开源库到硬件加速，从等保密评到 DTLS 国密，全面剖析国密生态的技术选型与合规落地路径。