这篇文章上次修改于 2019 天前，可能其部分内容已经发生变化，如有疑问可询问作者。

5.公钥密码

秘钥配送问题（key distribution problem）

公钥密码（public-key cryptography）

秘钥分为加密秘钥和解密秘钥，发送者使用加密秘钥对消息加密，接收者使用解密秘钥对密文解密。

RSA 加密

加密： E次方的mod N
解密： D次方的mod N

生成秘钥对

• 1 求N
• 2 求L (L是仅在生成秘钥对的过程中使用的数）
• 3 求E
• 4 求D

1. 求N

首先准备两个很大的质数，p, q
使用伪随机数生成器生成512bit的数，再判断这个数是不是质数，不是的话重新生成。判断是不是质数通过数学方法。费马测试，米勒*拉宾测试

1. 求L

L是p-1 和q-1 的最小公倍数

1. 求E

E是一个比1大， 比L小的数，E和L的最大公约数必须为1，通过伪随机数生成1到E之间的数，判断最大公约数是否为1，求最大公约数使用辗转相除法。

1. 求D

数字D是通过E计算得到

1 < D < L
E x D mod L = 1