如何用上锁的箱子传递开箱子的钥匙：神奇的非对称加密
自从密码学诞生的那一天起，人们就面临着一个悖论。加密是为了安全地传递信息，但为了让接受者解开加密的信息，你又需要把密钥给他，那这个密钥又该怎么传递呢？如果不加密传递给他的话，有被截获的风险。但如果加密发送的话，接受者还没有密钥，又怎么能解开呢？这就变成了一个鸡生蛋、蛋生鸡的问题。
如果用形象一点的例子来说明的话，相当于A要向B传递一封信，但他不信任邮差，所以他把信放在一个箱子里锁起来，再让邮差把箱子送给B。但B收到箱子也是没有用的，因为他没有钥匙。那么这把钥匙要怎么送给B呢？直接让邮差送是不行的，因为邮差可能会打开箱子看信里的内容。那把第一个箱子的钥匙放进第二个箱子再锁起来呢？这样也不行，因为B也没有第二个箱子的钥匙。这样就陷入了一个死循环。
在1977年之前，这个问题基本上是无解的。二战时德军发明了超级复杂的加密机器英格玛机，但这个机子的密码本还是得用传统的方式送往前线，这样才能完成正常的加密和解密工作。如果一本密码本被截获，那么至少某一段时间内的加密通信就不再安全了。
后来，有人想到了一个办法：A先把信放到箱子里后上一把锁，然后让邮差把箱子送给B。B在接到箱子后不打开，而是再上一把锁，这样箱子上就有两把锁了。B再让邮差把箱子送回给A，然后A把箱子上自己那把锁打开，让邮差再把箱子送回给B。这时箱子上只有B的一把锁了，B用自己的钥匙把箱子打开就可以了。这个过程中，邮差接触不到任何一把钥匙。
这种方法用箱子和锁来操作虽然行得通，但计算机算法却很难实现。因为一份数据先后经过了A算法加密、B算法加密，却要先用A的密钥来解密。而且同样的数据要来来回回发送三次，严重降低了通信效率。
1977年，三位科学家Rivest、Shamir、Adleman共同发明了一种牛逼算法，彻底解决了这个问题。
在这种算法中有公钥和私钥两种密钥，其中公钥可以公布给全世界的人知道，人们可以用公钥给数据加密。而只有拥有对应私钥的人才能对加密后的数据进行解密。这样人们就避免了密钥传递的问题。
如果用前面锁和箱子的例子来比喻的话，就相当于B制造了无数的处于开启状态的锁，并把这些锁丢在一个公共的广场上，同时B手里掌握着能打开这些锁的唯一的钥匙。如果有人要向B写一封信，他就把信放进到箱子里，然后从广场上捡一把锁回来把箱子锁上。接下来，他让邮差把这个箱子送到B那里去，B再用手里的钥匙把箱子打开。整个过程中，邮差都没有接触过钥匙。
就这样，划时代的非对称式加密算法诞生了。人们用三名科学家姓氏的首字母来命名这种算法：RSA算法。
那么，RSA算法里的公钥和密钥到底长什么样子？我们今天就来把这个问题讲清楚。
要想实现RSA这样的非对称加密，首先你需要找到一种运算。这种运算正向算起来很容易，但它的逆运算却非常非常困难。我们来举一个例子吧，假如你有十桶不同颜色的油漆，你按比例把他们混合在一起，会得到一种新的颜色，这是一件很容易做到的事情。但你让一个人拿着混合好的油漆，让他逆向推导出来你用了哪几种油漆、勾兑比例是什么，这就是一件很难的事情。
在RSA算法中，作者巧妙地使用质数设计了这样一种运算。比如说，现在给你两个质数1559和2273，让你计算它们的乘积。你很快就能算出答案是3543607，很容易对不对？但你现在把3543607给另外一个人，让他告诉你这是哪两个质数的乘积，他要看着质数表，花很长的时间才能试出这个结果。这只不过是两个四位的质数，在实际的通信加密中，人们使用的是上百、上千位的大质数，这就使得逆向计算更加困难。如果用现在的计算机对2048位的数字进行暴力分解，可能要花费几百年的时间。所以，我们认为可以这样的数字是无法被暴力破解的。
如果你还是觉得太抽象，那么我们今天就来实打实地加密解密一次，让你感受一下RSA算法到底是怎么回事。
假设我们在国外潜伏了一名优秀的间谍，现在他需要用加密的方式发送一个数字“15”给我们。我们知道，任何信息在电脑上都可以转换为数字，所以能发送加密的数字就意味着能发送任何加密的信息。
我们先想办法搞一个公钥出来。首先我们需要选择两个质数，为了计算方便我们就选择13和17这两个数吧。你只要知道在实际加密中用的是比这个大得多的数字就行了，计算原理都是一样的。
我们首先计算出13 X 17 = 221，好，记住221这个数字。
然后，我们把13和17各减去1，再乘起来，也就是12 X 16 = 192。接下来我们要随机选择一个小于192且与192互质的数。两个数互质的意思是他们没有除了1以外的公约数。
我们把192分解成因数相乘的形式：
192 = 2 X 2 X 2 X 2 X 2 X 2 X 3
我们就随便选择一个不能被2和3整除的数好了，我们这里就选择5吧。好，（221，5）这一对数字就是你的公钥。当221是一个很大很大的数字的时候，没人能够算的出来它是13和17的乘积，所以你可以放心地把它公开给全世界。
拿到这个公钥后，我们的间谍可以开始加密了。他看到公钥中的第二个数字是5，所以他先计算一下15的5次方，也就是：
15^5 = 759375
然后他再用这个数字除以221，也就是公钥中的第一个数字，计算出来的余数是19。这个数字就是间谍要发给我们的经过加密后的数字。
我们在收到19这个数字后，下一步就是用私钥对它进行解密了。我们得先计算出我们的私钥。还记得我们之前算出来的192和我们随机选择的5吗？我们要找到这样一个数：它是5的倍数，然后除以192刚好余1。这个数很好找，它就是385。然后385除以5等于77，那么（221，77）就是你的私钥。跟公钥不同，私钥是绝对不能给别人的，因为只要有了私钥，就可以对间谍发给我们的加密信息进行解密了。
好了，我们开始解密吧。间谍发给我们的加密后的数字是19，我们手里的私钥是（221，77）。我们首先计算一下19的77次方，然后再计算它除以221的余数。注意如果你用excel去直接计算的话，是算不出结果的，因为19的77次方这个数字太大了。不过好在求余数的运算有一个性质，那就是两个数乘起来再求余数，计算结果等于“对两个数先分别求余数，然后把两个余数乘起来再求余数”，写成公式就是：
(a＊b)%c=(a%c)＊(b%c)%c
我们在excel里把19的77次方拆成几个数字的乘积，然后一步步计算出这几个数字除以221的余数，把这些余数乘起来再对221求余数，最后的答案是：
15
也就是我们的间谍想要发给我们的数字。这样，我们就完成了解密的过程。如果再有人跟你说数学没有用，请你直接把这篇文章甩到他脸上。
最后顺便讲一下，为什么大家都说如果量子计算机被发明后，RAS加密算法就无效了呢？因为人们相信量子计算机可以在很短的时间内把两个大质数的乘积进行分解。在本文的例子中，如果有人用量子计算机对221进行了暴力分解，得到了13和17这两个数字，那么他就可以把这两个数分别减去1然后乘起来得到192。然后公钥（221，5）是公开的，所以他也可以去找到那个“5的倍数、被192除余1”的数，也就是385。385除以5等于77，这个77是什么呢？就是你手里的私钥（221，77）。这样，这套密码就等于被破解了。
- 全文完 -
最后，欢迎关注我的公众号“十一点半讲历史”并加星标，不错过每一篇推送。
