Shor's Algorithm Explained: How It Threatens RSA, ECC, and Crypto Wallets

Shor's algorithm, published by mathematician Peter Shor in 1994, is the single most consequential threat to modern public-key cryptography. It demonstrates that a sufficiently powerful quantum computer can factor large integers and compute discrete logarithms in polynomial time, two tasks that underpin virtually every cryptographic system securing the internet and crypto wallets today. This article explains the algorithm's mechanics, what it does to RSA and elliptic-curve cryptography (ECC), how many fault-tolerant qubits it actually needs, where timelines realistically stand, and why the crypto industry is already responding.

What Shor's Algorithm Actually Does

Shor's algorithm solves two related mathematical problems that classical computers find intractable at large scales:

1. Integer factorisation — given a large composite number *N*, find its prime factors *p* and *q*.
2. Discrete logarithm — given a base *g* and a result *y* in a finite group, find the exponent *x* such that *g^x ≡ y*.

Both problems are "easy" to verify but "hard" to solve in one direction. Classical algorithms scale exponentially with the size of the input (in bits). The best classical algorithm for factoring, the General Number Field Sieve, runs in sub-exponential time, roughly *O(exp((64/9)^(1/3) · (log N)^(1/3) · (log log N)^(2/3)))*. For a 2048-bit RSA key, that requires more computation than any classical supercomputer can perform in the lifetime of the universe.

Shor's algorithm reduces the same problem to polynomial time, specifically *O((log N)^3)* quantum gate operations. That is not a modest improvement — it is a categorical phase shift from infeasible to feasible.

The Two-Phase Structure

Shor's algorithm combines classical and quantum computation in two phases:

Phase 1 — Classical reduction. The factoring problem is reduced to a period-finding problem. Given *N*, choose a random integer *a < N*. The function *f(x) = a^x mod N* is periodic with some period *r*. If *r* is even and *a^(r/2) ≢ -1 (mod N)*, then *gcd(a^(r/2) ± 1, N)* yields a non-trivial factor. This reduction is entirely classical and fast.

Phase 2 — Quantum period finding. Finding *r* efficiently is where quantum mechanics does the work. The algorithm initialises a quantum register in a superposition of all values of *x*, applies the modular exponentiation function *f(x)* to a second register, then applies the Quantum Fourier Transform (QFT) to the first register. Measurement collapses the system to a state that encodes information about *r*, which is then extracted via classical continued-fractions algorithms.

The QFT is the critical quantum subroutine. It is the quantum analogue of the classical Fast Fourier Transform but operates on quantum amplitude distributions, exploiting interference to amplify the periodicity signal and suppress noise.

Why This Breaks RSA

RSA security rests entirely on the difficulty of factoring the product of two large primes. If Shor's algorithm can factor *N = p · q* efficiently, an attacker can reconstruct the private key from the public key. There is no secondary layer of protection. RSA-2048, considered secure against classical attack for decades, falls to a sufficiently large quantum computer running Shor's algorithm.

Why This Breaks Elliptic-Curve Cryptography

ECC — used in Bitcoin (secp256k1), Ethereum, and TLS — bases its security on the elliptic-curve discrete logarithm problem (ECDLP). Given a public key point *Q = k · G* on an elliptic curve, recovering the private scalar *k* is computationally infeasible classically. Shor's algorithm, adapted for the discrete logarithm variant, solves ECDLP in polynomial time on a quantum computer. A 256-bit ECC key, equivalent in classical security to RSA-3072, requires far fewer qubits to break than RSA-2048, making ECC *more* vulnerable in the quantum context, not less.

---

Qubit Requirements: How Many Are Actually Needed?

The gap between Shor's algorithm in theory and a machine that can run it is enormous. Qubit count alone is misleading. The operative question is fault-tolerant logical qubits, which require many noisy physical qubits each.

Physical vs Logical Qubits

Current quantum hardware operates with physical qubits that have error rates typically between 0.1% and 1% per gate operation. Shor's algorithm requires error rates far below that threshold for a meaningful computation. Quantum error correction (QEC) encodes one reliable *logical* qubit across many physical qubits.

The most studied QEC scheme for this purpose is the surface code, which currently requires roughly 1,000 physical qubits per logical qubit at realistic error rates (~0.1%). More optimistic assumptions (error rate ~0.01%) push that ratio toward 100:1.

Estimates for Breaking Cryptographic Keys

Researchers have published increasingly refined estimates over the years. The table below summarises key academic findings:

The 2022 Webber et al. analysis from Universal Quantum is notable for its engineering realism: breaking RSA-2048 within one hour would require roughly 13 million physical qubits with a gate error rate of 10^-6. At the more achievable 10^-3 error rate, the physical qubit count rises to around 317 million and the runtime stretches to a decade, making it practically useless as an attack vector at current hardware capability.

The Error-Correction Bottleneck

Error correction is not a software patch. It requires physical redundancy, specialised hardware layouts (often 2D grids for surface codes), classical co-processors running real-time syndrome decoding, and extreme environmental isolation (superconducting qubits operate near absolute zero). Scaling from today's largest quantum processors, which range from a few hundred to a few thousand noisy physical qubits, to the millions required for cryptographically relevant attacks is an engineering challenge that is widely regarded as a decade or more away.

---

Realistic Timelines: What Experts Actually Say

There is a wide spectrum of credible expert opinion on when, or whether, cryptographically relevant quantum computers (CRQCs) will exist.

Near-Term Consensus (2024–2030)

No credible expert expects a CRQC within this window. Current systems from IBM, Google, IonQ, and others are NISQ (Noisy Intermediate-Scale Quantum) machines. They are useful for certain optimisation and chemistry simulations but orders of magnitude below the fault-tolerant scale required for Shor's algorithm on real cryptographic keys. Google's 2023 announcement of reduced error rates in surface codes was a scientific milestone, not a cryptographic emergency.

Medium-Term Uncertainty (2030–2040)

This is where serious disagreement begins. Some government assessments, including analyses cited in NIST documentation and by CISA, suggest a non-negligible probability of a CRQC emerging in this window. Others, including several academic quantum physicists, argue that fundamental engineering barriers make the 2030s highly unlikely and the 2040s optimistic.

The "Harvest Now, Decrypt Later" Threat

Regardless of when CRQCs arrive, one threat is immediate: adversaries can intercept and store encrypted data today and decrypt it once quantum capability matures. This is sometimes called the "store now, decrypt later" (SNDL) attack. For long-lived secrets — government communications, financial records, patient data, seed phrases — the relevant question is not when quantum computers arrive but how long the secret needs to remain confidential.

---

What Shor's Algorithm Does NOT Break

Symmetric encryption and certain hash functions are not directly threatened by Shor's algorithm:

• AES-256 is considered secure against quantum attack. Grover's algorithm provides a quadratic speedup in brute-force search, effectively halving the security level, but AES-256 would still offer 128-bit quantum security, well above the practical attack threshold.
• SHA-256 and SHA-3 are similarly resistant. Their preimage and collision resistance is weakened by Grover but not broken outright.
• Lattice-based cryptographic schemes (CRYSTALS-Kyber, CRYSTALS-Dilithium) have no known efficient quantum algorithm. These form the core of NIST's post-quantum cryptography (PQC) standards, finalised in 2024.

The specific vulnerabilities are public-key cryptosystems based on factoring and discrete logarithm problems. That covers RSA, DSA, ECDSA, ECDH, and Diffie-Hellman — essentially the entire fabric of asymmetric cryptography in use today.

---

Why This Matters for Crypto Wallets Specifically

Standard crypto wallets use ECDSA (Elliptic Curve Digital Signature Algorithm) to generate key pairs and sign transactions. The public key is mathematically derived from the private key via elliptic curve point multiplication. As long as a public key has not been exposed on-chain, an adversary cannot derive the private key classically.

The Reuse and Exposure Problem

Bitcoin and Ethereum addresses derived from public keys enjoy one layer of hash protection (addresses are hashes of public keys, not public keys themselves). However:

• Every signed transaction reveals the public key on-chain.
• Address reuse is common and compounds exposure.
• On Ethereum, the public key is always derivable from the signature, meaning every transaction is a potential quantum attack surface once CRQCs exist.

A quantum attacker running Shor's algorithm would not need to brute-force the seed phrase. They would extract the private key directly from the exposed public key, then sign fraudulent transactions or drain funds before the legitimate owner can react.

UTXO vs Account Model Differences

Projects building quantum-resistant wallets — using NIST PQC-aligned schemes such as lattice-based cryptography — address this exposure directly. BMIC.ai is one such project, designing its wallet architecture around post-quantum primitives rather than retrofitting ECDSA after the fact.

---

The Post-Quantum Migration Challenge

Migrating the global cryptographic infrastructure to post-quantum algorithms is a multi-decade undertaking. NIST finalised its first set of PQC standards in August 2024: FIPS 203 (ML-KEM / Kyber) for key encapsulation and FIPS 204 (ML-DSA / Dilithium) and FIPS 205 (SLH-DSA / SPHINCS+) for digital signatures.

For the crypto industry specifically, migration is harder than for web PKI because:

1. Blockchain immutability means old keys and addresses cannot be retroactively upgraded.
2. Signature size increases significantly with PQC schemes (Dilithium signatures are ~2.4 KB vs ~72 bytes for ECDSA), raising transaction fees and on-chain storage costs.
3. Consensus-layer changes are required to validate new signature schemes, demanding protocol-level upgrades with community governance.
4. User key migration requires individuals to actively move funds to quantum-safe addresses, a process that historically sees poor participation rates.

The prudent approach is to begin migration before CRQCs are confirmed, not after. The window between a confirmed quantum breakthrough and widespread exploitation may be very short.

---

Summary: Key Takeaways

• Shor's algorithm solves integer factorisation and discrete logarithm in polynomial time, breaking RSA and ECC at scale.
• It requires millions of fault-tolerant logical qubits backed by billions of physical qubits at current error rates. No machine today is anywhere near this threshold.
• The realistic timeline for a cryptographically relevant quantum computer is broadly estimated at the 2030s to 2040s, with significant uncertainty in both directions.
• The "harvest now, decrypt later" threat means long-lived secrets are at risk today, regardless of timelines.
• Standard crypto wallets using ECDSA have a genuine long-term vulnerability; address reuse and Ethereum's account model are the highest-exposure patterns.
• NIST PQC standards (2024) provide the algorithmic foundation for migration; the challenge is implementation speed and ecosystem coordination.