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.
decimal digits in an RSA-2048 modulus. Factoring it classically would take longer than the age of the universe.
Mathematical property of RSA-2048the year RSA was published. Nearly 50 years of internet infrastructure rests on this one difficulty.
Rivest, Shamir, Adleman — MITQuantum 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. A system of 300 qubits in superposition can represent 2³⁰⁰ states at once — a number larger than the atoms in the observable universe.
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 uses quantum interference to make the correct answer — the prime factors — more probable to be observed when measured, while making wrong answers less probable. It encodes the factoring problem as a wave function, explores many candidate factors simultaneously, then applies interference operations that amplify correct answers and cancel incorrect ones. The result: factoring in polynomial time, not exponential time. For RSA-2048, that means hours — 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.
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 — which squares the classical difficulty — adds only a modest polynomial factor to the quantum computation. 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, and against Shor's Algorithm, both are equally broken.
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.
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, 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.
physical qubits (IBM Condor, 2023)
qubits (Google Willow, Dec 2024)
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. The ASD's 2030 guidance target isn't conservative. For large organisations with complex cryptographic infrastructure, it may already be tight.
Every system in scope for the ASD's 2030 guidance is running quantum-vulnerable cryptography today
The ASD's 2024 Information Security Manual identifies the following as highest priority for post-quantum transition: systems handling data that must remain confidential for more than ten years, authentication infrastructure including certificate authorities and PKI systems, secure communications platforms, and code signing infrastructure protecting software supply chain integrity.
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. The NSA's CNSA 2.0 explicitly cites harvest-now-decrypt-later as justification for immediate action. For organisations handling data that requires confidentiality beyond the next decade, this is current risk management — not future planning.
What to take into your next risk conversation
RSA'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.
Shor's Algorithm uses interference, not brute force
It encodes factoring as a wave function, uses interference to amplify correct answers, and reads out a result in polynomial time — not by checking every possibility.
Key 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.
Elliptic 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.
The New Standards: What's Replacing Your Encryption
The transition is technical. The decisions that drive it are made by people.
Understanding why the threat is real — not just that it is — is where informed decisions start. Click or Flick Corporate builds that awareness at every level of your organisation, from technical teams to the board.