Start with two different locks
RSA and ECC do not hide the same secret. RSA hides the prime factors of a large number. ECC hides how many group operations connect a public starting point P to a public point Q.
Shor does not read every possible answer. It uses coherent superposition, interference, and a quantum Fourier transform to make clues about hidden mathematical structure easier to measure.
The eight plates establish the period idea before the folded engineer note works through N = 15. The experiment below repeats that calculation and lets you try bases that fail to produce factors. It finds orders by classical enumeration and implements no quantum circuit.
Which lock does a quantum computer threaten?
Browser padlocks, banking connections, and signed firmware often depend on public-key cryptography. Its job is usually to authenticate a party, establish a shared secret, or verify a signature. Bulk traffic is then commonly protected by a symmetric cipher such as AES.
RSA and elliptic-curve cryptography rely on particular mathematical problems. On a sufficiently large fault-tolerant quantum computer, Shor’s algorithm can efficiently solve integer factorization and discrete logarithms. That could allow an attacker to reconstruct an RSA private key or recover an ECC secret scalar. The hardware requirement matters; the existence of a quantum computer alone does not establish that such attacks are practical.
Shor's original work covers both integer factorization and discrete logarithms. That distinction matters because RSA and ECC fail through related quantum machinery but different mathematical routes. [1]
RSA and ECC hide different secrets
RSA begins with two very large primes and multiplies them into a public modulus. Multiplication is easy; recovering the primes from the product is hard for known classical algorithms at real key sizes. The primes are not literally the private key, but knowing them reveals the information needed to reconstruct it.
ECC starts from a public point P. Repeating a defined group operation k times gives a public point Q. Computing Q from P and the secret scalar k is fast; recovering k from P and Q is the elliptic-curve discrete-logarithm problem.
The gears and jumps are teaching analogies. RSA is not a physical gear puzzle, and elliptic-curve points do not run along a smooth track. The real work follows arithmetic rules in finite groups.
Shor looks for hidden structure, not the private key directly
Classical cryptanalysis is not limited to trying keys one at a time. Number theory has produced sophisticated factoring and discrete-logarithm algorithms, but their cost is still impractical when modern parameters are chosen correctly.
Shor changes the question. For RSA, it reduces factoring to finding the order or period of a modular-exponentiation function, then uses ordinary integer arithmetic to extract factors. For ECC, it analyzes a hidden relation inside the elliptic-curve group.
The echo metaphor helps remember the period clue. Measurements still require candidate-order reconstruction, condition checks and classical post-processing; one measurement may be unhelpful and does not hand over a private key. The experiment below uses N=15 to connect an order with factors and lets you try a base that requires a retry. It enumerates the order classically and runs no quantum circuit.
Quantum interference makes period clues measurable
A quantum register can hold a coherent superposition of many inputs and evaluate a function while preserving phase relationships. That does not let us read every computed value; measurement still returns limited information.
The algorithm instead arranges interference. Some amplitudes cancel and others reinforce. A quantum Fourier transform turns repeated structure into frequency information that appears as a pattern of likely measurement outcomes.
Several runs provide samples. Classical continued-fraction and verification steps then recover a candidate period. The bright peaks in the plate are clues compatible with the period, not a private key printed by the quantum computer.
RSA uses the period to extract factors
Once a useful period r is known, the algorithm uses the factorization of a^r minus 1 and computes greatest common divisors with the RSA modulus N. A successful run exposes non-trivial factors; an unhelpful choice or period simply requires another attempt.
This is why period finding and key recovery are separate steps. The quantum stage supplies the difficult structural clue. Classical arithmetic, validation, and possible retries finish the factorization, after which the RSA private key can be reconstructed.
Engineer extension: what the N = 15 example is actually doing
For N = 15 and a = 2, the modular sequence returns to 1 at 2^4, so r = 4 is useful. Because 15 divides 2^4 - 1, the difference of squares gives (2^2 - 1)(2^2 + 1) = 3 x 5.
Real inputs are not always this tidy. First require an even order r, then compute gcd(a^(r/2) - 1, N) and gcd(a^(r/2) + 1, N). A non-trivial factor must be greater than 1 and less than N. If r is odd or only 1 and N appear, retry with another a. For a = 14, N = 15 and r = 2, the results are gcd(13,15) = 1 and gcd(15,15) = 15, so another base is needed. The toy example illustrates why a period creates a factorable expression; it is not the full RSA attack.
ECC uses Shor to recover the secret scalar k
An elliptic-curve public key is commonly written as Q = kP. The curve, base point P, and public point Q are public; k is secret. ECDH key agreement and ECDSA signatures rely on the difficulty of recovering k.
Shor's discrete-logarithm algorithm prepares a superposition over two indices, evaluates their combined group element, and Fourier-analyzes the resulting hidden linear relation. Measurement plus classical post-processing can recover k. [1]
Keep the two routes separate: RSA recovers factors, while ECC recovers a scalar. Shor threatens both, but ECC is not factored like an RSA modulus.
Today's machines cannot do this attack, but old ciphertext can wait
Shor's mathematical result does not mean today's quantum hardware can break RSA-2048 or commonly deployed ECC. A practical attack requires a large, fault-tolerant cryptanalytically relevant quantum computer capable of running long circuits reliably. The arrival date remains uncertain. [2]
Long-lived secrets create a present-day risk. An attacker can capture ciphertext now and keep it until future hardware can decrypt it. CISA, NSA, and NIST describe this as collect-now-decrypt-later or harvest-now-decrypt-later and recommend early migration planning. [3]
Signatures create a different exposure. Stored ciphertext raises future-confidentiality concerns; vulnerable signing keys raise future forgery concerns for identities, certificates, firmware, and software updates.
Inventory public-key uses, then migrate to PQC
Shor directly targets integer factorization and discrete logarithms. RSA, finite-field Diffie-Hellman and DSA, ECDH, and ECDSA therefore belong in the migration inventory. AES and cryptographic hashes are not direct Shor targets, although other quantum algorithms such as Grover still affect how their security strength is assessed.
NIST published its first finalized PQC standards in 2024: ML-KEM in FIPS 203 for key establishment, plus ML-DSA in FIPS 204 and SLH-DSA in FIPS 205 for signatures. NIST now recommends that organizations begin applying the standards and migrating systems. [4][5]
A practical program inventories algorithms and certificates, records how long data must stay secret, checks vendor and protocol support, tests interoperability, and migrates in stages. PQC changes key, signature, and packet sizes as well as performance, hardware cost, certificate chains, and upgrade paths.
Five points to keep
- RSA relies on hard integer factorization; ECC relies on the hard elliptic-curve discrete logarithm.
- Shor uses coherent superposition, interference, and a QFT to expose structural clues—not to read every answer.
- The RSA route extracts factors from a useful period; the ECC route recovers the secret scalar k from a group relation.
- No current machine can run this attack against deployed RSA or ECC, but long-lived ciphertext creates a harvest-now-decrypt-later risk.
- Migration starts with a cryptographic inventory, then staged adoption of standardized PQC with interoperability testing.
The next lesson will ask how ML-KEM lets two parties establish the same shared secret without relying on RSA or ECC.
References
- Peter W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer: The original expanded paper covering polynomial-time quantum algorithms for factorization and discrete logarithms.
- NIST NCCoE, Migration to Post-Quantum Cryptography FAQ: Current NIST guidance on CRQC risk, cryptographic inventory, and PQC migration.
- CISA, NSA, and NIST, Quantum-Readiness: Migration to Post-Quantum Cryptography: Official roadmap covering harvest-now-decrypt-later risk and early migration planning.
- NIST approval of FIPS 203, 204, and 205: Official announcement of the first finalized NIST post-quantum standards.
- NIST FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard: The ML-KEM standard for establishing a shared secret over a public channel.
- NIST IR 8547 IPD: Transition to Post-Quantum Cryptography Standards: The initial public draft identifying quantum-vulnerable standards and the expected migration direction.
Extract factors of 15 from an order
With a=2, follow the remainders back to 1 and find the smallest positive order r. Inspect the value at r/2 and both greatest common divisors. Then try a=14: an order still exists, but only trivial factors appear, so another base is needed.
The order is found by classical enumeration. There are no quantum registers, QFT or quantum speedup. This demonstrates only the classical post-processing in Shor’s factoring procedure.
Learning guide
Security Foundations
Open the course outline → · Progress counts published lessons only
Prerequisites
- Basic public-key and symmetric-key roles
What I learned
- Separate RSA factorization from the ECC discrete logarithm
- Explain why interference reveals period clues instead of every answer
- Identify quantum-vulnerable public-key uses and plan PQC migration