Classical Cryptography MOC

up:: Foundations MOC

Classical Cryptography

Classical cryptography is the set of math-based locks that protect essentially all digital data in use today, and it divides into two halves that the quantum threat treats completely differently: public-key (asymmetric) algorithms, which a large quantum computer breaks outright, and symmetric ciphers and hash functions, which survive the transition with larger sizes. Everything else about the field organizes itself once you hold that split. Shor’s algorithm destroys the public-key half, so RSA, ECC, and Diffie-Hellman all have to be replaced. Grover’s algorithm only dents the symmetric half, so AES-256 and the SHA-2 and SHA-3 hashes carry forward.

Map of content

A short overview of classical cryptography, and the index that routes you to every note in this section. Skim it to get oriented, then follow the links to go deep.

The short version:

• Classical cryptography has two families. Symmetric crypto uses one shared secret and does the bulk work; public-key crypto uses a public and private key pair and solves the problem of how strangers agree on a secret in the first place.
• Public-key breaks. RSA, ECDH, DH, ECDSA, and Ed25519 all rest on factoring or the discrete logarithm, and Shor’s algorithm solves both efficiently. A capable quantum computer ends them.
• Symmetric survives. Grover’s algorithm only halves the effective strength of AES and the SHA-2 and SHA-3 hashes, so AES-256 stays safe and AES-128 is the one to move up.
• The vulnerable public-key algorithms get replaced with post-quantum standards; the dented symmetric ones get upsized or kept. That’s why the whole transition is overwhelmingly a public-key migration.
• Real protocols like TLS use both halves together: public-key to agree on a key, then symmetric to encrypt the data. The public-key half is the exposed part.

Picture two kinds of lock. A symmetric lock takes one key that both people already share: it’s fast and strong, and its only real problem is getting that one key to the other person without a stranger grabbing it. A public-key lock is a padlock anyone can snap shut in the open, but only the owner’s private key opens it, which is exactly what lets two strangers set up a secret over a line everyone can hear. A quantum computer picks the public-key padlock and walks past the shared-key lock almost untouched, and that single asymmetry is the reason the migration is shaped the way it is.

What is classical cryptography?

Classical cryptography is the body of pre-quantum cryptographic algorithms in wide deployment today, the ones built and standardized for ordinary (classical) computers rather than for the post-quantum world. It covers four working parts that combine to protect real systems:

1. Symmetric ciphers encrypt bulk data with a single shared key. AES is the workhorse, and AES-256 is its strongest common size.
2. Cryptographic hash functions turn any input into a fixed-size fingerprint that proves data was not altered. SHA-256 and the wider SHA-2 and SHA-3 families do this.
3. Public-key (asymmetric) algorithms let strangers agree on a secret and prove identity over an open channel. RSA, ECC, and Diffie-Hellman are the core three.
4. The trust layer built on top of them, meaning digital signatures, the certificate system, and the certificate authorities that vouch for who owns which key.

The word “classical” here means pre-quantum, not old or weak. These are the algorithms running underneath every web session, VPN, signed software update, and encrypted backup right now. The reason they get a collective name is that the quantum transition forces a collective question about all of them at once: which survive, and which have to go.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov.

What’s the difference between symmetric and public-key cryptography?

Symmetric cryptography uses one shared secret for both locking and unlocking, and public-key cryptography uses a linked pair of keys where one is public and one is private. That one structural difference decides everything downstream, including how each half fares against a quantum computer.

Property	Symmetric cryptography	Public-key (asymmetric) cryptography
Keys	One shared secret, held by both parties	A public key anyone can hold plus a matching private key
Speed	Fast, built for bulk data	Slow, used for small setup steps
Core job	Encrypt the actual data, and fingerprint it	Agree on a shared secret, and prove identity
Rests on	Key size and a well-mixed design, no hidden structure	A hard math problem (factoring or the discrete logarithm)
Examples	AES-256, AES-128, SHA-256, SHA-2, SHA-3	RSA, ECC, DH, ECDSA, Ed25519
Quantum attack	Grover’s (quadratic speedup)	Shor’s (solves the exact math)
Quantum verdict	Weakened, survives at larger size	Broken, must be replaced

The one problem symmetric cryptography cannot solve on its own is the first one: how do two people who have never met agree on that shared secret over a line a stranger is listening to? Public-key cryptography exists precisely to answer that, and once it hands over a shared secret, the fast symmetric cipher takes over the heavy lifting. Hold that division of labor, because it is why breaking the public-key half is so much more consequential than denting the symmetric half.

Source: NIST SP 800-57 Part 1 Rev. 5, “Recommendation for Key Management,” 2020, csrc.nist.gov.

How does symmetric cryptography work, and what does quantum do to it?

Symmetric cryptography scrambles data with a shared key through many rounds of substitution and mixing, and its security comes from the plain fact that nobody can search a large enough key space by brute force. AES takes a 128-bit block of data and runs it through repeated rounds of byte substitution, row shifting, column mixing, and key addition, so that flipping one input bit changes roughly half the output. A hash function like SHA-256 does something related for integrity: it compresses any input into a fixed fingerprint that you cannot run backward and that changes unpredictably if a single bit of the input changes.

Against a quantum computer, the only relevant attack on this half is Grover’s algorithm, and Grover only speeds up brute-force search quadratically. Searching a space of N possibilities drops from about N steps to about √N steps, which halves the effective bit-strength of a key or a hash preimage. The practical consequences are mild and already understood:

1. AES-256 stays safe. Halved by Grover, its 256-bit key leaves about 128 bits of effective security, which is far beyond any foreseeable machine.
2. AES-128 is the one to move. The same halving drops it to about 64 bits of effective strength, below the comfort line for long-lived data, so the sensible move is standardizing on AES-256.
3. Hash functions carry forward. SHA-256 keeps roughly 128 bits of preimage strength under Grover, and its collision resistance is barely touched because the classical birthday bound already sat near 128 bits. NIST points to SHA-384 for the highest-assurance, longest-lived work, but SHA-256 is not structurally broken.

NIST states the general case plainly: Grover’s speedup “can have the effect of requiring larger key sizes, even in the symmetric key case,” and doubling the key size is enough to preserve security. The symmetric response is upsize, not replace, and there is no new symmetric family to migrate to.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov.

How does public-key cryptography work, and why does quantum break it?

Public-key cryptography gives every party a linked pair of keys, one published and one kept secret, and the two are joined by a math problem that is easy to compute one way and believed impossibly hard to reverse. RSA multiplies two large primes into a public modulus, and its security is that pulling that product back into its primes is factoring, which no efficient classical method solves at the sizes RSA uses. Elliptic-curve algorithms and Diffie-Hellman rest on the discrete logarithm problem instead, where multiplying a base point by a secret number is quick but recovering that number is believed hard. From those two hard problems come both of public-key cryptography’s jobs: agreeing on a shared secret (ECDH, DH, RSA key transport) and proving identity through signatures (ECDSA, Ed25519, RSA signatures).

The quantum threat to this half is total, and it comes from Shor’s algorithm, published by Peter Shor in 1994. Shor’s algorithm solves both integer factorization and the discrete logarithm in polynomial time on a fault-tolerant quantum computer. Because public-key security rests entirely on those problems being hard, a large enough machine recovers the private key directly from the public key, which is a structural collapse rather than a shrinking margin. Once the private key falls, the attacker can decrypt what the key protected and forge any signature it made.

Two facts sharpen why this is urgent rather than academic:

1. Bigger keys don’t rescue it. Shor’s cost grows only polynomially with key size, so moving from RSA-2048 to RSA-4096 raises the classical attacker’s cost enormously while barely inconveniencing the quantum one. The answer is to replace these algorithms rather than resize them.
2. Elliptic curves fall on a smaller machine than RSA. Because ECC packs equivalent classical strength into a much smaller number, a quantum computer has less to chew through. A widely cited estimate puts breaking a 256-bit curve at roughly 2,330 logical qubits, fewer than RSA of comparable classical strength needs, so retreating deeper into ECC to buy time is the wrong bet.

Source: P. W. Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” SIAM Journal on Computing, 1997, epubs.siam.org; M. Roetteler, M. Naehrig, K. Svore, K. Lauter, “Quantum Resource Estimates for Computing Elliptic Curve Discrete Logarithms,” ASIACRYPT 2017, arxiv.org.

Which classical algorithms does the quantum threat break, and what replaces them?

The single most useful table in the whole field sorts every common classical algorithm by which quantum attack applies, what the verdict is, and what to do about it. Read it top to bottom and the shape of the migration is obvious: everything in the “broken” rows is public-key and gets a new post-quantum standard, and everything in the “weakened” or “safe” rows is symmetric and gets upsized or kept.

Algorithm	Type	Rests on	Quantum attack	Verdict	Replacement or response
RSA (key transport)	Public-key	Factoring	Shor’s	Broken	ML-KEM
RSA (signatures)	Public-key	Factoring	Shor’s	Broken	ML-DSA / SLH-DSA
DH / DHE	Public-key	Discrete log	Shor’s	Broken	ML-KEM
ECDH / X25519	Public-key	EC discrete log	Shor’s	Broken	ML-KEM
ECC (curve family)	Public-key	EC discrete log	Shor’s	Broken	Post-quantum standards
ECDSA	Public-key	EC discrete log	Shor’s	Broken	ML-DSA / SLH-DSA
Ed25519 / Curve25519	Public-key	EC discrete log	Shor’s	Broken	ML-DSA / SLH-DSA
AES-128	Symmetric	Key size	Grover’s	Weakened	Move to AES-256
AES-256	Symmetric	Key size	Grover’s	Safe	Keep
SHA-256 / SHA-2	Hash	Output size	Grover’s	Mostly safe	Keep, or SHA-384 for high assurance
SHA-3	Hash	Output size	Grover’s	Mostly safe	Keep

Sources: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov; NIST IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards,” 2024, csrc.nist.gov; NIST, “NIST Releases First 3 Finalized Post-Quantum Encryption Standards,” August 13, 2024, nist.gov.

The PKI and certificate authority layer is not a separate algorithm in this table, but it inherits the verdict of whatever public-key algorithm signs its certificates, which is why a CA signing key is the highest-blast-radius target of the whole transition: break one, and every certificate under it can be forged.

Why does public-key fall while symmetric survives?

It comes down to structure. Public-key algorithms buy their magic (letting strangers set up a secret in the open) by embedding a specific mathematical structure, and that same structure is a handle a quantum computer can grab. Shor’s algorithm is not a faster brute-force search; it exploits the periodic structure hiding inside factoring and the discrete logarithm to solve them directly. Take away the hardness of those two problems and every algorithm resting on them stops working at once.

Symmetric ciphers and hash functions have no such structure to exploit. There is no shortcut number-theory to solve, just a large space of keys or preimages to search, so the only quantum tool that applies is Grover’s general-purpose search, and Grover is provably limited to a quadratic speedup. Quadratic is survivable: it just means a key twice as long restores the original margin. Shor’s exponential-to-polynomial collapse is not survivable by resizing, because the cost barely moves as the key grows.

So the honest headline is narrow. Quantum computers break the public-key half of cryptography and dent the symmetric half. That is why “quantum breaks all encryption” is the wrong framing, and why pointing remediation effort at AES wastes the effort that belongs on finding and replacing the vulnerable public-key algorithms around it.

Source: NIST, “Report on Post-Quantum Cryptography,” NISTIR 8105, April 2016, csrc.nist.gov.

How do the two halves work together in a real connection?

In practice, almost every secure connection uses both halves in sequence, and seeing that sequence is what makes the quantum exposure concrete. A TLS session, the protocol behind the browser padlock, runs in two stages:

1. Setup, using public-key. The browser and server authenticate with certificates (ECDSA or RSA signatures, vouched for by a CA) and agree on a shared secret using a key exchange (ECDH, very often X25519). This stage is small, slow, and done once per connection.
2. Bulk work, using symmetric. Once both sides hold the shared secret, they switch to AES (commonly AES-256-GCM) to encrypt every byte of the actual page, form, and API call, with SHA-2 hashing underneath for integrity. AES-GCM is the one cipher suite TLS 1.3 requires every implementation to support (specifically AES-128-GCM; AES-256-GCM and ChaCha20-Poly1305 are recommended).

A quantum computer attacks stage one. If it breaks the recorded key exchange, it recovers the shared secret and reads the AES traffic without ever attacking AES. This is why harvest now, decrypt later threatens even AES-256-encrypted sessions: an adversary records the whole exchange today and waits for a capable quantum computer to unlock the key-agreement step later. The AES layer was never the weak link; the public-key channel that delivered its key is the exposure.

Source: E. Rescorla, “The Transport Layer Security (TLS) Protocol Version 1.3,” RFC 8446, August 2018, rfc-editor.org.

When do these classical algorithms have to be gone?

The clock is set by NIST IR 8547, NIST’s transition roadmap, which puts every classical public-key algorithm on a deprecation-then-disallowance schedule while keeping the symmetric primitives at appropriate sizes. The two dates that matter for the broken half:

Milestone	Year	What it means
Deprecated	2030	112-bit-strength public-key (RSA-2048, P-224-class ECC) becomes deprecated: still usable, but only with the data owner formally accepting the risk
Disallowed	2035	All classical public-key at any size becomes disallowed for U.S. federal use, with no exceptions

Source: NIST IR 8547 (initial public draft), “Transition to Post-Quantum Cryptography Standards,” 2024, csrc.nist.gov.

The symmetric side has no such cliff. CNSA 2.0, the NSA suite for national-security systems, keeps AES-256 as the required symmetric cipher and keeps hashing in the SHA-2 family at SHA-384 or larger, the same advisory that retires RSA and ECDH. Because insurers, sector regulators, and procurement programs align to NIST and NSA, these dates function as the real industry timeline even for organizations that never touch a government contract.

Source: NSA, “Announcing the Commercial National Security Algorithm Suite 2.0,” CSA U/OO/194427-22, September 2022, nsa.gov.

Common misconceptions

1. “Quantum breaks all encryption, so everything has to be replaced.” It breaks the public-key half. Symmetric ciphers like AES-256 and hashes like SHA-256 survive with larger sizes, so the transition only replaces the public-key layer.
2. “Bigger keys will save RSA and ECC.” Enlarging a public key defends against classical attack, not against Shor’s algorithm, whose cost grows only polynomially with size. NIST is disallowing these algorithms at every size.
3. “Elliptic-curve crypto is newer, so it’s more quantum-safe than RSA.” The reverse holds. ECC’s compactness means it falls to a smaller quantum computer than RSA of equal classical strength, so it is the easier quantum target.
4. “AES-256 needs a post-quantum replacement.” There is no post-quantum symmetric family to move to, because AES-256 already carries enough margin. The replacements are for public-key algorithms.
5. “If my data is AES-256 encrypted, harvest-now-decrypt-later doesn’t apply.” It still applies, because the attacker targets the public-key key exchange that delivered the AES key, not the cipher itself.
6. “Signatures and encryption are separate quantum problems.” Both fall to the same break. Once Shor’s algorithm recovers a private key, the attacker can forge signatures and decrypt with the same key.

Questions people ask

What is the difference between symmetric and asymmetric cryptography in one line? Symmetric uses one shared key and does the fast bulk encryption; asymmetric (public-key) uses a public and private key pair to let strangers agree on that shared key and to prove identity. Real protocols use asymmetric to set up and symmetric to do the work.

Which classical algorithms are quantum-safe and which are not? AES-256 and the SHA-2 and SHA-3 hashes are considered safe with current sizes. RSA, ECC, Diffie-Hellman, ECDSA, and Ed25519 are broken by a quantum computer and have to be replaced.

Why does a quantum computer break public-key but not symmetric? Public-key security rests on factoring or the discrete logarithm, and Shor’s algorithm solves both directly. Symmetric security rests only on key size, where the best quantum attack, Grover’s, gives just a quadratic speedup you fix by doubling the key.

Do I need to replace AES? No, if you use AES-256. Move AES-128 up to AES-256 for anything long-lived, but there is no new algorithm to adopt; it’s a size change, not a family change.

Do I have to replace SHA-256? Generally no. SHA-256 keeps about 128 bits of effective strength under quantum search. Raise policy to SHA-384 where the assurance or data lifetime demands the wider margin, especially for national-security or decades-long integrity.

What replaces the broken public-key algorithms? ML-KEM takes over key establishment, and ML-DSA and SLH-DSA take over signatures, all finalized by NIST in August 2024. See the new standards for the full set.

When do the vulnerable algorithms have to be gone? NIST IR 8547 deprecates the weakest public-key strengths after 2030 and disallows all classical public-key for federal use after 2035. Anything that must stay secret past a quantum computer’s arrival is already exposed through harvest now, decrypt later.

Is my encrypted traffic already at risk? For confidentiality, yes, if it must stay secret for years, because recorded traffic can be decrypted once the key exchange is broken. For signatures and live trust, the risk starts when a quantum computer actually exists, which is why signing and PKI migrate on a deliberate track toward 2035.

Go deeper

Symmetric encryption: Symmetric-Key Cryptography · AES (Advanced Encryption Standard) (the AES umbrella note) · AES-256 · AES-192 · AES-128 · FIPS 197 · Block Cipher Modes (ECB, CBC, CTR, and XTS, and the move to AEAD) · Galois-Counter Mode (GCM) · ChaCha20-Poly1305 · Authenticated Encryption (AEAD) · Even-Mansour construction

Hashing: SHA-256 · SHA-384 · SHA-512 · 256 · SHA-2 · SHA-3 · SHAKE128 · SHAKE256 · SHA-1 · MD5 (the broken hash and the canonical migration lesson) · FIPS 180-4 · FIPS 202 · Merkle Tree

Public-key algorithms: RSA · RSA Padding (OAEP and PSS) (why textbook RSA is unsafe) · Elliptic-Curve Cryptography (ECC) · Diffie-Hellman (DH) · Elliptic-Curve Diffie-Hellman (ECDH) · Curve25519 · Ed25519 · X25519 · Curve448 · Ed448 · X448 · NIST P-256 · ECDSA · Pairing-Based Cryptography · FIPS 186-5

Keys and trust: Public Key Infrastructure (PKI) · Certificate Authority · X.509 Certificate · Certificate Revocation (CRL and OCSP) (revocation and the PQC size problem) · Certificate Transparency · PKCS

Implementation and its attacks: Side-Channel Analysis · Differential Power Analysis · Masking (Cryptographic Countermeasure) · Side-Channel and Fault Attacks on PQC

The hard problems underneath: discrete logarithm problem · integer factorization

Where the quantum threat comes from is in the threat; what NIST published to replace the broken algorithms is in the new standards; the classification of exactly what survives is in Quantum-Vulnerable Algorithm.

---

Everything here is the map, given freely. When your team needs its own classical cryptography sorted into what survives the quantum transition and what has to move, that’s the work I do, and there’s an alignment briefing for it.

Last verified 2026-07-09 · Maintained by Addie LaMarr, LaMarr Labs.