Why Quantum Computers Threaten Today's Encryption

Every time you open a banking app, connect to a corporate VPN, sign in with a passkey, install a Windows update or enrol a laptop in Intune, the same small family of mathematical ideas is quietly doing the work. They are called public-key cryptography, and almost all of it rests on two algorithms: RSA and elliptic-curve cryptography (ECC).

Both are believed to be safe against every computer we have today. Both would be broken by a large enough quantum computer running Shor's algorithm. That single fact is why governments have set deadlines, why browsers are already changing how they connect, and why quantum computing matters to every IT and security team, including the ones that will never touch a quantum computer.

Today: What RSA and ECC Hold Up

The diagram is short, but it hides a lot of infrastructure. HTTPS protects every website and API. VPNs protect remote workers and site-to-site links. PKI issues the certificates that devices use for Wi-Fi, VPN and authentication. Digital signatures prove that software updates, firmware, documents and login tokens are genuine. Remove the trust layer at the top and every one of them needs replacing.

To understand why a quantum computer threatens this layer, and why it threatens some cryptography but not all, you need to know what each piece does.

Public-Key Cryptography: Solving the Stranger Problem

Encryption itself is old. If you and I share a secret key, we can encrypt messages with a fast symmetric algorithm such as AES, and anyone without the key sees noise. The hard question is: how do two strangers on the Internet agree on a secret key without anyone listening in? Your browser has never met your bank's server before, and everything they send each other can be watched.

Public-key cryptography, invented in the 1970s, solves this with a pair of linked keys:

• A public key, which you can give to anyone.
• A private key, which you never share.

Everyday analogy: a public key is like an open padlock that you hand out freely. Anyone can snap it shut on a box and send it to you, but only you have the key that opens it. And a digital signature works in reverse: like a wax seal that only you can make, but anyone can check.

In practice, systems use both: public-key cryptography to agree a key and prove who's who, then fast symmetric encryption for the data itself. Keep that split in mind, because the quantum threat lands almost entirely on the public-key half.

RSA: Security From Factoring

RSA, published in 1977 by Rivest, Shamir and Adleman, is built on a simple asymmetry: multiplying two large prime numbers is easy, but splitting the result back into those primes (factoring) is extremely hard.

• The private key is built from two secret primes, p and q.
• The public key includes their product, n = p × q, which everyone can see.
• Anyone can encrypt with n, but decrypting requires a number derived from p and q. So whoever can factor n can compute the private key.

Here's the whole idea with toy numbers (real keys use primes hundreds of digits long):

p, q = 61, 53                 # the secret primes
n = p * q                     # 3233, part of the public key
phi = (p - 1) * (q - 1)
e = 17                        # public exponent
d = pow(e, -1, phi)           # private exponent, needs p and q
 
msg = 65
c = pow(msg, e, n)            # anyone can encrypt with (n, e)
print("ciphertext =", c, "decrypted =", pow(c, d, n))
 
# An attacker who can factor n recovers the private key
f = next(k for k in range(2, n) if n % k == 0)
d2 = pow(e, -1, (f - 1) * (n // f - 1))
print("attacker factors", n, "=", f, "x", n // f, "-> message", pow(c, d2, n))

ciphertext = 2790 decrypted = 65
attacker factors 3233 = 53 x 61 -> message 65

For a four-digit n, the attacker's loop finishes instantly. For a real 2048-bit key (a number about 617 digits long), no known classical method comes close. The largest RSA challenge number ever factored classically, RSA-250 in 2020, had 829 bits and took roughly 2,700 years of computer core time. Each extra bit makes the job harder, and 2048 bits is far beyond reach.

That's the entire security of RSA: factoring is hard. It is not proven to be hard; it's just that nobody has found a fast classical method in decades of trying.

ECC: Smaller Keys, Same Kind of Weakness

Elliptic-curve cryptography uses a different hard problem. Points on an elliptic curve can be "added" together, and adding a point to itself many times is easy. Working backwards, from the result to how many times the point was added, is called the elliptic-curve discrete logarithm problem, and it is believed to be very hard.

ECC's big advantage is efficiency: it gets the same security as RSA with much smaller keys.

Smaller keys mean faster handshakes and smaller certificates, so ECC has taken over much of modern cryptography:

• TLS key exchange (ECDHE, usually with the X25519 or P-256 curves) in almost every HTTPS connection.
• ECDSA and Ed25519 signatures in certificates, SSH keys and code signing.
• Passkeys and FIDO2 security keys, which sign login challenges with ECC (see Phishing-Resistant MFA).
• TPM-backed keys, Windows Hello, mobile devices and cryptocurrencies.

Here's the uncomfortable twist: Shor's algorithm breaks elliptic curves too, and because ECC keys are so much smaller, estimates suggest a quantum computer would need fewer logical qubits to break a 256-bit elliptic-curve key than a 2048-bit RSA key. Moving from RSA to ECC, which improved security against classical attacks, gives no protection against quantum ones.

Digital Signatures: Proving Who Sent It

Encryption keeps things secret. Signatures prove where something came from and that it hasn't been changed. The signer uses their private key to produce a signature over the data; anyone can check it with the public key.

Signatures are arguably even more important than encryption, because so much trust depends on them:

Almost all of these use RSA or ECDSA today. A quantum computer that can compute private keys from public keys can forge signatures: issue a fake certificate, sign malware so it looks like an official update, or mint login tokens.

TLS: Where It All Comes Together

TLS (the "S" in HTTPS) is the best place to see exactly what a quantum computer would and wouldn't break, because one connection uses all three kinds of cryptography.

This difference between the first two steps is the most important idea in quantum security:

• Key exchange and encryption are at risk retroactively. Anything recorded today could be decrypted on the day a large quantum computer exists. This is the "harvest now, decrypt later" threat.
• Signatures are at risk from that day forward. A forged signature can't change what was already verified, but every system that still trusts RSA or ECC signatures on that day can be fooled.

Certificates and PKI: A Long-Lived Chain of Trust

Certificates are how public keys are trusted at scale. A certificate binds a public key to a name (a website, a device, a user) and is signed by a certificate authority (CA). The CA's own certificate is signed by a higher CA, up to a root CA that operating systems and browsers trust directly. Intune, AD CS and Microsoft Cloud PKI all work this way, as covered in the PKI deep dive and the Cloud PKI vs AD CS comparison.

Every link in that chain is a signature, and almost every one uses RSA or ECDSA. That makes PKI the slowest part of the system to change, for three reasons:

• Roots live for decades. Root CA certificates are often valid for 20 years or more. A root created today may still be trusted after the date when quantum attacks become possible.
• Everything below the root must change too. Issuing CAs, templates, device certificates, relying parties (RADIUS, VPN gateways, web servers) and the devices that check them all need to support new algorithms.
• Hardware is involved. Smart cards, TPMs, HSMs, network appliances and embedded devices may only support the algorithms they shipped with.

You can see this on any Windows machine. This PowerShell lists the public-key algorithms in the local machine's trusted root and personal certificate stores:

# Which public-key algorithms do this machine's certificates use?
Get-ChildItem Cert:\LocalMachine\Root, Cert:\LocalMachine\My |
    Group-Object { $_.PublicKey.Oid.FriendlyName } |
    Select-Object Name, Count
 
# Trusted roots still valid after 2030
Get-ChildItem Cert:\LocalMachine\Root |
    Where-Object { $_.NotAfter -gt [datetime]'2030-01-01' } |
    Select-Object Subject, @{ n = 'Key'; e = { $_.PublicKey.Oid.FriendlyName } }, NotAfter

On the test machine used for this post, the first command found 32 RSA and 5 ECC certificates, and 24 trusted roots valid beyond 2030, including Microsoft's own 2011 root certificate authority, an RSA root valid until 2036. Every one of them is quantum-vulnerable. None of that is a problem today, but it shows how much of the trust chain was built long before anyone planned for quantum computers.

VPNs: The Same Problem, Again

VPNs use exactly the same building blocks:

• IPsec / IKEv2 (Always On VPN, many site-to-site tunnels) agrees keys with Diffie-Hellman or elliptic-curve Diffie-Hellman and authenticates with certificates.
• TLS-based VPNs (many SSL VPNs and OpenVPN) inherit TLS's key exchange and certificates.
• WireGuard uses Curve25519 for key exchange, with an optional pre-shared key that adds a layer of quantum resistance if it's managed properly.

So a recorded VPN session is a "harvest now, decrypt later" target in the same way as HTTPS, and it's often a more valuable one, because VPN traffic carries internal business data.

Shor's Algorithm: The Attack

Now the attacker's side. In 1994, Peter Shor showed that a quantum computer could solve both factoring and discrete logarithms, including the elliptic-curve version, exponentially faster than any known classical method. The algorithms post walks through it with a worked example (factoring 15); the essential idea is:

1. Factoring can be turned into finding the period of a repeating sequence of numbers.
2. A quantum computer puts many inputs into superposition at once and uses interference (through the Quantum Fourier Transform) to reveal that period.
3. A classical computer turns the period into the factors, and the factors into the private key.

Here is the threat as a chain, step by step:

Two things make this different from an ordinary vulnerability:

• It can't be patched. It isn't a bug in an implementation; it attacks the mathematics. The only fix is to replace the algorithms.
• Public keys are, by design, public. Every certificate, every TLS handshake and every signed file hands the attacker exactly the input Shor's algorithm needs.

What a Quantum Computer Does Not Break

The threat is serious but specific. Not all cryptography is affected equally:

Why is symmetric encryption safe? Grover's algorithm speeds up brute-force key search, but only by a square root: searching 2¹²⁸ keys takes about 2⁶⁴ quantum steps instead of 2¹²⁸ classical ones. That sounds alarming, but each quantum step is slow, the steps can't be spread across many machines efficiently, and the overheads of error correction are huge. NIST considers AES-128 secure for the foreseeable future, and AES-256 leaves an enormous margin. BitLocker, encrypted backups and AES-encrypted data at rest are not the main concern (see BitLocker and Endpoint Encryption), as long as the keys protecting them aren't themselves wrapped with RSA or ECC.

Reality Check: How Far Away Is This?

This is where many headlines go wrong, so it's worth being precise.

Where quantum computers are today. The largest machines have hundreds to a few thousand physical qubits, with error rates around 0.1% to 1% per operation, and error correction is only beginning to work (covered in Quantum Error Correction). Shor's algorithm on real hardware has factored only trivially small numbers like 15 and 21.

What's needed. A machine able to break RSA or ECC is often called a cryptographically relevant quantum computer (CRQC). In 2019, the best estimate for breaking RSA-2048 was about 20 million noisy physical qubits running for 8 hours. In 2025, Craig Gidney of Google cut that to under one million noisy qubits, running for under a week. Elliptic-curve keys are expected to need fewer resources than RSA-2048. Either way, that's a fault-tolerant machine with roughly a thousand or more logical qubits and billions of reliable operations.

When. Nobody knows. Vendor roadmaps aim at fault-tolerant machines around the end of this decade, but useful scientific machines and cryptographically relevant ones are not the same thing. Surveys of quantum experts give a meaningful (and growing) probability of a CRQC within 10 to 15 years, with wide disagreement. Government agencies plan around migration deadlines in the early-to-mid 2030s precisely because the date is uncertain.

Why It Matters Now: Harvest Now, Decrypt Later

If a CRQC is years away, why are governments setting deadlines today? Because of two facts that don't depend on when it arrives.

1. Recorded data can be decrypted later. An attacker who records encrypted traffic today (a VPN tunnel, an API call, a backup sent over TLS) can store it until a quantum computer exists. Intelligence agencies have warned about exactly this "harvest now, decrypt later" strategy. Data that must stay secret for many years (health records, legal and financial records, trade secrets, government and defence information, personal data with long legal retention) is already at risk.

2. Migration takes years. Replacing cryptography touches protocols, libraries, operating systems, applications, certificates, hardware security modules, smart cards, network appliances and vendor products. Large organisations have taken a decade or more to complete earlier cryptographic migrations, such as moving away from SHA-1.

Michele Mosca, a quantum computing researcher, turned these two facts into a simple test:

• x: how long your data must stay secret.
• y: how long it will take you to migrate to quantum-safe cryptography.
• z: how long until a cryptographically relevant quantum computer exists.

If x + y > z, you have a problem today. In the example, data must stay secret for 10 years and migration takes 7, so anything encrypted near the end of the migration must stay safe until year 17. If a CRQC arrives in year 12, five years of that data is exposed. You can't control z, but you can shorten y by starting early.

What's Affected in a Typical Organisation

What You Can Do Now

The fix is post-quantum cryptography (PQC): new public-key algorithms based on mathematical problems that are believed to be hard for quantum computers too. In August 2024, NIST published the first standards, ML-KEM (FIPS 203) for key exchange and ML-DSA (FIPS 204) and SLH-DSA (FIPS 205) for signatures. Its proposed transition plan deprecates RSA and elliptic-curve algorithms by 2030 and disallows them by 2035. Browsers and large websites already use hybrid key exchange, combining classical X25519 with ML-KEM, so much of your HTTPS traffic may already be protected against "harvest now, decrypt later" without you noticing.

Stage 09 covers PQC in depth. For now, these are the practical first steps:

Quick Recap

• Public-key cryptography (RSA and ECC) is the trust layer under HTTPS, VPNs, PKI, certificates and digital signatures.
• RSA relies on factoring being hard; ECC relies on the elliptic-curve discrete logarithm being hard. Shor's algorithm makes both easy on a large quantum computer.
• ECC is not safer against quantum attacks; it may fall sooner than RSA.
• In TLS, key exchange is at risk retroactively (harvest now, decrypt later), signatures from Q-day onward, and AES encryption hardly at all.
• PKI is the slowest part to change, because roots live for decades and hardware is involved.
• No quantum computer can break RSA or ECC today; the threat is a future, fault-tolerant machine, probably needing around a million physical qubits.
• It matters now because recorded data can be decrypted later and migration takes years: if x + y > z, act today.
• The fix is post-quantum cryptography, already standardised by NIST and already appearing in browsers.

What's Next on the Learning Path

The next stage, 09, Post-Quantum Cryptography: How Do We Protect the Internet?, explains the new algorithms (ML-KEM, ML-DSA, SLH-DSA), how hybrid key exchange works in TLS today, what crypto-agility means in practice, and how an enterprise, including its PKI and Intune certificates, can plan the migration. The full 11-stage path is listed at the end of the beginner's guide.