How do quantum computers affect different cryptographic algorithms, and what is post-quantum cryptography?
Quantum computers break RSA, DH, and ECC completely (Shor's algorithm). Symmetric ciphers and hash functions only lose half their security (Grover's algorithm). Post-quantum algorithms are designed to resist quantum attacks.
* Shor breaks the asymmetric family outright; Grover only halves symmetric strength. *
Impact of quantum computers:
| Algorithm | Classical Security | Quantum Security | Status |
|---|---|---|---|
| AES-128 | 128 bits | 64 bits (Grover) | Double key → AES-256 |
| AES-256 | 256 bits | 128 bits | Still secure |
| SHA-256 | 128 collision | 85 collision | Mostly OK |
| RSA-3072 | ~128 bits | Broken (Shor) | Must replace |
| DH-3072 | ~128 bits | Broken (Shor) | Must replace |
| ECC-256 | ~128 bits | Broken (Shor) | Must replace |
Shor's algorithm: Factors integers and computes discrete logs in polynomial time — completely breaks RSA, DH, ElGamal, ECC, DSA, ECDSA.
Grover's algorithm: Speeds up brute-force search quadratically — effectively halves key length. Manageable by doubling key sizes.
Post-quantum cryptography (PQC):
- NIST standardized the first PQC algorithms in 2024
- CRYSTALS-Kyber (now ML-KEM): Lattice-based key encapsulation
- CRYSTALS-Dilithium (now ML-DSA): Lattice-based signatures
- SPHINCS+ (now SLH-DSA): Hash-based signatures (conservative fallback)
- These are designed to resist both classical and quantum attacks
Timeline: Large-scale quantum computers capable of breaking RSA/ECC don't exist yet, but the "harvest now, decrypt later" threat means migration should start now.
Go deeper:
Post-quantum cryptography (Wikipedia) — the quantum threat and the lattice/hash-based replacements.- NIST Post-Quantum Cryptography project — the official standardization behind ML-KEM, ML-DSA and SLH-DSA.
- Shor's algorithm (Wikipedia) — why factoring and discrete logs fall in polynomial time.