THE SECURITY OF ELLIPTIC CURVE CRYPTOSYSTEMS IS BASED IN THE INTRACTABILITY OF THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM. THE BEST CLASSICAL ALGORITHM KNOWN UNTIL DQTE TO SOLVE THIS PROBLEM IS FULLY EXPONENTIAL IN TIME. THIS IS THE REASON WHY THE ELLIPTIC CURVE PUBLIC KEY CRYPTOGRAPHY IS CONSIDERED THE MOST SECURE KNOWN UNTIL DATE. WE PRESENT IN THIS PAPER AN ALGORITHM THAT RUNNING ON A QUANTUM COMPUTER, CAN SOLVE IN POLYNOMIAL TIME THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM. THEN, IF A FUNCTIONAL QUANTUM COMPUTER ISEVER BUILD, ALL THE ELLIPTIC CURVE CRYPTOSYSTEMS WOULD BECOME INSECURE.
THE SECURITY OF ELLIPTIC CURVE CRYPTOSYSTEMS IS BASED IN THE INTRACTABILITY OF THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM. THE BEST CLASSICAL ALGORITHM KNOWN UNTIL DQTE TO SOLVE THIS PROBLEM IS FULLY EXPONENTIAL IN TIME. THIS IS THE REASON WHY THE ELLIPTIC CURVE PUBLIC KEY CRYPTOGRAPHY IS CONSIDERED THE MOST SECURE KNOWN UNTIL DATE. WE PRESENT IN THIS PAPER AN ALGORITHM THAT RUNNING ON A QUANTUM COMPUTER, CAN SOLVE IN POLYNOMIAL TIME THE ELLIPTIC CURVE DISCRETE LOGARITHM PROBLEM. THEN, IF A FUNCTIONAL QUANTUM COMPUTER ISEVER BUILD, ALL THE ELLIPTIC CURVE CRYPTOSYSTEMS WOULD BECOME INSECURE.
Computer security in a post-quantum world is a topic of great significance. The security of a vast number of public key encryption and key distribution techniques is dependent upon various number theoretic frameworks such as factoring, discrete logarithms and elliptic curves. Yet, variations on Shor’s algorithm have provided a theoretical basis for rendering such systems vulnerable to quantum attacks. In this work, we review quantum solutions for typical number theoretic problems. After leading up to elliptic curve systems, we highlight the relevance of computing modular inverses. Finally, refinements to quantum versions of the extended Euclidean algorithm are presented.
This article analyzes the threats to the security of modern cryptographic systems posed by the development of quantum computers, as well as the emergence of the concept of post-quantum cryptography as a solution to these problems. The study demonstrates that classical public-key cryptosystems, particularly RSA, DSA, and elliptic curve-based algorithms, can be broken using quantum algorithms. At the same time, new cryptographic systems based on hash functions, codes, lattices, and multivariate quadratic equations are considered a promising direction. The main challenges related to the efficiency, reliability, and applicability of post-quantum cryptography are also highlighted. As a result, the necessity of developing new cryptographic standards to ensure future information security is demonstrated.
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.
We show in some detail how to implement Shor's efficient quantum algorithm for discrete logarithms for the particular case of elliptic curve groups. It turns out that for this problem a smaller quantum computer can solve problems further beyond current computing than for integer factorisation. A 160 bit elliptic curve cryptographic key could be broken on a quantum computer using around 1000 qubits while factoring the security-wise equivalent 1024 bit RSA modulus would require about 2000 qubits. In this paper we only consider elliptic curves over GF(p) and not yet the equally important ones over GF(2^n) or other finite fields. The main technical difficulty is to implement Euclid's gcd algorithm to compute multiplicative inverses modulo p. As the runtime of Euclid's algorithm depends on the input, one difficulty encountered is the ``quantum halting problem''.
With the rise of quantum computing, traditional cryptographic algorithms, such as the Elliptic Curve Digital Signature Algorithm (ECDSA), face potential vulnerabilities. Quantum computers could efficiently solve problems that are currently computationally infeasible for classical computers, thus threatening the security of cryptographic systems. As a result, there is a pressing need to develop quantum- resistant cryptographic algorithms to ensure secure communication in a future where quantum computing is prevalent. ECDSA, widely used for securing digital communications, relies on elliptic curve cryptography to provide robust security through digital signatures. However, the advent of quantum computing poses a significant threat to ECDSA's security, as quantum algorithms such as Shor's algorithm could break the elliptic curve-based encryption by efficiently solving discrete logarithm problems. To address this issue, we propose a quantum-resistant cryptographic algorithm based on lattice-based cryptography. Our approach utilizes the Learning With Errors (LWE) problem, known for its resistance to quantum attacks. We implement the proposed algorithm and compare its performance with ECDSA in terms of key generation time, signing time, and verification time. The algorithm's security is analyzed against quantum attacks using theoretical and empirical methods. The experimental results demonstrate that the quantum-resistant algorithm provides a comparable level of security to ECDSA while offering significant advantages in the context of quantum resistance. Specifically, our quantum-resistant algorithm achieved key generation times of 120 ms, signing times of 150 ms, and verification times of 100 ms. In comparison, ECDSA showed key generation times of 80 ms, signing times of 90 ms, and verification times of 70 ms. Despite these performance trade-offs, the quantum resistance of the proposed algorithm ensures future-proof security for digital communications.