We take a look at RSA encryption algorithm and what makes it secure. Some consideration is given to its current use, showing that it plays an important role in ensuring privacy on the Internet. A way of factoring large numbers with Shor’s factorization algorithm is given, as well as a shortcut to directly breaking RSA. Next, we present basics of some of the implementations, their drawbacks and make an estimation of how long will our RSA keys remain safe.
We take a look at RSA encryption algorithm and what makes it secure. Some consideration is given to its current use, showing that it plays an important role in ensuring privacy on the Internet. A way of factoring large numbers with Shor’s factorization algorithm is given, as well as a shortcut to directly breaking RSA. Next, we present basics of some of the implementations, their drawbacks and make an estimation of how long will our RSA keys remain safe.
Abstract This chapter sets the background for the famous Shor algorithm that can allow a sufficiently powerful quantum computer to easily break the current classical RSA encryption method. The RSA algorithm relies on the impossibility of even the most powerful classical computers to factor large numbers in any practical length of time. Before going through the details of the RSA encryption method, the number theory of the modulus or mod function is explained with many examples including exponential ones. The connection between factoring and the periodicity of mod functions is emphasized because it is needed for the RSA and Shor algorithms. The in-depth explanation of the RSA algorithm makes use of number theory to explain how the encryption key can be made public while other information is kept secret to ensure secure communication.
Abstract This chapter is the most formidable in the book, but it provides a deep and complete understanding of the classic Shor factoring algorithm. Alice and Bob set the context for the algorithm by explaining how the difficulty of factoring large numbers plays a critical role in securing encrypted communications channels, using RSA encryption as an example. The Shor algorithm, if implemented on a sufficiently large quantum computer, could defeat those encryption schemes by finding those factors relatively quickly, a task that would take years or more on even the fastest classical supercomputers. Alice and Bob lead us through some number theory to establish the connection between factoring and finding the period of a periodic function. They then show how the clever use of quantum algorithms—this is Shor’s main contribution—leads to a fast way to find the required period using quantum Fourier transforms.
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.
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.
This dissertation analyzes the impact of quantum computing on the security of classical cryptographic systems, with a focus on the vulnerability of the RSA algorithm. RSA cryptography is based on the difficulty of factoring large prime numbers, a task considered computationally very difficulty for classical computers. However, with quantum computing, especially through Shor’s algorithm—this barrier can be overcome. Shor’s algorithm allows factorization in polynomial time, which would completely compromise the security of RSA.The dissertation presents the theoretical foundations of both cryptography and quantum computing, explaining key concepts such as qubits, superposition, entanglement, and quantum parallelism. It details the operation of Shor’s algorithm, from identifying the period of the modular exponential function to applying the Quantum Fourier Transform (QFT) and phase estimation to obtain the prime factors of a composite number.In addition to the theoretical component, the work includes practical implementations of the algorithm in both classical and simulated quantum environments, using IBM’s Qiskit library. Finally, it discusses post-quantum cryptography as a secure alternative in light of technological advancements, highlighting methods based on lattices, codes, hash functions, and multivariate systems.The conclusion emphasizes the urgency of adopting cryptographic systems resistant to quantum computing, as ongoing advances increasingly make the breaking of RSA a realistic threat. Post-quantum cryptography is mentioned as a necessary response to the challenge posed by quantum computing.In conclusion, although current quantum computers do not yet have sufficient power to break RSA in practice, technological progress is steadily bringing that scenario closer. Therefore, it is essential to develop and adopt quantum-resistant cryptographic systems to ensure information security in the coming decades.