vlambda博客
学习文章列表

关于非对称加密，小蔚已经聊过很多次，这一次我们继续更深入的探讨一下。

近现代，密码学已经成为一个重要的学科，无论是军事还是生活，处处都有密码学的身影。

从密码学诞生之日起，一个难题始终困扰着人们。为了让接收信息的一方获得原始信息，必须事先将解密的方法告诉对方。但这样一来，解密的方法就存在泄露的风险，一旦泄露，所加密的信息就会在阳光下裸奔。

有没有一种方法，不需要事先告诉对方解密的方法，就可以让对方轻易获取被加密的信息呢？

如果甲写了一封机密信件，打算发送给乙。甲所在的地区只有一个邮差，而且甲已经知道这名邮差是个间谍，会千方百计找机会窃取机密信件。

于是甲将这封机密信锁在一个无法被暴力破坏的铁箱子里，打开箱子的唯一方法是获得钥匙，将机密信件锁在铁箱子里后，再让邮差将箱子送给乙。

问题是，乙没有钥匙，也打不开这个铁箱子。

先邮寄铁箱子，再邮寄钥匙？这样也不行，邮差可以轻易获得钥匙，打开铁箱子。

先让乙邮寄一把锁过来，然后再用乙的锁锁铁箱子？还是不行。只要锁或者钥匙经过邮差的手，机密信就不安全。

在很久很久以前，人们只能通过“线下”的方式来解决这个问题。两个人线下见面商量一个“密钥”，再在通信时使用这个密钥进行加密。

但这样做还是存在泄密的风险，不怀好意的人总能找到破绽窃取秘密。

后来，聪明的人想到了一个办法：

甲先将上锁的箱子邮寄给乙，乙虽然打不开，但可以在箱子上再加一把锁，再邮寄回给甲。甲使用自己的钥匙打开锁后，又邮寄给乙，最终乙用自己的钥匙打开箱子，拿到这封机密信件。

这个方法看起来行得通，整个过程邮差接触不到钥匙，打不开箱子。

不过这个方法有一个很大的问题——效率。以前只需要一趟，现在却需要三趟。要知道，信息的时效性是非常重要的，李云龙在攻打平安县城时说过：“你少来那一套！你我都知道一分钟就能决定战斗的胜负！”

要是传递信息的时间增加了两倍，后果不堪设想。

兼具安全和效率的方法，一直没有被找到，直到1977年，一种设计巧妙的方法被发明了出来。

它就是大名鼎鼎的“非对称加密。”

非对称加密算法需要两把密钥来进行加密的解密，一把公开密钥，只能用于加密，一把私有密钥，只能用于解密。公钥和密钥合在一起形成“密钥对。”

公钥是公开的，任何人都可以用公钥加密数据，持有这一公钥对应私钥的人，才能解密，这样一来，就不存在要传递“钥匙”的情况，同时也兼顾了效率。

只要用我的公钥加密数据，全世界的锁我都能解开，而且只有我行！

按照上面的例子进行解释，非对称加密大致是这样的过程：

甲将大量的钥匙散发到全世界各地，并宣布凡是要与自己通信的，只需要将信息放到铁箱子里，并用这些钥匙（公钥）上锁即可。（假定锁必须有钥匙才能上锁）

假如乙要和甲取得联系，只需要将机密信件放入一个铁箱子里，并用甲的公钥上锁，紧接着邮寄给甲，甲就可以用自己的私钥开锁拿到信件。

整个过程，甲、乙既不需要对方的密钥，邮差只能拿到公钥，公钥只能加密不能解密，从而保证了信件的安全性。

接下来我们来真实地感受一下非对称加密的艺术。

这种算法跟质数分不开。

现在给你13和17两个质数，让你算出它们的乘积，我们很容易算出是221。

如果告诉你221这个数字，要求你算出这是哪两个质数的乘积，就比较难了。你得翻一翻质数表，才能知道原来这个数是13和17。

这只是两位数质数的乘积，如果是几十位、上百位甚至上千位的质数乘积呢？逆向推理就变得十分困难。

举个五位数的例子，请问9936899831是哪两个质数的乘积？

虽然有困难，但通过计算机，还是可以得出这两个数是99679和99689。但如果是上千位数，就十分困难了。

以现在计算机的算力，要对一个2048位的数字进行暴力破解，可能要用上几百年的时间，可以被认为是无法破解的。

为了方便计算和理解，我们还是使用13和17这两个质数。

假如甲要发送“15”给乙，为了数据传输安全，乙首先要生成一个密钥对，即一个公钥和一个私钥。

首先13*17=221。

然后我们把13和17各减去1，再乘起来，也就是12 X 16 = 192。接下来我们要随机选择一个小于192且与192互质的数。两个数互质的意思是他们没有除了1以外的公约数。我们把192分解成因数相乘的形式：

192 = 2* 22222*3

选择一个不能被2和3整除的数，我们就选择5这个数字。

（221,5）就是公钥。

这个公钥可以让任何人知道，完全没有关系，所有人都可以使用这个公钥加密数据，然后发送给你。

还记得我们之前算出来的192和我们随机选择的5吗？我们要找到这样一个数：它是5的倍数，然后除以192刚好余1。这个数很好找，它就是385。然后385除以5等于77。

于是我们得出了私钥：（221,77）。

私钥只能自己知道，一旦泄露，传输的数据就等于是在阳光下裸奔。

好了，有了密钥对，我们终于可以进行加密和解密了。

甲先将想要发送的信息，也就是“15”这个数字，使用乙的公钥进行加密。乙的公钥是（221,5）。

首先甲算出15的5次方，得出759375这个数字。接着再用759375除以221，得出余数是19。

最后一步，甲将“19”发送给乙。

乙拿到“19”后，使用私钥进行解密。私钥是（221,77）。

首先乙会先计算19的77次方，然后再用得到的数字除以221，求出该数的余数，得出最终的答案就是“15！”

非对称加密大体上就是这么一个过程，非常具有艺术感！

那么，非对称加密有没有缺点呢？

有！还是效率问题。

如果甲和乙商量好一个密钥，假定这个密钥是数字“5”，甲想发给乙“15”这个数字，甲首先会用15*5得到75，再将“75”这个数字发给乙，乙拿到数字后，再除以5，就能得到“15”这个数字。

上面这种方法就是对称加密。它的缺点是安全性很差，加密和解密都使用同一个密钥，一旦密钥泄露，传输的数据就无安全性可言。

但它有一个好处，就是效率高。甲乙传递的信息，只需要乘以5和除以5即可，没有非对称加密这么复杂。

于是，有一个聪明的家伙，结合非对称加密和对称加密，使其具备效率和安全性的优势。

具体是怎么做的呢？

思路如下：

首先利用非对称加密传递“密钥”，对方拥有密钥后，再使用密钥传输数据即可，这样一来，既保证了安全性，又有效率。

还是上面的例子。数字“5”是密钥，甲首先使用乙的公钥（221,5）进行加密。

5的5次方，除以221的余数是31，甲将31发送给乙，乙拿到这个数字后，再利用私钥（221,77）解密，算出31的77次方除以221的余数是5。

此时乙已经知道了“5”这个密钥。

以后，甲和乙就用“5”这个密钥进行对称加密的数据传输。

第二次通讯时，甲要传递“6”，只要5*6=30，传给乙30这个数字，乙再用30/5得到6即可。

第一次用非对称加密传递密钥，第二次之后用对称加密进行通讯加密，安全性有了，效率也有了。

可能熟悉的同学已经知道了，对，SSL证书就是这么干的！