完全破解也只需62分钟，CPU单核即可搞定。两位鲁汶大学学者基于数学理论破解量子加密算法的消息，最近轰动了密码学界。

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

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

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

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

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

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

　　这是一种利用椭圆曲线作为定理的加密算法，看上去可以由一个y⊃2;=x⊃3;+Ax+B来表述，其中A和B是数字。该方法的关键之处是使用了同源（Isogenies），也就是把一条椭圆曲线的点映射到另一条椭圆曲线上。

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

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

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

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

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

　　这个终点由于可以被秘密确定，所以可将它作为共享密钥。这种加密方式最大的好处在于，即便是攻击者知道了Alice和Bob发送给彼此的中间点，也无法得知中间的过程。

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

　　来自比利时鲁汶大学的学者们，在8月5日的一篇论文中详细解释了破解方法。作者Thomas Decru表示，虽然椭圆曲线是一维的，但是在数学中，它可以被可视化表示为二维或者任何维度，所以可以在这些广义对象之间创建映射关系。

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

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

　　破解中用到的关键定理，来自数学家恩斯特·卡尼 (Ernst Kani ) 在1997年发表的一篇论文。在实际操作中，研究人员通过一台已经用了10年的台式机，只需4分钟就能找到SIKE密钥。

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

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

　　奥克兰大学的数学家Steven Galbraith认为，此次破解中使用的核心理论来自数学。这也在一定程度上验证了，对于研究密码学，数学基础理论的积累非常重要。SIKE的提出者之一BOB全站，加拿大滑铁卢大学教授David Jao肯定了这次工作：

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

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

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

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

　　本文为澎湃号作者或机构在澎湃新闻上传并发布，仅代表该作者或机构观点，不代表澎湃新闻的观点或立场，澎湃新闻仅提供信息发布平台。申请澎湃号请用电脑访问。