Quantum computers will break RSA encryption not when they become universally powerful, but when they can reliably execute Shor’s algorithm for a specific key size.
Let’s see it in action. Imagine a 2048-bit RSA public key. This key is essentially a massive number, the product of two large prime numbers. Factoring this number back into its prime components is computationally infeasible for classical computers. But Shor’s algorithm, designed for quantum computers, can do this efficiently.
Here’s the core idea: Shor’s algorithm leverages quantum properties like superposition and entanglement to perform a specific mathematical operation called "period finding." For RSA, this period finding is applied to a mathematical function related to the public key. The result of this period finding directly reveals the prime factors of the public key, thus breaking the encryption.
The "when" hinges on two critical factors: the number of stable qubits and their coherence time.
- Number of Qubits: Shor’s algorithm, for a 2048-bit RSA key, requires approximately 4,098 logical qubits. These logical qubits must be error-corrected, meaning they are built from a much larger number of physical qubits. Estimates suggest that 10 million to 1 billion physical qubits might be needed for robust factoring of 2048-bit RSA. This is a massive leap from the hundreds of physical qubits available today.
- Coherence Time & Error Correction: Quantum states are fragile. Qubits lose their quantum properties (decohere) very quickly. To run Shor’s algorithm, qubits must maintain their state for long enough to complete the computation. This necessitates sophisticated quantum error correction codes. These codes use redundant physical qubits to protect a single logical qubit. The longer the computation, the more robust the error correction, and thus the more physical qubits required per logical qubit.
The actual process of breaking RSA with a quantum computer would look something like this:
- Initialization: The quantum computer is initialized with qubits in a superposition of all possible states.
- Quantum Fourier Transform (QFT): This is the heart of Shor’s algorithm. It’s a quantum operation that efficiently finds the period of a function.
- Measurement: The state of the qubits is measured. This measurement yields information about the period, which, through classical post-processing, reveals the prime factors of the RSA modulus.
- Classical Post-processing: The results from the QFT are fed into a classical algorithm (like the continued fractions algorithm) to deduce the prime factors.
The "breaking" isn’t a single event. It’s a race against time and error. A quantum computer must execute Shor’s algorithm for the specific key size before its qubits decohere or errors accumulate to an unrecoverable level.
The current state of quantum computing is focused on building these large, stable, and error-corrected quantum computers. Companies are experimenting with different qubit modalities: superconducting circuits, trapped ions, photonic systems, and topological qubits, each with its own strengths and weaknesses regarding scalability and error rates.
The most surprising true thing about breaking RSA is that it’s not a matter of brute-forcing the key space like classical computers do. Shor’s algorithm doesn’t try every possible factor. Instead, it cleverly transforms the factoring problem into a period-finding problem, which quantum computers excel at. This is why a relatively small number of qubits can, in theory, break keys that would take a classical supercomputer longer than the age of the universe to factor.
The immediate next step for those concerned about quantum threats is the transition to post-quantum cryptography (PQC).