RSA 加密原理
| 步驟 | 說明 | 描述 | 備注 |
|---|---|---|---|
| 1 | 找出質(zhì)數(shù) | P 、Q | - |
| 2 | 計算公共模數(shù) | N = P * Q | - |
| 3 | 歐拉函數(shù) | φ(N) = (P-1)(Q-1) | - |
| 4 | 計算公鑰E | 1 < E < φ(N) | E的取值必須是整數(shù)E 和 φ(N) 必須是互質(zhì)數(shù) |
| 5 | 計算私鑰D | E * D % φ(N) = 1 | - |
| 6 | 加密 | C ＝ M E mod N | C：密文 M：明文 |
| 7 | 解密 | M ＝C D mod N | C：密文 M：明文 |
公鑰＝(E , N)
私鑰＝(D, N)
對外，我們只暴露公鑰。
示例
1、找出質(zhì)數(shù) P 、Q
P = 3
Q = 11
- 1
- 2
2、計算公共模數(shù)
N = P * Q = 3 * 11 = 33
N = 33
- 1
- 2
3、 歐拉函數(shù)
φ(N) = (P-1)(Q-1) = 2 * 10 = 20
φ(N) = 20
- 1
- 2
4、計算公鑰E
1 < E < φ(N)
1 <E < 20
- 1
- 2
E 的取值范圍 {3, 7, 9, 11, 13, 17, 19}
E的取值必須是整數(shù), E 和 φ(N) 必須是互質(zhì)數(shù)
為了測試，我們?nèi)∽钚〉闹?E =3
3 和 φ(N) =20 互為質(zhì)數(shù)，滿足條件
5、計算私鑰D
E * D % φ(N) = 1
3 * D % 20 = 1
- 1
- 2
根據(jù)上面可計算出 D = 7
6、公鑰加密
我們這里為了演示，就加密一個比較小的數(shù)字 M = 2
公式：C ＝ ME mod N
M = 2
E = 3
N = 33
- 1
- 2
- 3
C = 23 % 33 = 8
明文 “2” 經(jīng)過 RSA 加密后變成了密文 “8”
7、私鑰解密
M ＝CD mod N
C = 8
D = 7
N = 33
- 1
- 2
- 3
M = 87 % 33
8 * 8 * 8 * 8 * 8 * 8 * 8=2097152
8 * 8 * 8 * 8 * 8 * 8 * 8 % 33 = 2
密文 “8” 經(jīng)過 RSA 解密后變成了明文 2。
公鑰加密 - 私鑰解密流程圖
image
私鑰加密 - 公鑰解密流程圖
image
