Kvantecomputeren stjæler dine koder

Vi er derfor nødt til at finde nye måder at kryptere fortrolige oplysninger på, og også her ligger svaret i kvantemekanikken.

Kampen mellem kodeskabere og kodebrydere er dermed på vej ind i en ny æra, hvor den vil foregå med våben, begge parter henter i partikelfysikkens sære kvanteverden.

Kodeskaberne stikker af

Det historiske kapløb mellem kodeskabere og kodebrydere rækker længere tilbage end vores tidsregning. Hver gang kodeskabere har fundet nye måder at kryptere deres budskaber på, har det blot været et spørgsmål om tid, før koderne er blevet knækket.

Men i 1977 fik kodeskaberne pludselig et gigantisk forspring. Det skete med udviklingen af det såkaldte RSA-krypteringssystem, som er opkaldt efter opfinderne, matematikerne Ron Rivest, Adi Shamir og Len Adleman.

RSA-systemet bygger på, at krypteringen og afkodningen af den hemmelige information kræver to nøgler.

Afsenderen bruger en såkaldt offentlig nøgle til krypteringen – dvs. til at oversætte almindelig tekst til kodet tekst, som er uforståelig for andre, også selvom de har adgang til den offentlige nøgle.

Afkodningen af budskabet kræver nemlig en privat nøgle, som kun den retmæssige modtager er i besiddelse af.

Det matematiske grundlag for RSA-kryptering er primtal, dvs. tal, som kun er delelige med 1 og sig selv. Eksempler på primtal er 2, 3, 5, 7, 11, 13 og 17 – eller lidt større: 971, 977, 983, 991 og 997.

Til at skabe de to nøgler i RSA-systemet bruges der dog to meget større primtal, ofte med over hundrede cifre. De to tal ganges med hinanden, og ud fra resultatet – et såkaldt RSA-tal – dannes den offentlige nøgle. Den private nøgle er til gengæld baseret på både RSA-tallet og de to primtal.

Det geniale ved systemet er, at det er relativt nemt at udvikle nøglerne, men nærmest umuligt at regne sig frem til den private nøgle ud fra den offentlige.

Årsagen er, at de to primtal let kan ganges med hinanden, mens det er uhyre vanskeligt at finde de to tal, der blev ganget med hinanden. Faktorisering, som processen kaldes, kræver en enorm regnekraft og meget lang tid.

Med de store primtal, vi bruger til at beskytte vores data på internettet, vil selv nutidens hurtigste supercomputere være tusinder af år om at knække koden. I praksis er RSA-kryptering dermed ekstremt sikker.

Alligevel er eksperter enige om, at RSA-systemet står for fald. Hackerne vil nemlig få et nyt stærkt våben i hænderne: kvantecomputeren.

Kort fortalt gør kvantecomputeren op med en helt grundlæggende begrænsning ved den klassiske computer.

Hvad enten vi taler om processoren i din mobiltelefon eller NASA’s stærkeste supercomputere, virker de vha. såkaldt binære koder, dvs. rækker af nuller og 1-taller. Computerens mest basale enhed – en såkaldt bit – kan kun indtage én af to positioner ad gangen, 0 eller 1.

I kvantecomputeren kaldes den mindste enhed qubit, og den besidder nogle sære egenskaber, som hersker i kvantefysikkens verden. Her kan atomer eller mindre partikler som elektroner og fotoner være i flere tilstande samtidig, såkaldt superposition.

En qubit kan dermed ikke blot være 0 eller 1, men en mellemting af begge dele, og det giver kvantecomputeren en ufattelig høj regnehastighed.

Derfor frygter kodeskaberne, at kvantecomputere vil true sikkerheden i RSA-koderne – og det er netop, hvad kinesiske forskere har bevist i et nyt eksperiment.

Forskere jagter den hellige gral

I spidsen for forsøget stod Bao Yan fra State Key Laboratory of Mathematical Engineering and Advanced Computing. Forskerholdet udviklede en algoritme, som kan faktorisere RSA-tal, ved at dele regnearbejdet mellem en almindelig computer og en kvantecomputer.

Kvantecomputeren skulle kun tage sig af de mest tidskrævende trin i beregningerne, og derfor behøvede den ikke indeholde så mange qubit, som opgaven ellers ville kræve.

Ved hjælp af tre qubit faktoriserede forskerne tallet 1961, med fem qubit knækkede de tallet 48.567.227, og med ti qubit lykkedes det at bryde tallet 261.980.999.226.229 ned i de to primtalsfaktorer.

Og det er kun begyndelsen. Som de skriver i deres videnskabelige artikel:

“Vi mener, at et kvantekredsløb med 372 qubit vil kunne udfordre RSA-2048.”

RSA-2048 er med sine 617 cifre det største af alle RSA-tal – og derfor den hellige gral for matematikere, som arbejder med denne type faktorisering. Navnet har tallet fået, fordi der skal 2048 bit til at beskrive det med en binær kode.

Sammen med en række andre RSA-tal blev RSA-2048 offentliggjort i 1991 af det amerikanske sikkerhedsfirma RSA Laboratories. Det skete som led i en konkurrence under navnet “RSA Factoring Challenge”, som havde til formål at opmuntre matematikere til at udfordre RSA-systemet – og dermed også anskueliggøre, hvor sikkert det er.

Som en ekstra motivation udlovede firmaet store pengepræmier, heriblandt 200.000 dollars for faktoriseringen af RSA-2048.

Konkurrencen udløb i 2007, men ud af de i alt 54 RSA-tal er 31 stadig ikke blevet knækket.

I 2020 lykkedes det franske og amerikanske forskere at faktorisere det seneste og hidtil største med 250 cifre. Opgaven blev løst på nogle få måneder, men krævede titusindvis af computere – svarende til, at en enkelt computer ville have været 2700 år om det.

Der er dog stadig langt op til de 617 cifre, RSA-2048 indeholder, så hvis matematikerne skal nå den hellige gral inden for en overskuelig tidsramme, kræver det formentlig hjælp fra stærke kvantecomputere.

Allerede i 1994 fremlagde den amerikanske matematiker Peter Shor en algoritme, som i teorien kan gøre kvantecomputere i stand til at faktorisere store RSA-tal på kort tid. Siden har andre forskere vist, at metoden virker i praksis, men foreløbig kun med meget små tal. Faktisk er tallet 21 (3 gange 7) det største, det er lykkedes med.

Problemet er, at Shors algoritme kræver ekstremt mange qubit for at fungere pålideligt i stor skala. Eksperter har vurderet, at der måske skal helt op til en milliard til for at knække RSA-2048.

Ved at forenkle nogle af processerne i Shors algoritme bragte forskere i 2021 kravet ned på 20 millioner qubit, men det ligger stadig milevidt fra de kvantecomputere, som findes i dag. Den hidtil største er IBM’s Osprey fra 2022, som indeholder 433 qubit.

Derfor er det nye kinesiske resultat så opsigtsvækkende. Hvis Bao Yan og hans kolleger har ret i, at 372 qubit er nok til at klare opgaven, står RSA-2048 for fald langt tidligere, end matematikerne havde regnet med – måske allerede inden for de næste ti år.

Fotoner skjuler hemmeligheder

Når det lykkes at knække RSA-2048, er vores datasikkerhed på nettet truet, og det bliver derfor nødvendigt at skifte RSA-systemet ud med noget nyt.

Den allerbedste løsning er – ligesom kvantecomputeren – baseret på nogle specielle egenskaber i partikelfysikkens verden. Ved at udnytte polariseringen i fotoner er det muligt at kryptere information, som ingen andre end den retmæssige modtager kan afkode.

Hvis en hacker skulle forsøge at måle på fotonerne undervejs fra afsenderen til modtageren, vil det ændre deres polarisering, så angrebet omgående bliver opdaget.

En stor fordel ved kvantekrypteringen er, at infrastrukturen allerede findes. Fotonerne kan nemlig sendes gennem lyslederkablerne i det fibernet, som efterhånden er vidt udbredt.

Tilbage står udfordringen med at udvikle afsender- og modtagerudstyr, som er praktisk, småt og billigt nok til, at det kan installeres i alle de led, som udveksler fortrolig information via internettet.

Spørgsmålet er så, om det sker hurtigt nok. Efter mere end 40 år med den sikre og trygge RSA-kryptering er et nyt kapløb mellem kodeskabere og hackere skudt i gang – og vinderen bliver den part, som bedst udnytter kvantemekanikkens særheder.