When quantum computers arrive, RSA and ECC break overnight. This research examines the algorithms being standardized to replace them — and implements them with real cryptographic libraries.
2024 · SVCSI · Stanford University
This research examined five key cryptographic algorithms, tracing the evolution from historical ciphers to the lattice-based constructions being standardized by NIST for the post-quantum era.
128-bit block, 128/192/256-bit keys, 10–14 rounds. Quantum-resistant at AES-256; Grover's algorithm halves effective key length, so AES-128 drops to ~64-bit security post-quantum.
Security rests on integer factorization hardness. Shor's algorithm solves this in polynomial time on a quantum computer, making RSA completely insecure in the post-quantum era.
Lattice-based Key Encapsulation Mechanism. Security rests on Module-LWE problem. Selected by NIST for standardization in 2022; being deployed in TLS and SSH implementations now.
56-bit key, 64-bit block cipher. Brute-forced in 22 hours in 1999. Studied as a historical baseline — illustrates why key length and algorithm choice both matter for security longevity.
Keccak sponge construction (SHA-3). Strong resistance under Grover's algorithm, though effective security is halved — requiring double the output length for post-quantum applications.
Lattice-based digital signature scheme. Security based on Module-LWE and Module-SIS hardness problems. NIST's primary recommendation for post-quantum digital signatures.
Julius Caesar protected military orders by shifting each letter by a fixed number. A shift of 3 turns "HELLO" into "EBIIL." Simple — but it establishes the fundamental concept of a key-controlled transformation.
AES operates on 128-bit data blocks arranged in a 4×4 byte state matrix. Each of the 10–14 rounds applies four distinct operations in sequence. Click any operation to understand what it does.
Quantum computing doesn't threaten all cryptography equally. The impact depends entirely on which mathematical problem underlies the scheme.
Solves integer factorization and discrete logarithm problems in polynomial time on a quantum computer. This completely breaks RSA, Diffie-Hellman, and ECC — the foundations of today's internet security. No mitigation exists; the algorithms must be replaced.
Provides a quadratic speedup for unstructured search problems. This halves the effective bit-security of symmetric ciphers — AES-128 drops to ~64-bit, but AES-256 remains strong at ~128-bit post-quantum security. Mitigation is straightforward: double the key length.
Bit-security of each algorithm under each threat model. Note how RSA collapses to zero under Shor's, while Kyber holds its ground.
The Learning With Errors (LWE) problem provides security that appears hard for both classical and quantum computers — unlike the factorization and discrete-log problems that Shor's breaks.
A lattice is a regular grid of points in n-dimensional space. The visualization shows a 2D lattice (white dots) with an observed vector (blue) that has been perturbed by small random error.
Given public matrix A and observed vector b, recover secret s knowing only that error e is small. Even for quantum computers, this appears computationally infeasible in high dimensions.
Kyber is a Key Encapsulation Mechanism. Alice generates a key pair and shares her public key. Bob encapsulates a shared secret using it. Alice decapsulates with her private key. Both end up with the same shared secret K — which neither ever transmitted.
Generates a public key pk and secret key sk using the Module-LWE problem structure.
Receives ciphertext c from Bob. Uses her secret key sk to recover the shared secret K.
K — shared secret ✓Receives Alice's public key pk. Generates a shared secret K and ciphertext c that encapsulates it using pk.
K — shared secret ✓Three open-source cryptographic libraries were used to implement and test algorithms ranging from classical to post-quantum schemes.
# AES-256-CBC encryption with OpenSSL $ openssl enc -aes-256-cbc -salt \ -in plaintext.txt \ -out encrypted.bin \ -pass pass:your_passphrase # Decrypt $ openssl enc -d -aes-256-cbc \ -in encrypted.bin \ -out decrypted.txt \ -pass pass:your_passphrase # Generate RSA key pair (classical — will be broken post-quantum) $ openssl genpkey -algorithm RSA -pkeyopt rsa_keygen_bits:4096 -out private.pem $ openssl rsa -in private.pem -pubout -out public.pem
from nacl import public, encoding # Generate Curve25519 key pair alice_sk = public.PrivateKey.generate() alice_pk = alice_sk.public_key # Encrypt message from Bob to Alice from nacl.public import Box bob_sk = public.PrivateKey.generate() box = Box(bob_sk, alice_pk) encrypted = box.encrypt(b"Hello, Alice!") # Alice decrypts alice_box = Box(alice_sk, bob_sk.public_key) plaintext = alice_box.decrypt(encrypted) # Signing with Ed25519 from nacl.signing import SigningKey signing_key = SigningKey.generate() signed = signing_key.sign(b"message")
import oqs # Kyber-768 KEM — post-quantum key encapsulation with oqs.KeyEncapsulation('Kyber768') as alice: # Alice generates her key pair public_key = alice.generate_keypair() # Bob encapsulates: generates ciphertext + shared secret with oqs.KeyEncapsulation('Kyber768') as bob: ciphertext, shared_secret_bob = bob.encap_secret(public_key) # Alice decapsulates using her secret key shared_secret_alice = alice.decap_secret(ciphertext) # Both parties now hold the same shared secret assert shared_secret_alice == shared_secret_bob # True ✓ print(f"Shared secret: {shared_secret_alice.hex()[:32]}...")
Unlike RSA and ECC, lattice-based schemes resist both classical and quantum attacks. The Shortest Vector Problem (SVP) and Learning With Errors have no known efficient quantum algorithms.
Kyber and Dilithium are not experimental. They're being deployed in TLS, SSH, and Signal Protocol implementations today. The standardization process took 6 years and multiple cryptanalysis rounds.
With Grover's algorithm only halving effective key length, AES-256 retains approximately 128-bit post-quantum security — well above the 80-bit threshold considered secure today.
Not "if" but "when." Harvest-now-decrypt-later attacks mean adversaries are collecting encrypted traffic today to decrypt once quantum computers arrive. Migration needs to start now.