Q-day：量子计算机打破互联网密码安全的那一天

自然（Nature）期刊今年2月份专栏文章关于量子计算机和密码学*进展的通讯文章，作者Davide Castelvecchi。

关注量子计算和密码学的朋友，欢迎后台留言交流学习。

*密码学：Cryptography，通常社媒上crypto的说法指Cryptocurrency（但在密码学者和研究员眼里，Cryptography才应该是Crypto，)

从量子黑客手中拯救互联网的竞赛

量子计算机革命可能打破加密算法--但更安全的算法可以保障隐私

Nature602, 198-201 (2022)

doi:

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

我们在网上所做的一切计算机安全学，几乎都是通过背后安静，无休止工作的加密算法来实现的。这些扰乱原始数据的算法系统，用以保护我们的隐私，建立我们的数字身份，并确保我们的支付安全。它们工作得很好：即使用今天最好的超级计算机，破解网络世界目前运行的密码也是一项几乎无望的任务。

但是，将利用了量子物理学奇异特点的机器会威胁到整个体系。如果一旦达到全面规模，量子计算机将以指数级的速度破解目前的加密算法，甚至比最好的非量子机器还快。"位于加利福尼亚州旧金山的Mozilla公司火狐浏览器团队的首席技术官埃里克-雷斯科拉说："真正的量子计算机将是极其危险的。

就像老套的时间穿越故事一样，尚不存在的机器不仅危及我们未来的通信，而且还危及我们现在和过去的通信。窃听互联网流量的数据窃贼可能已经在积累加密数据，一旦量子计算机可用，他们就可以解开这些数据，有可能查看从我们的病历到我们的旧银行记录的一切。"假设量子计算机在2024年被部署，"雷斯科拉说。"你在2024年之前在互联网上所做的一切都会被公开讨论。"

即使是最乐观的量子计算支持者也说，我们需要等待一段时间，直到机器强大到足以破解加密密钥，而且许多人怀疑这将在这十年内发生--如果真的有的话。

但这种风险是真实的，以至于互联网正在准备进行改造，以限制Q-day发生时的损害。这意味着要改用更强大的加密系统，或称密码系统。幸运的是，几十年来在理论计算机科学方面的研究已经发现了很多候选方案。这些后量子算法似乎不受攻击：即使使用考虑到量子计算的数学方法，程序员还没有找到在合理时间内击败它们的方法。

这些算法中的哪一种将成为标准，可能在很大程度上取决于马里兰州盖瑟斯堡的美国国家标准与技术研究所（NIST）即将宣布的一项决定。

2015年，美国国家安全局（NSA）宣布，它认为目前的密码系统是脆弱的，并建议美国企业和政府取代它们。第二年，NIST邀请全球计算机科学家提交候选的后量子算法，该机构将在整个加密社区的帮助下测试它们的质量。此后，它已将其名单从65个减至15个。在接下来的几个月里，它将选择几个获胜者，然后公布这些算法的官方版本。从法国到中国，其他国家的类似组织也将发布自己的公告。

但是，这将只是更新世界密码系统这一漫长过程的开始--这一变化将影响我们在线生活的方方面面，尽管人们希望它对普通互联网用户来说是看不见的。经验表明，这可能是一条崎岖不平的道路：谷歌等公司的早期测试并没有全部顺利进行。

"我认为这是我们知道如何做的事情；只是不清楚我们是否能及时做到，"麻省理工学院的数学家彼得-肖尔在2020年告诉《自然》，他的工作显示了当今加密技术的漏洞。

即使Q-day永远不会发生，破译量子机器密码的可能性已经改变了计算机科学--特别是古老的密码学艺术。"加州大学伯克利分校西蒙斯计算理论研究所所长、计算机科学家沙菲-戈德瓦瑟说："我认识的大多数人都在考虑抗量子密码学。

彼得-肖尔表明，量子算法可以击败加密系统。

公钥密码学的诞生

军队和间谍一直能够安全地发送信息，即使在一个容易被窃听的渠道（无论是信鸽还是无线电链路），只要他们的信息是加密的。然而，直到20世纪70年代，这需要双方事先商定一个共享的秘密密码。

然后，在1976年，三位美国计算机科学家Whitfield Diffie、Martin Hellman和Ralph Merkle提出了公钥密码学的革命性概念，它允许两个人安全地交换信息，即使他们之前没有协议。这个想法建立在一个使用两个数字的数学技巧上：一个是公钥，用于加密信息，它与第二个是私钥，用于解密信息。想接收保密信息的人可以向全世界宣布他们的公钥，比如说，把它印在报纸上。任何人都可以使用公钥来窜改他们的信息并公开分享。只有接收者知道私钥，使他们能够解开加密信息并阅读它。

在实践中，公钥通常不是用来加密数据的，而是用来安全地共享一个传统的对称密钥--双方都可以用它来向任何方向发送机密数据。(对称密钥系统也可以被现有的量子算法削弱，但不是以灾难性的方式）。

从20世纪90年代中期开始的互联网时代的前20年，最常用的公钥交换算法是RSA，以其发明者罗恩-里维斯特、阿迪-沙米尔和伦纳德-阿德尔曼命名。

RSA是基于质数--诸如17或53这样的整数，除了它们本身和1之外，不能被任何数字平均分割。只有一方知道这些因子，它们构成了私钥。虽然两个大数相乘很简单，但要找到一个非常大的数字的未知质数因子是非常困难的，因此隐私得到了保护。

最近，互联网一直在淘汰RSA的过渡中，RSA甚至在经典攻击面前都很脆弱，更不用说量子攻击。2018年，互联网工程任务组（IETF），一个基于共识的虚拟组织，在全球范围内引导安全标准的采用，认可了另一个公钥系统来取代它。该系统被称为椭圆曲线密码学，因为它的数学源于十九世纪几何学的一个分支，研究的对象被称为椭圆曲线。

椭圆曲线加密法是基于计算一个整数（与曲线上的一个点相关）的n次方。只有一方知道这个数字n，也就是私钥。计算一个数字的指数很容易，但给定结果后，要找到n是什么就非常困难了。这种技术比RSA更快、更安全。

从移动电话到汽车，各种设备都使用公钥加密来连接互联网。该技术也已扩散到网络空间之外：例如，从信用卡到安全通行证的射频芯片通常使用椭圆曲线算法。

突破RSA

就在全球互联网用户数量--以及RSA等公钥密码系统的使用开始呈指数级增长时，当时在新泽西州默里山的AT&T贝尔实验室的Shor为这些算法的消亡奠定了基础。他在1994年展示了量子计算机如何能够以指数级的速度将大数分解为素数，而不是经典计算机(P. W. ShorProc. 35th Annu. Symp. Found. Comput. Sci. 124–134; 1994).肖尔的量子算法中的一个步骤也可以有效地破解椭圆曲线的密钥。

肖尔算法不是第一个量子算法，但它是第一个表明量子计算机可以解决实际问题的算法。当时，这在很大程度上是一项理论工作，因为量子计算机仍然是物理学家的梦想。但在那十年的晚些时候，IBM的研究人员通过在核磁共振机器中操纵分子，首次进行了量子计算的原理证明。到2001年，他们已经证明他们可以运行肖尔的算法--但只是计算出15的质因数是3和5。从那时起，量子计算技术已经取得了巨大的进步，但在大整数上运行肖尔的算法仍然是一个漫长的过程。

不过，在肖尔的突破之后，密码研究界开始关注Q-day的可能性。戈德瓦瑟说，研究人员已经在研究替代的公钥算法，这一消息吸引了很多人才进入这一领域。

基于格子（Lattice）的系统

大多数进入NIST最终名册的算法都直接或间接地依赖于20世纪90年代从格子数学中发展出来的一个密码学分支。它使用位于整个空间延伸的直线格子的交叉点上的点集。这些点可以用向量的代数来相互添加；有些可以被分解成更小的向量的总和。如果晶格有很多维度--例如500--计算最小的此类向量是非常耗时的。这与素数的情况类似：知道短向量的人可以用它们作为私钥，但解决这个问题对其他人来说非常困难。

自20世纪90年代以来，研究人员开发了大量的公钥加密算法，这些算法要么直接使用格子，要么与格子有某种关联。最早的一种类型是1996年开发的，叫做NTRU。它的密钥由整数系数的多项式组成，但它被认为是安全的，因为它在理论上与格子问题相似。为了证明一个密码系统是值得信赖的，研究人员经常证明它至少和格子问题一样难以破解。

基于格子的密码学的一种流行方法被称为带错误学习（LWE），它构成了NIST决赛中几个项目的基础。它是由纽约大学的计算机科学家Oded Regev于2005年提出的。在其最简单的形式中，它依靠的是算术。为了创建一个公钥，想要接收信息的人要选择一个大的秘密数字--私钥。然后他们计算出这个数字的几个倍数，并在每个倍数上添加随机的 "错误"：得出的数字列表就是公钥。发送者将这些整数和另一个代表信息的数字相加，并将结果发送出去。

为了取回信息，接收者所要做的就是用密匙除以信息，并计算出余数。Regev说："这真的是高中水平的数学"。

深刻的一步是Regev在2009年证明，任何破解这种算法的人也能够破解看似更复杂的格子问题。戈德瓦瑟说，这意味着LWE具有与格子相同的安全性，但无需处理多维向量。"这是一个很好的表述，因为它使它很容易操作。"具有讽刺意味的是，雷杰夫是在试图找到一种能破解格子问题的量子算法的过程中发现LWE的，但没有成功。他说："有时候，失败就是成功"。

Oded Regev介绍了基于格子的密码学的一个分支，称为带错误学习。

此后，研究人员一直致力于解决基于格子系统的一个缺点。中国上海交通大学的密码学家郁昱说 “基于格的密码受制于巨大的公钥”。目前互联网应用的公钥只有一条微博的大小，而基于格子的加密通常需要大到一兆字节或更多的密钥。"结构化格子"系统使用本质上是代数的调整来大幅减少公共密钥的大小，但这可能使其更容易受到攻击。今天最好的算法必须在规模和效率之间取得微妙的平衡。

量子候选方案

2015年，美国国家安全局异常坦率地承认，量子计算机对隐私有严重的风险，这使得政策界的人们注意到了Q-day的威胁。”NSA不经常公开谈论密码学，所以人们注意到了"，NIST数学家Dustin Moody在去年的一次密码学会议上发言时说。

在穆迪的领导下，NIST已经在进行它在2016年宣布的竞赛，它邀请计算机科学家提交公钥密码学的候选后量子算法，将它们发布给研究界进行审查。同时，NIST呼吁提交数字签名算法--例如，使网络服务器能够建立其身份的技术，以防止骗子窃取密码。实现公钥交换的数学技术通常也适用于这个问题，目前的数字签名系统也同样容易受到量子攻击。

超越量子优势：寻找有用的量子计算机

来自学术实验室和公司的团队，其成员来自六大洲的四十多个国家，提交了82种算法，其中65种被接受。忠实于其创造者的极客身份，许多算法的名字都有星球大战、星际迷航或指环王的主题，如FrodoKEM、CRYSTALS-DILITHIUM或New Hope。

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

算法一经提交，就是公开的时段。密码学研究人员以破解对方的算法为乐，在NIST提交的算法被公开后，几个系统很快被破解。"穆迪说："我认为人们在研究这些算法时有很大的乐趣。

尽管NIST是一个美国政府机构，但更广泛的加密社区一直在参与其中。”位于加拿大滑铁卢的计算机安全公司ISARA的数学家菲利普-拉芳斯说："这是一项全球性的努力。这意味着，在这个过程结束时，幸存的算法将获得广泛接受。"他说："世界将基本上接受NIST的标准。他是一个工作组的成员，该工作组代表欧洲电信标准协会监测NIST的选择，欧洲电信标准协会是全球团体的一个伞式组织。穆迪说："我们确实期望看到国际上大量采用我们将创建的标准。“

不过，由于密码学影响到敏感的国家利益，其他国家也在密切关注--一些人对此持谨慎态度。"位于巴黎的法国国家网络安全局的密码学专家Mélissa Rossi说："后量子算法的成熟度不应该被高估：许多方面仍然处于研究状态。然而，她补充说，这不应该推迟采用后量子系统来加强当前的密码学。

据说中国正在计划自己的选拔过程，将由国家商用密码管理办公室管理（该机构没有回应《自然》杂志的评论请求）。”北京清华大学的数学家丁津泰说：”中国的研究人员的共识似乎是，这个竞赛将是一个公开的国际竞赛，这样中国的[后量子密码学]标准将达到国际最高标准。

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

系统更新

NIST的15个候选方案里，9个是公钥系统，6个是数字签名。入围者包括NTRU和LWE的实现，以及另一个使用纠错技术代数的、经过测试的系统。这些系统被称为 "基于代码的算法"，以冗余的方式存储数据，使其有可能在原始文件被噪声轻微破坏后重建。在密码学中，数据存储算法是公钥，而重建原始信息则需要一个秘钥。

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

选择和规范算法不会是故事的终点。位于纽约市的互联网服务公司Cloudflare的应用密码学家尼克-沙利文（Nick Sullivan）说："获选候选人当然是一个坚实的步骤，但作为后续行动，互联网必须就如何将算法整合到现有协议中达成一致"。

为了破解加密，像中国的九方2.0这样的量子计算机将需要更多的量子比特。Credit: Chao-Yang Lu

Cloudflare和谷歌--经常合作--已经开始对一些后量子算法进行实际测试，将其纳入Chrome浏览器的一些测试版本和服务器软件中。测试是至关重要的，因为要使互联网通信顺利进行，仅有完全兼容的服务器和浏览器是不够的。为了连接它们，数据还必须通过网络设备，这些设备可能会阻止那些因其不熟悉的加密协议而被标记为不寻常的流量。(这些系统可以用来防止黑客攻击或阻止用户访问被禁止的内容）。反病毒软件也可能造成类似的问题。苏利文说，这些问题也存在于 "更广泛的互联网范围内，在一些跟踪用户行为的国家"。他说，网络安全工作者将这些问题称为 "协议僵化"；它已经使从RSA的过渡变得复杂，并可能破坏量子安全算法的推广。

2016年的一次早期测试在Chrome浏览器的测试版中实现了新希望--一种以最初的《星球大战》电影命名的结构化版本的LWE，它的运行没有出现任何问题。Erdem Alk?m说："这次试验表明它是可用的，"他是一名计算机科学家，现在在土耳其伊兹密尔的Dokuz Eylül大学工作，他写了一些代码作为他论文的一部分。"我认为这对我的博士论文来说是一个很好的结果。"

但是，谷歌在2021年就一种不同的算法进行的更大规模的实验遇到了一些障碍。一些互联网设备显然 "坏了"--网络安全术语是指当客户的浏览器试图以不寻常的协议进行通信时，一个小工具会阻止连接。问题可能是浏览器的打开信息比预期的长，因为它携带了一个大的公钥。以这种方式破坏互联网的算法可以被搁置，直到这些问题得到解决。

首台装入100个量子比特的量子计算机

雷斯科拉评论说：”有时你会遇到这样的情况，当你添加新的东西时，一些网络元素会出现故障“。说服供应商调整他们的产品--这通常可以通过一个简单的软件更新来完成--可能需要一些劝说。他说”“这可能需要一段时间。“

不过，雷斯科拉还是很乐观，至少在涉及互联网浏览器时是这样。因为只有少数公司控制着大多数浏览器和许多服务器，所需要发生的就是他们改变加密系统。"每个人都很有信心，一旦NIST和IETF指定了新的标准，我们将能够很快地推出它们。"

过渡可能比较棘手的地方是众多的现代连接设备，如汽车、安全摄像机和各种 "智能家居 "机器，它们受到协议僵化的影响--特别是那些可能将安全功能硬性植入其芯片的设备，而且不经常更换。"设计一辆车需要五到七年的时间，而它将在路上行驶十年，"拉芳斯说。"十年后，它还会是安全的吗？"

无论怎样，最初的实施将是混合型的，在现有系统的基础上使用后量子技术来增加安全性。瑞士苏黎世IBM公司的计算机科学家Vadim Lyubashevsky说，他的团队在NIST的决赛中拥有两种基于格子的算法，他认为后量子和当前的加密方法应该一起运行十年，然后再专门使用新算法。

如果一切按计划进行，当计算进入其量子时代时，互联网将远远进入其后量子时代。这个后量子时代的互联网有一天可能会被量子互联网所取代，令人困惑的是，这意味着一个使用量子物理学原理的网络，使信息交换不受黑客攻击。

研究人员估计，要破解密码系统，量子计算机将需要拥有比目前多1000倍的计算组件（量子比特）。"柳巴舍夫斯基说："有一个非常好的机会，我们将有第一个量子计算机，可以在他们能够破解密码之前做积极的事情。

但这并不是我们自满的理由。雷斯科拉说，将所有技术完全过渡到抗量子化至少需要五年时间，而且每当Q-day发生时，可能会有一些隐藏在某处的小工具仍然很脆弱，他说。他说："即使我们尽力而为，一台真正的量子计算机也将具有令人难以置信的破坏性。"

《自然》 602, 198-201 (2022)

doi:

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!