RSA 加密算法的原理与加密过程深度解析（下篇）

• 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。

个人简介

👋 你好，我是 Lorin 洛林，一位 Java 后端技术开发者！座右铭：Technology has the power to make the world a better place.

🚀 我对技术的热情是我不断学习和分享的动力。我的博客是一个关于Java生态系统、后端开发和最新技术趋势的地方。

🧠 作为一个 Java 后端技术爱好者，我不仅热衷于探索语言的新特性和技术的深度，还热衷于分享我的见解和最佳实践。我相信知识的分享和社区合作可以帮助我们共同成长。

💡 在我的博客上，你将找到关于Java核心概念、JVM 底层技术、常用框架如Spring和Mybatis 、MySQL等数据库管理、RabbitMQ、Rocketmq等消息中间件、性能优化等内容的深入文章。我也将分享一些编程技巧和解决问题的方法，以帮助你更好地掌握Java编程。

🌐 我鼓励互动和建立社区，因此请留下你的问题、建议或主题请求，让我知道你感兴趣的内容。此外，我将分享最新的互联网和技术资讯，以确保你与技术世界的最新发展保持联系。我期待与你一起在技术之路上前进，一起探讨技术世界的无限可能性。

📖 保持关注我的博客，让我们共同追求技术卓越。

我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！