Quantum Academy
A quantum computer running Shor’s algorithm, which Peter Shor published in 1994, would break RSA, Diffie-Hellman and elliptic-curve cryptography, the public-key half of cryptography. Against the symmetric half, AES and the SHA-2 hash functions, the main quantum attack is Grover’s algorithm, a speedup for brute-force search that reduces their security margin without breaking them. Shor’s attack needs a cryptographically relevant quantum computer (CRQC), and nobody knows when one will exist. One HTTPS connection uses public-key and symmetric cryptography together, so the question for any system is which half protects which step.
What each family does
Public-key cryptography uses a key pair, a public key anyone can have and a private key one party keeps secret. It has two jobs. In key establishment, two parties end up with the same secret key over an open network, through key agreement such as Diffie-Hellman and its elliptic-curve form ECDH, or by encrypting a key to the other party’s RSA public key. With a digital signature, made with RSA, ECDSA or EdDSA, anyone with the signer’s public key can check who produced the data and that nobody changed it.
Symmetric cryptography uses one secret key that both sides share, with AES as the standard cipher for bulk data. Hash functions such as SHA-256 take no key, but NIST classes them with the symmetric algorithms, and the same quantum attack applies to both. Public-key operations are far slower, so protocol designers use them only to set up a key.
One TLS session, both halves
Take one HTTPS connection over TLS 1.3, which RFC 9846 specifies, where your browser and the server negotiate X25519 key agreement, an ECDSA P-256 certificate and the cipher suite TLS_AES_128_GCM_SHA256.
Your browser sends an X25519 key share, a one-time elliptic-curve public key, and the server replies with its own. Each side combines its private value with the other’s share, and both compute the same 32-byte secret without sending it. The server proves its identity with its certificate and an ECDSA signature over the handshake, which your browser checks. Both sides then derive traffic keys from the secret using HKDF with SHA-256, and encrypt every record, TLS’s unit of data, with AES-128 in GCM mode. The cipher suite name describes only those last two steps, because in TLS 1.3 the browser and server negotiate key exchange and signatures separately.
| Step | In this session | Family | Quantum attack | Effect |
|---|---|---|---|---|
| Key agreement | X25519 | Public-key | Shor’s algorithm | Broken |
| Server authentication | ECDSA P-256 | Public-key | Shor’s algorithm | Broken |
| Key derivation | HKDF with SHA-256 | Hash | Grover’s algorithm | Margin reduced |
| Record encryption | AES-128-GCM | Symmetric | Grover’s algorithm | Margin reduced |
Factoring, discrete logarithms and Shor’s algorithm
RSA depends on factoring. Diffie-Hellman depends on the discrete logarithm problem, recovering a secret exponent from the result of raising a known number to that power modulo a prime, and elliptic-curve cryptography depends on the same problem over the points of a curve. All three have a periodic structure. Raise 7 to successive powers modulo 15 and you get 7, 4, 13, 1, then the same four again, a period of 4. Half the period gives 7² = 49, which is 4 modulo 15. The greatest common divisors of 15 with 3 and 5, the numbers one below and one above 4, are its factors. For a 2048-bit RSA modulus, the period is far too long to find by stepping through it. Shor showed that a quantum computer can find it using the quantum Fourier transform, a quantum form of frequency analysis, in a number of steps polynomial in the key length. Shor also gave an algorithm for discrete logarithms, which John Proos and Christof Zalka adapted to elliptic curves in 2003. No comparable shortcut is known for AES or SHA-2.
Grover’s algorithm and symmetric key sizes
With Lov Grover’s 1996 algorithm, a quantum computer can search N possibilities in about √N steps, where a classical search checks about half of them. For a 128-bit AES key, that’s roughly 2⁶⁴ steps instead of 2¹²⁷. For finding an input that produces a given SHA-256 output, it’s about 2¹²⁸ instead of 2²⁵⁶.
Christof Zalka proved in 1997 that the full speedup requires every Grover step to run in series. On k machines, a classical search runs k times faster and a Grover search about √k times faster. With 1,000 machines, the search finishes only about 32 times sooner. NIST concludes in its post-quantum FAQ that “AES 128 will remain secure for decades to come.”
Where did the AES key come from?
Usually from the public-key half, which is why “the data was AES-encrypted” doesn’t end the analysis. An attacker who recorded the TLS session above and later gets a CRQC never attacks AES. They compute the private value for one of the X25519 key shares in the recording and recompute the shared secret. The HKDF steps are public, so the AES keys for every record follow.
Forward secrecy doesn’t prevent this. TLS 1.3 removed static RSA key exchange, so an attacker who later steals the private key for a server’s certificate learns nothing about past sessions. That protection depends on nobody being able to compute a private value from its public share, and a CRQC could.
OpenPGP and S/MIME software encrypts each message’s symmetric key to the recipient’s RSA or elliptic-curve public key. An attacker who stores encrypted email can decrypt it once a CRQC exists. That’s how harvest now, decrypt later works, and which data is actually at risk depends on how long it must remain confidential.
The working rule
Replace the public-key algorithms with post-quantum cryptography (PQC), meaning public-key algorithms designed to resist both classical and quantum attack, and keep the symmetric ones at adequate sizes. NIST published the first three PQC standards on August 13, 2024: ML-KEM (Kyber) in FIPS 203 for key establishment, and ML-DSA (Dilithium) in FIPS 204 and SLH-DSA (SPHINCS+) in FIPS 205 for signatures. FN-DSA (Falcon) is due in the forthcoming FIPS 206.
Replace key establishment first wherever recorded traffic must remain confidential, because a recording made today can be decrypted once a CRQC exists. Signature forgery becomes possible only once a CRQC exists, but any system still verifying signatures after that day has to trust a post-quantum key before it. In the TLS session above, the first change is the hybrid group X25519MLKEM768, specified for TLS 1.3 in RFC 10024, which runs X25519 and ML-KEM-768 together so the session key remains secure as long as either algorithm does.
NIST sets out the same rule in its November 2024 draft transition report, IR 8547. It proposes disallowing RSA, Diffie-Hellman and elliptic-curve algorithms after 2035, and it states that approved symmetric primitives with at least 128 bits of classical security are believed to satisfy at least Category 1, NIST’s lowest post-quantum security level, defined by key search on AES-128. So adequate means at least AES-128 and SHA-256.
What CNSA 2.0 still approves
NSA’s Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) sets the algorithms for US National Security Systems, the networks that contain classified information or are otherwise critical to military and intelligence activities. NSA intends all of them to be quantum-resistant by 2035. In its CNSA 2.0 FAQ, NSA writes that quantum computing techniques are “generally considered much less effective against symmetric algorithms” and approves these, which it describes as essentially the same as in CNSA 1.0:
- AES-256, from FIPS 197, at all classification levels
- SHA-384 or SHA-512, from FIPS 180-4
- SHA3-384 or SHA3-512, from FIPS 202, for internal hardware functions only
Its public-key picks are new: ML-KEM-1024, ML-DSA-87, and LMS or XMSS from NIST SP 800-208 for signing software and firmware. NIST’s general guidance still accepts AES-128 and SHA-256, so CNSA 2.0 is the stricter of the two.
Post-Quantum Foundation is our starting course in post-quantum cryptography and covers the quantum threat to current cryptography, the NIST post-quantum standards and the regulatory drivers behind PQC migration, with no prior quantum knowledge required.
Mapping one system
Pick one system you’re responsible for and write down the algorithm at each of the four steps in the table. For a TLS 1.3 endpoint, the cipher suite name gives only the last two, so also record the negotiated key-exchange group and the server certificate’s key type. Put every step that uses RSA, Diffie-Hellman or an elliptic curve on your replacement list. Leave AES-128, SHA-256 and anything larger as they are, unless CNSA 2.0 applies, in which case the minimum is AES-256 and SHA-384.