“量子安全”加密解密遭到10年前的电脑攻击

━━ ━━

未来的量子计算机有可能迅速破解现代密码。而现在，研究人员发现，一种有望保护计算机免受高级攻击的算法在短短4分钟内就能被攻破。令人惊奇的是，这只需4分钟的破解并不是由尖端机器完成的，而是一台10年前的传统台式计算机。研究人员表示，这一最新的意外失败说明，后量子密码技术在应用之前，还需要克服诸多障碍。

理论上，量子计算机能够快速解决传统计算机可能需要花上一辈子才能解决的问题，这种差异被作为现代密码学的基础。密码学加密机制的强度来自传统计算机很难解决的某些数学难题，例如，巨大数字的因式分解。但是，量子计算机原则上能够运行算法，快速破解这类加密。

为了应对这种量子威胁，世界各地的密码学家在过去20年里，一直在设计后量子密码学（PQC）算法。这些算法以量子计算机和传统计算机都难以解决的新数学问题为基础。

多年来，美国国家标准技术研究所等组织的研究人员一直在研究哪种PQC算法能够成为世界将采用的新标准。2016年，美国国家标准技术研究所宣布征求候选PQC算法，并在2017年收到82份提交方案。2022年7月，经过3轮审查后，美国国家标准技术研究所公布了4种算法将成为标准，以及另外4种算法将可能作为附加竞争者进入另一轮审查。

目前，一项新的研究揭示了一种可完全破解超奇异同源密钥封装（SIKE）的方法，SIKE是正在接受审查的竞争者之一（亚马逊、Cloudflare、微软和其他公司一直在研究这种算法）。“这一打击是突然的，子弹是致命的。”并未参与这项新工作的美国密歇根大学的密码学家克里斯托弗•佩科特（Christopher Peikert）说。

SIKE是涉及椭圆曲线的一类PQC算法。“数学研究椭圆曲线由来已久。”未参与相关研究的美国国家标准技术研究所数学家达斯汀•穆迪（Dustin Moody）说。

穆迪说，1985年，“数学家发现了一种方法，可以建立涉及椭圆曲线密码系统，而且这些系统得到了广泛的部署。不过，事实证明，这些椭圆曲线密码系统很容易被量子计算机破解。”2010年左右，研究人员发现了一种在密码学中使用椭圆曲线的新方法。“人们相信这种新的理念不容易被量子计算机破解。”他说。

穆迪说，这种新方法的基础是，如何在椭圆曲线上添加2点，以导出椭圆曲线上的另一个点。“同源”是指从一条椭圆曲线到另一条椭圆曲线的映射保持椭圆曲线加法定律。

“如果让这种映射足够复杂，假设很难找到两条给定的椭圆曲线之间同源，就可用于数据加密。”比利时鲁汶大学的数学密码学家托马斯•德克鲁（Thomas Decru）说，他是介绍SIKE破解论文的共同作者之一。

SIKE是一种基于同源的密码方法，它以超奇异同源Diffie-Hellman（SIDH）密钥交换协议为基础。“SIDH/SIKE是第一批实用的基于同源的密码协议。”德克鲁说。

不过，SIKE存在一个漏洞：为了能够工作，它需要公开提供额外的信息，名为辅助扭转点。“攻击者一直试图利用额外信息，但未能用它成功破解SIKE。”穆迪说，“不过，这篇新的论文（讲述了）一种方法，使用相当高级的数学来破解SIKE。”

德克鲁解释说，虽然椭圆曲线是二维对象，但在数学中，椭圆曲线可以被视为任意维度的对象。人们可以在这些广义对象之间创建同源。

应用一条25年前的定理，这种新破解方法可以使用SIKE公开的额外信息构建二维同源。然后，这种同源可以重构SIKE用来加密信息的密钥。2022年8月5日，德克鲁和该小组的首席研究员沃特•卡斯特里科（Wouter Castryck）在密码研究预印本（Cryptology ePrint Archive）上详述了他们的发现。

“最让我惊讶的是，这种攻击似乎不知道是从哪里冒出来的。”未参与这项新工作的马里兰大学帕克分校的密码学家乔纳森•卡茨（Jonathan Katz）说，“之前很少有研究结果表明SIKE有任何弱点，然后就突然出现了这种完全毁灭性打击的研究结果。也就是说，它找到了整个密钥，而且不需要任何量子计算即可相对快速地破解。”

使用基于这种新型打击的算法，一台10年前的英特尔台式电脑只用了4分钟就找到了SIKE保护的密钥。

“从首次提出SIDH，到完全被攻破，十一二年来对SIDH/SIKE的攻击实际上毫无进展。”佩科特说。

SIKE的漏洞直到现在才被发现的原因是，这种新型攻击“采用了非常先进的数学方法，除了攻破系统外，我想不出还有哪些场景下的攻击会拥有如此深度的数学运算。”未参与该研究的新西兰奥克兰大学的数学家史蒂文•加尔布雷斯（Steven Galbraith）说，“世界上能够同时理解这个底层数学方法和加密方法的人不足50个。”