- 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
代码语言：txt复制φ(N) = φ(P) * φ(Q) = (P - 1)*(Q -1) = 60 × 52 = 3120
随机从 1<E<φ(N) 选取一个整数，且与 N 互质，比如我们选择 17。第三步：计算 E 对 φ(N) 的模反元素 D
代码语言：txt复制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) 成立
代码语言：txt复制// 根据加密规则
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 加密算法可靠性如何保证
代码语言：txt复制从上面我们可以看到一共涉及：
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。
个人简介
