RSA 的核心思想：为什么「分解大数」这么难

1. 为什么要关心这个问题？

1977 年，三位 MIT 的研究者——Rivest、Shamir 和 Adleman——发表了一个看似不可能的东西：一种加密方法，让你可以公开发布加密用的密钥，而只有你能解密。

这彻底改变了安全通信的游戏规则。

在 RSA 之前，Alice 想和 Bob 安全通信，他们必须先见面交换密钥。现在，Bob 可以在网站上公开他的公钥，任何人都可以给他发加密消息，而只有 Bob 能读取。

这怎么可能？答案藏在一个数学问题的不对称性里。

2. 定义

RSA 是一种非对称加密算法，使用一对数学上相关但不同的密钥：

• 公钥（Public Key）： 可以公开，用于加密数据或验证签名
• 私钥（Private Key）： 必须保密，用于解密数据或创建签名

RSA 的安全性基于整数分解问题：给定两个大质数 p 和 q，计算 n = p × q 很容易，但给定 n，找出 p 和 q 极其困难。

3. 核心直觉：单向函数

乘法 vs 分解

正向（容易）：
p = 61
q = 53
n = p × q = 3233

反向（困难）：
n = 3233
p = ?
q = ?

对于小数字，你可以手算。但当数字变大：

n = 25195908475657893494027183240048398571429282126204
    03202777713783604366202070759555626401852588078440
    69182906412495150821892985591491761845028084891200
    72844992687392807287776735971418347270261896375014
    97182469116507761337985909570009733045974880842840
    17974291006424586918171951187461215151726546322822
    16869987549182422433637259085141865462043576798423
    38718477444792073993423658482382428119816381501067
    48104516603773060562016196762561338441436038339044
    14952634432190114657544454178424020924616515723350
    77870774981712577246796292638635637328991215483143
    81678998850404453640235273819513786365643912120103
    97122822120720357

这是 RSA-2048 的一个模数
目前没有人能分解它

为什么分解这么难

尝试分解 n = 15：
15 ÷ 2 = 7.5 ✗
15 ÷ 3 = 5 ✓ → 15 = 3 × 5

尝试分解 n = 2048 位的数：
需要尝试大约 √n 个候选质数
√(2^2048) ≈ 2^1024
即使每秒尝试 10^18 次
也需要 10^290 年
宇宙的年龄才 1.4 × 10^10 年

4. RSA 密钥是怎么来的

步骤 1：选择两个大质数

p = 一个大质数（例如 1024 位）
q = 另一个大质数（同样大小）

步骤 2：计算模数 n

n = p × q

这个 n 是公开的
它的位数就是「RSA-2048」中的 2048

步骤 3：计算欧拉函数 φ(n)

φ(n) = (p - 1) × (q - 1)

这个值必须保密！
知道 φ(n) 就等于知道 p 和 q

步骤 4：选择公开指数 e

e 必须满足：
1 < e < φ(n)
gcd(e, φ(n)) = 1（e 和 φ(n) 互质）

常用值：e = 65537 = 2^16 + 1
为什么？因为二进制只有两个 1，计算快

步骤 5：计算私有指数 d

d × e ≡ 1 (mod φ(n))

即：d 是 e 对于 φ(n) 的模逆元
使用扩展欧几里得算法可以高效计算

密钥对

公钥 = (n, e)
私钥 = (n, d)

实际上私钥还会存储 p、q 和一些预计算值来加速运算

5. RSA 加密和解密

加密（使用公钥）

密文 C = M^e mod n

M = 明文（必须小于 n）
e = 公开指数
n = 模数

解密（使用私钥）

明文 M = C^d mod n

C = 密文
d = 私有指数
n = 模数

为什么这能工作？

C^d mod n
= (M^e)^d mod n
= M^(e×d) mod n
= M^(1 + k×φ(n)) mod n  （因为 e×d ≡ 1 mod φ(n)）
= M × M^(k×φ(n)) mod n
= M × (M^φ(n))^k mod n
= M × 1^k mod n         （欧拉定理：M^φ(n) ≡ 1 mod n）
= M

6. 数字示例

# 小数字示例（仅用于理解，实际 RSA 使用大得多的数字）

# 步骤 1：选择质数
p = 61
q = 53

# 步骤 2：计算 n
n = p * q  # n = 3233

# 步骤 3：计算 φ(n)
phi_n = (p - 1) * (q - 1)  # φ(n) = 60 × 52 = 3120

# 步骤 4：选择 e
e = 17  # gcd(17, 3120) = 1 ✓

# 步骤 5：计算 d
# d × 17 ≡ 1 (mod 3120)
# d = 2753（可以验证：17 × 2753 = 46801 = 15 × 3120 + 1）

d = 2753

# 公钥：(n=3233, e=17)
# 私钥：(n=3233, d=2753)

# 加密消息 M = 123
M = 123
C = pow(M, e, n)  # C = 123^17 mod 3233 = 855

# 解密
M_decrypted = pow(C, d, n)  # 855^2753 mod 3233 = 123
print(M_decrypted)  # 123 ✓

7. 为什么密钥越来越长

RSA 密钥长度的演进

为什么需要这么长

对称密钥 vs RSA 密钥的安全级别：

AES-128（128 位）≈ RSA-3072（3072 位）
AES-256（256 位）≈ RSA-15360（15360 位）

RSA 密钥需要比对称密钥长得多
因为分解问题的复杂度不是指数级的
而是次指数级（数域筛法）

量子威胁

Shor 算法可以在多项式时间内分解大数
如果大规模量子计算机实现：
- RSA 将完全失效
- 需要迁移到后量子密码学

目前：
- 实用的量子计算机还不存在
- 但「现在收集，未来解密」是真实威胁
- 敏感数据应该考虑后量子方案

8. RSA 的实际限制

消息大小限制

RSA 只能加密小于 n 的数
对于 RSA-2048：
最大明文 = 2048 位 = 256 字节

实际更小，因为需要填充
OAEP 填充后：256 - 42 = 214 字节

性能问题

RSA 加密：O(e × log³n)
RSA 解密：O(d × log³n)

因为 d 很大（接近 n），解密很慢
比 AES 慢约 1000 倍

这就是为什么 RSA 不直接加密数据
而是加密对称密钥（混合加密）

填充的重要性

教科书 RSA（不带填充）是不安全的：

1. 确定性加密
   相同明文 → 相同密文
   攻击者可以建立对照表

2. 可延展性
   C' = C × 2^e mod n
   解密得到 2M
   攻击者可以操纵密文

正确做法：使用 OAEP 填充
RSA-OAEP 是语义安全的

9. 代码示例

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes

# 生成 RSA 密钥对
private_key = rsa.generate_private_key(
    public_exponent=65537,
    key_size=2048,
)
public_key = private_key.public_key()

# 加密（使用公钥）
message = b"Hello, RSA!"
ciphertext = public_key.encrypt(
    message,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

# 解密（使用私钥）
plaintext = private_key.decrypt(
    ciphertext,
    padding.OAEP(
        mgf=padding.MGF1(algorithm=hashes.SHA256()),
        algorithm=hashes.SHA256(),
        label=None
    )
)

print(f"原文: {message}")
print(f"密文长度: {len(ciphertext)} 字节")
print(f"解密: {plaintext}")

10. 常见误区

11. 本章小结

三点要记住：

1. RSA 的安全性来自分解的困难。 乘法容易，分解难。这个不对称性让公钥可以公开而不泄漏私钥。

2. RSA 密钥需要比对称密钥长得多。 RSA-2048 只提供约 112 位的安全性，相当于 AES-128 级别。

3. RSA 不适合直接加密数据。 它有大小限制且速度慢。实际系统使用 RSA 加密对称密钥，然后用对称密钥加密数据。

12. 下一步

我们理解了 RSA 的数学基础。但在现代系统中，RSA 的角色正在改变。TLS 1.3 甚至完全移除了 RSA 密钥交换。

在下一篇文章中，我们将探讨：RSA 在现代系统中的真实角色——为什么不用 RSA 直接加密数据，RSA 在 TLS 中的历史与退场，以及实际的安全问题。