Shor's Algorithm: How a Quantum Computer Actually Breaks RSA

What is Shor's algorithm?

Shor's algorithm is a quantum algorithm, published by mathematician Peter Shor in 1994, that can factor large numbers exponentially faster than any known classical method. That single capability is the entire reason quantum computers threaten modern encryption. RSA and elliptic-curve cryptography rest on the assumption that certain math problems (factoring large numbers, computing discrete logarithms) are effectively impossible to solve at scale. Shor's algorithm dissolves that assumption on a sufficiently powerful quantum computer.

Understanding it in plain terms helps enterprise leaders see why "quantum-safe" is a genuine mathematical necessity, not a vendor slogan. The threat is not that quantum computers are "faster computers": it is that one specific algorithm exploits quantum physics to solve the exact problems our security depends on being unsolvable.

Why is RSA secure today?

RSA's security depends on a simple asymmetry. Multiplying two large prime numbers together is easy: any computer does it instantly. But working backward from the product to recover those original primes, factoring, is astronomically hard for classical computers. A 2048-bit RSA key would take conventional machines longer than the age of the universe to factor by brute force. That gap between easy-forward and impossible-backward is the whole foundation of the security, and elliptic-curve cryptography relies on a similar one-way hardness in the discrete-logarithm problem.

For decades, that asymmetry has been rock-solid, because no efficient classical factoring method exists. The trust the entire internet places in RSA and ECC rests on it.

How does Shor's algorithm break that?

Shor's algorithm changes the game by using quantum mechanics (specifically superposition and interference) to find hidden periodic structure in the mathematics of factoring. Rather than trying candidate factors one by one, it transforms factoring into a problem of finding a repeating pattern (a "period"), which a quantum computer can evaluate across enormous numbers of possibilities simultaneously and then amplify the right answer through interference.

The upshot is that what was practically impossible becomes tractable, given enough stable qubits. The same underlying approach solves the discrete-logarithm problem behind elliptic-curve cryptography. In other words, Shor's algorithm does not chip away at RSA and ECC: it targets the exact mathematical hardness they are built on, collapsing centuries of computing time into something achievable.

Does Shor's algorithm break all encryption?

No, and this distinction is critical to responding sensibly. Shor's algorithm targets public-key (asymmetric) cryptography: RSA, Diffie-Hellman, and ECC. It does not break symmetric encryption like AES the same way.

The impact varies by category. Public-key, or asymmetric, cryptography, including RSA, ECC, and Diffie-Hellman, is broken outright by Shor's algorithm. Symmetric cryptography such as AES-256 is only weakened by a different algorithm, Grover's, and remains safe at 256-bit key lengths. Hash functions such as SHA-256 and SHA-384 are only modestly weakened and remain manageable.

A separate quantum algorithm, Grover's, speeds up brute-forcing symmetric keys, but only quadratically, which is a far weaker effect. Doubling a symmetric key's length restores its security margin, which is why AES-256 remains considered quantum-safe. The urgent problem is the public-key cryptography Shor's algorithm shatters, because it underpins the key exchange and digital signatures used everywhere online.

What does Shor's algorithm mean for your enterprise?

It means the algorithms protecting your key exchanges and signatures have a defined expiry: the day a cryptographically relevant quantum computer can run Shor's algorithm at the scale needed for real keys. Everything RSA and ECC protect today (TLS sessions, VPNs, code signing, certificates, encrypted key exchange) needs a quantum-safe replacement. The NIST post-quantum standards exist precisely because Shor's algorithm makes the current public-key algorithms obsolete.

Because migration takes years and data is being harvested now, the practical response is to begin replacing public-key cryptography well before a quantum computer can run Shor's at the required scale, not to wait for the threat to materialize.

How close are we to Shor's algorithm breaking real keys?

Running Shor's algorithm against a 2048-bit RSA key requires thousands of error-corrected logical qubits, far beyond today's machines, which struggle with error rates and coherence. So the immediate risk of a working attack is low. But the trajectory, not the current gap, is what matters for planning, because migration itself is slow and the arrival of the capability is uncertain and possibly silent. Use the Mosca inequality to weigh your data's shelf-life and your migration time against that uncertain horizon: for long-lived data, the responsible conclusion is usually to start now.