Shors og Grovers algoritmer forklaret

Kvantecomputere kører ikke blot klassiske algoritmer hurtigere — de udnytter kvantesuperposition og interferens til at løse bestemte problemer eksponentielt hurtigere. To algoritmer truer det meste af den kryptografi, der er taget i brug: Shors (bryder RSA/ECC) og Grovers (svækker symmetriske algoritmer og hashfunktioner).

Shors algoritme (1994) løser heltalsfaktorisering og diskret logaritme i polynomiel tid på en kvantecomputer. Det bryder direkte RSA (baseret på faktorisering), Diffie-Hellman (diskret logaritme mod p) og ECDH/ECDSA (diskret logaritme på elliptiske kurver).

Den afgørende ingrediens i Shors algoritme er kvante-Fouriertransformationen (QFT) — en kvanteversion af DFT, der er eksponentielt hurtigere. Ved periodebestemmelse identificerer QFT perioden for f(x) = a^x mod N, hvorfra faktorerne i N udledes via GCD.

For at faktorisere N: (1) Vælg et tilfældigt a < N, og kontrollér gcd(a,N)=1. (2) Find perioden r for f(x)=a^x mod N ved hjælp af QFT. (3) Med høj sandsynlighed giver gcd(a^{r/2}±1, N) en ikke-triviel faktor. Det klassiske trin er O(log N); kvantebaseret periodebestemmelse er O((log N)^3) — polynomielt.

Bedste klassiske faktorisering: GNFS — subeksponentiel O(exp((64/9 log N)^{1/3} log log N)^{2/3})). Shors algoritme på en fejltolerant kvantecomputer: polynomiel O((log N)^3). RSA-2048 kræver ~4000 logiske qubits + ~10^9 gateoperationer. Dagens NISQ-computere har ~1000 støjende qubits — de udgør endnu ikke en trussel.

Grovers algoritme (1996) giver en kvadratisk hastighedsforbedring ved ustruktureret søgning. For et søgeområde med N elementer kræver klassiske algoritmer O(N) forespørgsler; Grovers algoritme kræver O(√N). Anvendt på kryptografi bryder den n-bit symmetriske nøgler i O(2^{n/2}) i stedet for O(2^n).

AES-128: klassisk sikkerhed 2^128, Grover reducerer den til 2^64 — usikker over for en stor kvantecomputer. AES-256: 2^256 → 2^128 — stadig sikker. Løsning: fordobl størrelsen på symmetriske nøgler. Kollisionsmodstanden i SHA-256: 2^128 → 2^85 (fødselsdagsangreb + Grover). Førbilledmodstanden i SHA-256: 2^256 → 2^128 — i orden.

De nuværende NISQ-kvantecomputere (IBM Heron: 133 qubits, Google Sycamore: 70 qubits) er for små og for støjende til kryptografisk relevante beregninger. Estimater for at bryde RSA-2048: 2035-2050 med fejltolerante kvantecomputere. Angreb, hvor data indsamles nu og dekrypteres senere, udgør allerede en aktuel trussel.

Angribere indsamler krypteret trafik i dag og gemmer den. Når en kvantecomputer bliver tilgængelig, dekrypterer de trafikken bagudrettet. Det gør langtidsholdbare hemmeligheder (klassificerede offentlige data, patientjournaler) sårbare allerede i dag. Migreringen til PQC skal begynde nu for sådanne data.

Gitterproblemer (LWE, SIS), kodebaserede problemer (McEliece), hashbaserede signaturer (SPHINCS+), multivariate problemer — der findes ingen kendt kvantealgoritme i polynomiel tid. Disse problemer danner grundlaget for NISTs postkvantestandarder.

NISTs PQC-standarder (ML-KEM, ML-DSA, SLH-DSA) blev færdiggjort i 2024. Organisationer bør: opgøre den aktuelle brug af kryptografi, identificere langtidsholdbare data og prioritere udrulning af PQC til nøgleudveksling (mest presserende på grund af angreb, hvor data indsamles nu og dekrypteres senere). Signaturer kan vente længere.

Shors algoritme (polynomiel tid) bryder RSA, DH og ECC. Grovers algoritme (kvadratisk hastighedsforbedring) halverer styrken af symmetriske nøgler. Løsning: migrér til NISTs PQC-standarder (gitterbaserede). Næste emne: CRYSTALS-Kyber KEM.