量子计算|12年来无人攻破的量子加密算法:被一台高龄老爷机降伏了( 二 )


作者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标准算法的候选者之一 。