211service.com
Hvordan en kvantedatamaskin kunne bryte 2048-biters RSA-kryptering på 8 timer
Et nærbilde av D-Wave Vesuvius-brikken Steve Jurvetson | Flickr
Mange bekymrer seg for at kvantedatamaskiner vil kunne knekke visse koder som brukes til å sende sikre meldinger. Kodene det er snakk om krypterer data ved å bruke matematiske funksjoner som fungerer lett i én retning, men ikke i den andre. Det gjør kryptering av data enkelt, men å dekode det enormt vanskelig uten hjelp av en spesiell nøkkel.
Disse krypteringssystemene har aldri vært uknuselige. I stedet er sikkerheten deres basert på den enorme tiden det vil ta for en klassisk datamaskin å gjøre jobben. Moderne krypteringsmetoder er spesielt utformet slik at dekoding av dem vil ta så lang tid at de er praktisk talt uknuselige.
Men kvantedatamaskiner endrer denne tankegangen. Disse maskinene er langt kraftigere enn klassiske datamaskiner og skal være i stand til å bryte disse kodene med letthet.
Det reiser et viktig spørsmål - når vil kvantedatamaskiner være kraftige nok til å gjøre dette? Etter denne datoen blir all informasjon som er beskyttet av denne formen for kryptering usikker.
Så informatikere har forsøkt å beregne ressursene en slik kvantedatamaskin kan trenge og deretter finne ut hvor lang tid det vil ta før en slik maskin kan bygges. Og svaret har alltid vært tiår.
I dag må denne tankegangen revideres takket være arbeidet til Craig Gidney ved Google i Santa Barbara og Martin Ekerå ved KTH Royal Institute of Technology i Stockholm, Sverige. Disse karene har funnet en mer effektiv måte for kvantedatamaskiner å utføre kodeknusende beregninger, og redusere ressursene de trenger i størrelsesordener.
Følgelig er disse maskinene betydelig nærmere virkeligheten enn noen mistenkte. Resultatet vil gjøre ukomfortabel lesing for regjeringer, militære og sikkerhetsorganisasjoner, banker og alle andre som trenger å sikre data i 25 år eller lenger.
Først litt bakgrunn. Tilbake i 1994 oppdaget den amerikanske matematikeren Peter Shor en kvantealgoritme som overgikk sin klassiske ekvivalent. Shor sin algoritme faktorer store tall og er det avgjørende elementet i prosessen for å knekke falldør-baserte koder.
Trapdoor-funksjoner er basert på multiplikasjonsprosessen, som er enkel å utføre i én retning, men mye vanskeligere å gjøre i revers. For eksempel er det trivielt å multiplisere to tall sammen: 593 ganger 829 er 491 597. Men det er vanskelig å starte med tallet 491 597 og finne ut hvilke to primtall som må multipliseres for å produsere det.
Og det blir stadig vanskeligere etter hvert som tallene blir større. Faktisk anser informatikere det som praktisk talt umulig for en klassisk datamaskin å faktorisere tall som er lengre enn 2048 biter, som er grunnlaget for den mest brukte formen for RSA-kryptering.
Shor viste at en tilstrekkelig kraftig kvantedatamaskin kunne gjøre dette med letthet, et resultat som sendte sjokkbølger gjennom sikkerhetsindustrien.
Og siden den gang har kvantedatamaskiner økt i kraft. I 2012 brukte fysikere en fire-qubit kvantedatamaskin til faktor 143. Så i 2014 brukte de en lignende enhet til faktor 56.153.
Det er lett å forestille seg at kvantedatamaskiner med denne fremskrittshastigheten snart skal kunne utkonkurrere de beste klassiske.
Ikke så. Det viser seg at kvantefaktoring er mye vanskeligere i praksis enn man ellers kunne forvente. Årsaken er at støy blir et betydelig problem for store kvantedatamaskiner. Og den beste måten å takle støy på er å bruke feilkorrigerende koder som krever betydelige ekstra qubits selv.
Å ta dette i betraktning øker dramatisk ressursene som kreves for å faktorisere 2048-bits tall. I 2015 anslo forskere at en kvantedatamaskin ville trenge en milliard qubits for å gjøre jobben pålitelig. Det er betydelig mer enn de 70 qubitene i dagens toppmoderne kvantedatamaskiner.
På det grunnlaget kunne sikkerhetseksperter godt ha vært i stand til å rettferdiggjøre ideen om at det ville ta flere tiår før meldinger med 2048-bits RSA-kryptering kunne bli ødelagt av en kvantedatamaskin.
Nå har Gidney og Ekerå vist hvordan en kvantedatamaskin kunne gjøre beregningen med bare 20 millioner qubits. De viser faktisk at en slik enhet vil ta bare åtte timer å fullføre beregningen. [Som et resultat] har verstefallsestimatet på hvor mange qubits som vil være nødvendig for å faktorisere 2048-biters RSA-heltall falt nesten to størrelsesordener, sier de.
Metoden deres fokuserer på en mer effektiv måte å utføre en matematisk prosess kalt modulær eksponentiering. Dette er prosessen med å finne resten når et tall heves til en viss potens og deretter divideres med et annet tall.
Denne prosessen er den mest beregningsmessig dyre operasjonen i Shors algoritme. Men Gidney og Ekerå har funnet ulike måter å optimalisere den på, og redusere ressursene som trengs for å kjøre algoritmen betydelig.
Det er interessant arbeid som bør ha viktige implikasjoner for alle som lagrer informasjon for fremtiden. En kvantedatamaskin på 20 millioner qubit virker absolutt som en fjern drøm i dag. Men spørsmålet disse ekspertene bør stille seg er om en slik enhet kan være mulig innen de 25 årene de ønsker å sikre informasjonen. Hvis de tror det er det, trenger de en ny form for kryptering.
Sikkerhetseksperter har faktisk utviklet postkvantekoder som selv en kvantedatamaskin ikke vil være i stand til å knekke. Så det er allerede mulig å sikre data i dag mot fremtidige angrep fra kvantedatamaskiner. Men disse kodene er ennå ikke brukt som standard.
For vanlige folk er det liten risiko. De fleste bruker 2048-biters kryptering, eller noe lignende, for oppgaver som å sende kredittkortopplysninger over internett. Hvis disse transaksjonene registreres i dag og brytes om 25 år, vil lite gå tapt.
Men for regjeringer er det mer som står på spill. Meldingene de sender i dag – mellom ambassader eller militæret, for eksempel – kan være viktige om 20 år og derfor verdt å holde hemmelig. Hvis slike meldinger fortsatt sendes via 2048-biters RSA-kryptering, eller noe lignende, bør disse organisasjonene begynne å bekymre seg – raskt.
Ref: arxiv.org/abs/1905.09749 : Hvordan faktorisere 2048 bit RSA-heltall på 8 timer ved å bruke 20 millioner støyende qubits