Shor's Algorithm: Why Quantum Computers Threaten RSA and ECC

In 1994, mathematician Peter Shor developed an algorithm that would eventually threaten the foundation of internet security. Shor's algorithm can efficiently solve the mathematical problems underlying RSA and elliptic curve cryptography—problems that classical computers find practically impossible.

The Mathematical Foundation

RSA's security relies on the difficulty of factoring large numbers. Given two large prime numbers p and q, it's easy to compute their product N = p × q. But given only N, finding p and q is extraordinarily difficult for classical computers.

Similarly, elliptic curve cryptography relies on the discrete logarithm problem in elliptic curve groups—another problem that classical computers struggle with.

How Shor's Algorithm Works

Shor's algorithm exploits quantum mechanics to find the period of modular exponentiation functions, which can then be used to factor numbers. The key steps are:

• Superposition: A quantum computer can evaluate a function on all possible inputs simultaneously
• Quantum Fourier Transform: Extracts periodicity information from the quantum state
• Classical post-processing: Uses the period to find factors via the greatest common divisor

Requirements for Running Shor's Algorithm

Breaking RSA-2048 with Shor's algorithm requires:

• Approximately 4,000 error-corrected logical qubits
• Millions of physical qubits (due to error correction overhead)
• Stable coherence for the duration of the computation
• High-fidelity quantum gates

Current quantum computers have ~1,000-1,500 physical qubits with high error rates. We're not there yet—but progress is steady.

Impact on Different Cryptographic Schemes

Shor's algorithm affects public-key cryptography differently:

• RSA: Completely broken (factoring)
• Diffie-Hellman: Completely broken (discrete log)
• ECC/ECDSA: Completely broken (elliptic curve discrete log)
• AES (symmetric): Key size effectively halved by Grover's algorithm—AES-256 remains secure
• SHA-256 (hashing): Output size effectively halved—SHA-256 remains secure

The threat is specifically to public-key cryptography, not symmetric encryption or hashing.

Timeline Considerations

While large-scale quantum computers don't exist yet, several factors accelerate the threat:

• Continuous hardware improvements from IBM, Google, IonQ, and others
• New error correction techniques reducing qubit overhead
• Alternative computing approaches (photonic, topological) may leapfrog current limitations
• Unknown classified developments by nation-states

Why This Matters Now

Even if quantum computers capable of running Shor's algorithm are 10-15 years away:

• Data encrypted today can be harvested and decrypted later
• Cryptographic migrations take years to complete
• Standards and compliance requirements are emerging now
• Being proactive is less expensive than being reactive

The Post-Quantum Solution

Post-quantum cryptographic algorithms (Kyber, Dilithium, etc.) are designed to resist Shor's algorithm. They're based on mathematical problems—like lattice problems—that remain difficult even for quantum computers.

Shor's algorithm represents an existential threat to current internet security. Understanding this threat is the first step toward addressing it with quantum-resistant alternatives.