In this paper,we introduced the Peter Shor′s algorithm.Then,we applied it to attacking several kinds of public-key cryptography such as RSA which is based on integer factoring hard problem,and ELGamal,ECC which are based on discrete logarithm hard problem.
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.
The emergence of some quantum algorithms has brought a serious threat to modern cryptography,among which Shor’s algorithm is the most important threatening algorithm for cryptanalysis currently.Shor’s algorithm can solve the integer factorization problem (IFP) and discrete logarithm problem (DLP) in polynomial-time,which makes the current widely used RSA,ElGamal and ECC public key cryptosystem unsafe any more under the quantum computing environment.Therefore,it is necessary to research the cryptanalysis in the quantum computing environment.Solving the IFP is the core idea of Shor’s algorithm for attacking RSA,but breaking RSA does not have to be solved by solving the IFP.A quantum algorithm is designed to attack the RSA cryptosystem starting from the angle of non-factorization.Focusing on the characteristics of RSA public key cryptosystem,using the quantum Fourier transform,the RSA plaintext M can be got by calculating the eth root modulus n .That is,without solving the IFP,RSA is broken.Different from the previous practices that cryptanalysts try to recover the private-key,a ciphertext-only attack algorithm for RSA,directly from recovering the plaintext M to start, is presented.Results show that the probability of success of the new algorithm is higher than that of Shor’s algorithm attacking RSA.At the same time,the new algorithm does not recover the RSA plaintext from the ciphertext without factoring the modulus n ,and avoids the restriction that the order of ciphertext C modules n is even.
Today we witness an explosive growth in attention to Q-computing. Q-computing technologies, along with artificial intelligence (AI) and machine learning (ML) technologies, cloud and foggy computing, as well as technologies for collecting and streaming processing of Big Data and ETL, are constantly leading the lists of ""end-to-end"" information technologies for the digital economy of technologically developed countries of the world. One of the main reasons for this is the potential ability of quantum computers to solve some computational problems more efficiently than any of the most modern classical computers of the von Neumann architecture (supercomputers). The most expressive and interesting, from an applied point of view, examples of such problems are integer factorization, effectively performed by Shor's quantum algorithm, as well as record search in an unordered database, effectively solved by Grover's algorithm. This monograph contains the best practice for solving problems of quantum cryptanalysis to improve cyber security and resilience of the digital economy. The book discusses well-known and author's software implementations of promising quantum Shor algorithms, Grover, Simon et al. Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problems (DLPs) and elliptic curve discrete logarithm problems (ECDLPs). The mentioned tasks are widely used in TLS, SSH or IPsec cryptographic applications of Internet/Intranet and IIoT/IoT networks, communication protocols based on Diffie–Hellman key agreements (dependent on the strength of the DLP or ECDLP), digital signature algorithms (DSA, ECDSA, RSA-PSS), public key encryption algorithms (El Gamal, RSA-OAEP), etc. In other words, Shor's quantum algorithm is potentially capable of violating these algorithms, and with them all the mechanisms of public-key cryptography deployed in cyberspace.
The advent of quantum computing poses an existential threat to classical cryptographic systems. Shor’s algorithm (1994) can factor large integers and compute discrete logarithms in polynomial time, breaking widely used schemes like RSA, ECC, and Diffie-Hellman. This paper surveys the state-of-the-art in quantum cryptanalysis, examining its impact on symmetric and asymmetric cryptography, recent progress in quantum attacks, and defenses via post-quantum cryptography (PQC). We analyze key quantum algorithms (Shor’s, Grover’s), their real-world feasibility given current hardware (NISQ-era limitations), and emerging PQC standards (NIST’s CRYSTALS-Kyber, Dilithium). We also discuss novel attack vectors (e.g., hybrid quantum-classical cryptanalysis) and future research directions.
The defense of public key cryptography (PKC) lies in computational issues like the difficulty of factorizing enormous prime numbers and the discrete logarithm calculations. Such kinds of algorithms are called one-way functions because although it is straightforward to compute output given input, it is difficult to compute input if output is given. It is expected that such numerical or computational issues which are utilized in current cryptographic plans are difficult to address for an adversary utilizing present PCs. Yet, many organizations are attempting to assemble a high-powered quantum PC and in the future quantum PCs will be available for business use. Traditional asymmetric cryptographic algorithms are not secure against strong quantum machines. Shor’s algorithm running on a powerful quantum PC is able to solve integer factorization problems and discrete logarithm problems in polynomial time. So, asymmetric algorithms that are used today, like RSA, DSA and Diffie-Hellman will become insecure. Similarly, Grover’s algorithm running on a powerful quantum computer poses a serious threat to symmetric key algorithms which uses small key size. There is a need to work on alternate algorithms to resist quantum threat. NIST has already started with a process for the standardization of algorithms which are known as post-quantum cryptography (PQC) algorithms. Specialists globally are exploring progress toward post-quantum cryptography.
The aim of this thesis is to study quantum computers and their impact on public-key cryptography. Crucial part of the work is dedicated to theoretical basis and definitions necessary for understanding the basic principles of quantum computers. The further chapters describe Shor's algorithm, explain the part of integer factoring problem in the security of current public key cryptographic algorithms, and show how to break the most widely used assymetric algorithm RSA by means of effective factoring. Last chapter provides comparison of classical factoring algorithms with Shors algorithm, mentions cryptography resistant to quantum computer attacks and discusses the current state of development in the field of qunatum computing. The conclusion summarizes both potential and real impact of quantum computers on public-key cryptography.