原文：Davide Castelvecchi

翻译：Kurt Pan

量子计算机革命可能会破坏加密——但更安全的算法可以保护隐私。

在网络安全界，他们称之为 Q-day：量子计算机攻破整个互联网的那一天。

几乎我们在网上能做的一切之下都有着密码学算法运作时安静却不间断的嗡嗡声。这些算法会将数据搅乱，以保护我们的隐私、建立我们的身份并确保我们的支付安全。现在它们的运行非常良好：即使用当今最好的超级计算机，破解当前运行于网络空间的密码算法也将是一项几乎没有希望的任务。

但是那些利用量子物理学奇妙性质的机器将威胁到整个形势。达到完全规模的量子计算机将破解当前的加密算法，甚至比最好的非量子机器也要快指数倍。“一台真正的量子计算机将非常危险，”Mozilla Firefox 浏览器团队的首席技术官 Eric Rescorla 说。

如同一个俗气的时间旅行比喻一样，那个尚不存在的机器不仅会危及我们未来的通信，还会危及我们当前和过去的通信。窃听互联网流量的数据窃贼可能已经在积累加密数据，一旦量子计算机可用，他们就可以解锁这些数据，从我们的病史到过去的银行记录的所有内容都将被泄露。“假设在 2024 年部署了一台量子计算机，”Rescorla 说。“你在 2024 年之前在互联网上所做的一切都将被公开讨论。”

即使是最看好量子计算的支持者也表示，想要机器强大到足以破解加密密钥，我们将还要不得不等待一段时间，而且许多人怀疑是否会在这十年发生——如果终会发生的话。

但风险是真实存在的，互联网正在为此做好准备，即切换到更强大的密码系统，以限制 Q-day 到来时的损害。幸运的是，数十年的理论计算机科学研究已经为此找到了很多候选方案。这些后量子算法似乎不会受到攻击影响：即使使用将量子计算考虑在内的数学方法，程序员也尚未找到在合理时间内找到破解它们的方法。

这些算法中的哪一种将成为标准可能在很大程度上取决于美国国家标准与技术研究院 (NIST) 即将宣布的决定。

但这只是更新全世界密码系统的漫长过程的开始——这一变化将影响我们在线生活的方方面面，尽管我们希望不会使得普通互联网用户觉察。经验表明，这会是一条崎岖不平的道路：谷歌等公司的早期尝试并非一帆风顺。

“我认为这是一件我们知道该怎么做的事情，只是不清楚我们能否及时做到，”MIT的数学家Peter Shor的工作展示了当今加密算法的漏洞，他在 2020 年告诉《自然》杂志。

即使 Q-day 永远不会到来，一台可以破解密码的量子机器可能已经改变了整个计算机科学——尤其是古老的密码学艺术。“我认识的大多数人都在考虑抗量子密码学，”加州大学伯克利分校Simons计算理论研究所所长、计算机科学家Shafi Goldwasser说。

Part1公钥密码学的诞生

即使信道——无论是信鸽还是无线电链路——很容易被窃听，只要他们的消息是加密的，军队和间谍总是能够安全地发送消息。然而，直到 1970 年代以前，这都需要双方事先就共享的秘密达成一致。

在 1976 年，三位美国计算机科学家 Whitfield Diffie、Martin Hellman 和 Ralph Merkle 提出了公钥密码学的革命性概念，它允许两个人在没有事先约定的情况下安全地交换信息。这个想法依赖于一个使用两个数字的数学技巧：一个是公钥，用于加密消息；另一个是私钥，用于解密消息。想要接收机密消息的人可以向全世界公布他们的公钥，例如将其印在报纸上。任何人都可以使用公钥以公开的方式来搅乱他们的消息。而只有接收者知道私钥，使其能够解密消息并阅读。

在实践中公钥通常不用于加密数据，而是用来安全地共享传统的对称密钥——双方都可以使用该密钥向对方发送机密数据。（现有的量子算法也可以削弱对称密钥系统，但不会对其产生灾难性的影响。）

从 1990 年代中期开始的互联网时代的前二十年，最常用的公钥交换算法是 RSA，以它的发明者 Ron Rivest、Adi Shamir 和 Leonard Adleman 的名字命名。

RSA 是基于素数的——即那些例如 17 或 53的不能被除自身和 1 之外的任何数字整除的数。公钥是至少两个素数的乘积，其因子即是只有一方知道的私钥。隐私受到以下事实的保护：尽管将两个大数相乘很简单，但要找到一个大数的未知素因子却非常困难。

由于RSA甚至容易受到经典攻击——还不算量子攻击，最近互联网已经从 RSA 开始过渡。2018 年，互联网工程任务组 (IETF)，一个基于共识的在全球范围内引导采用安全标准的组织，认可了另一个公钥系统来取代它。该系统被称为椭圆曲线密码学，因为它的数学起源于 19 世纪几何学的一个分支，该分支研究称为椭圆曲线的对象。

椭圆曲线密码学基于计算一个与曲线上的点相关联的数的次方。只有一方知道数字，也就是私钥。计算一个数的指数很容易，但给定结果却很难找到是多少。这种技术比 RSA 更快、更安全。

从手机到汽车，各种设备都使用公钥加密连接到互联网。该技术还已经扩展到网络空间之外：例如，从信用卡到安全护照的各种射频芯片通常会采用椭圆曲线算法。

Part2破解 RSA

正当全球互联网用户的数量——以及 RSA 等公钥密码系统的用户数——开始呈指数级增长之时，当时在AT&T 贝尔实验室工作的 Shor 已经为这些算法的消亡奠定了基础。他在 1994 年展示了量子计算机如何能够以比经典计算机指数程度快的速度将大数分解为素数。Shor量子算法中的一个步骤也可以有效地破解椭圆曲线密钥。

Shor算法并不是第一个量子算法，但它是第一个证明量子计算机可以解决实际问题的算法。在当时这主要只是是一种理论上的练习，因为量子计算机还只是是物理学家的梦想。但在90年代后期，IBM 的研究人员通过操纵核磁共振机中的分子，首次证明了量子计算的原理。到2001 年，他们已经证明他们可以运行 Shor 算法——但只是用来计算出 15 的素因子是 3 和 5。从那时起，量子计算技术取得了巨大进步，但在大整数上运行 Shor 算法仍然还有很长的路要走。

尽管如此，在 Shor 的突破之后，密码学学术界开始关注 Q-day 的可能性。Goldwasser 说，研究者们已经在研究新的公钥算法替代者，这一消息吸引了该领域的大量人才。

Part3基于格的系统

进入 NIST 最终名单的大多数算法直接或间接地依赖于一个 1990 年代从格数学发展而来的密码学分支。它使用的是延伸到整个空间的直线的交叉点构成的点集。这些点可以用向量代数相加；有些可以分解为更短向量的和。如果格有很多维——比如说500维——计算最短的这样的向量是非常耗时的。这类似于质数的情况：知道短向量的人可以将它们用作私钥，但解决该问题对其他人来说非常困难。

自 1990 年代以来，研究人员发明了大量的公钥加密算法，这些算法要么直接使用格，要么以某种方式与格相关。最早的类型之一是 1996 年发明的，被称为 NTRU。它的密钥由具有整系数的多项式组成，但它的安全性建立在它理论上与格问题的相似性上。为了证明一个密码系统是值得信赖的，研究者通常要证明它至少与格问题一样难以破解。

一种流行的基于格的密码学方法被称为带错误学习 (LWE)，它构成了很多 NIST 入围算法的基础。它由纽约大学的计算机科学家 Oded Regev 于 2005 年提出。在最简单的形式中，它依赖于算术。要创建公钥，想要接收消息的人选择一个大的秘密数——私钥，然后计算该数的几个倍数，并为每个倍数添加随机“错误”：生成的数的列表就是公钥。发送者将这些数和另一个代表消息的数相加，然后将结果发送。

为了得回消息，接收者所要做的就是将它除以私钥并计算余数。“这其实只是高中数学的水平，”Regev 说。

意义深远的一步是 Regev 在 2009 年证明，任何破解此算法的人也将能够破解看似更复杂的格问题。这意味着 LWE 与格具有相同的安全性，但却无需处理多维向量，Goldwasser 说。“这是一个很棒的形式化，因为它使其很容易被使用。” 具有讽刺意味的是，Regev 是在一次试图找到一种可以解决格问题的量子算法的失败尝试中发现了 LWE。“有时失败就是成功，”他说。

Part4量子候选方案

2015 年，NSA异常坦率地承认了量子计算机会对隐私构成严重威胁，这让政界人士开始关注到 Q-day 的威胁。“NSA 并不经常公开谈论密码学，所以特别引人注意，”NIST 数学家Dustin Moody去年在一次密码学会议上演讲中说。

在Moody的领导下，NIST 开始开展它在 2016 年宣布的竞赛，邀请计算机科学家提交用于公钥密码学的候选后量子算法，并将其发布以供学术界审查。与此同时，NIST 呼吁提交数字签名算法——使比如说网络服务器能够建立其身份以防止诈骗者窃取口令的技术。实现公钥交换的相同数学技术通常也适用于这个问题，并且当前的数字签名系统同样容易受到量子攻击。

来自六大洲四十多个国家的学术实验室和公司的团队提交了 82 种算法，其中的 65 种被接受。忠实于其创造者的nerd资历，许多算法的名字都包含有《星球大战》、《星际迷航》或《指环王》的内容，例如 FrodoKEM、CRYSTALS-DILITHIUM 或 New Hope。

这些算法的评判标准是它们的安全性和效率，包括执行速度和公钥的紧凑性。NIST 会选择标准化的任何算法都将是免版税的。

算法一提交，就到了公开评审阶段。密码学家乐于破解彼此的算法，在 NIST 提交方案的文件公开后，其中几个方案很快就被破解了。“我认为人们在分析这些算法之中得到了很多乐趣，”Moody说。

尽管 NIST 是美国政府机构，但更广泛的密码学社区一直参与其中。“这是一项全球性的努力，”计算机安全公司 ISARA Corporation 的数学家 Philip Lafrance 说。这意味着，在该竞赛结束时，胜出的算法将获得广泛接受。“世界将基本上接受 NIST 标准，”他说。他是代表欧洲电信标准协会监督 NIST 选择的工作组的一员，该协会是为全球团体服务的联盟式组织。“我们确实希望看到我们将创建的标准在国际上得到大量采用，”Moody说。

尽管如此，由于密码学影响敏感的国家利益，其他国家仍在密切关注——有些国家持谨慎态度。“不应高估后量子算法的成熟度：许多方面仍处于研究状态，”法国国家网络安全局的密码学家Mélissa Rossi说。尽管如此，她补充说，也不应该延迟采用后量子系统来加强当前的密码学。

据说中国正在计划自己的选择竞赛，由国家商业密码管理局管理（该机构没有回应Nature的置评请求）。清华大学数学家丁津泰说：“中国研究人员的共识似乎是，这场竞赛将是一场公开的国际比赛，因此中国的后量子密码标准将达到国际最高标准。”

与此同时，一个名为中国密码学会的组织已经举办了自己的后量子算法竞赛。其结果于 2020 年公布，导致其他国家的一些研究人员错误地得出中国政府已经做出官方选择的结论。

Part5更新系统

在NIST 的 15 个候选方案中，9 个是公钥系统，6 个是数字签名系统。入围者包括 NTRU 和 LWE 的实现，以及另一种使用纠错代数技术的久经考验的系统。这些系统被称为“基于编码的算法”，以冗余方式存储数据，从而可以在原始文件被噪声轻微损坏后重建它。在密码学中，数据存储算法属于公钥，需要一个私钥来重建原始消息。

在接下来的几个月里，该机构将为每个应用选择两种算法。然后将开始为其中一个起草标准，同时保留另一个作为备用，以防第一选择最终被意外的量子或其他攻击攻破。

选择和标准化算法不会是故事的结局。互联网服务公司 Cloudflare 的应用密码学家Nick Sullivan说：“这当然是对候选方案激励的坚实一步，但作为后续，互联网必须就如何将算法集成到现有协议中达成一致。”

Cloudflare 和谷歌——以合作的方式——已经开始对一些后量子算法进行实践中的测试，将它们包含在 Chrome 浏览器的一些 beta 版本和服务器软件中。测试至关重要，因为要使互联网通信顺利进行，仅拥有完美兼容的服务器和浏览器是不够的。为了连接它们，数据还必须通过那些可能会阻止由于不熟悉的加密协议而标记为异常的流量的设备。（这些系统可用于防止黑客攻击或阻止用户访问被禁止的内容。）防病毒软件可能会导致类似的问题。Sullivan说，这些问题还存在于“更广泛的互联网范围内，在一些跟踪用户正在做什么的国家”中。网络安全工作者将这些问题称为“协议僵化”，他说; 其已使从 RSA 的过渡变得复杂，并且也可能破坏量子安全算法的推出。

2016 年的一项早期测试在 Chrome 测试版中实现了 New Hope（以来自《星球大战》电影命名的 LWE 的结构化版本），并且运行顺利。“这项试验表明它是可用的，”现在土耳其伊兹密尔 Dokuz Eylül 大学的计算机科学家 Erdem Alkım 说，他曾编写了其中的一些代码以作为博士论文的一部分。“我认为这对我的博士学位来说是一个很好的结果。”

但谷歌在 2021 年对一个不同算法进行的更大规模的实验遇到了一些障碍。一些网络设备显然被“中断”了——这是一个网络安全用语，指当客户端的浏览器尝试与不寻常的协议通信时，阻止这个连接的小工具。问题可能是由于浏览器的打开消息比预期的要长，因为带有一个大公钥。会以这种方式破坏互联网的算法只会被束之高阁，直到这些问题得到解决。

“有时，当你添加新内容时，你会遇到某些网络元素变得行为异常的情况，”Rescorla 评论道。他说，说服供应商调整他们的产品——通常可以通过一次简单的软件更新来完成——可能得需要一些推动力。“这可能需要一段时间。”

尽管如此，Rescorla 还是乐观的，至少在互联网浏览器方面是这样。因为少数公司控制着大多数浏览器和服务器，所以需要做的就是让他们改变加密系统。“每个人都非常有信心，一旦 NIST 和 IETF 指定新标准，我们将能够很快推广它们。”

过渡可能更会更棘手的地方在于大量现代的物联网设备，例如汽车、安全摄像头和各种“智能家居”机器，它们遭受协议僵化——尤其是那些可能将安全功能硬写入到其芯片中并且不经常更换的设备。“设计一辆汽车需要五到七年的时间，而且它会在路上行驶十年，”Lafrance 说。“十年后它仍然是安全的吗？”

无论哪种方式，初始实现都将是混合模式的，使用后量子技术在现有系统之上增加安全性。Vadim Lyubashevsky 是IBM 的计算机科学家，他的团队拥有在 NIST 决赛入围方案中的两种基于格的算法，他说他认为，在新算法被单独使用之前，后量子的和当前的加密算法应该一起运行十年。

如果一切按计划进行，当计算进入量子时代时，互联网将顺利进入后量子时代。这个后量子互联网有朝一日可能还会被量子互联网——使用量子物理学原理使信息交换免受黑客攻击的网络——所替代。

研究人员估计，要破解密码系统，量子计算机将需要比目前多 1000 倍的计算组件（量子比特）。Lyubashevsky 说：“我们很有可能会有一台可以在破解密码学之前做一些积极的事情的量子计算机。”

但这不是自满的理由。Rescorla 说，将所有技术完全转变为抗量子版至少需要五年时间，而且当 Q-day 到来时，很可能会有一些隐藏在某个地方的小组件仍然对攻击脆弱，他说。“即使我们尽可能做到最好，真正的量子计算机也将具有令人难以置信的颠覆性。”