本文整理自Gilles Brassard教授的演讲。

视频

【墨子沙龙】Secrecy in a Quantum Word ——Gilles Brassard_腾讯视频

图文

我的报告主要是告诉大家，量子现象是如何改变我们在保密通信中的加密和解密方式的。

首先允许我给大家介绍一些密码学的内容。密码学长久以来都是两个角色之间的争斗，加密者和破译者。这种斗争已经持续了很长的时间了。比如说，这个叫做密码棒的东西，至少已经问世2500年之久了。它是密码学最早的见证者之一。可能有其他的东西比它更早。所以说密码学是一个古老的话题，在很长的时间内它都是一门艺术，但是现在变成了科学。

密码棒图片来源：维基百科

在今天的报告里，我们最关心的事情是：事实上，我们住在一个量子的世界中。Artur已经告诉我们一些关于量子的含义。事实上，我们确实住在一个量子的世界。这对于加密者来说是好事吗？或者换一种说法，量子的世界对加密者和破译者哪一个更好？和经典世界相比，有哪些东西发生了改变？当然，还有一个更重要的问题，在这个问题诞生之初人们就各执一词：谁将会获胜，加密者还是破译者？

我想先介绍一位科学家、诗人兼小说家，Edgar Allan Poe。他是一位19世纪的美国小说家和诗人，据我所知他没有任何的科学研究背景。而且我还知道他是一位非常优秀的自学成才的非专业破译密码学家。事实上，他写了一本叫做The Gold-Bug的小说，这本书是他最有名的著作之一。Poe讲了这样的一个故事，一个名叫William Legrand的人，他在森林中发现了这个看起来非常奇怪的手稿，他不知道这是什么。他想如果他透过光线来观察它，可能会有一些事情发生。因此他把这张羊皮纸靠近火光，想透过火光观察它。出乎他意料的是，当他把它靠得离火焰很近的时候，密文出现了。

William Legrand意识到这些文字一定和海盗宝藏的埋藏地点有关。他是怎么解密这段密文的呢？他解密的过程是一个非常精彩的故事，作者大约用了10页的文字来解释William Legrand如何破译一段这样的密文。这个故事十分有趣，许多现实世界的密码学家在他们小的时候都读到了这个故事，他们纷纷被密码学的艺术之美所吸引，进而成长为真正的密码学家，尤其是弗里德曼先生。

我们再回到这个故事，William Legrand已经有了这样的密文。首先要做的事是统计每个字符出现的次数。我们得到了这个结果——字符“8”是出现最频繁的。在大多数西方语言中，包括英语，出现次数最频繁的字母是“e”。因此William Legrand认为“8”就代表字母“e”。字符“4e;”出现了很多次。因为假设原文是英文，所以这必定是单词“the”。“the”是由3个字母构成并且以“e”结尾的、出现最频繁的单词。所以很可能“；”代表“t”，“4”代表“h”。在经过10页文字的推导后，他得到了结论——‘;’代表‘t’，‘4’代表 ‘h’，‘8’代表 ‘e’，等等。

The Gold-Bug 中密文和明文的对应关系

我们按照对应关系来替换掉密文中的字符——随便说一句，这叫做密钥，在密码学中，密钥是明文和密文之间相互转换的工具，William Legrand通过推理找到了密钥。密文经过变换后，我们就会得到明文。这样看起来就可以理解了。现在他需要把空格加在这段文字里。当加入空格后，我们得到了一段文字，看起来好像仍然不知所云。因为在这个时候，你需要在一定程度上去猜它是什么含义。最后他在当天就找到了宝藏，很棒。

The Gold-Bug 中的明文

Poe并不是第一个找到破解密文方法的人。这种加密方法是将每个字母替换为另一个符号。用密码学的术语叫作“单码替换法”。并不是Poe发明了破解单码替换法的方法，而是Al-Kindi。Al-Kindi也有多重身份，他在相当长的一生中写了300本书。尤其是他写了一本书，介绍了如何破译加密的信息。在这本书里，Al-Kindi解释了如何解码，如何破译Poe书中提到的那种类型的密码。你可能会认为这个工作是所有密码学或者说密码破译的起源，然而并不是。这本书有一部分遗失，直到距今不久才被发现。所以在历史上它并没很大的影响力，这是一件令人遗憾的事。

那么，究竟谁会获胜呢？是加密者还是解密者？Poe是怎么认为的呢？Poe有一个非常清晰的观点，他笃信破译者将会是最后的赢家：“可以全面断言，人类的创造力还不足以创造出人类不能破译的密码。”换句话说，不论你是一个多么聪明的加密者，总会有一个比你更聪明的破译者。可能需要一段时间，但是你终将被一个足够聪明的破译者击败。Poe十分坚信这一点，因为他本身在破译密码上就有非常高的造诣。他于1841年在一本奇特的杂志上写下了以上的话语，请注意1841年，因为在当时有一个这样的密码，通常被认为是Vigenère在1586年在他的书《数字的密写》中提出的。在1586年，Vigenère提出了一种加密方式，直到Poe的论点诞生时，它都没有被破解。事实上，Poe是在1841年写下这个论点，而Vigenère在1586年写下这本书（但可以明确的是，在1553年这种加密方式就已经诞生了），直到Poe写下这个论点时，它都始终没有被破译，而Poe非常确信破译者终将会获胜。但是这个加密方式十分强大，持续了将近300年没人能够破解。Poe怎么也想不到的是，仅仅在他发表这个论点几年后，Babbage就破解了它。这个加密方式存在了301年后才被打破。但是它最终确实被破译了，所以可能Poe还是对的。

所以Poe所说的破译者终将获胜是正确的吗？在我回答他是否是正确的之前，我要先告诉你一些关于密码学的内容。回到密码的产生上来，有两个问题。其中一个就是如何获得一串共享密钥。如果有两个人，名字通常用Alice和Bob表示。Alice和Bob想要秘密的进行通信。如果他们想要使用Poe故事里的单码替换法，他们需要知道密钥是什么。通信的双方需要用共享的密钥，一个用来进行加密，另一人则用来进行解密。所以怎么获得共享的密钥是产生密码时要考虑的一个主要问题。另一个问题是怎么使用密钥。我们在Poe的小说里看到一种使用方式。但是应该有别的途径，有更好的方法，比如像Vigenère那样。所以第一个问题我们把它叫做密钥的建立问题，第二个问题是在加密和解密过程中如何使用密钥。加密的意思是将明文转换为密文，解密的意思是将密文翻译成明文——在你拥有密钥的情况下。让我们首先关注第二个问题，在我们已经有密钥的情况下怎么使用它。

我们已经见过一个现成的例子了。在The Gold-Bug中，一种使用密钥的方式是将明文中的字母按照密钥中的对应关系依次替换。这样就得到了密文。一旦你有了密文，如果你也有密钥，你可以反过来将每个字符一一替换成明文，这样就重新得到了明文。这是一种在你拥有密钥的情况下使用密钥的方法。但是这并不好，因为在9世纪 Al-Kindi就已经破解了它。

让我们看看是否有更好的方法。再次强调，这不是一个好方法。它只适用于初学者。Vigenère的方案在长达300年的时间内都很好，但是它最终还是被破解了。还有恩尼格玛密码机。恩尼格玛是一台德国人在二战中使用的机器，万幸的是它被破译了，这也不是个好方案。在15年甚至更长的时间里，美国政府想要使用一个叫做DES（Data Encryption Standard,即数据加密标准）的加密系统——它起源于1977年，但是后来也都放弃了。之后美国政府提出了“高级加密标准”，它是由比利时人发明的。美国政府举行了一个竞赛，鼓励人们提出取代DES的新方案。有许许多多的方案，最终胜出的是两个比利时人。他们发明了一套叫做Rigndael的系统，后来被美国政府重命名为AES。这就是现在的标准，已经使用了将近20年，还没有人声称找到破解它的方法。这很好，但是我们没有一个严格的证明。它的安全性我们不得而知，但是可能它是安全的。

有另一种加密方式诞生于19世纪，叫做“一次一密”。大多数人认为它是被Vernam或者 Mauborgne在20世纪发明的，但不是，应当更早，“一次一密”是1882年被一位银行家发明的。“一次一密”是一种加密和解密信息的方式，它是无条件安全的。无条件安全的意思是说，如果窃听者得到了编码信息，也就是密文，他不能够获得任何明文的信息。除非有一些信息的泄露，比如说有几个字符。但是除此之外，严格的讲，在你没有密钥的情况下，不能通过拦截密文来获取信息。而且，即使你有无尽的计算能力和最尖端的技术也是无法破译的。如果你熟悉公钥密码学，你会知道它并不能保证无条件安全——公钥密码在有足够计算能力的情况下总是可以被破解的。我所说的完美的安全性可以抵抗各种破解技术，我们可以证明“一次一密”拥有所有这些特性，它可以做到无条件安全。20世纪中叶，Shannon证明了这种加密算法的安全性，但是它却在更晚的时间被发明出来。

请允许我简单介绍一下“一次一密”的工作原理。Alice和Bob是想要通信的双方，他们共享密钥，并且其他人无法获知它。Alice想要给Bob发送信息，她通过手里的信息和密钥，对信息进行了简单的加密，获得她要发送给Bob的密文。“一次一密”的理论说的是，窃听者在没有密钥的情况拦截密文，那么他将不会得到任何明文的信息。Bob手持密钥和密文，简单地把它们摞在一起，就得到一段清晰的文字。再次强调，这种加密算法是绝对安全的。

在故事的最后，我们已经有了一种完美的加密和解密方式，我们为什么还要用别的方案呢？我们为什么还在浪费时间研究量子密码学或者一些其他的加密方式呢？是因为这里存在一个问题——你需要大量的密钥。对每一比特的信息，你都需要一比特的密钥进行加密。这是很不方便的。不过，在对于安全需求很高的情景，我们使用这种加密算法是合理的。比如说，在冷战时期，赫鲁晓夫和肯尼迪之间的通话就使用了这种方式。赫鲁晓夫和肯尼迪之间的通信叫做“红色电话”，实际上电话并不是红色的，而且他们之间的通话也不是通过电话。但是至少，赫鲁晓夫和肯尼迪在冷战期间的秘密通信是通过“一次一密”的方式完成的。

现在的问题是一次性密码本是怎么在两个领导人之间传递的？这个密码本首先在华盛顿或者莫斯科产生，哪里都可以。然后这串完全随机的比特被保存在磁带上，这种方式在那个年代已经有了。这个磁带被保存在一个外交公文包里，外交官牢牢掌控着。外交官会乘坐飞机把密钥亲手交给对方。这种级别安全性的通信需求不太普遍的情况下，这种方式是很好的。但是在当代，当任意两个人想要秘密的通信时，这种方式就没有意义了。

还有另外的一个问题，密钥是怎么建立的。我们知道了怎么使用密钥。现在让我们谈谈如何建立密钥。实际上有3种方式可以实现密钥建立。Alice和Bob可以使用一个可信的第三方，就像赫鲁晓夫和肯尼迪之间的公文包。这种方法已经应用在现实生活中，让我们更深入地研究一些其他方法。

我们可以使用基于计算复杂度的计算安全性。Artur刚刚已经谈到了，或者我们可以使用量子理论。出乎你的意料，我将更多的介绍一些计算安全性的内容，因为它有一段非常有趣的历史。从定义出发，计算安全性对密钥的保护是基于这一前提：窃听者没有足够的计算能力破解它。所以从定义来说，它就不是无条件安全的。在计算时间充足的条件下总可以破解它。

密钥建立是指， Alice和Bob一开始没有共享的密钥，他们想要建立一个。他们要做什么呢？他们要通过一个信道进行交流。这是一个公共信道，公共的意思是这个信道对于窃听是没有任何保护措施的，你可能会对此感到震惊。但是信道是验证过的，意思是Alice知道来自Bob的一切信息，反之亦然，信息在传递过程中没有被修改。我们假设他们用这样的验证过的公共信道进行通信。在经过一些通信后，他们将相同的信息作为密钥。他们都有相同的一串字符，被用来作为密钥。更神奇的是，有一个全程窃听的人，他想要获取密钥，但是他却做不到。如果你没见过这个现象，这听起来就像是黑魔法一样。这两个人一开始没有密钥，他们各自做一些计算，然后进行通信，有一个人全程窃听，在最后，他们可以得到密钥，而窃听全部通信过程的人却不知道密钥是什么。听起来像是黑魔法，不过我们知道如何在一些对于计算能力的假设下做到这一点。

现在来看它的发展历史。大多数人认为这种方法首先由Whitfield Diffie和Martin Hellman在1976年发明。那一年诞生了一篇非常有名的文章——《密码学的新方向》。一年后，Rivest, Shamir, Adleman从Diffie和Hellman的工作出发，发展出了著名的RSA加密系统。RSA在世界范围内的安全网络中广泛应用。大约在同时，McEliece也提出了另一个实现Diffie和Hellman想法的途径。这是我们通常所认为的发展历史。

但是事实上，在Diffie和Hellman之前2年，Merkle就有了和他们几乎相同的想法。Hellman是斯坦福一位非常有名的教授，Diffie是一位非常出色的学生，他们有能力推动这个想法的发展。而Merkle就位于隔壁的伯克利，但是没有人能够理解他在干什么，所以非常不幸，他在1974年的想法在1978年才得以发表。这就是真正的事实——Merkle先于Diffie和Hellman提出RSA想法。但是实际上，RSA是在更早些的时候被Clifford Cocks提出的。他在英国特勤局工作，他发明了它却不能告诉其他人。实际上，Cocks的工作是基于Ellis的。Eillis是我们能了解到的极限，除非还有一些别的人突然从石头缝里蹦出来。我们目前为止知道，Ellis是第一个认为可能可以基于一些计算假设实现密钥建立的人。这只是个疯狂的想法，但是他不知道怎么能让它实现。当Cocks进入特情局时，他们给他一张桌子。他无所事事。因此他们递给他一张Ellis在3年前写的一份草稿。他在读过后感到十分有趣。那天晚上他回到家，由于不在特勤局的高墙之内时，是不允许写任何东西的，至少是任何和工作有关的东西，所以他就一直躺在床上，不被允许使用纸和笔等等一系列物品。就在那一晚，他发明了RSA加密系统。第二天早上他早早来到办公室，你能想象的到，他把他的想法记录下来并且来验证它是否可行，结果成功了。这就是基于计算假设的密钥建立的历史。

你还记得我们的问题吧？我们所居住的量子世界改变了这一切。请允许我告诉你一些关于加密者、破译者和通信信道的内容。加密者是经典的，意味着他们只有经典计算机，他们不懂量子理论。或者他们有一台量子计算机，就像Artur之前谈到的。破译者可以是经典的或者量子的，Alice和Bob之间的信道也可以是经典或者量子的。这给我们提供了多种组合的可能。

特别地，如果每个人都是经典的，那么从一开始我们就置身于一个经典的环境中。我们有许多经典条件下的人。这样的场景从2500年前开始就存在，比如说前面说的故事就发生在一个经典的世界中。在经典世界中，我们每天都在大量的、数以百万计的使用Diffie-Hellman和RSA这些方案来建立密钥，并保证整个互联网框架的安全性。

如果破译者有量子计算机会发生什么？我们把这个称为后量子密码学，是说加密者还只是经典的但是破译者可以使用量子计算机。在这种情形下，有一种分解大数的方案，它是由Peter Shor提出的，他也是2018量子墨子奖的获奖者之一。Shor发现量子计算机可以有效地分解大数，也可以有效地提取离散对数，而这两点正是RSA和Diffie-Hellman算法所依赖的，甚至包括椭圆曲线加密算法也是如此。要完成这两件事，你需要一个量子计算机，而一旦你拥有，一切将迎刃而解。

另一个重要的量子算法是Grover算法。如果你有一个函数，对于N个点，只有一个点的结果为1，其他的均为0。你想要找到这个满足f(x) = 1的点。如果用经典的方法来找这个点，我们除了尝试不同的输入以外别无他法，不管是随机试还是逐个试。这样平均下来需要尝试半数的点才能找到。所以在经典的情形下，你需要调用N/2次函数f才可以找到x。Grover发现了一种依托量子计算机的算法，你可以只需根号N次的调用就可以找到。这种算法十分出色。Shor算法可以使我们的运算速度比在经典计算机上有指数级的提升，而Grover的算法相比经典只有平方量级的提升，但是它却拥有非常广泛的应用——任何搜索问题都可以应用Grover算法进行加速。

无论什么情况，让我们回到密钥建立问题。如果我们给窃听者一台量子计算机，量子窃听者将会改变这一切。我没有说明Merkle系统是如何工作的。但是一旦你掌握了Grover算法，Merkle系统就被破解了。所以说Grover破解了Merkle。Shor算法对离散对数的提取破解了Diffie-Hellman，而对大数的分解破解了RSA；是Cocks发明了RSA，Shor破解了Cocks。没人知道如何用量子计算机破解McEliece。从一开始我们就使用Diffie-Hellman和RSA真的是个灾难。如果使用的是McEliece，我们今天将会是安全的。但是不幸的是，整个密码学框架都仰仗于Diffie-Hellman或 RSA的安全性，一旦量子计算机被发明，这个框架将会瞬间崩塌。我们只有使用McEliece，今天才不会如此窘迫。选择RSA和Diffie-Hellman的原因之一是因为McEliece需要更长的密钥——不是更多的计算，而是更长的密钥，MB量级的密钥；而对于Diffie-Hellman和RSA，kB量级的密钥就足够。在当时——1980年代早期，也可能是1970年代末期，我们已经想到我们未来可能将会有手持加密设备，如智能卡，如果需要MB量级的密钥，加密设备的体积会大到一只手拿不下的地步。这在当时是显然的，虽然今天看来，MB是非常小的。无论如何，我们在当时做了最好的决定，但是现在我们不得不面对这一切。

如果加密者是量子的，那么就有可能挽救今天的局面。但是如果加密者是量子，那就意味着Alice和Bob现在拥有了量子计算机。可能量子计算机将会使得Alice和Bob实现安全的密钥建立来抵御量子的攻击者。不幸的是，现在还做不到。到目前为止，量子计算看起来对破译者更有优势。Poe很高兴，加密者很惆怅。

总的来说，在经典信道中，RSA 和 Diffie-Hellman可以抵抗经典攻击者。我们不能完全证明这一点，但是它看起来是安全的。而它对于量子攻击者来说是不安全的。所以量子看起来对于加密者是件坏事。还记得我们的问题吗？量子理论对于加密者是好事还是坏事？答案看起来像是后者。但是McEliece可能是安全的，因此我们还有一些别的可能。另外在当时还发展了一些其他的方案。比如一些叫做New Hope和Frodo等的完全经典的加密系统。他们可能可以抵抗量子计算的攻击。

我的报告接近尾声了，但是我还想告诉你们一些在拥有量子信道后发生的故事，它又使得一切变得不一样。事实上，甚至不需要加密者是量子的，他们只需要一个小的干涉。Alice和Bob之间的信道变成量子的，将会发生什么？Alice和Bob可以是经典的，他们只需要一个小小的量子干涉，不需要其他的。这并不像说的那么容易，而是需要一批科学家倾其一生来实现。但是这比实现量子计算机要容易得多。我们做的这一切叫做量子密码术。

我想向你们介绍一个人，Stephen Wiesner，他是第一个考虑将量子效应引入密码学中的人。Wiesner在1968年写下了这篇文章，很不幸的是，它在很长一段时间内都没能发表。在这篇文章中，Wiesner提出了量子钞票的概念。量子钞票只是一个量子力学的想法，它是把量子理论用于信息学和密码学的最早的想法之一。Wiesner的想法是如此具有革命性，以至于这篇文章被杂志退回了。他没有继续发展他的想法，而把它放进了抽屉里。幸运的是，Wiesner把他的想法告诉了Bennett，他最好的朋友之一；Bennett用笔记录了下来。在1970年，他用“量子信息理论”来命名这些笔记，可能这就是“量子信息理论”这几个词的诞生。他想向人们分享Wiesner的想法，但是没有成功，没人听他的。

直到有一天我在波多黎各的圣胡安游泳，有个疯狂的人游向我，并且向我讲述了Wiesner的想法——量子钞票。当我们游回岸边时，我们至少在脑海中构建好了我们的第一篇文章。长话短说，不管怎样，是Wiesner的想法促进了量子密钥分发和量子密码学的诞生。

基于这个想法，我们可以以偏振光子的形式发送信息来抵御窃听者。因为这些光子无法被可靠地区分，所以任何窃听都将会产生可被探测的错误。所以如果Alice以偏振光子的形式发送信息给Bob，有一个窃听者在他们的信道上而使得信息发生篡改，Bob将收到不同于Alice的信息，这就是量子密码学基本的想法。除此以外，我们可以用它来建立密钥。在你拥有字母对照表后，密钥就可以在“一次一密”中使用。这就是窃听保护，这就是量子密码学。

1984年，我们把这个想法发表在印度举办的一个会议的公报中，这就是熟知的BB84。我们实现了无条件保密的信息传递。无论窃听者掌握何种技术和计算能力，它都是安全的，这就是无条件的定义。因此，谁将会获胜？Poe错了，加密者将会获胜。当然，这种无条件安全的通信已经实现了。

我想说中国是目前为止在量子密码学的实现中走在最前列的国家。谢谢潘建伟，他也获得了2019年的量子墨子奖，但他今天只介绍演讲者而不做报告。中国在量子密钥分发的应用领域是处于国际领先的。你们还发射了一颗叫“墨子号”的卫星，和这个奖的名字相同，好巧！

“墨子号”可以被用来在遥远的两地之间建立密钥。首个由量子密码学加密的视频电话，是于几年前在奥地利科学院院长Anton Zeilinger和中国科学院院长白春礼之间进行的。他们的视频电话很令人兴奋，因为这是人类历史上最安全的视频通话。当然，周围到处都是吵闹的记者。

北京和维也纳之间的量子通信

现在有覆盖全球的量子卫星方案。Poe错了。这是真的吗？可能并不是。因为有量子黑客的存在。量子黑客没有破译量子密码学。他们只是阻止量子密码学的实现。量子密码是安全的，但是完美的实现它有一定的难度。Vadim Markov，首屈一指的量子黑客，他在寻找实现量子密码的漏洞上有着非凡的天分。他随身带着一个完美的量子黑客的公文包环游世界，看他通过机场的安检是一件有趣的事情。他时不时地会破译一些实际的量子密码系统。

Poe究竟是不是对的？实际上，在长达2500年的时间内，密码学是数学家之间的一场战役，最近这场战役渐渐转移到了工程师之间，因为有许多量子密码方案在理论上都是完美的。你不仅需要工程师，也需要像潘建伟这样的科学家来尽最大可能地实现量子密码，还有一些其他的工程师比如Markov来试图破译它。所以争斗的中心已经由数学转移到了工程学。Poe到底是不是对的？是量子黑客总是可以破坏量子密码的实现，还是我们可以建造一些量子密码使得量子黑客再也不能攻击它？换句话说，猫和老鼠的游戏还没有结束。

现在给我的报告做个总结。我们住在量子的世界中，这对于加密者是坏事还是好事？答案是：我不知道。历史将会说明一切，但是现在我还不知道。当然，我希望加密者将会赢，想出方法来更好地实现量子密码使得Markov不能破解它，但是这还没有得到证明。

谢谢大家!

关于“墨子沙龙”

墨子沙龙是由中国科学技术大学上海研究院主办、上海市浦东新区科学技术协会及中国科大新创校友基金会协办的公益性大型科普论坛。沙龙的科普对象为对科学有浓厚兴趣、热爱科普的普通民众，力图打造具有中学生学力便可以了解当下全球最尖端科学资讯的科普讲坛。