vlambda博客
学习文章列表

手上只有一把钥匙,怎么解开全世界的锁?揭秘神奇的非对称加密

手上只有一把钥匙,怎么解开全世界的锁?揭秘神奇的非对称加密

作者丨小蔚

来源丨蔚可云(ID:wecloud-cn)

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

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

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

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

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

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

手上只有一把钥匙,怎么解开全世界的锁?揭秘神奇的非对称加密

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

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

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

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

手上只有一把钥匙,怎么解开全世界的锁?揭秘神奇的非对称加密

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

后来,聪明的人想到了一个办法:

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

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

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

手上只有一把钥匙,怎么解开全世界的锁?揭秘神奇的非对称加密

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

兼具安全和效率的方法,一直没有被找到,直到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证书就是这么干的!

手上只有一把钥匙,怎么解开全世界的锁?揭秘神奇的非对称加密