量子密码学有什么用（量子世界的密码学）

在今天的报告中，我们最关心的是：我们生活在一个量子世界中这一事实。 Artur 已经告诉我们一些关于量子的含义。 事实上，我们确实生活在一个量子世界中。 这对密码学家来说是好事吗？ 或者换句话说，量子世界的加密者和破解者哪个更好？ 与经典世界相比，改变了什么？ 当然，还有一个更重要的问题，一个从一开始就存在分歧的问题：谁将获胜，是加密者还是解密者？

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

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

话又说回来，William Legrand 已经有了这样的密文。 首先要做的是计算每个字符出现的次数。 我们得到这个结果——字符“8”是最常出现的。 在包括英语在内的大多数西方语言中，最常出现的字母是“e”。 所以威廉罗格朗认为“8”代表字母“e”。 字符“4e;” 多次发生。 由于假定原文是英文的，所以这一定是单词“the”。 “the”是最常出现的以“e”结尾的三字母单词。 所以很可能是“;” 代表“t”，“4”代表“h”。 经过10页的推导，他得出了一个结论——';' 代表't'，'4'代表'h'，'8'代表'e'，等等。

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

我们根据对应关系替换密文中的字符——顺便说一句，这叫做密钥。 在密码学中，密钥是一种在明文和密文之间进行转换的工具。 威廉罗格朗通过推理找到了关键。 密文经过变换后，我们就得到了明文。 这似乎可以理解。 现在他需要在这段文字中添加空格。 添加空格后，我们得到一段看起来仍然难以理解的文本。 因为这时候，你需要在一定程度上猜测它的意思。 结果当天就捡到宝了，太好了。

金甲虫中的明文

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

那么，谁会赢呢？ 加密器还是解密器？ 坡怎么想的？ Poe 的观点非常明确，他坚信破解者将是最终的赢家：“可以充分断言，人类的创造力不足以创造出人类无法破解的密码。” 换句话说，无论你多么聪明。 总会有比你聪明的破解者。 这可能需要一段时间，但您最终会被足够聪明的密码破解者打败。 坡对此深信不疑，因为他本人在破译电码方面的造诣非常高。 1841年，他在一本奇特的杂志上写下上述文字，注意年份是1841年，因为当时有这样一种密码，一般认为是维热内尔在1586年在他的著作《数列立体图》中提出的。 1586年, Vigenère 提出了一种加密方法，直到 Poe 的论点诞生之前，这种加密方法一直没有被破解。 事实上，Poe 在 1841 年写了这个论点，而 Vigenère 在 1586 年写了这本书（但很明显加密方法诞生于 1553 年），直到 Poe 写了这个论点，它一直没有被破译，Poe 很确定破译者将获胜。 但是这种加密方式太强大了，近三百年没有人能破解。 Poe 几乎不知道巴贝奇在他发表这篇文章几年后就破解了这个论点。 这种加密在被破解之前存在了 301 年。 但它最终还是被破译了，所以也许 Poe 还是对的。

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

我们已经看到了一个现成的例子。 在The Gold-Bug中，一种使用密钥的方法是根据密钥中的对应关系替换明文中的字母。 这样就得到了密文。 一旦你有了密文，如果你也有密钥，你可以走另一条路，用明文一个一个地替换每个字符，你就可以得到明文。 如果您拥有密钥，这里有一种使用密钥的方法。 但这并不好，因为 Al-Kindi 在 9 世纪就已经破解了它。

让我们看看是否有更好的方法。 同样，这不是一个好方法。 它仅适用于初学者。 Vigenère 的计划行之有效了 300 年，但最终还是被破解了。 还有 Enigma 密码机。 Enigma 是德国人在 WW2 中使用的机器，幸运的是它被破译了，这也不是一个好主意。 在长达 15 年或更长的时间里，美国政府想要使用一种叫做 DES（Data Encryption Standard，数据加密标准）的加密系统——它起源于 1977 年，但后来被废弃了。 然后美国政府想出了“高级加密标准”，这是比利时人发明的。 美国政府举办了一场竞赛，鼓励人们想出 DES 的新替代品。 提案很多，最后两个比利时人胜出。 他们发明了一个名为 Rigndael 的系统，后来被美国政府改名为 AES。 那是现在的标准，已经快 20 年了，还没有人声称找到了破解它的方法。 这很好，但我们没有确凿的证据。 我们不知道它有多安全，但可能是这样。

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

请允许我简要解释一下 One Time Pad 的工作原理。 Alice 和 Bob 是想要通信的两方，他们共享秘钥，其他人无法得知。 爱丽丝要给鲍勃发消息，她只需用手中的信息和密钥对消息进行加密，就可以得到她要发给鲍勃的密文。 “一次性一密”理论是说，如果窃听者在没有密钥的情况下截获密文，他将得不到任何明文信息。 Bob 持有密钥和密文，简单地将它们叠加在一起就可以得到明文。 同样，这种加密算法是绝对安全的。

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

现在的问题是，一次性一密本是如何在两位领导人之间传递的？ 密码本最初是在华盛顿或莫斯科创建的，视情况而定。 然后将这串完全随机的位存储在磁带上，这在当时已经完成了。 录音带放在一个外交公文包里，外交官把它牢牢地控制在手里。 外交官们将通过飞机相互交接钥匙。 这适用于这种安全级别的通信需求不太常见的情况。 但在现代，当任何两个人想要秘密交流时，这种做法就没有意义了。

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

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

密钥建立是指爱丽丝和鲍勃一开始没有共享密钥，他们想创建一个。 他们将要做什么？ 他们想通过一个渠道进行交流。 这是一个公共频道，这意味着它无法防止窃听，这可能会让您感到惊讶。 但是通道是经过验证的，这意味着 Alice 知道 Bob 的所有信息，反之亦然，信息在传输过程中没有被修改。 我们假设他们通过此类经过身份验证的公共渠道进行通信。 经过一番对应后，他们就拥有了与钥匙相同的信息。 它们都具有用作密钥的相同字符串。 更神奇的是，还有一个人一路偷听，他想拿到钥匙，却拿不到。 如果您还没有看到这种现象，那听起来就像是黑魔法。 两个人一开始都没有钥匙，各自做了一些计算，然后沟通，一个人偷听了整个过程，最后拿到了钥匙，但是偷听的人整个通信过程都不知道密钥是什么。 听起来像是黑魔法，但我们知道如何在一些关于计算能力的假设下做到这一点。

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

但事实上，在 Diffie 和 Hellman 之前 2 年，Merkle 的想法几乎与他们相同。 Hellman是斯坦福非常有名的教授，Diffie是非常优秀的学生，他们有能力推动这个想法向前发展。 而默克尔就在伯克利的隔壁，但没有人能理解他在做什么，所以不幸的是，他 1974 年的想法在 1978 年发表了。这是真实的——默克尔在迪菲和赫尔曼之前提出了 RSA 的想法。 但实际上，RSA 是由 Clifford Cocks 更早提出来的。 他为英国特勤局工作，他发明了它，不能告诉任何人。 事实上，Cocks 的工作是基于 Ellis 的。 埃利斯是我们所能学到的东西的极限，除非有人从岩石的裂缝中突然冒出来。 据我们所知，Ellis 是第一个认为基于某些计算假设可能建立密钥的人。 这只是一个疯狂的想法，但他不知道如何实现它。 当考克斯进入特勤局时，他们给了他一张桌子。 他无事可做。 于是他们递给他一份埃利斯三年前写的草稿。 他读后觉得很有趣。 那天晚上他回到家，因为当他不在特勤局的高墙内时，他不被允许写任何东西，至少是任何与工作有关的东西，他只是躺在床上，不允许纸、笔、等等等等一系列的项目。 就在那天晚上，他发明了RSA加密系统。 第二天一早他就来到了办公室，正如你想象的那样，他记下了自己的想法，然后来看它是否可行，而且它确实奏效了。 这是基于计算假设的密钥建立的历史。

还记得我们的问题吗？ 我们居住的量子世界改变了这一切。 请允许我告诉您一些有关加密器、破解器和通信通道的信息。 密码学家是经典的，这意味着他们只有经典计算机，他们不了解量子理论。 或者他们有一台量子计算机，就像 Artur 之前谈到的那样。 破解者可以是经典的也可以是量子的量子计算机多久可以破解比特币，Alice 和 Bob 之间的通道也可以是经典的也可以是量子的。 这给了我们多种组合的可能。

特别是，如果大家都是经典的，那我们一开始就是经典的环境。 我们有很多具有经典条件的人。 这样的场景从2500年前就存在了。 例如，上面提到的故事发生在一个经典的世界。 在经典世界中，我们每天大量、数百万地使用 Diffie-Hellman 和 RSA 方案来建立密钥，确保整个互联网框架的安全。

如果密码破译者拥有一台量子计算机会怎样？ 我们称之为后量子密码学，这意味着加密者只是经典的，而破解者可以使用量子计算机。 在这种情况下，有一个大数因式分解的方案，是由 Peter Shor 提出的，他也是 2018 年量子墨子奖的获得者之一。 Shor 发现量子计算机可以高效地分解大数并提取离散对数，这是 RSA 和 Diffie-Hellman 算法所依赖的，甚至是椭圆曲线加密算法。 要完成这两件事，您需要一台量子计算机，一旦拥有它，一切都会正常进行。

另一个重要的量子算法是 Grover 算法。 如果你有一个函数，对于N个点，只有一个点结果为1，其他的结果为0。你想找到f(x) = 1的这个点。如果我们用经典方法找到这个点，我们别无选择，只能随机或逐个尝试不同的输入。 这样平均下来，需要尝试找一半的点。 所以在经典情况下，您需要调用函数 f N/2 次才能找到 x。 Grover 发现了一种依赖于量子计算机的算法，你可以在根 N 调用中找到它。 这个算法很棒。 秀尔算法可以使我们的计算速度与经典计算机相比呈指数级增长，而格罗弗算法与经典相比只有二次方的提升，但它的应用范围非常广泛——任何搜索问题都可以应用格罗弗算法进行加速。

不管怎样，让我们​​回到密钥建立问题。 如果我们给他们一台量子计算机，量子窃听者将改变这一切。 我没有解释 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 数量级的密钥就足够了。 当时——80年代初期，可能是70年代后期，我们已经想到未来可能会有手持式加密设备，比如智能卡，如果需要兆字节的密钥，它会和手掌一样大 不能带它。 这在当时是显而易见的，尽管在今天，MB 非常小。 不管怎样，我们当时做出了最好的决定，但现在我们不得不面对这一切。

如果密码学家是量子的，就有可能挽救今天的局面。 但是如果加密器是量子的，那就意味着爱丽丝和鲍勃现在有了量子计算机。 量子计算机有可能允许 Alice 和 Bob 实现针对量子攻击者的安全密钥建立。 不幸的是，这还不可能。 到目前为止，量子计算看起来比密码破译者更有优势。 Poe 很高兴，Encryptor 很伤心。

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

我的报告即将结束，但我还想告诉您一些关于在拥有量子通道后发生的事情的故事，它再次改变了一切。 事实上，加密器甚至不需要是量子的，他们只需要一个小的干扰。 如果 Alice 和 Bob 之间的通道变成量子通道会发生什么？ 爱丽丝和鲍勃可以是经典的，他们只需要一点量子干涉就可以了。 这并不像听起来那么容易，而是需要一群科学家倾其一生才能实现。 但这比实现量子计算机要容易得多。 我们所做的这一切被称为量子密码学。

我想向您介绍一个人，斯蒂芬·维斯纳 (Stephen Wiesner)，他是第一个考虑将量子效应引入密码学的人。 维斯纳这篇文章写于 1968 年，可惜很久没有发表。 在这篇文章中，维斯纳提出了量子纸币的概念。 量子钞票只是一种量子力学思想，是最早将量子理论应用于信息学和密码学的思想之一。 威斯纳的想法是如此具有革命性，以至于这篇文章被该杂志拒绝了。 他没有发展他的想法，而是把它放在抽屉里。 幸运的是，Wiesner 与他最好的朋友之一 Bennett 分享了他的想法； 贝内特做了笔记。 1970年，他将这些笔记命名为“量子信息论”，这可能是“量子信息论”一词的诞生。 他试图与人们分享维斯纳的想法，但没有成功，也没有人听他的。

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

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

1984年，我们在印度举行的一次会议公报中发表了这个想法，即所谓的BB84。 我们实现了信息传输的无条件保密。 不管窃听者有什么技术和算力，都是安全的，这就是无条件的定义。 那么谁会赢呢？ 坡错了，加密货币会赢。 当然，这种无条件的安全通信已经实现了。

我想说，到目前为止，中国处于量子密码学实施的最前沿。 谢谢潘建伟，他也获得了2019年的量子墨子奖，不过今天只介绍演讲者，不作报告。 中国在量子密钥分发应用方面处于国际领先地位。 你还发射了一颗与这个奖项同名的“墨子”卫星，好巧啊！

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

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

现在有覆盖全球的量子卫星解决方案。 坡错了。 这是真的吗？ 可能不会。 因为量子黑客的存在。 量子黑客并没有破解量子密码学。 它们只是阻止了量子密码学的实现。 量子密码是安全的量子计算机多久可以破解比特币，但很难完美实现。 领先的量子黑客 Vadim Markov 在寻找漏洞以实现量子密码学方面具有非凡的天赋。 他带着一个完美的量子黑客公文包环游世界，看着他通过机场安检很有趣。 他时不时地破解一些实际的量子密码学。

坡说得对吗？ 事实上，2500 年来，密码学一直是数学家之间的战争，最近这场战争逐渐转移到工程师身上，因为有很多理论上很完美的量子密码方案。 不仅需要工程师，还需要像潘建伟这样的科学家尽可能地实现量子密码，还需要一些像马尔可夫这样的工程师来尝试破译它。 所以战斗的中心已经从数学转移到了工程。 坡说得对吗？ 量子黑客能否始终破解量子密码的实现，或者我们能否构建一些量子密码，使量子黑客无法再攻击它？ 也就是说，猫捉老鼠的游戏还没有结束。

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

谢谢你们！

关于“墨子沙龙”

墨子沙龙是由中国科学技术大学上海研究院主办，上海市浦东新区科学技术协会、上海市新创校友基金会协办的非营利性大型科普论坛。中国科学技术大学。 沙龙的科普对象是对科学有浓厚兴趣、热爱科普的普通人，力求打造一个让中学生了解世界最前沿科学资讯的科普论坛。

,