Shor’s Algorithm and RSA Encryption
By Louise E. Turner
RSA Basics
The biggest quantum threat to cyber security is the possibility of a powerful quantum computer breaking RSA encryption. RSA encryption is a widely utilized encryption algorithm that is used to begin over 90% of internet connections during the SSL handshake (Forbes). For years, RSA was thought to be computationally unbreakable, so why do experts believe that a quantum computer could change that?
The Rivest-Shamir-Adleman (RSA) encryption algorithm is an asymmetric encryption algorithm that functions based on prime factorization. The term “asymmetric” means that both a public key and private key are used in the encryption and decryption process. The sender encrypts the message with a publicly known key and that message can only be decrypted by the receiver's private key. In the case of RSA encryption, the sender will encrypt their message using the product of two very large prime numbers. This product is the public key that is known to everyone. The receiver will decrypt that message using the private key that only they know: the two prime numbers that were multiplied together.
When multiplying two small prime numbers together, finding the prime factors of the public key isn’t very difficult. This is shown for the number 72:
What makes RSA so secure is that the public keys can end up being 617 decimal digits long! Numbers this large are computationally impossible for a classical computer to find the prime factors of.
Shor’s Algorithm
In 1994, mathematician Peter Shor developed a quantum factoring algorithm that, when executed by a powerful enough quantum computer, could theoretically break RSA encryption. Shor’s algorithm relies heavily on the Quantum Fourier Transform (QFT). A classical Fourier Transform can be used to dissect waveforms into their own “recipes” that contain the waves used to create the final combination of waves (Better Explained). Fourier Transforms are used to pick out trouble frequencies to be cancelled out by noise cancelling headphones.
In Shor’s algorithm a random “bad guess” number g will be used to find potential factors of the public key N. if g ends up finding potential factors, then Euclid's algorithm is used to the greatest common divisor of those potential factors. If g does not produce potential factors, then a different g is tested until the correct prime factors are found. Although these steps can be completed on a classical computer for small numbers, when we get into the realm of 617 decimal digits, calculations start to slow down significantly. The QFT uses the aspects of Fourier Transforms to find the period of a function related to g.
In other words, Shor’s Algorithm uses QFTs to find repeating patterns in the factors tested. Finding these patterns is essential to finding the true prime factors of the public key in a feasible human time (Veritasium). Although there is more complex math behind Shor’s algorithm, this high-level look should be sufficient to prove its importance.
Is Shor’s Algorithm Feasible?
Although Shor’s algorithm is incredibly powerful, RSA has not been broken yet due to the current hardware restrictions of quantum computers. To date, Shor’s algorithm has only been used with a quantum computer to successfully factor the number 15 into its prime factors of 3 and 5. This was accomplished by IBM in 2001 on a 7-qubit quantum computer and was an impressive feat for its time (IBM). As of 2024, the D-Wave Advantage quantum annealer has over 5000 qubits, so why haven’t we cracked RSA yet? The reason is not a matter of the quantity qubits but is a matter of stable qubits. Quantum computers are prone to noise and error, making them difficult to extract answers from. Although quantum computing has come a long way since 2001, a reliable way to construct vast amounts of stable qubits has not yet been devised.
Experts are conflicted regarding the timelines of quantum progression. Some believe that Shor’s algorithm will never be feasible, while others think it’s only a matter of years until RSA is broken. Regardless of feasibility and timeline, Shor’s algorithm is a great demonstration of quantum advantage, and the opportunities quantum computing provides us.