This chapter evaluates the stability of the modern cryptographic algorithms to clarify the tasks of cryptanalysis of asymmetric encryption schemes and digital signature based on factorization and discrete logarithm problems in various algebraic structures in a quantum computing model. It considers the features of modeling quantum cryptanalysis algorithms on a quantum scheme, and shows the differences between these algorithms and classical algorithms. The quantum algorithm is performed by implementing a series of sequential unitary operations. Grover's algorithm provides a quadratic increase in speed, while some other quantum algorithms, for example, the Shor factorization algorithm, give an exponential gain compared to the corresponding classical algorithms. Grover's algorithm is modified into an algorithm for recovering the symmetric encryption key from the message text and ciphertext. The stability of the RSA asymmetric encryption system is based on the super-polynomial computational complexity of factorization of natural numbers. However, there is a quantum algorithm whose complexity is polynomial.
This chapter evaluates the stability of the modern cryptographic algorithms to clarify the tasks of cryptanalysis of asymmetric encryption schemes and digital signature based on factorization and discrete logarithm problems in various algebraic structures in a quantum computing model. It considers the features of modeling quantum cryptanalysis algorithms on a quantum scheme, and shows the differences between these algorithms and classical algorithms. The quantum algorithm is performed by implementing a series of sequential unitary operations. Grover's algorithm provides a quadratic increase in speed, while some other quantum algorithms, for example, the Shor factorization algorithm, give an exponential gain compared to the corresponding classical algorithms. Grover's algorithm is modified into an algorithm for recovering the symmetric encryption key from the message text and ciphertext. The stability of the RSA asymmetric encryption system is based on the super-polynomial computational complexity of factorization of natural numbers. However, there is a quantum algorithm whose complexity is polynomial.
In quantum cryptanalysis, Shor's algorithm provides exponential acceleration of solving factorization problems, discrete logarithm problem, and elliptic curve discrete logarithm problems, widely used in cryptographic applications in cyberspace. Shor's quantum algorithm can potentially crack most protocols and schemes of asymmetric encryption (public key cryptography). In general, all known quantum algorithms can be divided into two groups: providing exponential gain (for example, Shor's algorithm) and providing quadratic gain (for example, Grover's algorithm). Particular attention is paid to the Shor quantum algorithm and other polynomial algorithms capable of solving cryptanalysis problems with the required reliability and complexity in polynomial time. For quantum computing, all cryptographies are divided into quantum-secure and quantum-insecure. Algorithms and cryptosystems of symmetric encryption are attributed to quantum-secure but with at least twice the key length increased. This chapter presents an overview of the concepts discussed in the subsequent chapters of this book.
Purpose of the article: development of quantum algorithms for efficient solution of cryptanalysis problems of asymmetric encryption schemes (RSA, ElGamal) and digital signature (DSA, ECDSA or RSA-PSS), based on computationally difficult problems of factorization and discrete logarithm.Research methods: Methods of quantum cryptanalysis based on the algorithms of Shor, Grover, Simon, etc.Results: algorithms for solving problems of quantum cryptanalysis of two-key cryptography schemes in polynomial time.Practical relevance: consists in developing a solution for computationally difficult problems of factorization and discrete logarithm in polynomial time, taking into account the security of the discrete algorithm (DLP) and the discrete elliptic curve algorithm (ECDLP). The obtained scientific results formed the basis for the development of a special Software Development Kit, SDK for cryptanalysis “Kvant-K”. The Certificate of state registration of the computer program No. 2020665981 was received.
The advent of quantum computing presents a paradigm shift in the field of cryptanalysis, challenging the security of classical encryption schemes that underpin modern digital communications. This study explores the capabilities of quantum algorithms, particularly Shor's algorithm and Grover's algorithm, in undermining widely used cryptographic systems. Shor's algorithm poses a direct threat to publickey cryptosystems such as RSA and ECC by enabling efficient integer factorization and discrete logarithm computation, which are computationally infeasible for classical computers. Meanwhile, Grover's algorithm provides a quadratic speedup for bruteforce attacks on symmetric-key cryptosystems like AES, significantly reducing their effective security. Through theoretical analysis and simulation-based evaluation, this paper highlights the vulnerabilities of classical encryption in the face of quantum advances and underscores the urgent need for post-quantum cryptographic solutions. The findings emphasize the critical importance of transitioning to quantum-resistant algorithms to ensure long-term data confidentiality in a future dominated by quantum technologies.
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.
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 main trends of the science and technology development in the field of quantum physics and quantum calculations are considered in the paper. It has been shown that over the past few years plenty of new discoveries and achievements have been made in the field of quantum physics, all these events, anyway, had a great influence on the invention and production of quantum computers. Many communities around the world have been engaged in the development of quantum computers and some of them have achieved significant results in it by now.It is shown that using quantum algorithms of Shor and Grover, which can be fulfilled on a properly implemented quantum computer, can compromise some symmetric and asymmetric cryptosystems. The analysis results of endurance of the known block ciphers regarding the quantum cryptanalysis are given. It is also shown that some of them are not able to resist the quantum cryptanalysis method based on Grover's algorithm. The analysis of Shor's algorithm possibilities, which can significantly reduces computational costs for solving mathematical problems of endurance of modern asymmetric cryptoalgorithms, is given. Herewith, Shor's quantum algorithm diminishes the complexity of the cryptanalysis from exponential and subexponential to polynomial. In addition, the assessment of quantum computer resources is given in the paper, which are necessary for the quantum cryptanalysis concerning such cryptosystems as DSA, RSA, EC and NTRU.