How Shor's Algorithm Breaks RSA and ECC Security
This article provides a direct look at why Shor’s quantum algorithm poses an existential threat to classical RSA and Elliptic Curve Cryptography (ECC). By examining the underlying mathematical problems that secure modern digital communications—specifically integer factorization and discrete logarithms—we will explore how quantum mechanics and the Quantum Fourier Transform enable Shor's algorithm to solve these problems exponentially faster than classical computers, effectively rendering current public-key encryption obsolete.
The Classical Mathematical Trapdoor
Modern public-key cryptography relies on "trapdoor" functions: mathematical problems that are easy to compute in one direction but practically impossible to reverse without a secret key.
- RSA Encryption relies on the integer factorization problem. Multiplying two massive prime numbers together to create a public key takes a classical computer milliseconds. However, taking that resulting product and factoring it back into the original two prime numbers takes classical supercomputers thousands of years.
- Elliptic Curve Cryptography (ECC) relies on the discrete logarithm problem. It is easy to take a base point on an elliptic curve and add it to itself a secret number of times to reach a final point. It is computationally infeasible for a classical computer to look at the starting point and final point and figure out how many times the point was added to itself.
Classical computers fail to break these systems because they must process guesses sequentially. Even with advanced classical shortcuts, the time required grows exponentially as the key size increases.
Reducing Cryptography to a Period-Finding Problem
In 1994, mathematician Peter Shor proved that both integer factorization and the discrete logarithm problem can be mathematically reframed into a single, different problem: finding the period of a periodic function.
In mathematics, a periodic function is one that repeats its values in regular intervals or cycles. Modular arithmetic—often referred to as "clock math," where numbers wrap around after reaching a certain value—is naturally periodic.
Shor demonstrated that if you take a random number, raise it to consecutive powers, and divide it by the RSA public key (or apply it to an elliptic curve group), the remainders will eventually fall into a repeating cycle. The length of this cycle is the "period." If you can find the period of this function, you can use basic algebra on a standard computer to instantly deduce the prime factors of an RSA key or the discrete logarithm of an ECC key.
While finding this period is just as hard as factoring for a classical computer, it is remarkably easy for a quantum computer.
Quantum Superposition and Parallelism
The first quantum mechanical advantage Shor's algorithm uses is superposition. Unlike classical bits, which must be either a 0 or a 1, quantum bits (qubits) can exist in a linear combination of both 0 and 1 simultaneously.
When Shor's algorithm begins, it places a register of qubits into an equal superposition of all possible states. This allows the quantum computer to input millions of different values into the modular math function at the exact same time. Through a process called quantum parallelism, the computer calculates the remainders for all these inputs in a single step, entangling the input values with their corresponding output remainders.
At this stage, the hidden period of the function is globally encoded within the quantum state of the system.
The Quantum Fourier Transform (QFT)
Having the answer encoded in a superposition is not enough. According to the laws of quantum mechanics, if you measure a quantum state in superposition, it immediately collapses into just one random input and output pair, destroying all the other information. Measuring the system at this point would yield no better results than guessing on a classical computer.
To extract the period without destroying it, Shor’s algorithm applies a mathematical operation called the Quantum Fourier Transform (QFT).
In classical math, a Fourier Transform takes a complex wave and breaks it down into the individual frequencies that make it up. The QFT does the exact same thing to the quantum wave function. Because qubits behave like waves, they have phases that can overlap and interact. The QFT manipulates these phases to trigger quantum interference:
- Destructive Interference: The probability waves of all the incorrect answers (values that do not correspond to the period) are shifted out of phase, causing them to cancel each other out.
- Constructive Interference: The probability waves that align with the true repeating period of the function are shifted into phase, amplifying each other.
The Collapse of RSA and ECC
Once the QFT has amplified the correct frequency and erased the wrong ones, the quantum computer measures the qubits. Because of the constructive interference, the measurement has an overwhelmingly high probability of collapsing onto a value that reveals the period of the function.
With the period found, the quantum portion of the algorithm is finished. A classical computer takes this period and applies Euclid's algorithm (a simple math equation known since 300 BC) to quickly calculate the exact prime factors for RSA, or the private scalar value for ECC.
What makes this particularly devastating is how efficiently the math scales. While classical algorithms require exponentially more time as encryption keys get larger, Shor's algorithm runs in "polynomial time." This means that increasing the size of an RSA or ECC key only slightly increases the time a quantum computer needs to break it. Ironically, because ECC uses smaller key sizes than RSA to achieve the same level of classical security, ECC is actually more vulnerable to Shor's algorithm, requiring fewer qubits to break than RSA.