单核CPU一小时破解抗量子加密算法

鲁汶大学研究人员提出一种针对SIDH协议的高效密钥恢复攻击方法，使用普通单核CPU，一小时即可攻破SIKE抗量子密码算法。

密钥封装机制是一种使用非对称密码学技术安全交换对称密钥的协议。SIKE (Supersingular Isogeny Key Encapsulation，超奇异同源密钥封装)是一种广泛应用的密钥封装机制，2022年7月入选NIST后量子密码学算法第4轮。有多个工业实现和部署实验。相比对称密钥算法，目前使用的密钥封装易被量子计算机攻击。使用复杂数学构建的超奇异同源图被认为可以对抗量子计算机的攻击。

SIKE协议的正确性和安全性依赖于SIDH（Supersingular Isogeny Diffie-Hellman，超奇异同源Diffie-Hellman），即计算超奇异椭圆曲线间同源的困难性问题。SIDH的安全性与寻找两条具有相同点数的超奇异椭圆曲线之间的同源映射问题密切相关。

而攻击恰恰利用了SIDH有辅助点和秘密同源的度已知的情况。SIDH协议中双方共享的辅助点已知是一个潜在的安全弱点，已经被用于GPST适应攻击、fault攻击等。

研究人员对攻击算法进行了实现——Magma，Magma成功破解了SIKEp434。Magma分别在4分钟和6分钟内成功解决了微软SIKE挑战赛$IKEp182 和$IKEp217问题。研究人员将Magma部署在Intel Xeon CPU E5-2630v2（2.60GHz）单核CPU上，运行约62分钟即成功恢复SIKEp434参数（满足NIST后量子安全等级level 1）。对于具有更高安全级别的SIKEp503 (安全等级level 2)、SIKEp610 (安全等级level 3)和SIKEp751 (安全等级level 5)，分别在2小时19分钟、8小时15分钟和21小时37分钟内恢复密钥。

SIDH发明者确认攻击不影响CSIDH或SDISign等同源加密算法。论文中指出采用SIDH的变种——B-SIDH也可能会受到攻击，因此单纯改变素数无法预防此类攻击。

该攻击对其他依赖其他数学难题的后量子密码算法没有影响。

编辑：陈十九

审核：商密君