Quantum computing and key breaking: evidence and implications

While practical quantum computers capable of breaking standard cryptographic keys like RSA-2048 are not yet available, significant theoretical and experimental advances underscore the feasibility and urgency of this threat. This article reviews the evidence supporting this claim, emphasizing the critical need for adopting post-quantum cryptography (PQC).

Theoretical advances: projected quantum capability

Proposed by Peter Shor in 1994, Shor's algorithm theoretically proves that quantum computers could factor large integers in polynomial time, threatening foundational encryption systems such as RSA and ECC. This single breakthrough fundamentally changed the long-term security outlook for classical public-key cryptography.

Gidney and Ekera (2021) estimated that a quantum computer equipped with approximately 20 million qubits could factor a 2048-bit RSA key within roughly eight hours — providing one of the most accurate projections for quantum computing capabilities to date. While current quantum systems are far from this scale, the trajectory of qubit counts and error correction research makes this milestone achievable within the coming decade.

Practical experiments: small-scale implementations

Early experimental evidence emerged in 2001 when IBM implemented Shor's algorithm on a 7-qubit quantum system, successfully factoring the number 15. More recently, in 2022, researchers employed a 10-qubit superconducting quantum computer to factor integers up to 48 bits, demonstrating significant progress in quantum computational engineering — though still far from practical cryptographic key sizes.

Key milestones in quantum key-breaking research

• 2001: IBM factors 15 using a 7-qubit NMR quantum system (Shor's algorithm, proof of concept)
• 2009: Classical team factors RSA-768 after months of compute — driving the industry to RSA-2048
• 2015: FREAK Attack exploits RSA-512 vulnerability in legacy TLS implementations
• 2022: 10-qubit superconductor factors 48-bit integers — demonstrating scaling progress

Historical context: classical computing attacks

Classical computing has historically compromised cryptographic keys, prompting increased key lengths and security measures. Notable historical incidents include:

• FREAK Attack (2015): Exploited the vulnerability of RSA-512, underscoring the obsolescence of short key lengths. Millions of websites were affected.
• RSA-768 Factoring (2009): A European research team successfully factored a 768-bit RSA key after months of computational effort, pushing the community towards RSA-2048 as the minimum standard.

These classical-era breaks are a direct precedent: as computational power grows, key lengths that once seemed unbreakable become obsolete. The quantum transition will be far more abrupt.

Conclusion

Theoretical and experimental developments clearly indicate that future quantum computers represent a tangible threat to current cryptographic practices. Early demonstrations confirm the correctness and potential scalability of Shor's algorithm, emphasizing the necessity of transitioning urgently toward quantum-resistant cryptography. Organizations that delay migration risk having their encrypted data — intercepted today — decrypted the moment quantum systems reach sufficient scale.

References

• Gidney, C., & Ekera, M. (2021). How to factor 2048-bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433. arXiv link
• Vandersypen, L. M. K. et al. (2001). Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature, 414, 883–887. Nature link
• Xu, K., Wu, S., et al. (2022). Factoring 48-bit integers with 10 superconducting qubits. arXiv link
• Wikipedia. FREAK (Factoring RSA Export Keys). Link
• Kleinjung, T., et al. (2010). Factorization of a 768-bit RSA modulus. IACR link