How Shor’s Algorithm Threatens RSA: Quantum Steps to Break Encryption

RSA Encryption vs Shor’s Algorithm

RSA was once regarded as the most reliable encryption method, but Shor’s algorithm—based on quantum computing—demonstrates that RSA’s security can be broken by efficiently finding integer factors.

Instead of brute‑force attacks, Shor’s algorithm exploits quantum parallelism to determine the period of the function f(x) = m^x (mod N), which undermines the assumption that factoring large numbers is hard.

Why RSA Was Considered Strong

RSA’s strength lies in the difficulty of factoring a huge composite number. Multiplying two primes is easy, but extracting the prime factors from a large product is computationally intensive, which many modern security systems rely on.

Shor’s Five‑Step Hybrid Procedure

The algorithm consists of five steps, only one of which requires a quantum computer; the others can be performed classically.

Step 1: Use the classical greatest common divisor (GCD) algorithm (Euclidean algorithm) on a random integer m and the modulus N. If gcd(m, N) = 1, continue; otherwise a non‑trivial factor is found.

Step 2: Find the period P of the sequence m mod N, m^2 mod N, m^3 mod N, …. This step requires a quantum computer.

Step 3: If the period P is odd, return to Step 1 with a new random m. If P is even, proceed.

Step 4: Verify the period. If the verification succeeds, move to Step 5; otherwise restart from Step 1.

Step 5: Compute the factor from the period. The resulting non‑trivial factor of N breaks the RSA encryption.

Quantum Period Finding Details

To find the period, a quantum computer creates a superposition using a Hadamard gate, applies the modular exponentiation, and then performs a Quantum Fourier Transform (QFT). Measuring the quantum state yields an approximation of the period, which can be refined classically.

The QFT is crucial for many quantum algorithms; it does not speed up the classical Fourier transform but enables exponential‑time improvements for problems like integer factorization and discrete logarithms.

1. Apply Hadamard gate to create superposition
2. Perform modular exponentiation (quantum step)
3. Execute Quantum Fourier Transform

Impact on RSA Security

Even with larger key sizes, RSA remains vulnerable because a sufficiently powerful quantum computer can factor the modulus quickly. For example, breaking a 2048‑bit RSA key could take a traditional computer billions of years, but a quantum computer might accomplish it in about 100 seconds (Dr. Krysta Svore, Microsoft Research).

Further Reading

Quantum Computer Science

Quantum Information and Quantum Computation

NIST Quantum Zoo – a list of quantum algorithms

Reference sources: Medium, Vulture, FreeBuf (FreeBuf.COM)