RSA 原理学习

一、RSA 原理

RSA 是一种基于大整数分解困难性的非对称加密算法。它使用一对密钥：公钥用于加密，私钥用于解密。

密钥生成步骤

1. 选择两个大素数 p 和 q。 素数是只能被 1 和自身整除的整数。
2. 计算 N = p × q。
3. 计算欧拉函数 φ(N) = (p - 1)(q - 1)。
4. 选择与 φ(N) 互质的整数 e 作为加密指数。
5. 计算 d = e-1 mod φ(N) 作为私钥。

最终得到：

• 公钥：(N, e)
• 私钥：d
• 中间参数：p、q、φ(N) 仅用于生成过程，之后不需要公开。

加密与解密

加密：c ≡ me (mod N)

解密：m ≡ cd (mod N)

其中 m 是明文，c 是密文。之所以能够正确解密，是因为 ed ≡ 1 (mod φ(N))。

二、简单实例

下面用一个小例子演示 RSA 的完整流程。真实场景中的密钥会远大于这里的数字。

第 1 步：Bob 生成密钥对

• p = 101
• q = 127
• N = 101 × 127 = 12,827
• φ(N) = (101 - 1) × (127 - 1) = 12,600
• e = 11
• d = 2,291

公钥：(N = 12,827, e = 11)

私钥：d = 2,291

第 2 步：Alice 将消息转成数字

采用 a=01, b=02, ..., z=26，空格为 00 的编码方式。

消息 love you 可编码为：

• l=12
• o=15
• v=22
• e=05
• space=00
• y=25
• o=15
• u=21

拼接后得到的数字过长，超过 N 的范围，所以需要分块处理。这里先以 LO 为例：

m = 1,215

第 3 步：使用公钥加密

c ≡ 1,21511 (mod 12,827)

得到密文：

c = 4,892

第 4 步：Bob 使用私钥解密

m ≡ 4,8922,291 (mod 12,827)

恢复明文：

m = 1,215，对应 LO。

实际应用中，整段消息会被拆成多个块分别加密和解密。

三、安全性分析

RSA 的安全性依赖于“大整数分解”这一困难问题。攻击者如果只知道公钥和密文，想恢复明文通常需要先分解 N，再推导出私钥 d。

攻击者需要做的事情

1. 分解 N 得到 p 和 q。
2. 计算 φ(N)。
3. 求出 d = e-1 mod φ(N)。
4. 使用私钥解密密文。

密钥强度对比

密钥位数	破解难度	状态
512 位	几小时	已破解
1024 位	数十年	开始不安全
2048 位	数百年	目前安全
4096 位	极其困难	长期安全