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

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

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 components.The classical lattice reduction algorithm is synergistically integrated with the Schnorr algorithm.The quantum annealing algorithm is incorporated,and the Babai algorithm's rounding direction is adjusted leveraging the quantum tunneling effect for precise vector determination.Leveraging the exponential acceleration capabilities of quantum computing,we address the challenge by computing two rounded directions for solutions on each bit of an N-dimensional lattice.This enables the realization of an exponential solution space search,a capability beyond the reach of traditional computing methods.This approach enhances the search efficiency for close vectors in the CVP(Closest Vector Problem)by considering both the resource and time costs associated with qubits.And we implement the first 50-bit integer decomposition on D-Wave Advantage.Randomly selecting RSA integer decompositions within the range of 4-5o bits serves as a demonstration to validate the algorithm's universality and expansibility.The experiments indicate that,in the context of slow progress in universal quantum computing devices,D-Wave quantum annealing has shown better realistic attack capabilities.Quantum annealing does not suffer from the critical deficiency of the NISQ(Noisy Intermediate-Scale Quantum)quantum computing VQA(Variational Quantum Algorithms)—the barren plateaus problem,which can lead to algorithmic convergence issues,and it cannot be extended to large-scale attacks.