Hvordan en kvantecomputer kunne bryde 2048-bit RSA-kryptering på 8 timer

Et nærbillede af D-Wave Vesuvius-chippen Steve Jurvetson | Flickr

Mange mennesker bekymrer sig om, at kvantecomputere vil være i stand til at knække visse koder, der bruges til at sende sikre beskeder. De pågældende koder krypterer data ved hjælp af matematiske funktioner, der fungerer let i den ene retning, men ikke i den anden. Det gør kryptering af data let, men at afkode det enormt vanskeligt uden hjælp af en speciel nøgle.

Disse krypteringssystemer har aldrig været ubrydelige. I stedet er deres sikkerhed baseret på den enorme tid, det ville tage for en klassisk computer at udføre arbejdet. Moderne krypteringsmetoder er specielt designet, så afkodning af dem vil tage så lang tid, at de er praktisk talt ubrydelige.

Men kvantecomputere ændrer denne tankegang. Disse maskiner er langt mere kraftfulde end klassiske computere og burde være i stand til at bryde disse koder med lethed.

Det rejser et vigtigt spørgsmål - hvornår vil kvantecomputere være kraftige nok til at gøre dette? Efter denne dato bliver enhver information, der er beskyttet af denne form for kryptering, usikker.

Så dataloger har forsøgt at beregne de ressourcer, sådan en kvantecomputer kan have brug for, og derefter regne ud, hvor lang tid der vil gå, før en sådan maskine kan bygges. Og svaret har altid været årtier.

I dag skal den tankegang revideres takket være arbejdet fra Craig Gidney hos Google i Santa Barbara og Martin Ekerå på KTH Royal Institute of Technology i Stockholm, Sverige. Disse fyre har fundet en mere effektiv måde for kvantecomputere at udføre de kodebrydende beregninger, hvilket reducerer de ressourcer, de kræver, i størrelsesordener.

Følgelig er disse maskiner væsentligt tættere på virkeligheden, end nogen anede. Resultatet vil gøre det ubehageligt at læse for regeringer, militær- og sikkerhedsorganisationer, banker og alle andre, der har brug for at sikre data i 25 år eller længere.

Først lidt baggrund. Tilbage i 1994 opdagede den amerikanske matematiker Peter Shor en kvantealgoritme, der udkonkurrerede sin klassiske ækvivalent. Shors algoritme faktoriserer store tal og er det afgørende element i processen til at knække falddørsbaserede koder.

Trapdoor-funktioner er baseret på multiplikationsprocessen, som er nem at udføre i én retning, men meget sværere at udføre i omvendt retning. For eksempel er det trivielt at gange to tal sammen: 593 gange 829 er 491.597. Men det er svært at starte med tallet 491.597 og regne ud, hvilke to primtal der skal ganges for at frembringe det.

Og det bliver stadig sværere i takt med, at tallene bliver større. Dataloger anser det faktisk for praktisk taget umuligt for en klassisk computer at faktorisere tal, der er længere end 2048 bit, hvilket er grundlaget for den mest almindeligt anvendte form for RSA-kryptering.

Shor viste, at en tilstrækkelig kraftig kvantecomputer kunne gøre dette med lethed, et resultat, der sendte chokbølger gennem sikkerhedsindustrien.

Og siden da har kvantecomputere været stigende i kraft. I 2012 brugte fysikere en fire-qubit kvantecomputer til faktor 143. Så i 2014 brugte de en lignende enhed til faktor 56.153.

Det er let at forestille sig, at kvantecomputere med denne fremskridtshastighed snart skulle kunne klare sig bedre end de bedste klassiske.

Ikke så. Det viser sig, at quantum factoring er meget sværere i praksis, end man ellers kunne forvente. Årsagen er, at støj bliver et væsentligt problem for store kvantecomputere. Og den bedste måde i øjeblikket at tackle støj på er at bruge fejlkorrigerende koder, der selv kræver betydelige ekstra qubits.

Hvis du tager dette i betragtning, øges de ressourcer, der kræves for at faktorisere 2048-bit tal, dramatisk. I 2015 anslog forskere, at en kvantecomputer ville have brug for en milliard qubits for at udføre arbejdet pålideligt. Det er betydeligt mere end de 70 qubits i nutidens avancerede kvantecomputere.

På den baggrund kunne sikkerhedseksperter meget vel have været i stand til at retfærdiggøre tanken om, at der ville gå årtier, før beskeder med 2048-bit RSA-kryptering kunne blive brudt af en kvantecomputer.

Nu har Gidney og Ekerå vist, hvordan en kvantecomputer kunne lave beregningen med blot 20 millioner qubits. Faktisk viser de, at en sådan enhed kun ville tage otte timer at fuldføre beregningen. [Som et resultat] er worst case-estimatet af, hvor mange qubits, der vil være nødvendige for at faktorisere 2048 bit RSA-heltal, faldet med næsten to størrelsesordener, siger de.

Deres metode fokuserer på en mere effektiv måde at udføre en matematisk proces kaldet modulær eksponentiering. Dette er processen med at finde resten, når et tal hæves til en bestemt potens og derefter divideres med et andet tal.

Denne proces er den mest beregningsmæssigt dyre operation i Shors algoritme. Men Gidney og Ekerå har fundet forskellige måder at optimere det på, hvilket væsentligt reducerer de nødvendige ressourcer til at køre algoritmen.

Det er interessant arbejde, der burde have vigtige konsekvenser for enhver, der gemmer information for fremtiden. En kvantecomputer på 20 millioner qubit virker bestemt som en fjern drøm i dag. Men spørgsmålet, disse eksperter bør stille sig selv, er, om en sådan enhed kunne være mulig inden for de 25 år, de ønsker at sikre informationen. Hvis de tror, ​​det er det, så har de brug for en ny form for kryptering.

Faktisk har sikkerhedseksperter udviklet post-kvantekoder, som selv en kvantecomputer ikke vil være i stand til at knække. Så det er allerede i dag muligt at sikre data mod fremtidige angreb fra kvantecomputere. Men disse koder er endnu ikke brugt som standard.

For almindelige mennesker er der ringe risiko. De fleste mennesker bruger 2048-bit kryptering eller noget lignende til opgaver som at sende kreditkortoplysninger over internettet. Hvis disse transaktioner registreres i dag og brydes om 25 år, vil der kun gå lidt tabt.

Men for regeringerne er der mere på spil. De beskeder, de sender i dag - mellem ambassader eller militæret, for eksempel - kan meget vel være vigtige om 20 år og derfor værd at holde hemmelige. Hvis sådanne meddelelser stadig sendes via 2048-bit RSA-kryptering eller noget lignende, bør disse organisationer begynde at bekymre sig - hurtigt.

Ref: arxiv.org/abs/1905.09749 : Sådan faktoriseres 2048 bit RSA-heltal på 8 timer ved hjælp af 20 millioner støjende qubits

skjule