公钥密码（非对称加密）

痛定思痛。 2022-11-20 08:22 216阅读 0赞

### 文章目录 ###

*   *   *   *  （一）秘钥配送问题
             *  （二）公钥秘钥
             *   *  （1）介绍
                 *  （2）公钥通信流程
             *  （三）RSA
             *   *  （1）介绍
                 *  （2）加密和解密
                 *  （3）生成密钥对
                 *  （4）生成密钥对详细步骤

#### （一）秘钥配送问题 ####

在对称加密的过程中，A如果想要给B发送信息，那么A需要将秘钥告诉B，然后B通过秘钥进行解密。但是在秘钥的发送过程中有可能被窃听者拦截并破解密文。

解决密钥配送问题的方法有以下几种:  
1：通过事先共享密钥来解决  
2：通过密钥分配中心来解决  
3：通过Diffie-Hellman密钥交换来解决  
4：通过公钥密码来解决

公钥密码解决秘钥配送问题  
在对称密码中，加密密钥和解密密钥是相同的，但公钥密码中，加密密钥和解密密钥却是不同的。只要拥有加密密钥，任何人都可以进行加密，但没有解密密钥是无法解密的。因此.公钥密码的一个重要性质，就是只有拥有解密密钥的人才能够进行解密。接收者事先将加密密钥发送给发送者，这个加密密钥即便被窃听者获取也没有问题。发送者使用加密密钥对通信内容进行加密并发送给接收者，而只有拥有解密密钥的人(即接收者本人)才能够进行解密。这样一来，就用不着将解密密钥配送给接收者了，也就是说，对称密码的密钥配送问题,可以通过使用公钥密码来解决。

#### （二）公钥秘钥 ####

##### （1）介绍 #####

公钥密码( public-key cryptography )中，密钥分为加密密钥和解密密钥两种。发送者用加密密钥对消息进行加密，接收者用解密密钥对密文进行解密。要理解公钥密码，清楚地区分加密密钥和解密密钥是非常重要的。加密密钥是发送者加密时使用的，而解密密钥则是接收者解密时使用的。

公钥和私钥是―一对应的，一对公钥和私钥统称为密钥对( key pair )。由公钥进行加密的密文，必须使用与该公钥配对的私钥才能够解密。密钥对中的两个密钥之间具有非常密切的关系——数学上的关系——因此公钥和私钥是不能分别单独生成的。  
公钥密码的使用者需要生成一个包括公钥和私钥的密钥对，其中公钥会给别人，私钥则仅供自己使用。

##### （2）公钥通信流程 #####

假设Alice要给Bob发送一条消息，Alice是发送者,Bob是接收者，而这一次窃听者Eve依然能够窃听到他们之间的通信内容。  
在公钥密码通信中，通信过程是由接收者Bob来启动的。

(1) Bob生成一个包含公钥和私钥的密钥对。私钥由Bob自行妥善保管。

(2)Bob将自己的公钥发送给Alice。Bob的公钥被窃听者Eve截获也没关系。  
将公钥发送给Alice，表示 Bob请Alice用这个公钥对消息进行加密并发送给他。

(3) Alice用 Bob的公钥对消息进行加密。  
加密后的消息只有用Bob的私钥才能够解密。虽然Alice拥有 Bob的公钥,但用Bob的公钥是无法对密文进行解密的。

(4) Alice将密文发送给Bob。  
密文被窃听者Eve截获也没关系。Eve可能拥有Bob的公钥，但是用Bob的公钥是无法进行解密的。

(5) Bob用自己的私钥对密文进行解密。

（3）公钥密码无法解决的问题  
公钥密码解决了密钥配送问题，但这并不意味着它能够解决所有的问题，因为我们需要判断所得到的公钥是否正确合法，这个问题被称为公钥认证问题。此外，公钥密码还有一个问题就是，它的处理速度只有对称密码的几百分之一。

#### （三）RSA ####

##### （1）介绍 #####

RSA是一种公钥密码算法，它的名字是由它的三位开发者，即 Ron Rivest、Adi Shamir和Leonard Adleman的姓氏的首字母组成的( Rivest-Shamir-Leonard )。  
RSA可以被用于公钥密码和数字签名,1983年，RSA公司为RSA 算法在美国取得了专利，但现在该专利已经过期。

##### （2）加密和解密 #####

![在这里插入图片描述][20201027202345431.png_pic_center]  
RSA 的密文是对代表明文的数字的E次方求mod N的结果。换句话说，就是将明文和自己做E次乘法，然后将其结果除以N求余数，这个余数就是密文。

加密公式中出现的两个数——E和N，到底都是什么数呢?RSA的加密是求明文的E次方mod N，因此只要知道E和N这两个数，任何人都可以完成加密的运算。所以说，E和N是RSA加密的密钥，也就是说，E和N的组合就是公钥。

注意：  
E和N这两个数并不是密钥对(公钥和私钥的密钥对)。E和N两个数才组成了一个公钥，因此我们一般会写成“公钥是(E,N)”或者“公钥是\{E,N\}”这样的形式，将E和N用括号括起来。

对于解密，对表示密文的数字的D次方求mod N就可以得到明文。换句话说，将密文和自己做D次乘法，再对其结果除以N求余数，就可以得到明文。  
这里所使用的数字N和加密时使用的数字N是相同的。数D和数N组合起来就是RSA 的解密密钥，因此D和N的组合就是私钥。只有知道D和N两个数的人才能够完成解密的运算

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center]

##### （3）生成密钥对 #####

RSA 的加密是求“E次方的mod N”，解密是求“D次方的mod N"，那么这里需要用到的三个数——E、D和N到底应该如何生成呢?  
由于E和N是公钥，D和N是私钥，因此求E、D和N这三个数就是生成密钥对  
RSA  
密钥对的生成步骤如下:  
(1)求N  
(2)求L(L是仅在生成密钥对的过程中使用的数)  
(3)求E  
(4)求D

##### （4）生成密钥对详细步骤 #####

求N  
首先准备两个很大的质数。这两个很大的质数为p和q  
p和q太小的话，密码会变得容易破译，但太大的话计算时间又会变得很长。例如,假设p和q的大小都是512比特，相当于155位的十进制数字。  
要求出这样大的质数，需要通过伪随机数生成器生成一个512比特大小的数，再判断这个数是不是质数。如果伪随机数生成器生成的数不是质数，就需要用伪随机数生成器重新生成另一个数

判断一个数是不是质数并不是看它能不能分解质因数，而是通过数学上的判断方法来完成  
准备好两个很大的质数之后，我们将这两个数相乘，其结果就是数N。也就是说，数N可以用下列公式来表达:

N=p × q(p、q为质数)

求L  
L这个数在RSA 的加密和解密过程中都不出现，它只出现在生成密钥对的过程中。  
L是p-1和q-1的最小公倍数(least common multiple，lcm )。如果用lcm(X,Y)来表示“X和Y的最小公倍数”，则L可以写成下列形式:

![在这里插入图片描述][2020102720241119.png_pic_center]  
求E  
E是一个比1大、比L小的数。此外，E和L的最大公约数必须为1。如果用gcd(X, Y)来表示X和Y的最大公约数，则E和L之间存在下列关系:

![在这里插入图片描述][20201027202420376.png_pic_center]  
要找出满足gcd(E,L)=1的数，还是要使用伪随机数生成器。通过伪随机数生成器在1<E<L的范围内生成E的候选数，然后再判断其是否满足gcd(E,L)=1这个条件。求最大公约数可以使用欧几里得的辗转相除法。  
简单来说，之所以要加上E和L的最大公约数为1这个条件，是为了保证一定存在解密时需要使用的数D。  
现在我们已经求出了E和N，也就是说我们已经生成了密钥对中的公钥。

求D

数D是由数E计算得到的。D、E和L之间必须具备下列关系:

![在这里插入图片描述][20201027202431424.png_pic_center]  
只要数D满足上述条件，则通过E和N进行加密的密文，就可以通过D和N进行解密。要保证存在满足条件的D，就需要保证E和L的最大公约数为1，这也正中对E所要求的条件。  
简单来说，E X D mod L=1保证了对密文进行解密时能够得到原来的明文。现在我们已经求出了D和N，也就是说我们也生成了密钥对中的私钥。

![在这里插入图片描述][20201027202441436.png_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center 1]

[20201027202345431.png_pic_center]: /images/20221120/8514e3673c7b40b8aa674bbe1f2caad5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201027202355772.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ==,size_16,color_FFFFFF,t_70#pic_center
[2020102720241119.png_pic_center]: https://img-blog.csdnimg.cn/2020102720241119.png#pic_center
[20201027202420376.png_pic_center]: https://img-blog.csdnimg.cn/20201027202420376.png#pic_center
[20201027202431424.png_pic_center]: https://img-blog.csdnimg.cn/20201027202431424.png#pic_center
[20201027202441436.png_pic_center]: https://img-blog.csdnimg.cn/20201027202441436.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201027202446260.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L09jdG9wdXMyMQ==,size_16,color_FFFFFF,t_70#pic_center