量子的世界对加密者和破译者哪一个更好？

在今天的报告中，我们主要关注的是：我们生活在一个量子世界的事实。Artur 已经告诉我们关于量子的含义。事实上，我们确实生活在一个量子世界中。这对密码学家来说是件好事吗？或者换一种说法，量子世界更适合加密器或解密器？与经典世界相比，有什么变化？当然，还有一个更重要的问题，一开始人们并不同意：谁会赢，加密者还是解密者？

我想首先介绍一位科学家、诗人和小说家埃德加·爱伦·坡。他是 19 世纪的美国小说家和诗人，据我所知，他没有科学背景。而且我也知道他是一个非常优秀的自学成才的非专业密码学家。事实上，他写了一部名为《金虫》的小说，这是他最著名的著作之一。坡讲述了一个名叫威廉·勒格朗的人的故事，他在森林里发现了这份看起来很奇怪的手稿，但他不知道那是什么。他想，如果他隔着光看，可能发生了什么事。于是他把羊皮纸放在火光附近，试图透过火光看清它。令他惊讶的是，当他将它握在非常靠近火焰的地方时，密文出现了。

威廉·勒格朗意识到，这话一定与海盗宝藏的埋葬地点有关。他是如何解密这个密文的？他的解密过程是一个精彩的故事，作者用大约10页的文字来解释威廉·勒格朗是如何破译这样一个密文的。这个故事很有意思，很多现实世界的密码学家在年轻的时候读过这个故事，被密码学的艺术美所吸引，然后成长为真正的密码学家，尤其是弗里德曼先生。.

让我们回到故事，威廉·勒格朗已经有了这样的密文。首先要做的是计算每个字符出现的次数。我们得到了这个结果——字符“8”是最常见的。在包括英语在内的大多数西方语言中，出现频率最高的字母是“e”。所以威廉·勒格朗认为“8”代表字母“e”。字符“4e;” 多次出现。由于假定原始文本是英文的，因此它必须是单词“the”。“the”是出现频率最高的单词，由 3 个字母组成并以“e”结尾。所以很可能是“;” 代表“t”，“4”代表“h”。10页文字后，他得出结论——’;’ 对于’t’

《金虫》中密文与明文的对应关系

我们根据对应关系替换密文中的字符——随便，这叫做密钥，在密码学中，密钥是明文和密文之间转换的工具，威廉·勒格朗通过推理找到了密钥。密文转换后，我们得到明文。似乎可以理解。现在他需要在这个文本中添加空格。添加空格时，我们得到一段似乎仍然没有意义的文本。因为此时，你需要在一定程度上猜测它的含义。结果他当天就找到了宝物，真是太好了。

Gold-Bug 中的明文

Poe 并不是第一个找到破解密文的方法的人。这种加密方法将每个字母替换为另一个符号。在密码学术语中，它被称为“单码替换法”。打破单码替换法的不是坡，而是Al-Kindi。Al-Kindi 也有多重身份，他在相当长的一生中写了 300 本书。特别是，他写了一本关于如何破译加密信息的书。在这本书中，Al-Kindi 解释了如何解码，如何破译 Poe 书中提到的密码类型。您可能认为这项工作是所有密码学或密码破解的起源，但事实并非如此。这本书的一部分丢失了，直到最近才被发现。所以很遗憾它在历史上没有太大的影响。

那么，谁会赢呢？加密器还是解密器？坡是怎么想的？坡有一个非常明确的观点，他相信破译者最终会获胜：“可以完全断言，人类的聪明才智不足以创造出人类无法破译的密码。” 换句话说，无论你多么聪明，总会有一个比你聪明的饼干。这可能需要一段时间，但你最终会被足够聪明的破译者打败。坡坚信这一点，因为他本人在破解密码方面的成就非常高。他在 1841 年在一本奇特的杂志注 1841 上写了上面的话，因为当时有这样一个密码，一般认为是 Vigenère 在他的著作《数字的隐写术》中于 1586 年提出的。1586 年，Vigenère 提出了一种加密方法，直到 Poe 的论点诞生后才被破解。事实上，Poe 于 1841 年写了这篇论文，Vigenère 于 1586 年写了这篇论文（但很明显，这种加密方法诞生于 1553 年），直到 Poe 写这篇论文之前，它从未被破译过，Poe 很确定破译者会赢。但这种加密方式是如此强大，以至于近300年来没有人能够破解它。坡永远无法想象的是，巴贝奇在他发表该论点仅仅几年后就破解了这个论点。这种加密方法在被破解之前已经存在了 301 年。但它最终还是被破译了，所以也许坡是对的。在坡写下这篇论文之前，它从未被破译，坡很确定破译者会赢。但这种加密方式是如此强大，以至于近300年来没有人能够破解它。坡永远无法想象的是，巴贝奇在他发表该论点仅仅几年后就破解了这个论点。这种加密方法在被破解之前已经存在了 301 年。但它最终还是被破译了，所以也许坡是对的。在坡写下这篇论文之前，它从未被破译，坡很确定破译者会赢。但这种加密方式是如此强大，以至于近300年来没有人能够破解它。坡永远无法想象的是，巴贝奇在他发表该论点仅仅几年后就破解了这个论点。这种加密方法在被破解之前已经存在了 301 年。但它最终还是被破译了，所以也许坡是对的。

那么坡说破译者会赢是正确的吗？在我回答他是否正确之前，我将告诉你一些关于密码学的知识。回到密码的生成，有两个问题。其中之一是如何获得一串共享密钥。如果有两个人，名字通常由 Alice 和 Bob 代表。Alice 和 Bob 想要私下交流。如果他们想使用坡的故事中的一位数替换方法，他们需要知道密钥是什么。通信双方需要使用一个共享密钥，一个用于加密，另一个用于解密。那么如何获取共享密钥是生成密码时需要考虑的一个主要问题。另一个问题是如何使用密钥。我们在坡的小说中看到了一种用途。但应该有另一种方式，一种更好的方式，比如 Vigenère。所以第一个问题我们称之为密钥建立问题，第二个问题是在加解密过程中如何使用密钥。加密意味着将明文转换为密文，而解密意味着将密文转换为明文——前提是您拥有密钥。让我们先关注第二个问题，当我们已经有了密钥时，如何使用它。

我们已经看到了一个现成的例子。在 The Gold-Bug 中，使用密钥的一种方法是根据密钥中的对应关系替换明文中的字母。这给出了密文。一旦你有了密文，如果你也有密钥，你可以通过用明文替换每个字符来反转每个字符，从而得到明文。这是一种在您拥有密钥时使用密钥的方法。但这并不好，因为 Al-Kindi 在 9 世纪破解了它。

让我们看看是否有更好的方法。同样，这不是一个好方法。它仅适用于初学者。Vigenère 的计划用了 300 年，但最终还是被破解了。还有 Enigma 机器。Enigma 是德国人在二战中使用的机器，幸运的是它被破译了，这也不是一个好计划。15 年或更长时间以来，美国政府一直想使用一种称为 DES（数据加密标准）的加密系统——它起源于 1977 年，但后来被放弃了。随后美国政府提出了比利时人发明的“高级加密标准”。美国政府举行了一场竞赛，以鼓励新的提议来取代 DES。有很多选择密码学算法 大数问题，最后两个比利时人赢了。他们发明了一种名为 Rigndael 的系统，后来被美国政府更名为 AES。那’ 现在是标准，它已经使用了将近 20 年，没有人声称已经找到了打破它的方法。这很好，但我们没有严格的证据。我们不知道它有多安全，但也许它是安全的。

19世纪还有另一种加密方式诞生，称为“一次性密密”。大多数人认为它是 20 世纪 Vernam 或 Mauborgne 发明的，但不，应该更早，“one time pad”是 1882 年一位银行家发明的。 One-time pad 是一种加密和解密信息的方式，它是无条件安全的。无条件安全是指如果窃听者得到编码信息，即密文，他就无法得到任何明文信息。除非有一些信息泄漏，说几个字符。但除此之外，严格来说，没有密钥的情况下，你无法通过截取密文来获取信息。即使您拥有无穷无尽的计算能力和尖端技术，也无法破译。如果您熟悉公钥密码学，你会知道它不能保证是无条件安全的——公钥密码总是可以用足够的计算能力破解的。我所说的完美安全就是抵抗各种破解技术，我们可以证明“一次性密码”具备所有这些特性，它可以是无条件安全的。在 20 世纪中叶，香农证明了这种加密算法的安全性，但它的发明要晚得多。

请允许我简要介绍一下“一次性便笺簿”的工作原理。Alice 和 Bob 是想要通信的两方，他们共享密钥，其他人无法知道。Alice 想给 Bob 发送一条消息，她只需用手中的消息和密钥对消息进行加密，就可以得到她想要发送给 Bob 的密文。“一次性密文”理论说，如果窃听者在没有密钥的情况下截获密文，他将无法获得明文中的任何信息。Bob 持有密钥和密文，并将它们简单地堆叠在一起以获得清晰的文本。同样，这种加密算法是绝对安全的。

说到底，我们已经有了完美的加解密方式，为什么还要使用另一种方案呢？为什么我们还在浪费时间研究量子密码学或其他加密方法？因为这里有一个问题——你需要很多钥匙。对于每一位信息，您都需要一个位密钥来加密。这是非常不方便的。但是在对安全性要求较高的场景下，我们使用这种加密算法是合理的。例如，在冷战期间，赫鲁晓夫和肯尼迪之间的通话就使用了这种方法。赫鲁晓夫和肯尼迪之间的交流被称为“红色电话”，而电话实际上并不是红色的，他们之间的交流也不是通过电话进行的。但至少，赫鲁晓夫和肯尼迪在冷战期间的秘密通信是通过“

现在的问题是，两位领导人之间的一次性垫底如何传递？该密码本最初是在华盛顿或莫斯科的任何地方生成的。然后，这个完全随机的比特串以当时存在的方式存储在磁带上。录音带放在外交官手里的一个外交公文包里。外交官将乘坐飞机亲自将钥匙交给对方。这种方法适用于这种安全级别的通信需求不太常见的情况。但在现代，当任何两个人想要秘密交流时，那是没有意义的。

还有一个问题，密钥是如何建立的。我们知道如何使用密钥。现在让我们谈谈如何建立密钥。实际上有3种方法可以实现密钥建立。爱丽丝和鲍勃可以使用受信任的第三方密码学算法 大数问题，例如赫鲁晓夫和肯尼迪之间的公文包。这种方法已经应用在现实生活中，让我们更深入地研究一些其他方法。

我们可以使用基于计算复杂性的计算安全性。阿图尔刚才讲了，或者我们可以用量子理论。令您惊讶的是，我将更多地介绍计算安全性，因为它有一段非常有趣的历史。根据定义，计算安全性保护密钥的前提是窃听者没有足够的计算能力来破解它。所以根据定义，它不是无条件安全的。只要有足够的计算时间，它总是可以破解的。

密钥建立意味着 Alice 和 Bob 最初没有共享密钥并且他们想要建立一个。他们将要做什么？他们必须通过渠道进行交流。这是一个公共频道，这意味着该频道没有防窃听保护，您可能会对此感到震惊。但是通道是经过身份验证的，这意味着 Alice 知道 Bob 的一切，反之亦然，信息在传输过程中没有被修改。我们假设他们使用这种经过身份验证的公共通道进行通信。经过一番交流，他们得到了与密钥相同的信息。它们都具有用作键的相同字符串。更神奇的是，有一个人一路窃听，想要拿到钥匙，却拿不到。如果你还没有看到这种现象，这听起来像黑魔法。两个人一开始没有钥匙，做了一些计算，然后沟通，一个人窃听了整个过程，最后得到了钥匙，窃听了整个过程的人沟通过程不知道关键是什么。听起来像黑魔法，但我们知道如何在一些关于计算能力的假设下做到这一点。

现在看看它的发展历程。大多数人认为，这种方法最早是由 Whitfield Diffie 和 Martin Hellman 在 1976 年发明的。那一年诞生了一篇非常著名的文章——《密码学的新方向》。一年后，Rivest、Shamir 和 Adleman 从 Diffie 和 Hellman 的工作中开发了著名的 RSA 加密系统。RSA 广泛用于世界各地的安全网络。大约在同一时间，McEliece 还提出了另一种实现 Diffie 和 Hellman 想法的方法。这就是我们通常认为的发展史。

但事实上，早在 Diffie 和 Hellman 的两年前，Merkle 就有了几乎相同的想法。Hellman 是斯坦福非常有名的教授，而 Diffie 是一个非常优秀的学生，有能力推动这个想法向前发展。Merkle 就在隔壁的伯克利，但没人知道他在做什么，所以不幸的是，他 1974 年的想法在 1978 年发表。这是真实的——Merkle 在 Diffie 和 Hellman 之前提出了 RSA 想法。但事实上，RSA 是由 Clifford Cocks 更早提出的。他为英国特勤局工作，他发明了它，但不能告诉其他人。事实上，科克斯的作品是基于埃利斯的。埃利斯是我们所能知道的极限，除非其他人从岩石的裂缝中跳出来。到目前为止，我们知道，Ellis 是第一个认为有可能基于一些计算假设来实现密钥建立的人。这只是一个疯狂的想法，但他不知道如何实现它。当科克斯进入特勤局时，他们给了他一张桌子。他无事可做。于是他们递给他一份埃利斯三年前写的草稿。他读了之后觉得很有趣。那天晚上他回到家，不让他写任何东西，至少任何与工作有关的东西，当他不在特勤局的围墙内时，他就躺在床上，不准使用纸笔等。 . 和其他项目。那天晚上，他发明了 RSA 加密系统。第二天一大早他就来到了办公室，你可以想象，他把他的想法记下来，来看它是否有效，并且有效。

你还记得我们的问题吗？我们生活的量子世界改变了这一切。请允许我告诉您一些有关加密器、解密器和通信渠道的信息。加密器是经典的，这意味着它们只有经典计算机，它们不了解量子理论。或者他们有一台量子计算机，正如 Artur 之前所说的那样。解密器可以是经典的或量子的，Alice 和 Bob 之间的通道也可以是经典的或量子的。这给了我们多种组合。

特别是，如果每个人都是经典的，那么我们从一开始就处于经典的环境中。我们有许多经典条件下的人。这样的场景从2500年前就已经存在了，比如前面提到的故事就发生在一个经典的世界里。在经典世界中，我们每天数百万次大量使用 Diffie-Hellman 和 RSA 方案来建立密钥并保护整个 Internet 框架。

如果破译者有一台量子计算机会发生什么？我们称之为后量子密码学，这意味着加密器仍然是经典的，但解密器可以使用量子计算机。在这种情况下，2018 年量子墨子奖获得者之一 Peter Shor 提出了一个大数分解的解决方案。Shor 发现量子计算机可以有效地分解大数并有效地提取离散对数，这两者都是 RSA 和 Diffie-Hellman 算法所依赖的，甚至是椭圆曲线加密。要做到这两件事，你需要一台量子计算机，一旦你拥有了它，一切都会变得简单。

另一个重要的量子算法是格罗弗算法。如果你有一个函数，对于 N 个点，只有一个会导致 1，其他会是 0。你想找到 f(x) = 1 的点。如果我们用经典方法找到这个点，我们别无选择，只能随机或一个一个地尝试不同的输入。因此，平均而言，尝试找到一半的点。所以在经典案例中，你需要调用函数 f N/2 次才能找到 x。Grover 发现了一种依赖于量子计算机的算法，你可以在平方根的 N 次调用中找到它。这个算法很棒。Shor 的算法可以让我们的计算速度比经典计算机上成指数级快，而 Grover 的算法只比经典快一个平方数量级，

无论如何，让我们回到密钥建立问题。如果我们给窃听者一台量子计算机，量子窃听者将改变这一切。我没有具体说明 Merkle 系统是如何工作的。但是一旦你掌握了格罗弗的算法，默克尔系统就被打破了。所以格罗弗破解了默克尔。Shor算法提取离散对数破解Diffie-Hellman，大数分解破解RSA；是 Cocks 发明了 RSA，Shor 破解了 Cocks。没有人知道如何用量子计算机破解 McEliece。从一开始我们就使用 Diffie-Hellman 和 RSA，这真是一场灾难。如果我们使用 McEliece，我们今天会很安全。但不幸的是，整个密码学框架依赖于 Diffie-Hellman 或 RSA 的安全性，而一旦发明了量子计算机，这个框架将立即崩溃。我们今天不会因为 McEliece 而感到尴尬。选择 RSA 和 Diffie-Hellman 的原因之一是因为 McEliece 需要更长的密钥——不是更多的计算，而是更长的密钥，以兆字节为单位；而对于 Diffie-Hellman 和 RSA，kB 数量级的密钥就足够了。当时——在 1980 年代初期，可能在 1970 年代后期，我们已经考虑过未来我们可能会拥有手持加密设备，例如智能卡，如果一个兆字节范围内的密钥是必需的。无法得到它。这在当时很明显，尽管今天 MB 非常小。无论如何，我们当时做出了最好的决定，但现在我们必须面对这一切。选择 RSA 和 Diffie-Hellman 的原因之一是因为 McEliece 需要更长的密钥——不是更多的计算，而是更长的密钥，以兆字节为单位；而对于 Diffie-Hellman 和 RSA，kB 数量级的密钥就足够了。当时——在 1980 年代初期，可能在 1970 年代后期，我们已经考虑过未来我们可能会拥有手持加密设备，例如智能卡，如果一个兆字节范围内的密钥是必需的。无法得到它。这在当时很明显，尽管今天 MB 非常小。无论如何，我们当时做出了最好的决定，但现在我们必须面对这一切。选择 RSA 和 Diffie-Hellman 的原因之一是因为 McEliece 需要更长的密钥——不是更多的计算，而是更长的密钥，以兆字节为单位；而对于 Diffie-Hellman 和 RSA，kB 数量级的密钥就足够了。当时——在 1980 年代初期，可能在 1970 年代后期，我们已经考虑过未来我们可能会拥有手持加密设备，例如智能卡，如果一个兆字节范围内的密钥是必需的。无法得到它。这在当时很明显，尽管今天 MB 非常小。无论如何，我们当时做出了最好的决定，但现在我们必须面对这一切。kB 数量级的密钥就足够了。当时——在 1980 年代初期，可能在 1970 年代后期，我们已经考虑过未来我们可能会拥有手持加密设备，例如智能卡，如果一个兆字节范围内的密钥是必需的。无法得到它。这在当时很明显，尽管今天 MB 非常小。无论如何，我们当时做出了最好的决定，但现在我们必须面对这一切。kB 数量级的密钥就足够了。当时——在 1980 年代初期，可能在 1970 年代后期，我们已经考虑过未来我们可能会拥有手持加密设备，例如智能卡，如果一个兆字节范围内的密钥是必需的。无法得到它。这在当时很明显，尽管今天 MB 非常小。无论如何，我们当时做出了最好的决定，但现在我们必须面对这一切。

如果加密器是量子的，就有可能挽救今天的局面。但如果加密器是量子的，那意味着 Alice 和 Bob 现在拥有量子计算机。可能量子计算机将使 Alice 和 Bob 能够针对量子攻击者实现安全密钥建立。不幸的是，还没有。到目前为止，量子计算看起来比破译器更有优势。坡很高兴，密码学家很忧郁。

一般来说，在经典通道中，RSA 和 Diffie-Hellman 对经典攻击者具有抵抗力。我们无法完全证明这一点，但它看起来很安全。而且它对量子攻击者是不安全的。所以量子对于密码学家来说是件坏事。还记得我们的问题吗？量子理论对密码学家来说是好是坏？答案看起来像后者。但是 McEliece 可能是安全的，所以我们还有一些其他的可能性。此外，当时还开发了一些其他解决方案。比如一些完全经典的加密系统，叫做 New Hope 和 Frodo。它们可能会抵抗量子计算攻击。

我的报告即将结束，但我想告诉你更多关于量子通道再次发挥作用的故事。事实上，加密器甚至不需要是量子的，它们只需要一个小的干扰。当 Alice 和 Bob 之间的通道变成量子时会发生什么？爱丽丝和鲍勃可以是经典的，他们只需要一个小的量子干涉就可以了。这并不像说的那么容易，而是需要一群科学家花费毕生精力来实现的。但这比实现量子计算机要容易得多。我们所做的一切都称为量子密码学。

我想向您介绍一个人，斯蒂芬威斯纳，他是第一个考虑将量子效应引入密码学的人。威斯纳在 1968 年写了这篇文章，可惜很久没有发表了。在这篇文章中，威斯纳提出了量子纸币的概念。量子钞票只是一种量子力学的想法，它是最早将量子理论应用于信息学和密码学的想法之一。威斯纳的想法是如此具有革命性，以至于该文章被杂志退回。他没有发展他的想法，而是把它放在抽屉里。幸运的是，威斯纳将自己的想法告诉了他最好的朋友之一贝内特。贝内特用笔把它记下来。1970年，他将这些笔记命名为“量子信息论”，这可能是“量子信息论”一词的诞生。他想分享威斯纳

直到有一天我在波多黎各的圣胡安游泳时，一个疯子游到我身边，告诉我威斯纳的想法——量子钞票。当我们游回岸边时，我们至少想到了我们的第一篇文章。长话短说，无论如何，正是 Wiesner 的想法导致了量子密钥分发和量子密码学。

基于这个想法，我们可以通过偏振光子的形式发送信息来抵御窃听者。由于这些光子无法可靠地区分，任何窃听都会产生可检测的错误。所以如果 Alice 以偏振光子的形式向 Bob 发送信息，而他们的信道上有窃听者，信息被篡改，Bob 会从 Alice 那里收到不同的信息，这就是量子密码学的基本思想。除此之外，我们可以使用它来建立密钥。一旦有了字母表，就可以在一次性键盘中使用该密钥。这是窃听保护，这就是量子密码学。

1984 年，我们在一个名为 BB84 的印度会议公报中发表了这个想法。我们已经实现了无条件的机密信息传输。不管窃听者有什么技术和计算能力，都是安全的，这就是无条件的定义。那么，谁会赢呢？坡错了，密码学家会赢。当然，这种无条件安全的通信已经实现了。

我想说，中国是迄今为止实现量子密码学的领先国家。谢谢潘建伟，他也获得了2019年量子墨子奖，不过今天只介绍演讲嘉宾，不做报告。中国在量子密钥分发应用方面处于国际领先地位。你们还发射了一颗名为“墨子”的卫星，和这个奖项同名，真是巧了！

“墨子”可以用来在遥远的两地之间建立钥匙。几年前，奥地利科学院院长安东·泽林格和中国科学院院长白春丽之间进行了第一次通过量子密码术加密的视频通话。他们的视频通话令人兴奋，因为这是人类历史上最安全的视频通话。当然，周围也有吵闹的记者。

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

现在有覆盖世界的量子卫星计划。坡错了。这是真的吗？可能不是。因为量子黑客的存在。量子黑客不会破译量子密码学。它们只是阻止了量子密码学的实现。量子密码学是安全的，但很难完美地实现它。首屈一指的量子黑客瓦迪姆·马尔科夫（Vadim Markov）在寻找启用量子密码学的漏洞方面具有非凡的天赋。他带着一个完美的量子黑客公文包环游世界，看着他通过机场安检很有趣。他不时会破译一些实际的量子密码学。

坡是对的吗？事实上，2500 年来，密码学一直是数学家之间的一场战斗，最近这场战斗已经转移到工程师身上，因为有许多理论上完美的量子密码方案。你不仅需要工程师，还需要像潘建伟这样的科学家尽可能地使量子密码学成为可能，还需要像马尔科夫这样的其他工程师来尝试破译它。因此，战斗的中心已经从数学转向了工程学。坡是对的吗？量子黑客是不是总能破解量子密码学的实现，还是我们可以建立一些量子密码学，让量子黑客永远无法再攻击它？换句话说，猫捉老鼠的游戏还没有结束。

现在总结一下我的报告。我们生活在一个量子世界中，这对密码学家来说是坏事还是好事？答案是：我不知道。历史会证明一切，但现在我不知道。当然，我希望密码学家能够获胜并找出更好地实现量子密码学的方法，这样马尔科夫就无法破解它，但这还没有得到证实。

谢谢你们