Test your cyber skills

Insights/ Threat Landscape · Post-Quantum Cryptography, Part 2 of 4

Why your encryption works, and why quantum breaks it

RSA's security rests on one asymmetry: factoring is hard, multiplying is easy. Why Shor's Algorithm breaks that asymmetry, and why no key length can fix it.

Mono Training team13 min read
Executive summary

Part 1 established the threat: quantum computers will eventually break the encryption protecting most of the world's digital infrastructure, the timeline has been compressed, and nation-state adversaries are already harvesting encrypted data. Part 2 explains the mechanism. Why does RSA work against classical computers? What specific property of quantum computers makes it vulnerable? And why does doubling your key length provide essentially no protection against a quantum attack?

Data sourcesShor, P.: SIAM Journal on Computing (1994) · Gidney, C., arXiv 2505.15917 (2025) · NIST IR 8413 (2022) · NSA CNSA 2.0 (2022) · IBM Condor processor (2023) · Google Willow (December 2024)Figures reflect publicly reported research as of October 2026. Findings evolve. Verify current studies before citing externally.

01The foundations

Why RSA works, and what it's actually protecting

RSA encryption, named for Rivest, Shamir, and Adleman, who published it in 1977, is built on a single mathematical asymmetry: multiplying two large prime numbers together is trivially easy. Factoring the result back into its two prime components is, for classical computers, computationally intractable.

RSA-2048, the most commonly deployed standard today, uses a public key derived from a product of two 1,024-bit prime numbers. Factoring that number on the fastest classical supercomputer, using the best known classical algorithm, would take longer than the current age of the universe. That's not an exaggeration. It's the actual mathematical basis for the security guarantee.

The security guarantee that has underpinned internet infrastructure for decades doesn't disappear in theory. It disappears in practice, once the hardware exists to run a specific algorithm Peter Shor described in 1994.

This asymmetry, easy to multiply, effectively impossible to factor, is why RSA works. Your browser uses it to verify every HTTPS certificate. Your VPN uses it to establish a secure tunnel. Your email uses it to sign messages. Every software update you install is verified with it. The entire trust infrastructure of the internet rests on this one mathematical difficulty.

617

decimal digits in an RSA-2048 modulus. Factoring it classically would take longer than the age of the universe.

Mathematical property of RSA-2048
1977

the year RSA was published. Nearly 50 years of internet infrastructure rests on this one difficulty.

Rivest, Shamir, Adleman: MIT

02The mechanism

Quantum computers don't try factors one at a time

Classical computers try factors sequentially, or in parallel across many processors, but still sequentially within each processor. A qubit in superposition doesn't have a value of zero or a value of one. It exists in a combination of both simultaneously, until measured. The state of 300 qubits is described by 2³⁰⁰ numbers, more than there are atoms in the observable universe. That is why quantum computers cannot be efficiently simulated, but it is not the same as trying 2³⁰⁰ answers at once.

That's what makes quantum computing sound like magic, and what makes people sceptical of it. The critical clarification: superposition alone doesn't solve hard problems. When you measure a quantum system, it collapses to a single state. If that state were random, quantum computing would be useless for computation. The power comes from what happens before measurement.

What Shor's Algorithm actually does

It does not guess factors. It turns factoring into a different problem: finding the period of a repeating mathematical function. A quantum computer can find that period efficiently using the quantum Fourier transform, an interference step that makes the right answer overwhelmingly likely to be observed when the qubits are measured, while wrong answers cancel out. Ordinary arithmetic then turns the period into the prime factors. The result: factoring in polynomial time, not super-polynomial time. For RSA-2048, current estimates are hours to days on a large enough machine, not billions of years.

This isn't a linear speedup. It's not ten times faster or a thousand times faster. It's the difference between a problem being effectively impossible and being tractable. The entire mathematical foundation of RSA, that factoring large numbers is hard, ceases to hold on a sufficiently powerful quantum computer.

03The critical implication

Key length can't save you. Neither can switching to elliptic curve

A natural question: if longer RSA keys are harder to factor classically, does moving from RSA-2048 to RSA-4096 or RSA-8192 provide meaningful quantum protection? No, and the reason matters.

Shor's Algorithm's time complexity scales polynomially with the number of digits being factored. Doubling the key length makes the classical problem astronomically harder, but makes the quantum computation only several times longer, with a modest increase in qubits. There is no RSA key length that is quantum-safe. Classical computers are fighting an exponential battle. Quantum computers are not.

Elliptic Curve Cryptography: same problem, different mathematics. ECC underpins most modern TLS connections, SSH keys, and cryptocurrency transaction signing. It uses a different mathematical problem, the elliptic curve discrete logarithm problem, but one equally vulnerable to a quantum variant of Shor's Algorithm. ECC's apparent advantage over RSA is that it achieves equivalent classical security with much shorter keys. Against a quantum computer, that advantage disappears entirely: ECC-256 provides roughly the same classical security as RSA-3072, yet its shorter keys make it easier for a quantum computer to break. Google Quantum AI estimated in March 2026 that 256-bit elliptic curve keys could fall to fewer than 500,000 physical qubits. Both are broken by Shor's Algorithm, and ECC may well fall first.

The prioritisation is clear for any organisation beginning its transition: RSA and ECC are the urgent problem. They protect HTTPS, TLS, SSH, certificates, VPNs, code signing, and authentication infrastructure. Every system using these algorithms is carrying a future liability, one that becomes a present liability the moment a cryptographically relevant quantum computer exists.

04The threshold that matters

What "cryptographically relevant" actually means

The phrase "cryptographically relevant quantum computer" (CRQC) appears in almost every piece of government post-quantum guidance. It's worth defining precisely: a CRQC is a quantum computer capable of running Shor's Algorithm on real-world cryptographic key sizes, specifically one capable of factoring RSA-2048 within a practical timeframe. A 2025 paper by Craig Gidney puts this at under one million physical qubits with sufficiently low error rates, running for under a week. 2026 preprints suggest around 100,000 may be enough on hardware designs that have not yet been demonstrated at scale.

First 1,000+ qubit chip
1,121

physical qubits (IBM Condor, 2023)

Best error-correction demo
105

qubits (Google Willow, Dec 2024)

CRQC threshold
<1M

physical qubits (Gidney, 2025 estimate)

The transition planning needed now isn't because a CRQC exists. It's because building one is a credible engineering project on a decade timescale, and the systems that need to change take years to change. ASD's end-of-2030 target isn't conservative. For large organisations with complex cryptographic infrastructure, it may already be tight.

05The exposure, locally

Every system in scope for the ASD's 2030 guidance is running quantum-vulnerable cryptography today

ASD's planning guidance asks organisations to transition critical systems and data first: systems critical to the organisation's function, systems handling highly sensitive, classified or long-lived confidential data, and systems that are hard or slow to update. In practice that list usually includes certificate authorities and PKI, secure communications, and code signing infrastructure.

For Australian critical infrastructure operators, energy, water, transport, health, financial services, these categories describe core operational systems. The encryption protecting SCADA communications, operational technology networks, and inter-agency data sharing is, in most cases, RSA or ECC. Understanding why those algorithms are vulnerable is the first step toward building a credible transition case internally.

The guidance is consistent with the broader Five Eyes posture: the NSA, NCSC, CCCS, and GCSB have all published aligned guidance. ASD names harvest-now-decrypt-later explicitly, and the NSA's CNSA 2.0 sets its deadlines on the basis that today's data will need protection for decades. For organisations handling data that requires confidentiality beyond the next decade, this is current risk management, not future planning.

·Key takeaways

What to take into your next risk conversation

01RSA's security rests on a single mathematical asymmetry

Multiplying two large primes is easy. Factoring their product is, classically, effectively impossible at RSA key sizes. Shor's Algorithm breaks this asymmetry entirely.

02Shor's Algorithm uses interference, not brute force

It encodes factoring as a wave function, uses the quantum Fourier transform to find the period that reveals the factors, and does it in polynomial time, not by checking every possibility.

03Key length can't fix the problem

Longer keys add only polynomial difficulty against Shor's Algorithm. There's no RSA or ECC key length that's quantum-safe. The problem is structural, not scale.

04Elliptic curve cryptography is equally vulnerable

ECC's shorter-key advantage over RSA disappears entirely against a quantum attacker. Both require replacement. There's no exception here.

Next in the series: Part 3 of 4The New Standards: What's Replacing Your Encryption