Quantum Annealing Public Key Cryptographic Attack Algorithm Based on D-Wave Advantage
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 2 269 753 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-50 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.
NETL
NSTL
万方数据
