Kvantecomputing og trusler mot kryptografi

En kvantecomputer med tilstrekkelig mange stabile qubits bryter de mest brukte asymmetriske kryptosystemene. To sentrale algoritmer:

Shors algoritme: Faktoriserer et heltall $n$ i polynomisk tid $O((\log n)^3)$. Bryter RSA, ElGamal og klassisk DH direkte. Bryter ECC analogt (diskret logaritme over elliptisk kurve).
Grovers algoritme: Søker i et ustrukturert rom av $N$ elementer på $O(\sqrt{N})$ (mot klassisk $O(N)$). Halverer effektiv nøkkelbit-lengde for symmetriske chiffer og hashfunksjoner.

Algoritme	Kvantetrussel	Post-kvantecomputer status
RSA-2048	Shors	Brutt
ECDH/ECDSA-256	Shors	Brutt
AES-128	Grovers	64-bit effektiv, svekket
AES-256	Grovers	128-bit effektiv, OK
SHA-256	Grovers	128-bit kollisjonssikkerhet, OK

Post-kvantum kryptografi (PQC)

PQC er kryptosystemer sikre mot both klassiske og kvantecomputere. Fire klasser:

Lattice-basert: Basert på Learning With Errors (LWE) og NTRU. Effektive, korte nøkler. Beste kandidat pr. i dag.
Hash-basert signaturer: Basert kun på hashfunksjonens sikkerhet. XMSS, SPHINCS+. Sikre men med begrenset antall signaturer.
Code-basert: McEliece (1978), basert på dekoding av tilfeldige lineærkoder. Meget store offentlige nøkler.
Multivariate: Basert på systemer av multivariate polynomlikninger. Effektiv verifisering, men store signaturer.

NIST PQC-standardisering

NIST startet standardisering i 2016. Første standarder publisert i 2024:

ML-KEM (CRYSTALS-Kyber, FIPS 203): Key Encapsulation Mechanism. Lattice-basert (Module LWE). Erstatter ECDH for nøkkelutveksling.
ML-DSA (CRYSTALS-Dilithium, FIPS 204): Digital signatur. Lattice-basert. Erstatter ECDSA.
SLH-DSA (SPHINCS+, FIPS 205): Hash-basert signatur. Konservativt sikkerhetsgrunnlag.

Harvest now, decrypt later (HNDL)

Angripere lagrer kryptert trafikk i dag for å dekryptere den når en kvantecomputer er tilgjengelig. Spesielt relevant for langlivede hemmeligheter (statshemmeligheter, medisinske data, sertifikater med lang levetid). Migrasjon til PQC bør begynne nå.

Hybride kryptosystemer: Under overgangen brukes hybride løsninger — klassisk (ECDH) kombinert med PQC (ML-KEM) i samme nøkkelutveksling. Sikker mot classical OG kvantecomputerangrep (angriperen må bryte begge).

Studieguide: Kvantesikker kryptografi

Studieguide: Kvantesikker kryptografi