Grunnleggende
Shors algoritme og Grovers algoritme
De to kvantealgoritmene som avgjør hva som må byttes ut, og hva som kan beholdes.
Hvorfor kryptografi bygger på «vanskelige» problemer
Mye av moderne kryptografi bygger på at et matematisk problem er lett å sette opp men vanskelig å løse uten en hemmelighet. For RSA er det å gange to store primtall (lett) mot å finne dem igjen fra produktet (vanskelig). For Diffie–Hellman og elliptiske kurver er det diskrete logaritmeproblemet. De beste klassiske algoritmene bruker tid som vokser raskt med nøkkelstørrelsen, derfor er 2048-bits RSA trygt i dag.
Hva Shors algoritme gjør
Shors algoritme, publisert av Peter Shor i 1994, viser at begge problemene kan løses effektivt på en kvantedatamaskin. Intuisjonen er at begge kan omformes til å finne perioden i en repeterende funksjon. Kvantedatamaskiner er særlig gode på det, fordi de kan sette et register i en superposisjon av mange verdier og bruke den kvantemekaniske Fouriertransformasjonen til å lese av perioden. Fra perioden kan man regne seg tilbake til primtallsfaktorene eller den hemmelige eksponenten med vanlig tallteori.
Konsekvensen er at tiden for å bryte nøkkelen øker polynomisk, ikke eksponentielt, med nøkkelstørrelsen. Å doble RSA-nøkkelen gjør derfor ikke angrepet vesentlig vanskeligere.
Hva som rammes
| Algoritme | Matematisk problem | Brytes? |
|---|---|---|
| RSA | Faktorisering | Ja |
| Diffie–Hellman (DH) | Diskret logaritme | Ja |
| ECDH, ECDSA, X25519, Ed25519 | Diskret logaritme på elliptiske kurver | Ja |
| DSA, ElGamal | Diskret logaritme | Ja |
Elliptiske kurver krever faktisk færre qubits å bryte enn RSA med tilsvarende sikkerhet i dag. De kortere nøklene som gjør dem effektive, gjør dem altså også til det første målet.
Grovers algoritme: en mindre trussel
Lov Grover viste i 1996 at en kvantedatamaskin kan søke i en usortert samling med N elementer på omtrent √N steg, mot N steg klassisk. Mot et kryptografisk søk betyr det at en nøkkel med n bits sikkerhet effektivt blir til omtrent n/2 bits. AES-128 får da i teorien rundt 64 bits kvantesikkerhet.
I praksis er trusselen svakere enn det høres ut. Grovers algoritme lar seg dårlig parallellisere, og hvert steg krever en dyr, feilrettet kvanteberegning av AES. Likevel anbefaler mange myndigheter 256-bits nøkler for symmetrisk kryptering som en enkel ekstra margin.
| Shors algoritme | Grovers algoritme | |
|---|---|---|
| Hastighetsgevinst | Eksponentiell (polynomisk tid) | Kvadratisk |
| Rammer | RSA, DH, elliptiske kurver | Symmetriske nøkler, hashfunksjoner |
| Løsning | Bytt til post-kvante-algoritmer | Bruk 256-bits nøkler og hash med minst 256 bits utdata |
Hvor stor må kvantedatamaskinen være?
Å kjøre Shors algoritme mot en 2048-bits RSA-nøkkel krever ikke bare mange qubits, men qubits som er så feilfrie at beregningen kan kjøre i timer eller dager. Fysiske qubits er svært feilutsatte, så man må sette sammen mange av dem til ett logisk qubit ved hjelp av feilrettende koder. Anslagene har gått kraftig ned over tid:
- 2012: omtrent én milliard fysiske qubits.
- 2019: Gidney og Ekerå anslo rundt 20 millioner støyende qubits og åtte timer.
- 2025: Gidney anslo under én million støyende qubits og under én uke.
Dagens største maskiner har noen hundre til noen tusen fysiske qubits, så gapet er fortsatt stort. Les mer i Når kommer kvantedatamaskinen?
Vanlige misforståelser
- «Kvantedatamaskiner prøver alle nøkler samtidig.» Nei. De utnytter matematisk struktur (som perioder). Mot problemer uten slik struktur, som godt valgte hashfunksjoner, hjelper de bare lite.
- «Det er allerede gjort i praksis.» Demonstrasjoner av Shor har faktorisert små tall som 15 og 21. Ingen har knekt en reell nøkkel.
- «AES er ødelagt.» Nei. Se Grover over.
- «Kvantekryptering er løsningen.» Det vanlige svaret er PQC, ikke QKD.
Vanlige spørsmål
Hvem oppfant Shors algoritme?
Matematikeren Peter Shor publiserte algoritmen i 1994, mens han arbeidet ved Bell Labs.
Kan Shors algoritme bryte Bitcoin?
Bitcoin bruker elliptiske kurver (ECDSA og Schnorr) for signaturer, som Shors algoritme kan bryte. Derfor diskuteres post-kvante-signaturer også i kryptovaluta-miljøene. Selve SHA-256 som brukes i utvinning er i liten grad truet.
Hva er forskjellen på fysiske og logiske qubits?
Et fysisk qubit er maskinvare med feil. Et logisk qubit er satt sammen av mange fysiske qubits med feilretting og oppfører seg som et nesten feilfritt qubit. Kryptoangrep krever logiske qubits.