在量子世界中保守秘密 | “自然聚焦—网络安全”增刊

原文作者：Neil Savage

德国Jülich研究中心的D-wave Systems Advantage量子计算机。

2022年7月，比利时的两位数学家震惊了网络安全界。他们采用了一种数据加密方案，用来抵御来自量子计算机的、复杂到目前还不存在的攻击，并使用一台已有九年历史的非量子电脑在10分钟内破解了该方案。

“我想我比大多数人都更惊讶，”数学密码学家Thomas Decru说，他在比利时鲁汶天主教大学（KU Leuven）进行博士后研究时参与了这次攻击。他和他的博士生导师Wouter Castryck在白板上勾勒出该方案的数学原理，但德克鲁不确定它是否有效，直到两人真正在电脑上运行它。“我花了一段时间才明白：‘好吧，它被破解了。’”

这一称为SIKE的加密方案在实现保密方面可谓野心勃勃。2022年美国国家标准与技术研究所(NIST)在其后量子密码学标准化过程中遴选了四个可能的方案，SIKE就是其中之一。这一标准化过程的目的是找到能够保护私人信息免受量子计算机迫在眉睫的威胁的算法。

当下的数字信息依靠加密来保证安全性。包含医疗数据的硬盘以及国家军队和情报机构掌握的秘密都是加密的。在线信用卡支付、数字签名、智能电表读数、无人驾驶汽车中的计算机以及护照中的芯片都依赖于20世纪70年代开发的算法，这些算法将易于阅读的数据转化为仅对那些拥有数学“密钥”来解锁的加密密码。这些函数易于用于创建密钥，但难以逆向运行以揭示它们：相当于数学上的煎鸡蛋。

然而，如果实用的量子计算机问世，这些难以解决的问题将突然变得轻而易举。RSA 是一种允许系统共享密钥的加密方案，对经典计算机来说，它可能需要花费宇宙寿命中的大部分时间来进行逆向工程。研究人员估计，量子计算机可以在8小时内完成同样的工作。迪菲-赫尔曼（Diffie– Hellman）密钥交换是另一种广泛使用的加密方法，以其两位发明者的名字命名，也可以轻松地被量子机器逆转。另一种不同类型的方案，即高级加密标准，不被认为受到计算进步的严重威胁，但它经常与其他方法结合使用，并且无法取代它们的保密能力。

经典计算机处理普通的二进制数字，即1和0，而量子计算机使用量子位，或称量子比特（qubits）。这些单位利用了一种叫做叠加（superposition）的量子力学属性，它允许一个量子比特同时处于不同状态，例如，可以同时是70%的‘1’（开）和30%的‘0’（关）。量子计算机能够同时处于部分开启和部分关闭的多种状态，从而比最复杂的经典计算机更快地执行复杂的数学运算。这一特性使处理跨时代的计算变得触手可及。

现有的量子计算机包含少量量子位（最多几百个），并且功能有限。全球科技公司 IBM计划在今年某个时候发布一款拥有1,121个量子位的芯片，并表示到2025年将拥有一台拥有超过4,000个量子位的计算机在2021年估计，要破解一个常用的2,048位RSA密钥，需要2000万个量子比特。剑桥麻省理工学院的计算机科学家Ronald Rivest表示：“当然，最大的问题是，所有使量子计算变得实际可行的努力是否都会在密码分析方面产生任何好处。”与以色列雷霍沃特魏茨曼科学研究所的计算机科学家Adi Shamir和洛杉矶南加州大学的Leonard Adleman共同开发。“这在很大程度上仍然是一个悬而未决的问题。”

但研究人员表示，即使实用的量子计算机再过20年才能建成，这个问题在今天也很紧迫。NIST计算机安全部门的数学家、后量子密码学项目的负责人达斯汀·穆迪(Dustin Moody) 解释说：“即使未来的量子计算机尚未建成，你的数据也可能已经丢失。” 间谍机构或网络犯罪分子现在就可以收集加密数据，然后等待技术的发展。许多研究人员认为，中国和美国等国家正在这样做。

为了迎接实用的量子计算机出现，全球的密码学家和标准化机构正在努力研究一套加密技术，使其对量子计算机来说像现有方案对经典计算机那样难以解密。为了实现这一目标，许多研究人员正在测试最新的算法。

Thomas Decru，赢得SIKE密码学挑战赛的两位数学家之一。

被破解的密钥

这次破解为Decru和Castryck赢得了微软SIKE加密挑战赛的50,000美元奖金。两人宣布了他们的发现后，其他小组很快就找到了更快地解读代码的方法。这并不是NIST第一个失败的未来算法。另一种基于不同的数学方法、名为Rainbow的候选算法，五个月前就被瑞士Rüschlikon的IBM苏黎世研究院博士后研究员Ward Beullens破解了，而且仅仅用了一个周末的时间。

NIST为开发后量子密码方案而举办的多年竞赛的目的是测试此类潜在的抗量子算法的极限。“最强者将生存，”Moody说。“有时它们看起来很有希望，但随着时间的推移，它们逐渐枯萎，我们会说，‘好吧，我们在这个方向已经走到了极限。我们需要一些新的想法。”

Moody表示，在2017年底选出的69种候选算法中，有25到30种要么完全被破解，要么遭受了一些重大攻击。今年8月下旬，NIST发布了其余三种算法的标准草案，并邀请公众发表评论。该机构计划在2024年内最终确定这些标准。

这三种算法中的一种是CRYSTALS-Kyber，用于通用加密和交换用于保护共享数据的公钥。另外两个，CRYSTALS-Dilithium和SPHINCS+，用于保护数字签名，确保提供文档的人是他们声称的人。另一种数字签名算法Falcon的标准草案标准也将于2024年由NIST发布，在该机构发出新一轮提交征集后，7月又收集了40个数字签名候选标准。“他们似乎在传达一条信息，即他们对他们现有的三种算法不满意，”荷兰埃因霍温理工大学编码理论和密码学小组负责人、SPHINCS+的开发贡献者之一的密码学家Tanja Lange说。

挖掘额外的信息

 任何密码系统都不仅仅是一个难以解决的数学问题。它还必须允许通过某种方式与需要解密的人共享有关问题的信息。这就带来了漏洞。“密码学中总是需要玩这个游戏，”Castryck解释说。你必须有一个难题来构建密码系统，“但总是需要额外的信息来传递，以使方案能够正常运行”。

SIKE系统基于等距同源（isogeny），等距同源是一种显示椭圆曲线上的点与另一椭圆曲线上的点对应关系的映射。解锁SIKE需要找到至少2434个这种曲线中的两条曲线之间的正确映射，这个数量之大以至于英语中没有合适的词汇来描述，即使对于量子计算机而言，这也几乎是不可能的，除非拥有密钥。为了与已编码消息的接收者共享密钥，每个发送者必须提供关于一条曲线上的两个点的信息。Castryck和Decru能够使用这些关于点的额外信息来重建映射，因此可以在不实际解决困难的数学问题的情况下破解代码。

目前在比利时布鲁塞尔自由大学工作的Decru表示，同源作为加密方案的基础并未消亡，但它的基础并不稳固。两人对SIKE的攻击并不影响NIST提出其他采用不同数学方法的标准。其中两个基于结构化网格（一种重复网格）。困难的数学问题是确定网格的各个部分如何相互关联。SPHINCS+基于哈希函数，该函数采用一串数字并将其转换为较短的字符串，从而形成原始字符串的可识别指纹。哈希函数是不可逆的，因此它们比其他方法更容易创建，但由于其单向性质，它们只能用于签名验证，不能用于交易加密密钥。

Castryck表示，在量子世界中确保数据安全时，以平衡安全性和效率的竞争需求的方式使用加密算法是另一个挑战。密钥越长越安全，因为问题的解决方案有更多可能，从而增加了找到正确解决方案的难度。但这也增加了生成和传输密钥所需的时间和计算带宽。“业界并不要求一个一次密钥交换需要一个小时的加密系统，即使它非常安全，”Castryck说。

官员们担心量子计算对国家安全构成的威胁。

侧信道攻击

德国波鸿马克斯·普朗克安全与隐私研究所的密码工程师Peter Schwabe正在研究如何保护密码方案免受侧信道攻击。在此类攻击中，对手从计算机收集信息，这些信息不是密钥本身的一部分，但可以为其提供提示。例如，在经典计算中，向服务器发送消息并测量获得响应所需的时间可以揭示给定位是“1”还是“0”，或者耗电量可能会根据密码密钥的结构而变化。攻击者可以利用这些线索拼凑出密钥。或者，如果攻击者可以在服务器上放置一些间谍软件，他们可能能够通过测量其对内存等资源的需求来了解该服务器正在执行的任务。

今年8月，跨国科技巨头英特尔发布了自2015年以来销售的多个品牌芯片的固件补丁，主要是因为在加州圣地亚哥谷歌安全研究员Daniel Moghimi 发现了他称为Downfall的漏洞后。这一漏洞利用了芯片加速收集分散在内存中的数据的过程的方式：有权访问芯片的攻击者发送加密随机数据的请求，然后收集从进程中泄漏的一些低级信息；攻击者可以分析该信息并寻找模式，最终可用于拼凑系统正在使用的加密密钥。

尽管攻击的具体情况会因特定的加密方案而异，但后量子密码学中没有任何东西可以从本质上排除此类攻击。“这个项目的一个目标是弄清楚我们如何系统地保护这些新的加密系统免受此类攻击，” Schwabe说。

NIST并不是唯一致力于加密标准的组织。德国联邦信息安全办公室还提供了有关使用哪些系统的建议。其中包括两项未进入NIST最终选择的标准。一个是基于点阵的密钥封装方案FrodoKEM，另一种是使用难以逆转的纠错码的Classic McEliece。两者都被认为比NIST提案更安全，但它们涉及更长的密钥，因此使用速度更慢。

其他标准组织也可能会参与其中。例如，互联网工程任务组不推荐特定的加密标准，但对包含这些标准的协议有发言权。2018年至2019年间，中国密码学研究会举办了自己的新算法竞赛。提交的内容涉及与NIST提案中相同的数学问题系列，最终获胜的方案是基于结构化网格的。

最终必须有一套国际商定的标准。“原因很简单，当你想要进行互联网通信时，两端都需要使用相同的加密技术，”Schwabe说。大型国际公司也将发挥作用。例如，谷歌在8月份宣布将Kyber整合到其Chrome浏览器中。“如果谷歌与Kyber达成了关键协议，那么每个想要与谷歌交谈的人都需要使用Kyber，无论他们位于世界的哪个地方，”Schwabe说。

实施NIST标准并将其或类似方法推广到世界各地的计算机系统需要时间。与此同时，密码学家将继续尝试开发算法，并尝试破解已经存在的算法。但Decru说，现在可以收集数据并在稍后阶段解密的威胁意味着这个问题很紧迫，世界越早采用后量子密码学越好。“我们不知道量子计算机是否会在20年、30年或 40年后出现，”他说。“但我认为在这方面没有时间可浪费，真的没有。”

Neil Savage是一位来自马萨诸塞州洛厄尔的科普作家。

原文以Keeping secrets in a quantum world为标题发布在2023年11月2日出版的《自然》增刊“自然聚焦-网络安全“上。

© nature

Nature | doi：10.1038/d41586-023-03336-4

版权声明：

本文由施普林格·自然上海办公室负责翻译。中文内容仅供参考，一切内容以英文原版为准。欢迎转发至朋友圈，如需转载，请邮件[email protected]。未经授权的翻译是侵权行为，版权方将保留追究法律责任的权利。

© 2023 Springer Nature Limited. All Rights Reserved