| 步骤 | 描述 | 注释 |
|---|---|---|
| 找出两个质数 | P,Q | |
| 计算公共模数 | N=P*Q | |
| 欧拉函数 | φ(N)=(P-1)(Q-1) | |
| 计算公钥E | 1<E<φ(N) | E的取值必须是整数 E和φ(N)必须是互质数 |
| 计算私钥D | E*D%φ(N)=1 | |
| 加密 | C=M的E次方 mod N | C：密文 M：明文 |
| 解密 | M=C的D次方 mod N | C：密文 M：明文 |
公钥=(E,N)
私钥=(D,N)
解密
示例
1，找出质数P,Q
$$
P=3
$$
$$
Q=11
$$
2，计算公共模数
$$
N=PQ=311=33
$$
3，欧拉函数
$$
φ(N) = (P-1)(Q-1) = 2 * 10 = 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 mod φ(N) = 1
$$
$$
3 * D mod 20 = 1
$$
6，公钥加密
M = 2
E = 3
N = 33
C = 8
7，私钥解密
C = 8
D = 7
N = 33
M = 2
