仅用了4分钟就破解了量子加密算法的密钥还是10年的台式机完全破解只需要62分钟，CPU单核就能搞定

鲁汶大学两名学者破解基于数学理论的量子加密算法的消息，最近几天在密码学领域引起轰动要知道，他们破解的算法SIKE一直被寄予厚望，12年来都没人破解过

它是不久前美国公布的后量子标准算法中的四个候选之一，未来很可能被加入到标准算法中他们使用的方法的原理实际上是25年前提出的这引发了微软，亚马逊等多家科技巨头对赛克的重新调查

与此同时，许多密码学家开始表达他们的感受。要了解密码学体系，还是要关注数学的基础理论！

一旦你破解了一个12年都没被破解的算法

上面提到的SIKE算法是一种PQC算法伴随着量子计算的出现，很多计算量巨大的问题得到了解决，但经典的加密算法也受到了威胁比如著名的RSA算法，其2048位长的加密信息被超级计算破解需要80年，而被量子计算暴力破解只需要8个小时因此，学术界提出了后量子密码学的概念来抵御量子计算机的破解

最近几天，美国国家标准与技术研究院刚刚公布了第一批后量子密码标准算法，共有四种SIKE等其他四种算法被确定为候选算法，将进入下一轮筛选SIKE的全称是超奇异同源密钥封装这是一个利用椭圆曲线作为定理的加密算法好像可以用a y = x+ax+b来表示，其中a和b是数

这种方法的关键点是利用了同调性，即一条椭圆曲线的点映射到另一条椭圆曲线上然后，基于超奇异同源Diffie—Hellman 密钥交换协议，实现了后量子密钥封装

这个方法可以抽象为一个过程:假设爱丽丝和鲍勃想要秘密地交换信息，但是他们处在一个不安全的环境中。

爱丽丝和鲍勃可以理解为两个图它们有相同的点，但有不同的边其中，每个点代表一条不同的椭圆曲线如果一条椭圆曲线可以用特定的方式转化为另一条椭圆曲线，即在两点之间画一条边，表示同源关系

爱丽丝鲍勃的边和爱丽丝鲍勃的边的区别是指它们是由不同的同源关系定义的现在，爱丽丝和鲍勃从同一点出发，每个人沿着他的图的边缘随机跳跃，并跟踪从一点到另一点的路径然后，两个人宣布他们到达的中间点，但路径保密然后，两人交换位置，重复他们之前的秘密路径，这样他们最终会到达同一点这个端点是可以秘密确定的，所以可以作为共享密钥

这种加密方式最大的好处是，即使攻击者知道爱丽丝和鲍勃互相发送的中间点，他也无法知道中间的过程没有办法找到最终的目的地

但是这种方法有一个问题，就是必须提供一个辅助的扭点，也就是爱丽丝和鲍勃开放交换点以外的一些信息。

很多破解方法都在尝试利用这些信息，这个也是一样比利时鲁汶大学的学者在8月5日的一篇论文中详细解释了破解方法

Decru和Castryck计算了Alice的起点椭圆曲线和公开发给Bob的椭圆曲线的乘积，从而得到一个阿贝尔曲面然后他们可以通过一个可以把阿贝尔曲面和椭圆曲线连接起来的数学定理，以及辅助扭点的信息，找到爱丽丝和鲍勃的共享密钥破解中用到的关键定理来自数学家恩斯特·卡尼1997年发表的一篇论文

在实践中，研究人员可以通过使用了10年的桌面，在短短4分钟内找到SIKE key完全破解SIKE算法只用了62分钟，整个过程只用了一个核心

对此，加密算法专家克里斯托弗·佩克特表示，一般来说，当一种加密算法被提出时，往往会立即出现许多破解方法可是，赛克从提出到现在12年，从来没有被破解过，直到这一次，被一击即中SIKE没有被选为PQC标准，也是因为学术界担心它没有得到充分研究，可能会遭受重大打击

这一次，赛克破解的关键归结于数学理论的应用。

奥克兰大学的数学家史蒂文·加尔布雷斯认为，这次破解中使用的核心理论来自数学这也在一定程度上证明了它对于密码学的学习和数学基础理论的积累是非常重要的

SIKE的支持者之一，加拿大滑铁卢大学教授David Jao肯定了这项工作:虽然一开始我对SIKE被破解感到很遗憾，但是这种利用数学的破解方法真的很奇妙同时，他很高兴SIKE在广泛部署之前就被破解了

不过，虽然SIKE已经被破解了，但是其他使用同源方法的加密方法并没有被破解。

值得一提的是，这并不是今年第一个被破解的PQC算法今年2月，多元算法彩虹也被破解苏黎世IBM研究所的学者沃德·伯伦斯用他的笔记本电脑计算了一个周末，破解了彩虹的密钥该算法也是NIST PQC标准算法的候选算法之一

参考链接: