全球观天下！10年老台式机4分钟攻破后量子加密算法，核心原理来自25年前

来源：量子位　2022-08-26 16:28:42

明敏发自凹非寺
量子位 | 公众号 QbitAI

只花 4分钟 ，就破解了量子加密算法的密钥。

(资料图片)

用的还是一台有 10年 “高龄”的台式机。

完全破解也只需 62分钟 ，CPU单核即可搞定。

两位鲁汶大学学者基于 数学理论 破解量子加密算法的消息，最近轰动了密码学界。

要知道，他们破解的算法 SIKE 一直以来都被寄予厚望，过去12年都无人破解。

在前不久美国公布的后量子标准算法中，它是4个候选者之一，后续很可能被加入标准算法中。

而他们使用的方法原理，其实在 25年前 就提出了。

这引发了微软、亚马逊等多家科技巨头对SIKE的重新调查。

同时也让不少密码学大佬开始感慨，理解密码系统，还是要关注数学基础理论啊！

一朝破解12年未被攻破的算法

如上提到的SIKE算法，是一种 PQC （后量子计算）算法。

随着量子计算的出现，很多超大计算量问题迎刃而解，但经典加密算法也受到了威胁。

比如著名的 RSA算法 ，其2048位长的加密信息，超算需要80年才能破解，而量子计算暴力破解只要 8个小时 。

因此，学界提出 后量子密码 的概念，来抵抗量子计算机的破解。

最近，美国国家标准技术研究所（NIST）刚刚公布了首批后量子密码标准算法，共有4个。

SIKE等另外4个算法，被认定为是候补选手，将进入下一轮的筛选。

SIKE 的全称为Supersingular Isogeny Key Encapsulation。

这是一种利用椭圆曲线作为定理的加密算法，看上去可以由一个y²=x³+Ax+B来表述，其中A和B是数字。

该方法的关键之处是使用了同源（Isogenies），也就是把一条椭圆曲线的点映射到另一条椭圆曲线上。

然后，基于Supersingular Isogeny Diffie-Hellman ( SIDH ) 密钥交换协议，实现后量子密钥封装。

该方法可以抽象为这样一个过程：

假设有Alice和Bob两方想要秘密交换信息，但是处于一个不安全的环境下。

Alice和Bob可以被理解为是两个图（graph），它们有着相同的点，但是边不同。

其中， 每个点代表一条不同的椭圆曲线 ，如果一条椭圆曲线能以特定方式转化为另一条椭圆曲线，即在两点之间画一条边， 这条边表示同源关系 。

Alice和Bob的边不同，意味着他们分别由不同的同源关系定义。

现在，Alice和Bob从同一个点出发，每个人沿着自己图上的边随机跳跃，并且跟踪从一个点到另一个点的路径。

然后，两个人公布自己到达的中间点，但是路径保密。

再然后，二人交换位置，重复自己之前的秘密路径，这样一来，二人最后会到达同一个点。

这个终点由于可以被秘密确定，所以可将它作为 共享密钥 。

这种加密方式最大的好处在于，即便是攻击者知道了Alice和Bob发送给彼此的中间点，也无法得知中间的过程。

更没法找到最终的终点。

SIDH/SIKE 也被认为是最早被使用的、基于同源的加密协议之一。

但这种方法有个问题，就是它必须对外提供一个 辅助扭转点 （auxiliary torsion points），也就是除了Alice和Bob公开交换位点外的一些信息。

很多破解方法都在尝试利用这个信息，这次也是如此。

来自比利时鲁汶大学的学者们，在8月5日的一篇论文中详细解释了破解方法。

作者Thomas Decru表示，虽然椭圆曲线是一维的，但是在数学中，它可以被可视化表示为二维或者任何维度，所以可以在这些广义对象之间创建映射关系。

Decru和Castryck计算了Alice的起点椭圆曲线与公开发给Bob的椭圆曲线的乘积，这样会得到一个阿贝尔曲面。

然后通过一种可以将阿贝尔曲面和椭圆曲线联系起来的数学定理，以及辅助扭转点的信息，他们就能找到Alice和Bob的共享密钥。

破解中用到的关键定理，来自数学家恩斯特·卡尼 (Ernst Kani ) 在 1997年 发表的一篇论文。

在实际操作中，研究人员通过一台已经用了 10年 的台式机，只需4分钟就能找到SIKE密钥。

完全攻破SIKE算法也只用了62分钟，而且全程只用了单核。

对此，加密算法专家Christopher Peikert表示，一般当一种加密算法被提出后，往往会立刻出现很多破解方法，但是SIKE在提出的12年来，始终没有被破解过，直到这次“一击即中”。

而SIKE没有被选为PQC标准，也是因为学界担心它还没有被充分研究，有遭受重大攻击的可能。

这一次，SIKE被破解的关键，被归功到了对数学理论的应用。

奥克兰大学的数学家Steven Galbraith认为，此次破解中使用的核心理论来自数学。这也在一定程度上验证了，对于研究密码学，数学基础理论的积累非常重要。

SIKE的提出者之一，加拿大滑铁卢大学教授David Jao肯定了这次工作：

虽然一开始我为SIKE被破解感到难过，但这种利用数学的破解方法实在太妙了。

同时，他也为SIKE在被大范围部署前被破解感到庆幸。

不过，虽然SIKE被破解了，但是其他使用 同源方法 加密的方法（CSIDH\SQsign）还没有被破解。

值得一提的是，这不是今年第一个被破解的PQC算法。

今年2月，多变量算法Rainbow也被破解了。

苏黎世IBM研究院的学者Ward Beullens，用自己的笔记本电脑计算了一个周末（53个小时），破解了Rainbow的密钥。

这一算法同样是NIST PQC标准算法的候选者之一。

参考链接： [1]https://spectrum.ieee.org/quantum-safe-encryption-hacked [2]https://www.degruyter.com/document/doi/10.1515/crll.1997.485.93/html [3]https://eprint.iacr.org/2022/214 [4]https://www.quantamagazine.org/post-quantum-cryptography-scheme-is-cracked-on-a-laptop-20220824/

— 完 —

量子位 QbitAI · 头条号签约

关注我们，第一时间获知前沿科技动态

关键词：椭圆曲线加密算法数学基础

推荐DIY文章