未来的量子计算机可能会快速突破现代密码学。因此，数学家和密码学家一直在寻找合适的新加密算法来抵御量子计算机的攻击。这种能够抵抗量子计算机对现有密码算法攻击的新一代密码算法被称为“后量子密码学（PQC，postquantumcryptography）”算法。但最近，比利时鲁汶大学的研究人员发现，一种很有前途的PQC加密算法可以在短短1小时内完全破解（有些版本只需要4分钟）。问题是，这个记录不是高端电脑创造的，而是十年前CPU单核的台式机创造的。研究人员表示，这一最新的、令人惊讶的失败凸显了后量子密码学在被采用之前需要克服的许多障碍。论文链接：https://eprint.iacr.org/2022/975理论上，量子计算机可以快速解决传统计算机需要花费大量时间才能解决的问题。例如，现代密码学在很大程度上依赖于经典计算机在处理复杂数学问题（如大数因式分解）时所面临的极端困难。原则上，量子计算机可以运行能够快速破解这种加密的算法。为了应对这种威胁，世界各地的密码学家花了20年时间设计后量子加密算法。这些算法基于量子计算机和经典计算机都难以解决的新数学问题。多年来，美国国家标准技术研究院(NIST)等机构的研究人员一直在研究哪些PQC算法应该成为世界可以采用的新标准。该机构在2016年宣布正在寻找候选PQC算法，并在2017年收到了82份提案。随后，经过三轮审查后，NIST宣布了四种即将成为标准的算法，还有四种将进入下一轮审查作为可能的竞争者。评测还没结束，其中一个竞争者倒下了，被一台用了10年的台式机摔坏了。该算法称为SIKE（超奇异同源密钥封装），已被微软、亚马逊、Cloudflare和其他公司研究过。“这次攻击来得如此突然，以至于它是一颗灵丹妙药[极其有效的解决方案]，”密歇根大学安娜堡分校的密码学家克里斯托弗·佩克特(ChristopherPeikert)说。什么是SIKE算法？SIKE是一系列涉及椭圆曲线的PQC算法。“长期以来，椭圆曲线一直是数学家的研究课题，”NIST数学家DustinMoody说。“它们由y^2=x^3+Ax+B等式描述，其中A和B是数字。例如，椭圆曲线可以是y^2=x^3+3x+2。”1985年，“数??学家想出了一种方法来制作涉及今天广泛部署的椭圆曲线的密码系统，”穆迪说。“然而，这些椭圆曲线密码系统很容易受到量子计算机的攻击。”2010年左右，研究人员发现了一种在密码学中使用椭圆曲线的新方法。人们相信，这种新想法不容易受到量子计算机的攻击。这种新方法是基于如何将椭圆曲线上的两个点相加得到椭圆曲线上的另一个点的问题。算法名称中的“同源性”代表同源性，即从一条椭圆曲线到另一条椭圆曲线的映射，它保留了加法定律。“如果你让这个映射足够复杂，那么数据加密的挑战就变成了，给定两条椭圆曲线，很难找到它们之间的同源性，”比利时鲁汶大学的研究合著者说。数学密码学家ThomasDecru说。SIKE是基于超奇异同源Diffie-Hellman(SIDH)密钥交换协议的同源密码术的一种形式。“SIDH/SIKE是最早实用的基于同源的加密协议之一，”Decru说。然而，SIKE的一个弱点是，为了使其发挥作用，它需要向公众提供额外的信息，即辅助扭曲点。“一段时间以来，攻击者一直试图利用这些额外信息，但未能成功利用它来破坏SIKE，”穆迪说。“然而，这篇新论文找到了一种方法，他们使用了一些非常高级的数学。”为了解释这种新的攻击，Decru说虽然椭圆曲线是一维对象，但在数学中，椭圆曲线可以是一个对象，可以被可视化为二维或任何其他维度。人们还可以在这些广义对象之间创建同源性。通过应用一个有25年历史的定理，新的攻击使用SIKE暴露的额外信息来构建二维同源性。然后，这种同源性可以重建SIKE用来加密消息的密钥。“最令我惊讶的是，这次攻击似乎不知从何而来，”马里兰大学帕克分校的密码学家JonathanKatz说。虽然没有参与新的研究，但他说：“之前很少有结果表明SIKE有任何弱点，而这次的结果突然给了SIKE一个完全毁灭性的攻击，因为它找到了完整的密钥，而且很快就发现了，没有任何量子计算。”攻击历时十余年，4分钟破解。CPUE5-2630v2)台式电脑至少4分钟就能找到某种SIKE算法保护的密钥，破解SIKE算法只需要62分钟被认为符合NIST量子安全1级标准。这些实验都是在CPU的一个核心上运行的。“通常，对密码系统的严重攻击发生在系统提出后不久，或者系统第一次引起注意时。”随着时间的推移，攻击变得更强或显着削弱系统。但是这次攻击，在没有任何征兆的情况下，密码系统突然被彻底攻破。Peikert说：“自从SIDH被首次提出以来，对SIDH/SIKE的攻击在过去的12年里几乎没有任何进展，直到这次才彻底攻破。”SIKE已经过十多年的测试，但未选择SIKE作为标准的原因之一是担心它太新且没有得到很好的研究。“人们担心SIKE可能会面临重大攻击的风险，事实证明他们是对的，”奥克兰大学的数学家史蒂文加尔布雷思说。那么为什么直到现在人们还没有发现SIKE中的漏洞呢？根据加尔布雷思的说法，一个重要原因是新攻击“应用了非常先进的数学”。Katz对此表示同意，他说：“我怀疑世界上只有不到50人同时拥有PQC基础数学和必要的密码学。”此外，PQC初创公司SandboxAQ的密码学家DavidJoseph曾表示，“无论是从实现角度还是从理论角度来看，同源问题是否‘出了名的困难’，使得它的根本缺陷更有可能是日后发现。”此外，“还应该指出的是，在NIST进行几轮筛选之前，可用于分析的PQC算法数量非常多，因此研究工作被稀释了。经过几轮筛选，研究人员已经能够专注于一个少量的算法，”约瑟夫说。SIKE的发明者之一、加拿大滑铁卢大学教授DavidJao说：“我认为这个新成果是一项了不起的工作，我给作者们最高的赞誉。起初，我对SIKE的破解感到难过，因为它在数学上是一个如此优雅的方案。“但新的发现只是反映了科学是如何运作的：我们提出一个系统，当时大家觉得它似乎没问题，然后经过分析，有人发现了它的弱点。他们花了10多年的时间弄明白。”发现一个弱点是不寻常的，但除此之外，它不在普通科学进步的范围之外，”DavidJao补充道。在Jao看来，SIKE现在被破解是一件好事，因为它还没有被广泛部署。SIKE被破解意味着什么？SIKE是今年第二个被破解的NISTPQC候选算法。今年2月，苏黎世IBM研究院的密码学家WardBeullens透露，他可以用笔记本电脑破解Rainbow算法是NIST第三轮审查的一部分。Katz说：“这表明所有PQC场景都需要进一步研究。”然而，Moody指出，虽然SIKE已被破解，但其他基于同源的密码系统，如CSIDH或SQIsign，尚未被破解，“有些人可能认为基于同源的密码学已经死了，但事实远非如此，我认为关于基于同源的密码学还有很多东西需要学习，”Decru说。此外，这项新工作可能无法反映NIST的PQC研究水平。正如Decru所指出的，SIKE是NIST收到的82个提案中唯一基于同源的密码系统；同样，Rainbow是这些提交中唯一的多元算法。Galbraith说，那些被NIST作为“标准”或在第四轮审查中采用的算法是基于密码学家长期研究和分析的数学思想。“这并不能保证它们是安全的，这只是意味着它们可以在攻击中存活更长的时间。”穆迪对此表示同意，并指出“破解密码系统总会有一些惊人的突破性成果。与任何密码系统一样，我们没有绝对的安全保证。最好的说法是经过许多聪明人的大量研究，没有人在这个密码系统中发现任何漏洞。”“我们的程序旨在允许攻击和破解，”穆迪说。“我们在每一轮评估中都看到了它们。这是获得安全信心的唯一途径。”加尔布雷思对此表示赞同，并指出像这样的研究“正在发挥作用”。尽管如此，“我认为Rainbow和SIKE的倒闭会让更多人认真思考NIST后量子标准化过程中任何获胜者是否需要备份计划，”Decru说。“仅仅依赖一个数学概念或方案可能风险太大。这也是NIST自己的想法——他们的主要方案可能是基于格的，但他们想要一个非基于格的备份。”选项。”Decru指出，其他研究人员已经开始开发新版本的SIDH/SIKE，他们认为可以防止这种新型攻击。“我本以为结果是，当攻击升级时，人们会尝试修补SIDH/SIKE，”Decru说。总而言之，事实证明，这种新攻击的起点是一个“与密码学完全无关”的定理，并且“揭示了进行纯数学基础研究以理解密码系统的重要性，”Galbraith说。Decru对此表示赞同，并指出“在数学中，并不是所有的东西都立即适用。有些东西几乎永远不会适用于任何现实生活中的情况。但这并不意味着我们不应该直接研究这些更晦涩的主题。”
