RSA 加密算法的原理与加密过程深度解析（下篇）
文章目录
- RSA 秘钥生成过程
- 第一步：选取两个质数 P、Q，计算秘钥长度 N
- 第二步：根据欧拉函数计算 φ(N) 并选取随机值 E
- 第三步：计算 E 对 φ(N) 的模反元素 D
- 第四步：将 N、E 封装为公钥，N、D 封装为私钥
- 加密和解密
- 加密需要使用公钥 N、E
- 如果 M >= N 如何处理
- 解密需要使用私钥 N、D
- 如何证明 CD ≡ M (mod N) 成立
- 其它
- 为什么 RSA 加密算法可靠性如何保证
- 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编程。
🌐 我鼓励互动和建立社区，因此请留下你的问题、建议或主题请求，让我知道你感兴趣的内容。我期待与你一起在技术之路上前进，一起探讨技术世界的无限可能性。
📖 保持关注我的博客，让我们共同追求技术卓越。