RSA Is a Math Problem — And Quantum Computers Solve It

The Trillion-Dollar Math Problem

RSA encryption — used by your bank, your email, and most of the internet — is secure because factoring large numbers takes classical computers billions of years. A quantum computer running Shor's algorithm could do it in hours. In 2024, approximately 90% of TLS/SSL-encrypted web traffic still relies on RSA or RSA-hybrid cryptosystems, protecting an estimated $44 trillion in annual global e-commerce. The entire digital economy sits on a single mathematical assumption: that no efficient classical algorithm exists for integer factorization. But what happens when a new computational paradigm renders that assumption obsolete?

Here's the uncomfortable reality: we already know the algorithm that breaks RSA. Peter Shor discovered it in 1994. The only thing protecting us is hardware — specifically, the fact that no quantum computer yet exists with enough stable qubits to run it. But quantum hardware is advancing at a compounded annual growth rate exceeding 100% in logical qubit capacity. The question isn't whether RSA will fall; it's whether we'll have migrated to post-quantum cryptography before it does.

How RSA Actually Works: The Mathematics of Trust

At its core, RSA is surprisingly elegant. The security rests on three mathematical operations that are easy to perform but seemingly impossible to reverse:

Key Generation:

1. Select two prime numbers, p and q (each 1024+ bits for RSA-2048)
2. Compute n = p × q (the modulus, 2048 bits total)
3. Compute Euler's totient: φ(n) = (p-1)(q-1)
4. Choose public exponent e (commonly 65537)
5. Compute private exponent d where d × e ≡ 1 (mod φ(n))

The public key is (n, e). The private key is d. Anyone can encrypt a message m by computing c = m^e mod n. Only the private key holder can decrypt by computing m = c^d mod n.

[!INSIGHT] The asymmetry is everything: multiplying two primes is O(n²) complexity, but the best known classical factoring algorithm — the General Number Field Sieve (GNFS) — runs in sub-exponential time: O(exp(1.923 × (ln n)^(1/3) × (ln ln n)^(2/3))). For RSA-2048, this translates to approximately 2^112 operations, requiring billions of years on classical hardware.

Why Factoring Breaks Everything

If an attacker can factor n back into p and q, they can immediately compute φ(n) and derive the private key d. The encryption becomes worthless. Every secret ever encrypted with that key — past, present, or future — becomes readable.

For RSA-2048, here's what classical computers face:

The numbers are almost incomprehensible. They're why we trust RSA with nuclear launch codes, billion-dollar wire transfers, and state secrets.

Shor's Algorithm: The Polynomial-Time Killer

In 1994, Bell Labs mathematician Peter Shor published a paper that sent shockwaves through the cryptography community. He demonstrated that a sufficiently powerful quantum computer could factor integers in polynomial time — specifically, O((log n)³) — transforming an impossible problem into a tractable one.

The Quantum Advantage

Shor's algorithm exploits two quantum phenomena:

1. Quantum Superposition: A quantum register can simultaneously represent all possible values. For factoring n, the algorithm creates a superposition of all integers from 1 to n, then computes a function across all of them at once.

2. Quantum Fourier Transform (QFT): The critical insight is that factoring reduces to finding the period of a function. The QFT can extract periodicity from a quantum superposition exponentially faster than any classical approach.

The algorithm proceeds in these stages:

1. Pick a random a < n
2. Find the period r of f(x) = a^x mod n using QFT
3. If r is even and a^(r/2) ≠ -1 (mod n), compute gcd(a^(r/2) ± 1, n)
4. Result: One of these GCDs yields a prime factor of n

[!INSIGHT] The quantum speedup comes entirely from step 2. Classically, finding the period requires O(n) evaluations. Quantum computers using QFT accomplish this in O((log n)²) quantum gate operations — an exponential improvement. For RSA-2048, this means ~2^40 operations instead of ~2^112.

Resource Requirements to Break RSA-2048

Current estimates for running Shor's algorithm on RSA-2048 vary, but a 2024 analysis by Gidney and Ekera suggests:

• Logical Qubits: ~4,000 (with error correction)
• Physical Qubits: 20-400 million (depending on error rates and architecture)
• Circuit Depth: ~10^11 T-gates
• Runtime: Hours to days (not billions of years)

[!NOTE] IBM's Condor processor (2023) achieved 1,121 qubits, and Google's error-corrected logical qubit demonstrations show rapid progress. While we're not at 4,000 logical qubits yet, the trajectory is clear. The National Institute of Standards and Technology (NIST) estimates a 50% probability of quantum computers breaking RSA-2048 by 2030.

The Harvest Now, Decrypt Later Threat

Here's what keeps CISOs awake at night: adversaries don't need to wait for quantum computers to start stealing secrets. They can collect encrypted data today — diplomatic communications, trade secrets, medical records — and store it until quantum decryption becomes viable.

This "harvest now, decrypt later" strategy means the quantum threat isn't future-tense — it's present-tense. Any data with long-term confidentiality requirements encrypted today under RSA is already at risk.

The Migration Challenge

Migrating to post-quantum cryptography (PQC) is not trivial:

1. NIST standardization of PQC algorithms (CRYSTALS-Kyber, CRYSTALS-Dilithium) completed in 2024, but implementation is slow
2. Performance overhead: PQC algorithms have larger key sizes and higher computational costs
3. Legacy systems: Billions of devices need updates, many unsupported
4. Hybrid approaches: Running classical and PQC in parallel during transition

Implications: The Cryptographic Cliff Edge

The transition from RSA to post-quantum cryptography represents one of the most complex technological migrations in history. Unlike Y2K, which had a fixed deadline, the quantum deadline is uncertain — but the consequences of missing it are catastrophic.

Financial institutions face particular urgency. SWIFT messaging, interbank transfers, and digital signature systems overwhelmingly rely on RSA. The Banking Industry Technology Secretariat estimates that full PQC migration for the global financial sector will take 8-12 years — longer than many expert estimates for quantum decryption capability.

Governments are also racing. The U.S. National Security Agency announced in 2015 that it would begin moving to quantum-resistant algorithms, with a target completion date of 2030. China has invested over $10 billion in quantum research, including the Micius satellite for quantum key distribution — a fundamentally different approach to secure communication.

[!NOTE] Quantum Key Distribution (QKD) offers theoretically unconditional security based on quantum mechanics rather than computational hardness. However, QKD requires dedicated hardware, limits distance, and cannot replace public-key cryptography for most applications. It's a complement to PQC, not a replacement.

Conclusion

RSA's security has always been provisional — a bet that computational limits would outlast our secrets. Shor's algorithm turned that bet into a countdown timer.

The mathematics is unambiguous: given enough stable qubits, RSA-2048 falls in hours. The engineering challenge — building those qubits — is substantial but progressing rapidly. The only questions are timeline and preparedness.

Sources: Shor, P.W. (1994). "Algorithms for quantum computation: discrete logarithms and factoring." FOCS '94; Gidney, C. & Ekera, M. (2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits." Quantum; NIST Post-Quantum Cryptography Standardization (2024); IBM Quantum Roadmap (2024); Mosca, M. (2018). "Cybersecurity in an era of quantum computing." Computer.