10 年老台式机 4 分钟攻破量子加密算法,此前 12 年无人破解,核心原理来自 25 年前

量子位 2022/8/26 13:01:45 责编:潇公子

只花 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/

相关文章

软媒旗下网站: IT之家 辣品 - 超值导购,优惠券 最会买 - 返利返现优惠券 iPhone之家 Win7之家 Win10之家 Win11之家

软媒旗下软件: 魔方 云日历 酷点桌面 Win7优化大师 Win10优化大师 软媒手机APP应用