Shor’s Algorithm: Why It Threatens RSA

To understand why Shor’s Algorithm keeps cybersecurity experts up at night, we have to look at the intersection of classical number theory and quantum weirdness.

At its core, the threat boils down to a single mathematical truth: it is incredibly easy to multiply two numbers together, but incredibly difficult to do the reverse.

The Classical Shield: Why RSA Works

The RSA (Rivest–Shamir–Adleman) encryption algorithm is the backbone of secure internet communication, protecting everything from credit card transactions to top-secret government data.

RSA relies on prime factorization.

  • If given two large prime numbers, p and q, you can multiply them instantly to get a massive composite number, N.

Example: 61 × 53 = 3233

  • But if given you N and ask you to find p and q, a classical computer has to guess and check.

Now given, 3233 and asked, what two prime numbers were multiplied together?

You would eventually discover 61 × 53 but you must search for the correct factors.

For a 2048-bit number (the current standard for RSA), N is a number that is hundreds of digits long. Finding its prime factors using the best known classical algorithm (the General Number Field Sieve) would take a conventional supercomputer billions of years, longer than the age of the universe. Because the math is so lopsided, our data is safe.

Why does factoring matter?

RSA generates two keys: Public Key and Private Key

Everyone can know the public key, only the owner knows the private key. The private key is mathematically linked to the two secret prime numbers used when creating the key. If someone factors the large RSA number into its original primes, they can compute the private key.

Once they have the private key, they can:

  • read encrypted messages
  • impersonate the owner
  • forge digital signatures
  • decrypt confidential information

This is why factoring is so important.

Why can’t today’s computers factor huge numbers?

The best classical algorithms become extremely slow as the numbers grow larger. Even supercomputers require enormous amounts of time for sufficiently large RSA keys. The difficulty increases rapidly because the number of possible factors becomes unimaginably large. This is why RSA has remained secure for decades.

The Quantum Cheat Code: Enter Peter Shor

In 1994, a mathematician named Peter Shor published a quantum algorithm that changed everything. Shor’s Algorithm proves that a sufficiently powerful quantum computer could factor these massive numbers not in billions of years, but in seconds or minutes.

Shor’s Algorithm achieves this by turning a factoring problem into a period-finding (or repetition-finding) problem.

How the Math Shifts:

  1. The Clock Problem: In number theory, if you take a number and repeatedly multiply it by itself modulo N, the sequence of answers will eventually start repeating in a periodic cycle.
  2. The Hidden Period: Finding the length of this period (let’s call it r) happens to be the secret key to unlocking the prime factors of N.
  3. The Classical Wall: For massive numbers, finding r is just as hard for a classical computer as factoring N directly. It has to check the sequence step-by-step.

The Quantum Superpower: Quantum Fourier Transform

This is where classical computers fail and quantum computers excel. A quantum computer doesn’t check the sequence one by one. Instead, it uses two quantum principles: superposition and interference.

  • Superposition: The quantum computer places its qubits into a state where they represent all possible steps of the sequence at the exact same time.
  • Quantum Fourier Transform (QFT): This is the crown jewel of Shor’s Algorithm. Think of QFT like a prism that separates a beam of light into its individual colors. QFT processes the superposition of all those sequence steps and uses constructive interference to amplify the correct period (r) while using destructive interference to cancel out all the wrong answers.

When you measure the qubits, the wrong answers have vanished, and the correct period r pops out with near-perfect probability. Once a quantum computer has r, a simple classical calculator can plug it into a standard formula to instantly reveal the prime factors p and q.

Exponential Speedup: Changing the Rules of Time

Mathematically, the difference in speed is staggering.

High-level steps of Shor’s Algorithm

Although the underlying mathematics is advanced, the overall workflow is straightforward:

Step 1

Choose the large number you want to factor.

Step 2

Select a random number related to it.

Step 3

Create a mathematical function that repeats after some unknown interval.

Step 4

Run the quantum computer to determine the repetition interval (the period).

Step 5

Use ordinary classical mathematics to convert the period into the original prime factors.

Step 6

Recover the RSA private key.

Why Haven’t We Broken the Internet Yet?

If Shor’s Algorithm was written in 1994, why are we still using RSA today?

Because of the hardware bottleneck. To run Shor’s Algorithm on RSA-2048, a quantum computer needs several thousand logical qubits. However, because today’s quantum hardware is noisy and prone to errors, we need thousands of physical qubits to create just one error-corrected logical qubit. In total, breaking RSA requires a machine with millions of physical qubits. Right now, the world’s most advanced quantum processors have around a few thousand physical, noisy qubits. We are still years away from the scale required to execute Shor’s Algorithm on real-world encryption.

The “Store Now, Decrypt Later” Threat: Even though the hardware doesn’t exist yet, malicious actors are actively intercepting and archiving encrypted data today. When a powerful enough quantum computer is built, they will be able to retroactively decrypt decades of stolen data.

This is why the cybersecurity world is currently transitioning to Post-Quantum Cryptography (PQC) – new encryption methods built on mathematical problems (like lattice-based cryptography) that neither classical nor quantum computers can easily solve.

Does Shor’s Algorithm affect all encryption?

No, Shor’s Algorithm mainly threatens public-key cryptography based on integer factorization or related mathematical problems.

Examples include:

  • RSA
  • many forms of Diffie–Hellman key exchange
  • Elliptic Curve Cryptography (ECC)

It does not directly break most symmetric encryption algorithms such as Advanced Encryption Standard. Those are affected differently by quantum computing, primarily through Lov Grover‘s algorithm, which offers a much smaller (quadratic rather than exponential) speedup.

All articles