Can a quantum computer break RSA today?
No. Shor's algorithm breaks RSA in principle but needs a large fault-tolerant quantum computer that does not exist yet; experiments factored only tiny numbers.
Shor's algorithm factors $N$ in time polynomial in its number of bits, which breaks RSA in theory. But the RSA keys used in practice are thousands of bits long, and running Shor on them requires thousands of error-corrected logical qubits, i.e. far more physical qubits, and very deep circuits. Current devices are far from that.
Published experiments have factored numbers such as 15 (Vandersypen et al. 2001), often with simplified circuits that exploit knowledge of the answer. Our lab simulates Shor only for $N\in\{15,21,33,35\}$, and builds the modular multiplication by classical computation, so it is a teaching tool, not evidence of any ability to break encryption.
Even so, the security community takes the threat seriously because of the risk of “harvest now, decrypt later”, which is why a transition to quantum-resistant encryption algorithms (Post-quantum Cryptography) is under way.
Related topics
References
- Peter W. Shor (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5):1484–1509 doi:10.1137/S0097539795293172
- L. M. K. Vandersypen; M. Steffen; G. Breyta; C. S. Yannoni; M. H. Sherwood; I. L. Chuang (2001). Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature 414:883–887 doi:10.1038/414883a
- John Preskill (2018). Quantum Computing in the NISQ era and beyond. Quantum 2:79 doi:10.22331/q-2018-08-06-79
