步骤
| 步骤 | 说明 | 描述 | 备注 | 数学知识 | 其他 |
|---|---|---|---|---|---|
| 1 | 找出质数 | P、Q | - | 质数(只能被1和自己整除) | |
| 2 | 计算公共模数 | N=P*Q | - | ||
| 3 | 欧拉函数 | φ(N) = (P-1)(Q-1) | - | 欧拉函数(小于n且与n互质的数的个数) | |
| 4 | 计算公钥构成元素E | 1 < E < φ(N) | E的取值必须是整数 E 和 φ(N) 必须是互质数 |
这一步其实是为了下一步计算私钥做准备 | |
| 5 | 计算私钥构成元素D | E * D % φ(N) = 1 | - | 模反元素、欧拉定理 | 可见D并不唯一 |
| 6 | 加密 | C ＝ M E mod N | C：密文 M：明文 | 即使我们有了以上的种种，那么怎么能想到这一步的加密过程呢？ | |
| 7 | 解密 | M ＝C D mod N | C：密文 M：明文 | 同理，即使有了上述所有，我们怎么能想到这一步呢？需要什么天才想法呢 |
公钥=(N,E)
私钥=(N,D)
示例
1. 找出质数P、Q
P = 3
Q = 11
2. 计算公共模数
N = P * Q = 3 * 11 = 33
N = 33
3. 欧拉函数
φ(N) = (P-1)(Q-1) = 2 * 10 = 20
φ(N) = 20
4. 计算公钥E
1 < E < φ(N)
1 <E < 20
E 的取值范围 {3, 7, 9, 11, 13, 17, 19}
E的取值必须是整数, E 和 φ(N) 必须是互质数
为了测试，我们取最小的值 E =3
3 和 φ(N) =20 互为质数，满足条件
5. 计算私钥D
E * D % φ(N) = 1
3 * D % 20 = 1
根据上面可计算出 D = 7
6. 公钥加密
我们这里为了演示，就加密一个比较小的数字 M = 2
公式：C ＝ M^E mod N
M = 2
E = 3
N = 33
C = 2^3 % 33 = 8
明文 “2” 经过 RSA 加密后变成了密文 “8”
7. 私钥解密
M ＝C^D mod N
C = 8
D = 7
N = 33
M = 8^7 % 33
8 * 8 * 8 * 8 * 8 * 8 * 8=2097152
8 * 8 * 8 * 8 * 8 * 8 * 8 % 33 = 2
密文 “8” 经过 RSA 解密后变成了明文 2。
