The RSA cryptosystem could be easily broken with large scale general purpose quantum computers running Shor's factorization algorithm. Being such devices still in their infancy, a quantum annealing approach to integer factorization has recently gained attention. In this work, we analyzed the most promising strategies for RSA hacking via quantum annealing with an extensive study of the low noise D-Wave 2000Q computational times, current hardware limitations and challenges for future developments.
The RSA cryptosystem could be easily broken with large scale general purpose quantum computers running Shor's factorization algorithm. Being such devices still in their infancy, a quantum annealing approach to integer factorization has recently gained attention. In this work, we analyzed the most promising strategies for RSA hacking via quantum annealing with an extensive study of the low noise D-Wave 2000Q computational times, current hardware limitations and challenges for future developments.
The majority of scholars believe that Shor’s algorithm is a unique and powerful quantum algorithm for RSA cryptanalysis, so current postquantum cryptography research has largely considered only the potential threats of Shor’s algorithm. This paper verifies the feasibility of deciphering RSA public key cryptography based on D-Wave, which is the second most effective RSA attack method after Shor’s algorithm. This paper proposes the influence of different column methods on the final integer factorization, puts forward a new dimension reduction formula, simplifies the integer factorization model based on quantum annealing, simulates it with the qbsolv quantum computing software environment provided by D-Wave, and factors the integer 1630729 (an 11-bit prime factor multiplied by an 11-bit prime factor). The research results show that choosing an appropriate number of columns and column width in the binary integer factorization multiplication table is very important for studying the optimization ability of the quantum annealing algorithm. In fact, Science, Nature, IEEE Spectrum, and the National Academies of Sciences (NAS) are consistent in asserting that the practical application of general-purpose quantum computers is far in the future. Therefore, although D-Wave computers were initially mainly purchased by Lockheed Martin, Google, etc., for purposes such as image processing, machine learning, combinatorial optimization, and software verification, post quantum cryptography research should further consider the potential of the D-Wave quantum computer in deciphering RSA cryptosystems in the future, and a discussion of this potential is one of the contributions of this paper.
In this world of massive communication networks, data security and confidentiality are of crucial importance for maintaining secured private communication and protecting information against eavesdropping attacks. Existing cryptosystems provide data security and confidentiality by the use of encryption and signature algorithms for secured communication. Classical computers use cryptographic algorithms that use the product of two large prime numbers for generating public and private keys. These classical algorithms are based on the fact that integer factorization is a non-deterministic polynomial-time (NP) problem and requires super-polynomial time making it impossible for large enough integers. Shor’s algorithm is a well-known algorithm for factoring large integers in polynomial time and takes only O(b3) time and O(b) space on b-bit number inputs. Shor’s algorithm poses a potential threat to the current security system with the ongoing advancements of Quantum computers. This paper discusses how Shor’s algorithm will be able to break integer factorization-based cryptographic algorithms, for example, Rivest–Shamir–Adleman (RSA) and Rabin Algorithms. As a proof of concept, experimental analysis of Quantum Shor’s algorithm on existing public-key cryptosystems using IBM Quantum Experience is performed for factorizing integers of moderate length (seven bits) due to limitations of thirty-two qubits in present IBM quantum computers. In a nutshell, this work will demonstrate how Shor’s algorithm poses threat to confidentiality and authentication services.
Quantum computing promises revolutionary advances in cryptography, particularly through Shor's algorithm, which can factor large integers in polynomial time and threaten traditional RSA encryption. Through simulation experiments, our research compares Shor's algorithm implementation in ideal versus noisy quantum environments. Under ideal conditions, we factored semiprimes up to N=299 with reasonable resources, but with noise introduction, this ceiling dropped to approximately N=95, beyond which computational costs increased exponentially. The performance gap is striking: ideal simulations factored N=91 in 4 seconds, while noisy simulations required 2,600 seconds—a 650-fold increase. Our hybrid quantum-classical approach showed that noise simulation required modified circuit architectures, reducing gate count growth from 50 to 42.5 gates for comparable test numbers. Qubit requirements followed a step-function pattern in both environments, scaling from 12 qubits for N=15 to 21 qubits for N=91-95, while circuit depth increased from 11 to 17-19 units, with slightly shallower circuits in noisy conditions. In our paper, we propose a hybrid implementation strategy that addresses hardware limitations, present empirical findings on the impact of quantum noise on factoring efficiency, and evaluate the cryptographic security implications under realistic conditions. Our findings underscore the need for fault-tolerant quantum computing and error correction, especially as optimizations suggest factoring 2048-bit RSA keys would require approximately 20 million qubits running for 8 hours. This highlights the urgency in transitioning to post-quantum cryptographic algorithms like CRYSTALS-Dilithium and CRYSTALS-Kyber being standardized by NIST.
The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.
The ongoing development of Quantum Computing (QC) is a breakthrough paradigm that holds the power to revolutionize the way we process information and solve complex problems today. Quantum Computation works on the fundamental principles of Superposition and Entanglement, enabling Quantum Computers to Leverage the power of Physics in Computing. QC has the potential to revolutionize fields such as Drug Development, Financial Modeling, Optimization, and Cryptography. Shor’s algorithm, a quantum algorithm used to factorize large numbers, poses significant threats to RSA, a widely used public key cryptosystem. RSA relies on the difficulty of factoring large semi-primes to keep its security. Shor's algorithm's ability to factorize quickly on a quantum computer undermines RSA's security assumptions, necessitating the exploration of post-quantum cryptographic solutions to ensure secure communication in the quantum era. The goal of this paper is to assess the present state of Shor's algorithm implementation and efficiency, specifically its application in the context of compromising public key cryptosystems like RSA.
Integer factorization, the core of the Rivest-Shamir-Adleman (RSA) attack, is an exciting but formidable challenge. As of this year, a group of researchers' latest quantum supremacy chip remains unavailable for cryptanalysis. Quantum annealing (QA) has a unique quantum tunneling advantage, which can escape local extremum in the exponential solution space, finding the global optimal solution with a higher probability. Consequently, we consider it an effective method for attacking cryptography. According to Origin Quantum Computing, QA computers are able to factor numbers several orders of magnitude larger than universal quantum computers. We try to transform the integer factorization problem in RSA attacks into a combinatorial optimization problem by using the QA algorithm of D-Wave quantum computer, and attack RSA-2048 which is composed of a class of special integers. The experiment factored this class of integers of size 22048,N=p×qAs an example, the article gives the results of 10 RSA-2048 attacks in the appendix. This marks the first successful factorization of RSA-2048 by D-Wave quantum computer, regardless of employing mathematical or quantum techniques, despite dealing with special integers, exceeding 21061−1 of California State University. This experiment verifies that the QA algorithm based on D-Wave is an effective method to attack RSA.