De foreslår en metode for å dekryptere RSA-2048-nøkler
En gruppe av forskere fra ulike vitenskapelige sentre og universiteter kinesisk jeg fridden en ny måte å optimalisere pår faktoriseringsprosessen for RSA-nøkkelparameter i kvantedatamaskiner.
Ifølge etterforskerne metoden de utviklet tillater bruk av en kvantedatamaskin med 372 qubits for å dekryptere RSA-2048-nøkler. Til sammenligning inneholder IBM Osprey, den kraftigste kvanteprosessoren som for tiden er bygget, 433 qubits, og innen 2026 planlegger IBM å bygge et Kookaburra-system med 4000 qubits.
Det er verdt å nevne det Metoden er fortsatt bare teoretisk, den er ikke testet i praksis og skaper skepsis blant enkelte kryptografer.
RSA-kryptering er basert på eksponentieringsoperasjonen modulo et stort antall. Den offentlige nøkkelen inneholder modulen og graden. Modulen er dannet basert på to tilfeldige primtall som bare eieren av den private nøkkelen kjenner til. Kvantedatamaskiner gjør det mulig å effektivt løse problemet med å dekomponere et tall til primfaktorer, som kan brukes til å syntetisere en privat nøkkel fra en offentlig.
Inntil nå det ble antatt at, gitt den nåværende utviklingen av kvantedatamaskiner, RSA-nøkler med en størrelse på 2048 biter kan ikke knekkes på lenge, siden bruk av den klassiske Shor-algoritmen, krever en kvantedatamaskin med millioner av qubits mye tid for å faktorisere en 2048-bits RSA-nøkkel.
Metoden foreslått av kinesiske forskere sår tvil om denne antagelsen. og, hvis bekreftet, gjør det det mulig å knekke RSA-2048-nøkler ikke i systemer i en fjern fremtid, men i allerede eksisterende kvantedatamaskiner.
Metoden er basert på Schnorr rask faktoriseringsalgoritme. foreslått i 2021, som muliggjør en drastisk reduksjon i antall operasjoner når du velger på konvensjonelle datamaskiner. Imidlertid viste algoritmen seg i praksis å være til liten nytte for å knekke ekte nøkler, siden den bare fungerte for RSA-nøkler med små modulo-verdier (et heltall som må dekomponeres til primtall). Algoritmen ble funnet å være utilstrekkelig for å faktorisere store tall. Kinesiske forskere hevder at de ved hjelp av kvantemetoder klarte å omgå begrensningen til Schnorrs algoritme.
Skepsis fra noen kryptografer skyldes det faktum det viser artikkelen til de kinesiske forskerne bruke metoden din bare på små tall, omtrent samme rekkefølge som Schnorrs algoritme fungerer for. Til tross for påstander om at størrelsesgrensen er overskredet, er det ennå ikke gitt bevis eller detaljer. I praksis er metoden vist å faktorisere 48-bits heltall ved bruk av en 10-qubit kvantedatamaskin.
Shors algoritme har alvorlig utfordret sikkerheten til informasjon basert på offentlige nøkkelkryptosystemer. For å bryte den mye brukte RSA-2048-ordningen krever imidlertid millioner av fysiske qubits, som er langt utover dagens tekniske evner. Her rapporterer vi en universell kvantealgoritme for heltallsfaktorisering ved å kombinere klassisk gitterreduksjon med en kvantefuzzy optimeringsalgoritme (QAOA).
Antallet qubits som kreves er O(logN/loglogN), som er sublineært i heltallsbitlengden N, noe som gjør den til den mest qubit-besparende faktoriseringsalgoritmen til dags dato. Vi demonstrerer algoritmen eksperimentelt ved å faktorisere heltall på opptil 48 biter med 10 superledende qubits, det største heltallet som er faktorisert i en kvanteenhet. Vi anslår at en kvantekrets med 372 fysiske qubits og en dybde på tusenvis er nødvendig for å utfordre RSA-2048 ved å bruke vår algoritme. Vår studie viser et stort løfte om å akselerere bruken av dagens støyende kvantedatamaskiner og baner vei for å faktorisere store heltall av realistisk kryptografisk betydning.
Det nevnes at antakelsen om at 372 fysiske qubits vil være nok til å faktorisere en RSA-2048-nøkkel er teoretisk, så det er svært sannsynlig at kvantemetoden basert på Schnorrs algoritme har samme skaleringsproblem og ikke fungerer ved faktorisering av tall. .
Hvis problemet med skalering virkelig er løst, vil sikkerheten til kryptoalgoritmer basert på kompleksiteten ved å faktorisere store primtall bli undergravd ikke på lang sikt, som forventet, men allerede i dag.
Til slutt, hvis du er interessert i å kunne vite mer om det, kan du se detaljene i følgende lenke.