The small Qubit quantum algorithm attack to RSA was proposed,the need Qubit of the first quantum register from 2L to L1,it can be reduced to 2 Qubit,the overall space complexity denoted (L1,L),where 2L1≥r,r is the period of decomposed.Because of the reduce of the first quantum register,it reduces the algorithm’s complexity and success rates,and use the binary look-up table method to compute the modular exponentiation,it enhances the computing speed.The improved algorithm’s quantum circuit complexity is T=O(2L2).It have a significant improvement on the time complexity and space complexity.Although the success rate is reduced,the overall success solution time is still lower than the Shor algorithm and the current major improvements Shor algorithm.Completed a simulation experiment.Respectively use the 11、10、9 Qubit decomposing the quantum circuit 119.The new algorithm explore the reality of using a universal quantum computer device to decipher the public key cryptography.
The small Qubit quantum algorithm attack to RSA was proposed,the need Qubit of the first quantum register from 2L to L1,it can be reduced to 2 Qubit,the overall space complexity denoted (L1,L),where 2L1≥r,r is the period of decomposed.Because of the reduce of the first quantum register,it reduces the algorithm’s complexity and success rates,and use the binary look-up table method to compute the modular exponentiation,it enhances the computing speed.The improved algorithm’s quantum circuit complexity is T=O(2L2).It have a significant improvement on the time complexity and space complexity.Although the success rate is reduced,the overall success solution time is still lower than the Shor algorithm and the current major improvements Shor algorithm.Completed a simulation experiment.Respectively use the 11、10、9 Qubit decomposing the quantum circuit 119.The new algorithm explore the reality of using a universal quantum computer device to decipher the public key cryptography.
Compared with electronic computers, quantum parallelism has led to a significant increase in the computing power of quantum computers.However, the computing power of quantum computers will also be limited by the laws of physics, and hence there is no doubt that the computing power of quantum computers is not unlimited.For an algorithm, we need to consider both its space complexity and time complexity.This not only requires quantum computers to achieve large-scale integration, but also requires the quantum coherence time to be sufficiently long.If either of the above two conditions is not met, the task cannot be completed.Shor's algorithm [1] reduced the computational complexity of large integer factorization to the polynomial level.This complexity is of the same order as that of the encryption and decryption for the RSA public key cryptography protocol, which leads to the insecurity of the RSA in universal quantum computing.In addition, some other quantum algorithms show different kinds of enhanced speeds for solving different problems, such as the Grover's search algorithm [2] and its improved works [ 3 , 4 ], and the HHL algorithm [5] .With the remarkable computational power of these quantum algorithms, physicists have begun to seek suitable physical systems for the implementation of quantum computing.The implementation of quantum computing includes several basic technologies, such as preparation, precise control, measurement of the physical qubits, and construction of logical qubits.At present, there are many experimental candidate quantum computing platforms, including the superconducting system [6] , trapped ions system [7] , nitrogenvacancy centers in diamonds [8] , and ultra-cold atoms [9] .Recently, Google experimentally demonstrated quantum supremacy with a superconducting quantum computer [10] , thus placing the research on quantum computing at the forefront.With the booming development of quantum computing technology, the public key cryptosystem also needs to be updated periodically.Thus, cryptographers have to constantly look for public key protocols to resist quantum computing attacks, which leads to the emergence of postquantum cryptography.It is worth noting that although the name of post-quantum cryptography contains the word 'quantum', it essentially consists of protocols of classical cryptography.The current research on post-quantum cryptography mainly includes protocols based on the following four frameworks: the protocols based on Hash function, the pro- * Corresponding author.
Shor’s factorization algorithm (SFA) aims at finding the non-trivial factor of a given composite number, but the algorithm does not always work. In some cases, it has to call back to the beginning of the algorithm to make recalculation. After the analysis of the principle of SFA and the characteristics of RSA public-key cryptography with a series of data calculations, it can be concluded that the random value selected by the algorithm is closely related to whether the obtained period is effective. Therefore, a new optimized scheme is proposed to tackle with this defect from two perspectives: (a) When the a value is a perfect square, the algorithm can be completed with an odd cycle r. (b) When the period r obtained by the randomly selected a value is a multiple of 3, the algorithm can be completed by modifying the decomposition method to relax the requirements for the period without affecting the complexity of the algorithm. Due to the limitations of hardware in applying the quantum algorithms, the classical algorithm is applied to simulate quantum algorithms to test the success rate of decomposition of some composite numbers. The result indicates the effectiveness of the improved algorithm, which significantly reduces the probability of repeated operations to save the quantum circuit resources.
Since the RSA public key cryptosystem was proposed, it has been widely used because of its strong security. Although the proposal of the Shor’s algorithm offers hope for cracking RSA, it is debatable whether the algorithm can actually pose a threat in practice. From the perspective of the quantum circuit of the Shor’s algorithm, we analyse the feasibility of cracking RSA with improved quantum circuits using an ion-trap quantum computer. We present an improved quantum circuit for the modular exponentiation of a constant, which is the most expensive operation in Shor’s algorithm for integer factorization. Whereas previous studies mostly focused on minimizing the number of qubits or the depth of the circuit, we minimize the number of CNOTs, which greatly affects the time to run the algorithm on an ion-trap quantum computer. First, we give the implementation of the basic arithmetic with the lowest known number of CNOTs and the construction of an improved modular exponentiation of a constant by accumulating intermediate data and using a windowing technique. Then, we precisely estimate the number of improved quantum circuits needed to perform the Shor’s algorithm for factoring an n -bit integer, which is 217 n 3 / log 2 n + 4 n 2 + n . We analyse the running time and feasibility of the Shor’s algorithm on an ion-trap quantum computer according to the number of CNOTs. Finally, we discussed the lower bound of the number of CNOTs needed to implement the Shor’s algorithm.
The complexity of public key algorithms like RSA and variants of Elgamal is based on the involvement of exponentiation in encryption and decryption. RSA is based on integer factorization and variants of Elgamal or based on discrete logarithms and are formed as hard problems. To achieve the perceived level of security, the required key length for public key cryptosystem needs to be determined. Quantum computers are capable of conducting an exponential number of simultaneous computations because of which they can find factors in polynomial time. Shor’s algorithm is popular algorithm for factoring huge integers in polynomial time on quantum computers. This paper presents RSA algorithm followed by various possible attacks for factoring and demonstrates Shor’s algorithm for factoring and discuss results for interpretations.
Security analysis of public-key cryptosystems is of fundamental significance for both theoretical research and applications in cryptography. In particular, the security of widely used public-key cryptosystems merits deep research to protect against new types of attacks. It is therefore highly meaningful to research cryptanalysis in the quantum computing environment. Shor proposed a well-known factoring algorithm by finding the prime factors of a number n = pq, which is exponentially faster than the best known classical algorithm. The idea behind Shor's quantum factoring algorithm is a straightforward programming consequence of the following proposition: to factor n, it suffices to find the order r; once such an r is found, one can compute gcd(ar/2± 1, n) = p or q. For odd values of r it is assumed that the factors of n cannot be found (since ar/2is not generally an integer). That is, the order r must be even. This restriction can be removed, however, by working from another angle. Based on the quantum inverse Fourier transform and phase estimation, this paper presents a new polynomial-time quantum algorithm for breaking RSA, without explicitly factoring the modulus n. The probability of success of the new algorithm is greater than 4φ(r)/π2r, exceeding that of the existing quantum algorithm for attacking RSA based on factorization. In constrast to the existing quantum algorithm for attacking RSA, the order r of the fixed point C for RSA does not need to be even. It changed the practices that cryptanalysts try to recover the private-key, directly from recovering the plaintext M to start, a ciphertext-only attack attacking RSA is proposed.
The present study explores the groundbreaking possibilities of Shor's algorithm in cracking RSA encryption, hence enhancing the security consequences of this extensively employed cryptographic protocol. Due to Shor's algorithm's exponential speed advantage over classical algorithms, RSA encryption—a popular public key cryptosystem—is vulnerable to quantum attacks. To keep its security, RSA depends on the difficulty of factoring huge semi-primes. RSA's security presumptions are called into question by Shor's algorithm's quick factorization on a quantum computer, which has prompted research into post-quantum cryptography solutions to guarantee secure communication in the quantum age. Even with parallel computation, the speed and storage capacity of classical computing are constrained. A key idea in quantum computing is quantum parallelism, which allows quantum systems to carry out several computations at once. In contrast to classical portions. The scope of this paper is to understand the fundamentals of Quantum Computing, the current state of Shor’s algorithm implementation, and efficiency, particularly its application in compromising public key cryptosystems like RSA. The project aims to achieve how factorization is done through classical methods and further, how is this done through Shor’s algorithm and QFT techniques.