What is Shor's algorithm, and why does it worry every cybersecurity team on the planet?

[GlobalOliver15]

Shor's algorithm is a quantum algorithm published by mathematician Peter Shor in 1994 that can efficiently factor large integers and solve the related discrete logarithm problem, the two mathematical problems that underpin RSA, Elliptic Curve Cryptography and Diffie-Hellman key exchange, the encryption schemes securing the overwhelming majority of internet traffic today. Classically, factoring a large number like a 2048 bit RSA key is considered computationally infeasible, taking longer than the age of the universe with any known classical method. Shor's algorithm reduces that same problem to something a sufficiently powerful quantum computer could solve in a practical amount of time

The algorithm works by reframing factoring as a period finding problem, something quantum computers are naturally well suited to because of a tool called the Quantum Fourier Transform, which quantum hardware can apply to many possibilities simultaneously thanks to superposition. No quantum computer today is anywhere close to running Shor's algorithm against real world key sizes, current estimates still require somewhere in the range of a million or more high quality physical qubits with extremely low error rates, well beyond what any existing machine has achieved

The threat is not purely theoretical or purely future facing though, because of a strategy security researchers call harvest now, decrypt later, where encrypted data intercepted and stored today could simply be decrypted once a capable enough quantum computer eventually exists. That risk is exactly why post quantum cryptography, new encryption schemes designed to resist Shor's algorithm even in principle, is already being standardized and rolled out well before the hardware that could actually break today's encryption exists

What Is Shorpostquantum.com

[Peter82]

Harvest now, decrypt later is the detail that actually makes this an urgent problem today rather than something to worry about only once the hardware exists

[Tom91]

The gap between where quantum hardware is now and the qubit count Shor's algorithm actually needs at real key sizes is enormous, worth remembering before panicking about any single new qubit count headline

[alwaysPatrick19]

Reframing factoring as a period finding problem is such an elegant piece of math, that reformulation is really the whole trick behind why this works on quantum hardware

[Aura]

This is exactly why encrypted data with a long shelf life, medical records, state secrets, financial history, needs post quantum protection now rather than waiting for the actual quantum threat to materialize

[Sentry39]

Good to see a plain explanation of why RSA and ECC specifically are the vulnerable ones rather than every kind of encryption across the board

[FinnHalliday]

The million plus physical qubit estimate really puts into perspective how far off an actual working Shor's algorithm attack still is with current hardware

[Leah_68]

Post quantum cryptography standardization happening years ahead of the actual hardware threat is a rare example of the security world being appropriately proactive

[Depot]

This connects directly to a lot of the current AI and quantum computing news, cryptography researchers clearly are not treating this as a distant hypothetical

[Memory Jaguar]

Appreciate that this explains both why the algorithm is mathematically elegant and why the actual near term risk is still fairly contained given current hardware limits