基于D-Wave Advantage的量子计算实用化SPN结构对称密码攻击研究

作     者：裴植 洪春雷 王启迪 胡巧云 王潮 PEI Zhi;HONG Chun-Lei;WANG Qi-Di;HU Qiao-Yun;WANG Chao

作者机构：上海大学特种光纤与光接入网重点实验室上海200444 

出 版 物：《计算机学报》 (Chinese Journal of Computers)

年 卷 期：2025年第48卷第1期

页      面：234-248页

核心收录：

学科分类：0839[工学-网络空间安全] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：密码科学技术全国重点实验室开放课题基金资助 

主　　题：对称密码 量子计算 量子退火 D-Wave量子计算机 量子隧穿效应 

摘      要：截至2023年,谷歌的量子霸权芯片Sycamore尚不能用于密码攻击。量子计算在理论上对公钥密码有致命性威胁,但对对称密码影响甚微,目前业内已经从缩减版密码算法开始积极探索对称密码的量子攻击。SPN结构是对称密码算法中的一种代表性结构,目前基于真实量子计算机的各类量子算法均未能对该结构未经缩减的全规模密码算法进行攻击。基于量子退火算法独有的隧穿效应,使得该算法有利于科学问题的指数级解空间搜索,可将其视为一类具有全局寻优能力的人工智能算法。受传统密码分析方法的影响,本文提出一种对称密码攻击架构:量子退火耦合传统数学方法密码攻击的新型计算架构——QuCMC(Quantum Annealing-Classical Mixed Cryptanalysis)。基于该架构,首先利用可分性刻画SPN结构对称密码算法的线性层和非线性层传播规律,将区分器搜索问题转化为MILP模型求解问题。进一步将MILP模型转化为D-Wave CQM模型,在求解该模型的过程中利用量子波动产生的量子隧穿效应跳出传统智能算法极易陷入的局部亚优解,获得更优的解,即攻击目标对称密码算法的积分区分器。本文使用D-Wave Advantage量子计算机攻击了PRESENT、GIFT-64、RECTANGLE三种SPN结构代表算法,均成功搜索到最长9轮的积分区分器。并且实验结果表明,量子退火算法在跳出局部亚优解能力与降低求解时间两个方面,均优于经典启发式全局寻优算法模拟退火。本研究首次成功利用真实量子计算机对多种全规模SPN结构对称密码算法完成了攻击,攻击效果与传统数学方法持平。