De föreslår en metod för att dekryptera RSA-2048-nycklar
En grupp av forskare från olika vetenskapliga centra och universitet chinos Jag friaden ett nytt sätt att optimerar faktoriseringsprocessen för RSA-nyckelparameter i kvantdatorer.
Enligt utredare, metoden de utvecklade tillåter användning av en kvantdator med 372 qubits för att dekryptera RSA-2048-nycklar. Som jämförelse innehåller IBM Osprey, den mest kraftfulla kvantprocessorn som byggs för närvarande, 433 qubits, och år 2026 planerar IBM att bygga ett Kookaburra-system med 4000 XNUMX qubits.
Det är värt att nämna det Metoden är fortfarande bara teoretisk, det har inte testats i praktiken och skapar skepsis bland vissa kryptografer.
RSA-kryptering är baserad på exponentieringsoperationen modulo ett stort antal. Den publika nyckeln innehåller modulen och graden. Modulen är bildad utifrån två slumpmässiga primtal som bara ägaren till den privata nyckeln känner till. Kvantdatorer gör det möjligt att effektivt lösa problemet med att sönderdela ett tal i primtalsfaktorer, som kan användas för att syntetisera en privat nyckel från en offentlig.
Hittills man trodde att, med tanke på den nuvarande utvecklingen av kvantdatorer, RSA-nycklar med en storlek på 2048 bitar kan inte knäckas under lång tid, eftersom man använder den klassiska Shor-algoritmen, kräver en kvantdator med miljontals kvantbitar mycket tid för att faktorisera en 2048-bitars RSA-nyckel.
Den metod som föreslagits av kinesiska forskare ställer tvivel på detta antagande. och, om det bekräftas, gör det det möjligt att knäcka RSA-2048-nycklar inte i system i en avlägsen framtid, utan i redan befintliga kvantdatorer.
Metoden är baserad på Schnorrs snabba faktoriseringsalgoritm. föreslog 2021, vilket möjliggör en drastisk minskning av antalet operationer när du väljer på konventionella datorer. Men i praktiken visade sig algoritmen vara till lite användbar för att knäcka riktiga nycklar, eftersom den bara fungerade för RSA-nycklar med små modulovärden (ett heltal som måste dekomponeras i primtal). Algoritmen visade sig vara otillräcklig för att faktorisera stora tal. Kinesiska forskare hävdar att de med hjälp av kvantmetoder kunde kringgå begränsningen i Schnorrs algoritm.
Skepsis från några kryptografer beror på det faktum som artikeln av de kinesiska forskarna visar tillämpa din metod endast på små tal, ungefär samma ordning som Schnorrs algoritm fungerar för. Trots påståenden om att storleksgränsen har överskridits har inga bevis eller detaljer ännu lämnats. I praktiken visas metoden att faktorisera 48-bitars heltal med hjälp av en 10-qubit kvantdator.
Shors algoritm har på allvar utmanat säkerheten för information baserad på kryptosystem med publik nyckel. Men för att bryta det allmänt använda RSA-2048-schemat krävs miljontals fysiska qubits, vilket är långt bortom nuvarande tekniska kapacitet. Här rapporterar vi en universell kvantalgoritm för heltalsfaktorisering genom att kombinera klassisk gitterreduktion med en kvantfuzzy optimeringsalgoritm (QAOA).
Antalet qubits som krävs är O(logN/loglogN), vilket är sublinjärt i heltalsbitlängden N, vilket gör den till den mest qubitsparande faktoriseringsalgoritmen hittills. Vi demonstrerar algoritmen experimentellt genom att faktorisera heltal på upp till 48 bitar med 10 supraledande kvantbitar, det största heltal som räknas in i en kvantenhet. Vi uppskattar att en kvantkrets med 372 fysiska qubits och ett djup på tusentals behövs för att utmana RSA-2048 med vår algoritm. Vår studie visar ett stort löfte om att påskynda tillämpningen av dagens bullriga kvantdatorer och banar väg för att faktorisera stora heltal av realistisk kryptografisk betydelse.
Det nämns att antagandet att 372 fysiska qubits kommer att räcka för att faktorisera en RSA-2048-nyckel är teoretiskt, så det är mycket troligt att kvantmetoden baserad på Schnorrs algoritm har samma skalningsproblem och inte fungerar vid factoring av tal. .
Om problemet med skalning verkligen är löst, kommer säkerheten för kryptoalgoritmer baserade på komplexiteten i att faktorisera stora primtal att undergrävas inte på lång sikt, som förväntat, utan redan idag.
Slutligen, om du är intresserad av att kunna veta mer om det, kan du konsultera detaljerna i följande länk.