基于D-Wave Advantage的量子退火公钥密码攻击算法研究  

Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage

作　　者：王潮[1] 王启迪 洪春雷 胡巧云 裴植 WANG Chao;WANG Qi-Di;HONG Chun-Lei;HU Qiao-Yun;PEI Zhi(Key Laboratory of Specialty Fiber Optics and Optical Access Networks,Shanghai University,Shanghai 200444)

机构地区：[1]上海大学特种光纤与光接入网重点实验室,上海200444

出　　处：《计算机学报》2024年第5期1030-1044,共15页Chinese Journal of Computers

摘　　要：D-Wave专用量子计算机的原理量子退火凭借独特的量子隧穿效应可跳出传统智能算法极易陷入的局部极值,可视为一类具有全局寻优能力的人工智能算法.本文研究了两类基于量子退火的RSA公钥密码攻击算法(分解大整数N=pq):一是将密码攻击数学方法转为组合优化问题或指数级空间搜索问题,通过Ising模型或QUBO模型求解,提出了乘法表的高位优化模型,建立新的降维公式,使用D-Wave Advantage分解了 200万整数2269753.大幅度超过普渡大学、Lockheed Martin和富士通等实验指标,且Ising模型系数h范围缩小了 84%,系数J范围缩小了 80%,极大地提高了分解成功率,这是一类完全基于D-Wave量子计算机的攻击算法;二是基于量子退火算法融合密码攻击数学方法优化密码部件的攻击,采用量子退火优化CVP问题求解,通过量子隧穿效应获得比Babai算法更近的向量,提高了 CVP问题中光滑对的搜索效率,在D-Wave Advantage上实现首次50比特RSA整数分解.实验表明,在通用量子计算机器件进展缓慢情况下,D-Wave表现出更好的现实攻击能力,且量子退火不存在NISQ量子计算机VQA算法的致命缺陷贫瘠高原问题:算法会无法收敛且无法扩展到大规模攻击.Quantum computing presents an exciting yet formidable challenge to cryptographic security.The advancement of various quantum computers in their efforts to attack RSA has been notably sluggish.In contrast to the constraints imposed by key technologies such as error correction codes on universal quantum computers,the developments of critical theoretical and hardware developments of D-Wave special quantum computers show a stable growth trajectory.Quantum annealing is the fundamental principle behind D-Wave special quantum computing.It has a unique quantum tunneling effect that can jump out of the local extremes that traditional intelligent algorithms are prone to fall into.It can be considered a class of artificial intelligence algorithms with global optimization-seeking capability.This paper introduces two technical approaches grounded in the quantum annealing algorithm,using pure quantum algorithm and quantum annealing combined with classical algorithm to implement RSA public key cryptography attack(factorizing the large integer N=pq).One is to convert the mathematical method of cryptographic attack into a combi-natorial optimization problem or exponential space search problem,which is solved by Ising model or QUBO model.We propose a high level optimization model for multiplication tables and establish a new dimensionality reduction formula from the two aspects of saving qubit resources and improving the stability of Ising model,and decompose the two million level of integers 2269753 using D-Wave Advantage.Not only does it significantly exceed the experimental indexes of Purdue University,Lockheed Martin and Fujitsu,but the range of coefficient h of the Ising model is reduced by 84%and the range of coefficient J is reduced by 80%,which greatly improves the success rate of decomposition.This is a class of attack algorithms entirely based on D-Wave quantum computers.Secondly,based on quantum annealing algorithm fused with mathematical methods of crypto-graphic attacks to optimize the attacks on cryptographic compone

关 键 词：RSA D-WAVE 量子退火 CVP 量子隧穿 整数分解 量子计算 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]