Kvantedatamaskinen stjeler kodene dine

Vi må derfor finne nye måter å kryptere fortrolige opplysninger på, og også her ligger svaret i kvantemekanikken.

Kampen mellom kodeskapere og kodeknekkere er dermed på vei inn i en ny tidsalder, der den vil foregå med våpen begge parter henter i partikkelfysikkens underlige kvanteverden.

Kodeskaperne tar ledelsen

Det historiske kappløpet mellom kodeskapere og kodeknekkere går tusenvis av år tilbake. Hver gang kodeskapere har funnet nye måter å kryptere budskapene sine på, har det bare vært et spørsmål om tid før kodene har blitt knekt.

Men i 1977 fikk kodeskaperne plutselig et gigantisk forsprang. Det skjedde med utviklingen av det såkalte RSA-systemet, som er oppkalt etter oppfinnerne, matematikerne Ron Rivest, Adi Shamir og Len Adleman.

RSA-systemet bygger på at krypteringen og avkodingen av den hemmelige informasjonen krever to nøkler.

Avsenderen bruker en såkalt offentlig nøkkel til krypteringen – altså til å oversette vanlig tekst til kodet tekst som er uforståelig for andre selv om de har tilgang til den offentlige nøkkelen.

Avkodingen av budskapet krever nemlig en privat nøkkel som bare den rettmessige mottageren har tilgang til.

Det matematiske grunnlaget for RSA-kryptering er primtall, altså tall som bare er delelige med 1 og seg selv. Eksempler på primtall er 2, 3, 5, 7, 11, 13 og 17 – eller litt større: 971, 977, 983, 991 og 997.

Til å lage de to nøklene i RSA-systemet brukes det imidlertid to mye høyere primtall, ofte med over hundre sifre. De to tallene ganges med hverandre, og ut fra resultatet – et såkalt RSA-tall – dannes den offentlige nøkkelen. Den private nøkkelen er derimot basert på både RSA-tallet og de to primtallene.

Det geniale med systemet er at det er relativt enkelt å utvikle nøklene, men mer eller mindre umulig å regne seg fram til den private nøkkelen ut fra den offentlige.

Årsaken er at de to primtallene enkelt kan ganges med hverandre, mens det er uhyre vanskelig å finne tilbake til de to tallene som ble ganget sammen. Faktorisering, som prosessen kalles, krever enorm regnekraft og veldig lang tid.

Med de høye primtallene vi bruker til å beskytte dataene våre på internett, vil selv dagens raskeste superdatamaskiner bruke tusenvis av år på å knekke koden. I praksis er RSA-kryptering dermed ekstremt trygg.

Likevel er eksperter enige om at RSA-systemet står for fall. Hackerne vil nemlig få et nytt sterkt våpen i hendene: kvantedatamaskinen.

Kort fortalt gjør kvantedatamaskinen slutt på en helt grunnleggende begrensning med den klassiske datamaskinen.

Uansett om vi snakker om prosessoren i mobiltelefonen eller Nasas sterkeste superdatamaskiner, er alt de gjør, basert på å behandle binære sifre, altså sekvenser av nuller og ettall. Datamaskinens mest grunnleggende enhet – en såkalt bit – har bare to mulige tilstander: 0 og 1, eller på og av, om man vil.

I kvantedatamaskinen kalles den minste enheten qubit, og den har noen underlige egenskaper som man bare ser i kvantefysikkens verden. Her kan atomer eller mindre partikler som elektroner og fotoner være i flere tilstander samtidig, såkalt superposisjon.

En qubit kan dermed ikke bare være 0 eller 1, men en mellomting, og det gir kvantedatamaskinen en ufattelig høy regnehastighet.

Derfor frykter kodeskaperne at kvantedatamaskiner vil true sikkerheten i RSA-kodene – og det er nettopp det kinesiske forskere har bevist i et nytt eksperiment.

Forskere jakter på den hellige gral

I spissen for forsøket sto Bao Yan ved det statlige kinesiske laboratoriet for matematikk og informatikk. Forskergruppen utviklet en algoritme for å faktorisere RSA-tall ved å dele regnearbeidet mellom en vanlig datamaskin og en kvantedatamaskin.

Kvantedatamaskinen skulle bare ta seg av de mest tidkrevende trinnene i beregningene, og derfor trengte den ikke inneholde så mange qubit som oppgaven ellers ville kreve.

Med tre qubit faktoriserte forskerne tallet 1961, med fem qubit faktoriserte de tallet 48 567 227, og med ti qubit klarte de å faktorisere tallet 261 980 999 226 229. Tallene har det til felles at de bare har to primtallsfaktorer.

Og dette er bare begynnelsen. I artikkelen skriver forskerne:

«Vi mener at et kvantekretsløp med 372 qubit kan utfordre RSA-2048.»

RSA-2048 er med sine 617 sifre det største av alle RSA-tall – og derfor den hellige gral for matematikere som jobber med denne typen faktorisering. Navnet har tallet fått fordi man trenger 2048 bit for å skrive det i binærkode.

Sammen med en rekke andre RSA-tall ble RSA-2048 offentliggjort i 1991 av det amerikanske sikkerhetsfirmaet RSA Laboratories. Det skjedde som et ledd i en konkurranse som ble kalt RSA-utfordringen, og som skulle oppmuntre matematikere til å utfordre RSA-systemet – og dermed også finne ut hvor sikkert det er.

Som en ekstra motivasjon utlovet firmaet store pengepremier, blant annet 200 000 dollar for faktoriseringen av RSA-2048.

Konkurransen ble avsluttet i 2007, men av de i alt 54 RSA-tallene er det 31 som fortsatt ikke har blitt knekt.

I 2020 klarte franske og amerikanske forskere å faktorisere det siste og hittil største, med 250 sifre. Oppgaven ble løst på noen få måneder, men krevde titusenvis av datamaskiner. En enkelt datamaskin ville ha brukt 2700 år.

Det er likevel langt opp til de 617 sifrene som RSA-2048 inneholder, så hvis matematikerne skal nå den hellige gral innen overskuelig tid, krever det antagelig hjelp fra kraftige kvantedatamaskiner.

Allerede i 1994 presenterte den amerikanske matematikeren Peter Shor en algoritme som i teorien kan gjøre kvantedatamaskiner i stand til å faktorisere høye RSA-tall på kort tid. Senere har andre forskere vist at metoden virker i praksis, men foreløpig bare med veldig små tall. Faktisk er tallet 21 (3 ganger 7) det største det har klart.

Problemet er at Shors algoritme krever ekstremt mange qubit for å fungere pålitelig i stor skala. Eksperter har ment at det kanskje kreves opptil en milliard qubit for å knekke RSA-2048.

Ved å forenkle noen av prosessene i Shors algoritme fikk forskere i 2021 kravet ned til tjue millioner qubit, men det ligger fortsatt milevidt fra de kvantedatamaskinene som finnes i dag. Den hittil største er IBMs Osprey fra 2022, som inneholder 433 qubit.

Derfor er det nye kinesiske resultatet så oppsiktsvekkende. Hvis Bao Yan og kollegene hans har rett i at 372 qubit er nok til å klare oppgaven, står RSA-2048 for fall mye tidligere enn matematikerne hadde regnet med – kanskje allerede i løpet av de neste ti årene.

Fotoner skjuler hemmeligheter

Når det lykkes å knekke RSA-2048, er datasikkerheten vår på nettet truet, og det blir derfor nødvendig å bytte ut RSA-systemet med noe nytt.

Den aller beste løsningen er – akkurat som kvantedatamaskinen – basert på mekanismer som bare finnes i partikkelfysikkens verden. Ved å utnytte polariseringen i fotoner er det mulig å kryptere informasjon som ingen andre enn den rettmessige mottageren kan avkode.

Hvis en hacker skulle forsøke å måle fotonene på veien fra avsenderen til mottageren, vil det endre polariseringen slik at angrepet blir oppdaget umiddelbart.

En stor fordel med kvantekrypteringen er at infrastrukturen allerede finnes. Fotonene kan nemlig sendes gjennom lyslederkablene i fibernettet som etter hvert er i bruk mange steder.

Utfordringen er å utvikle avsender- og mottagerutstyr som er praktisk, lite og billig nok til at det kan installeres i alle leddene som utveksler fortrolig informasjon via internett.

Spørsmålet er også om det skjer raskt nok. Etter mer enn førti år med den trygge RSA-krypteringen er et nytt kappløp mellom kodeskapere og hackere i gang – og vinneren blir den parten som best utnytter kvantemekanikkens særegenheter.