单核CPU一小时破解后量子加密候选算法

使用运行英特尔至强 CPU 的计算机在一小时内轻松破解了一种后期候选加密算法，该算法旨在抵御未来强大的量子计算机的解密。

有问题的算法是 SIKE——Supersingular Isogeny Key Encapsulation 的缩写——它进入了美国商务部国家标准与技术研究院 (NIST)的第四轮后量子密码学 (PQC) 标准化过程。

“在单核上运行，附加的Magma 代码分别在大约 4 分钟和 6 分钟内打破了 Microsoft SIKE 挑战$IKEp182 和 $IKEp217，”KU Leuven 研究人员 Wouter Castryck 和 Thomas Decru在一篇新论文中说。

“SIKEp434 参数的运行，以前被认为符合 NIST 的量子安全级别 1，大约需要 62 分钟，再次在单个核心上运行。”

学者们进一步指出，该代码是在 2.60GHz 的 Intel Xeon CPU E5-2630v2上执行的，该 CPU于 2013 年使用芯片制造商的 Ivy Bridge 微架构发布。

NIST 在 7 月初宣布了第一套抗量子加密算法：用于通用加密的 CRYSTALS-Kyber，以及用于数字签名的 CRYSTALS-Dilithium、FALCON 和 SPHINCS+。

“SIKE 是一种基于同源的密钥封装套件，它基于超奇异同源图中的伪随机游走，”算法作者的描述中写道。

微软是该算法的主要合作者之一，它表示 SIKE使用“在有限域上定义的椭圆曲线上的算术运算，并计算这些曲线之间的映射，即所谓的同源性”。

“SIDH 和 SIKE 的安全性取决于在两条这样的椭圆曲线之间找到特定同源的难度，或者等效地，在同源图中找到它们之间的路径的难度，”这家科技巨头的研究团队解释道。

抗量子密码学是一种尝试开发对量子和传统计算系统都安全的加密系统，同时还可以与现有的通信协议和网络进行互操作。

这个想法是为了确保今天使用当前算法加密的数据，如RSA、椭圆曲线加密 ( ECC )、AES和ChaCha20，在未来随着量子计算机的出现不会容易受到暴力攻击。

“这些系统中的每一个都依赖于某种数学问题，这在一个方向上很容易解决，但反过来却很难，”SIKE 的共同发明者之一、evolutionQ 的首席密码学家 David Jao 告诉黑客新闻。

“量子计算机可以轻松解决 RSA 和 ECC 背后的难题，如果要构建量子计算机，这将影响大约 100% 的加密互联网流量。”

虽然 SIKE 被定位为 NIST 指定的 PQC 竞争者之一，但最新研究有效地使该算法无效。

“Castryck 和 Decru 的作品打破了 SIKE，”Jao 说。“具体来说，它打破了SIDH [Supersingular Isogeny Diffie-Hellman]，这是 SIKE 所基于的‘难题’（类似于整数分解是 RSA 所基于的难题）。”

“除了 SIKE 之外，还有其他基于同源的密码系统。其中一些，例如B-SIDH，也是基于 SIDH 的，也被新的攻击破解了。其中一些，例如CSIDH和SQIsign，不是基于在 SIDH 上，据我们所知，并没有直接受到新攻击的影响。”

至于接下来的步骤，Jao 表示，虽然可以更新 SIDH 以修复密钥恢复攻击的新线路，但预计将推迟到进一步检查。

“有可能对 SIDH 进行修补或修复以避免新的攻击，我们对如何做到这一点有一些想法，但在我们可以自信地就任何可能的修复发表声明之前，需要对新攻击进行更多分析， ”乔说。