公钥密码学的诞生

虽然密码学家们设计了多种安全的加密算法，但这些加密算法在使用之前都要解决一个很麻烦的问题：密钥分发问题。

以门锁为例。我们几乎每天都要和门锁与钥匙打交道。安全的门锁大概有什么样的要求呢？简单地说有这么几条：

•  门锁要非常坚固，如果没有钥匙的话，任何人都不能够打开门锁；

•  钥匙必须足够复杂，除非得到了原始的开锁钥匙，否则钥匙非常难以复制；

•  当然了，门本身也必须足够结实。

对应来看的话，加密算法也需要具有这些特征：

•  加密算法要足够安全，没有密钥的攻击者无法从密文中解读出任何有价值的信息；

•  密钥必须足够复杂，足够长，哪怕密钥有一个数设置错误，都无法正确解密；

•  当然了，使用加密算法时也需要足够小心，不要有操作上的失误。

按照这样的安全要求，人们制作了很多安全的门锁，对应的钥匙也变得越来越复杂。但是，这些门锁都有一个共同的问题：锁门的时候必须用钥匙锁！在实际生活中这是个好事：如果不用钥匙锁，我把门直接撞上而自己又没带钥匙，岂不是我本人也进不去了。如果只是我自己或者家人锁门的话还好。可是，如果我希望别人帮我锁门的话，事情就比较麻烦了，比如：

•  亲戚来我家做客，但我临时有事要出门，不知道几点回来。难道我要请亲戚看家，等我回来再离开吗？最好的方法是亲戚离开我家的时候，帮我把门撞上就好了。

•  我新买了一套房子，需要装修队装修。装修过程中，我可以每天早上来新家把门打开，允许装修队随时进入。但是，如果今天的装修工作结束了，装修队需要等我晚上回来把门锁上才能走？

人类的智慧是无穷的。为了解决上面的问题，人类设计了能撞门的锁。锁门的时候，我们就不再需要钥匙了，直接把门撞上就可以离开。只要把门撞好，没有钥匙同样也打不开门锁。

图 17：对称加密体制简析

在双方进行通信时，我们也会遇到这样的问题。通信就好像双方互相之间发送密码保险箱一样：发送方把信息放在保险箱中，用钥匙将保险箱锁住，这就是加密过程；接收方用相同的钥匙打开保险箱，得到放置在内部的信息，这就是解密过程，整个过程如图 17 所示。在公钥密码学诞生之前，密码学家们所设计的所有加密算法都遵从了上面的原理。由于加密解密所使用的密钥相同的，看起来就像是镜子里面对称的一样，因此密码学上把这类加密方法称为「对称加密」（Symmetric Encryption）。

然而，我们遇到了一个很棘手的问题：双方在通信之前如何得到同一个保险箱的同一个钥匙呢？仅有的办法是两个人一同购买一个保险箱，每个人拿着一把钥匙。然而，在实际通信过程中绝大多数情况下双方很难见面，怎么办呢？第二次世界大战期间，德军解决的方法是设立通信兵。通信兵每个月集合一次，集合时下发这个月所使用的恩格玛机密钥。图 18 就是德军所使用的密钥表。表格中从左到右依次为：转子的排列顺序、转子的初始位置、插接板的连接方法、为进一步增加安全性所使用的附加密码。

图 18：德军所使用的恩格玛机密钥表

http://www.cryptomuseum.com/crypto/enigma/ukwd/img/lw_key_2744_full.jpg

那么，在密码学上能不能找到一种类似撞门的方法：设计一种加密算法，使得加密明文时发送方不需要知道密钥，只使用一个接收方公开的信息实现加密；解密时，接收方仍然可以使用自己的密钥进行解密，而其他人却无法从密文中获取任何有价值的信息呢？也就是实现如图 19 所示的过程。这时候，加密和解密所使用的密钥就不一样了，密钥不再对称。密码学上把这种加密方法称为「非对称加密」（Asymmetric Encryption）。由于加密时，发送方虽然也使用了密钥，但这个密钥是接收方向全世界公开的，因此这种加密方法又被称为「公钥加密」（Public Key Encryption）。所有利用公钥思想实现的密码学被称为「公钥密码学」（Public Key Cryptography）。在 1976 年之前，公钥密码学的想法被视为天方夜谭。但在 1976 年，密码学的天才们提出了并实现了这个想法。而这个想法的实现就用到了前面讲到的质数性质和困难问题。

图 19：非对称加密体制简析

讲到这里，我需要隆重推出一位为公钥密码学做出了突出贡献，但却鲜为人知的天才密码学家 Ralph Merkle[54]。Merkle 于 1970 年开始在伯克利大学研究计算机科学，并于 1974 年和 1977 年分别在伯克利大学获得了学士和硕士学位。Merkle 是个天才，在所有密码学家们还在深入研究对称加密体制等传统密码学时，Merkle 于 1974 年就提出了公钥密码学的思想：

是否可以在不安全的通信信道中建立安全通信机制？

然而，Merkle 的思想遭到了伯克利大学老师的严重反对。Merkle 在撰写博士研究计划时提出了两个项目，第 1 个项目就是公钥密码学的思想。然而，在浏览了 Merkle 所提出的思想后，伯克利大学老师对其的评论是：

第二个项目看起来更合理一些，或许是因为你所描述第一个项目实在是太糟糕了⁽ⁱⁱ⁾。

图 20：伯克利大学老师对Merkle 项目的评价，红色方框里为具体内容

http://119.90.25.33/www.merkle.com/1974/FirstCS244projectProposal.pdf

不幸的是，不光伯克利大学的老师们不认可 Merkle 的思想，当时世界上几乎所有的密码学家们也都不认同这一思想。Merkle 在 1975 年投稿至著名国际期刊「Communications of the ACM」的论文「不可信信道中实现安全通信」（Secure Communications over Insecure Channels）也被无情的拒稿。图 21 是「Communications of the ACM」的编辑给出的论文最终结论。

由于研究成果不被认可，Merkle 无法在伯克利取得博士学位。就在绝望的时候，他了解到斯坦福大学的两位老师 Diffie 与 Hellman 也在朦胧地考虑公钥密码学的思想。于是，Merkle 便前往斯坦福大学，成为 Hellman 的博士生，并于 Diffie 老师合作，继续践行自己的想法。

1976 年，信息理论的著名国际期刊「IEEE Transactions on Information Theory」向Diffie 与Hellman 发出邀请，希望他们撰写一篇论文，介绍密码学的最新研究进展。当时 Merkle 还是 Hellman 的博士生，这样著名的期刊当然不会邀请Merkle 撰写文章了。于是，Diffie 与 Hellman 作为作者，受邀在这一著名的国际期刊上发表了划时代的论文「New Directions in Cryptography」[55]。在论文中，Diffie 与 Hellman 首次公开了一种方法，使得通信双方可以通过不可信的信道分享出一个相同的密钥。Diffie 与 Hellman 因此成为了第一个公开提出公钥密码学思想的学者。后来，人们把这个协商密钥的方法称为 Diffie-Hellman 密钥协商协议。在论文发表 30 年后的 2015 年，Diffie 与 Hellman 因这一杰出贡献获得了图灵奖。

图 21：1975 年Communications of the ACM发送给Merkle 的拒稿信

http://119.90.25.22/www.merkle.com/1974/RejectionLetter.pdf

这样一个划时代的成果，其算法的构造会及其复杂吧？实际上，这个算法之简单，只要大家阅读了前面所介绍的模质数 p 下的运算，就可以很好地理解Diffie-Hellman 密钥协商协议。

图 22：（从右至左）Diffie、Hellman 与 Merkle 在一起工作

https://pic3.zhimg.com/e4d9cb99b4c9d5cc05e4744c1002b40e_r.png

图 23 给出了密钥协商协议的具体流程。假定 Alice 和 Bob 要在不安全的信道上共享一个密钥。所谓不安全的信道，是指攻击者可以看到 Alice 与 Bob 通信的全部内容。Diffie-Hellman 密钥协商协议流程如下：

1. Alice 和 Bob 约定一个很大的质数 p，以及模 p 下的生成元 g；

2. Alice 选择一个小于 p 的秘密随机数 a，计算 A=g^a(mod p)，并把 A 发送给 Bob；

3. Bob 选择一个小于 p 的秘密随机数 b，计算 B=g^b(mod p)，并把 B 发送给 Alice；

4. Alice 收到 B 后，计算 Key=B^a=(g^b)^a=g^ab(mod p)

5. Bob 收到 A 后，计算 Key=A^b=(g^a)^b=g^ab(mod p)

整个过程中，Alice 向 Bob 发送了 A，Bob 向 Alice 发送了 B。所有计算都可以快速完成。

这个协议神奇的地方在于，A、B、p、g 都可以通过不安全的信道发送。就算攻击者看到了 A、B、p、g，他也无法知道 Key 的值是多少。为什么呢？直观来看，想要得到 Key 的值，攻击者至少需要根据 A、g 和质数 p 求 a=log g^A ，或者根据B、g 和质数 p 求 b=log g^B。但这就要解决模质数 p 下的离散对数问题。前面已经讲过，离散对数问题是一个非常困难的问题，并没有方法可以快速解决。因此，只要 Alice 和 Bob 选择了足够大的 p，攻击者就算看到了 Alice 和 Bob 发送的全部信息，对于获取密钥 Key 也无能为力。实际上，已知 p、g、A=g^a(mod p)、B=g^b(mod p)，求 Key=g^ab(mod p) 的问题，称为计算 Diffie-Hellman 问题（Computational Diffie-Hellman 问题），这个问题几乎和离散对数问题一样困难。

图 23：Diffie-Hellman 密钥协商协议

随着 1976 年 Diffie 与 Hellman 这篇划时代论文的公布，密码学家们才真正认识到公钥密码学的来临。他们对 Merkle 的判断出现了错误。因此，在 1978 年，「Communications of the ACM」弥补了 1975 年所犯下的错误，正式接收了 Merkle 的论文「Secure Communications over Insecure Channels」[56]。

Diffie-Hellman 密钥协商协议现在仍然被认为是安全的。我们在浏览互联网时，Diffie-Hellman 密钥协商协议就在默默地保护着我们。本文中的大多数信息参考来源：维基百科网站，就在使用 Diffie-Hellman 密钥协商协议的变种，基于椭圆曲线的 Diffie-Hellman 密钥协商协议与我们的浏览器建立通信。图 24 是 2016 年 8 月 5 日中文维基百科网站的安全信息。「公钥参数」一栏写的是「ECDH_P256」。EC 就是椭圆曲线英文「Elliptic Curve」的缩写，DH 就是 Diffie-Hellman 的缩写，后面的 P256 指的是使用了模数为 256 为质数 P 的椭圆曲线。

图 24：维基百科的证书信息

https://zh.wikipedia.org/wiki/Wikipedia:%E9%A6%96%E9%A1%B5. Accessed 2016.08.05

Diffie-Hellman 密钥协商协议虽然很不错，但它在功能上有一个严重的缺失：人们只能用这个协议共享一个密钥，但是不能直接用这个协议实现信息的加密。这个问题在很长时间内一直困扰着 Diffie、Hellman 与 Merkle。实际上，他们只需要再突破一点点就能达到目的了。然而，在科学研究中，哪怕是这样一点点的突破都非常的困难。直到 1985 年，密码学家 ElGamal 才改进了 Diffie-Hellman 密钥协商协议，使它可以实现信息的加密。这个加密方案被称为 ElGamal 加密方案[57]。

那么，如何利用困难问题实现公钥加密呢？1976 年，来自麻省理工学院的三位年轻密码学家 Ron Rivest、Adi Shamir、Leonard Adleman 提出了一种模数为合数 n 下的算法，彻底实现了公钥加密的功能[58]。这个算法后来就以他们三个人的形式开头字母组成，称为 RSA 算法。

图 25：Rivest、Shamir 与Adleman

http://www.boiledbeans.net/wp-content/uploads/2007/10/3d454f411f112cb3df7e62ed5907b4a0.jpg

RSA 算法拥有三个步骤：密钥生成、加密、解密。Alice 执行密钥生成步骤，得到自己的公钥和私钥，并把公钥向外界公开。发送方 Bob 将利用 Alice 的公钥对明文进行加密，并把加密结果发送给 Alice。只有拥有公钥所对应私钥的 Alice 才能执行解密步骤，正确恢复出明文。RSA算法的具体过程如图 26 所示：

•  密钥生成：Alice 选择两个大质数 p、q，计算 n=p×q。随后，Alice 选择一个与欧拉函数 φ(n)=(p−1)(q−1) 互质的数 e，并计算 d=e^-1mod(p−1)(q−1)。前面我们知道，只有当 e 和 (p−1)(q−1) 互质，Alice 才能找到满足条件的 d。Alice 的私钥为 d，公钥为 (n, e)。

•  加密：Bob 想要给 Alice 发送明文 m，Bob 简单地计算 C=m^emod n，就得到了密文。

•  解密：Alice 收到密文C后，计算 C^d=(m^e)^d=m^ed=m^e×e−1=m¹=m(mod n)。

图 26：RSA算法

由于Alice 知道 n 的质因数 p 和 q，她可以很容易计算得到 (p−1)(q−1)，这样就可以求得私钥 d 了。然而，攻击者并不知道 n 的质因子，因此也就无法得到 (p−1)(q−1)。由于攻击者无法从公钥 e 中求得 d，因此攻击者无法从密文中解密出明文 m。由于对于比较大的 n 来说，n 整数分解是一个公认困难问题，因此攻击者对密文就无能为力了。

讲到这里有的朋友们会提出这样一个疑问：攻击者只能通过对 n 求整数分解，才能得到 d，或者才能得到 m 吗？是否有什么投机取巧的方法？很遗憾，经过 30 多年密码学家们的研究，只要各个数的选择得当，求 m 与 n 的整数分解几乎是一样困难的[59]。

RSA 算法构造即为简单，也很容易理解，只需要知道质数、合数、同余、指数运算、互质等基本的数学概念，结合一定的要求即可正确使用。与此同时，通过调换公钥和私钥的位置，RSA 还可以实现公钥密码学中的另一个功能：「数字签名」。现今，RSA 依然是被广泛使用的公钥加密与数字签名方案。我们常用的知乎网站就使用了 2048 位的 RSA。图 27 为知乎网站的安全信息。「公钥」一栏写的是「RSA (2048Bits)」，表示该网站使用了RSA算法，其合数 n 的程度为二进制 2048 位。

图 27：知乎的证书信息

https://www.zhihu.com. Accessed 2016.08.05

1994 年，麻省理工学院的教授 Peter Shor[60]宣称他找到了一个算法，可以快速解决整数分解问题，这个算法被称为 Shor 算法[61]。全世界的数学家们和密码学家们开始时对此并不太感兴趣，因为全世界几乎每隔一段时间就会有某个人站出来表示自己解决的整数分解问题，但是所有的算法都有严重的问题。然而，经过深入的检查后，全世界的数学家们发现，Peter Shor 所提出的算法没有任何问题，确实能快速解决整数分解问题[62]。唯一的遗憾是，他的算法在普通计算机上无法实现，而是需要在还不存在的「量子计算机」上实现。后续的研究工作表明，Shor 所提出的算法不仅可以解决整数分解问题，还可以经过修改后解决离散对数问题。如果在未来人类真的研制出了量子计算机，那么 Diffie-Hellman 密钥协商协议、RSA 算法，以及后续提出的多种公钥加密算法将都将变得不安全。

在 1994 年，就算是当时的超级计算机也是体积巨大、计算缓慢，量子计算机更是痴人说梦了。然而，20 多年后的今天，量子计算机正逐渐走进了人类的视野。量子计算机将为人类带来更强的计算能力。然而，它的到来真的会使得公钥密码学再一次坠入深渊吗？

我们还有希望。为了让密码学迎接量子计算机的挑战，2016 年 7 月 7 日，谷歌公司宣布将发起为期 2 年的研究，将抗量子计算攻击的新型公钥加密算法「新希望算法」（New Hope）[63]应用于谷歌的 Chrome 浏览器[64]。新希望算法中同样出现了质数的影子，只不过质数的使用方法变得更加复杂。现在，后量子时代的密码学正得到蓬勃的发展。公钥密码学将要走向何方？质数能否继续保护互联网时代的信息安全呢？我们拭目以待。

(ii) 原文为：Project 2 looks more reasonable, maybe because your describing Project 1 is huddled terribly.参见图 20。