10年老台式机4分钟攻破量子加密算法，核心原理来自25年前明敏发自凹非寺量子位|公众号

明敏发自凹非寺
量子位|公众号QbitAI
只花4分钟，就破解了量子加密算法的密钥。
用的还是一台有10年“高龄”的台式机。
完全破解也只需62分钟， CPU单核即可搞定。

文章图片
两位鲁汶大学学者基于数学理论破解量子加密算法的消息，最近轰动了密码学界。
要知道，他们破解的算法SIKE一直以来都被寄予厚望，过去12年都无人破解。
在前不久美国公布的后量子标准算法中，它是4个候选者之一，后续很可能被加入标准算法中。
而他们使用的方法原理，其实在25年前就提出了。
这引发了微软、亚马逊等多家科技巨头对SIKE的重新调查。
同时也让不少密码学大佬开始感慨，理解密码系统，还是要关注数学基础理论啊！
一朝破解12年未被攻破的算法如上提到的SIKE算法，是一种PQC（后量子计算）算法。
随着量子计算的出现，很多超大计算量问题迎刃而解，但经典加密算法也受到了威胁。
比如著名的RSA算法，其2048位长的加密信息，超算需要80年才能破解，而量子计算暴力破解只要8个小时。
因此，学界提出后量子密码的概念，来抵抗量子计算机的破解。
最近，美国国家标准技术研究所（NIST）刚刚公布了首批后量子密码标准算法，共有4个。
SIKE等另外4个算法，被认定为是候补选手，将进入下一轮的筛选。
SIKE的全称为SupersingularIsogenyKeyEncapsulation 。
这是一种利用椭圆曲线作为定理的加密算法，看上去可以由一个y2=x3+Ax+B来表述，其中A和B是数字。

文章图片
该方法的关键之处是使用了同源（Isogenies），也就是把一条椭圆曲线的点映射到另一条椭圆曲线上。
然后，基于SupersingularIsogenyDiffie-Hellman(SIDH)密钥交换协议，实现后量子密钥封装。
该方法可以抽象为这样一个过程：
假设有Alice和Bob两方想要秘密交换信息，但是处于一个不安全的环境下。
Alice和Bob可以被理解为是两个图（graph），它们有着相同的点，但是边不同。
其中，每个点代表一条不同的椭圆曲线，如果一条椭圆曲线能以特定方式转化为另一条椭圆曲线，即在两点之间画一条边，这条边表示同源关系。
Alice和Bob的边不同，意味着他们分别由不同的同源关系定义。
现在， Alice和Bob从同一个点出发，每个人沿着自己图上的边随机跳跃，并且跟踪从一个点到另一个点的路径。
然后，两个人公布自己到达的中间点，但是路径保密。
再然后，二人交换位置，重复自己之前的秘密路径，这样一来，二人最后会到达同一个点。
这个终点由于可以被秘密确定，所以可将它作为共享密钥。

文章图片
这种加密方式最大的好处在于，即便是攻击者知道了Alice和Bob发送给彼此的中间点，也无法得知中间的过程。
更没法找到最终的终点。
SIDH/SIKE也被认为是最早被使用的、基于同源的加密协议之一。
但这种方法有个问题，就是它必须对外提供一个辅助扭转点（auxiliarytorsionpoints），也就是除了Alice和Bob公开交换位点外的一些信息。
很多破解方法都在尝试利用这个信息，这次也是如此。
来自比利时鲁汶大学的学者们，在8月5日的一篇论文中详细解释了破解方法。