• hello，大家好，我是 Lorin，这是 RSA 算法解密的第二期 “RSA 加密算法的原理与加密过程深度解析” 主要介绍如何使用上期学到的数论知识来实现 RSA 加解密过程。

RSA 秘钥生成过程

• 我们以一个实际场景来描述秘钥的生成过程，假设现在小明和小王要进行通信：

第一步：选取两个质数 P、Q，计算秘钥长度 N

• 小王随机选取两个质数：P = 61 Q = 53，N = P * Q = 3233
• N 就是秘钥的长度，3233 写成二进制是 110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

第二步：根据欧拉函数计算 φ(N) 并选取随机值 E

φ(N) = φ(P) * φ(Q) = (P - 1)*(Q -1) = 60 × 52 = 3120

随机从 1<E<φ(N) 选取一个整数，且与 N 互质，比如我们选择 17。

第三步：计算 E 对 φ(N) 的模反元素 D

ED = 1 (mod φ(N))

// 等价于
ED - 1 = Kφ(N) 

// 即对二元一次方程组求解
E = 17，φ(N) = 3120
17D - 1 = 3120K

// 我们算出其中一组解(存在多组解)：
D = 2753，K = -15

第四步：将 N、E 封装为公钥，N、D 封装为私钥

• 即在我们例子中公钥：(3233,17)、私钥(3233,2753)
• 实际应用中，公钥和私钥的数据都采用ASN.1格式表达。

加密和解密

加密需要使用公钥 N、E

• 小明现在需要把数据 M 传递给小王，则他需要使用小王提供的公钥 N、E 对数据进行加密：
• M 必须是整数（字符串可以取ascii值或unicode值），且满足 0 ≤ M < N，对 M 加密其实是计算下面的公式：

// 假设 M = 65
M^E ≡ C (mod N)

65 ^ 17 ≡ 2790 (mod 3233) 即 C = 2790

如果 M >= N 如何处理

• 方式一：将消息分段，分段进行加密
• 方式二：使用 RSA 加密对称秘钥，然后使用对称加密秘钥加密信息

解密需要使用私钥 N、D

• 此时，小明将 C = 2790 传递给小王，小王使用私钥进行解密：

// 解密使用下列公式
C^D ≡ M (mod N)

// 代入 N,D (3233,2753) 你会发现 M 就是我们加密的原文信息
2790 ^ 2753 = M (mod 3233)，M = 65

如何证明 CD ≡ M (mod N) 成立

// 根据加密规则
M^E ≡ C (mod N)

C = (M^E - KN)

// 将 C 带入解密公式
(M^E - KN)^D ≡ M (mod N)

// 等同于
M^(ED) ≡  M (mod N)

// 由于 ED - 1 = Kφ(N)  则 ED = Kφ(N) + 1 代入得到
M^(Kφ(N) + 1) ≡  M (mod N)

# 下面分为两种情况来证明
1、M N 为互质关系
由欧拉定理 M^φ(N) ≡ 1 (mod N) 可得

(M^φ(N))^K * M ≡ M (mod N) 原式得到证明

2、M N 不为互质关系
这里就不写证明过程了，感兴趣的朋友可以自己尝试推导一下。

其它

为什么 RSA 加密算法可靠性如何保证

从上面我们可以看到一共涉及：
P Q N φ(N) E D，N、E 为公钥，N、D 为私钥
因此，其中最关键的是 D，若 D 泄漏相当于私钥泄漏。

// 在已知 N、E 条件下可以推导出 D？
1、由 ED = 1 (mod φ(N)) 可知，需要知道 φ(N) 才可以算出 D
2、φ(N) = φ(P) * φ(Q) = (P - 1)*(Q -1) 和欧拉公式可知，想要计算 φ(N) 一定要对 N 进行质因数分解

但是大数的质因数分解十分困难，只有使用暴力破解的方式，目前报道被破解的最长RSA密钥就是768位，因此可以说 1024 位长度的秘钥基本安全，2048 位秘钥非常安全。

当然，如果出现其它有效分解大数质因数的方法，或者计算机算力提高，比如量子计算机，那么 RSA 也是不安全的。

RSA 的复杂性导致加密过程十分慢

• 因此实际使用过程中，一般使用 RSA 算法加密对称秘钥，方便对称秘钥的传输，使用对称秘钥加密实际传输的信息。比如常见的 HTTPS。