Navrhujú spôsob dešifrovania kľúčov RSA-2048
Skupina výskumníkov z rôznych vedeckých centier a univerzít šortky navrhol somn nový spôsob optimalizácier proces faktorizácie kľúčových parametrov RSA v kvantových počítačoch.
Podľa vyšetrovateľov, metóda, ktorú vyvinuli, umožňuje použitie kvantového počítača s 372 qubitmi na dešifrovanie kľúčov RSA-2048. Pre porovnanie, IBM Osprey, momentálne najvýkonnejší kvantový procesor, obsahuje 433 qubitov a do roku 2026 plánuje IBM postaviť systém Kookaburra so 4000 XNUMX qubitmi.
Za zmienku stojí to metóda je stále len teoretická, nebol odskúšaný v praxi a vyvoláva u niektorých kryptografov skepticizmus.
Šifrovanie RSA je založené na veľkom počte operácií umocňovania modulo. Verejný kľúč obsahuje modul a stupeň. Modul je vytvorený na základe dvoch náhodných prvočísel, ktoré pozná iba vlastník súkromného kľúča. Kvantové počítače umožňujú efektívne riešiť problém rozkladu čísla na prvočísla, pomocou ktorých možno syntetizovať súkromný kľúč z verejného.
Do teraz verilo sa, že vzhľadom na súčasný vývoj kvantových počítačov, RSA kľúče s veľkosťou 2048 bitov sa nedajú dlhodobo prelomiťKeďže kvantový počítač s miliónmi qubitov používa klasický Shorov algoritmus, vyžaduje veľa času na faktorizáciu 2048-bitového kľúča RSA.
Metóda, ktorú navrhli čínski vedci, spochybňuje tento predpoklad. a ak sa potvrdí, umožní prelomiť kľúče RSA-2048 nie v systémoch vzdialenej budúcnosti, ale v už existujúcich kvantových počítačoch.
Metóda je založená na Schnorrovom algoritme rýchleho faktorizácie. navrhnutý v roku 2021, ktorý umožňuje drastické zníženie počtu operácií pri výbere na bežných počítačoch. V praxi sa však ukázalo, že algoritmus je málo užitočný na prelomenie skutočných kľúčov, pretože fungoval iba pre kľúče RSA s malými hodnotami modulo (celé číslo, ktoré sa musí rozložiť na prvočísla). Zistilo sa, že algoritmus je neadekvátny na faktorizáciu veľkých čísel. Čínski vedci tvrdia, že pomocou kvantových metód sa im podarilo obísť obmedzenie Schnorrovho algoritmu.
Skepticizmus od niektorých kryptografov je spôsobené skutočnosťou čo dokazuje článok čínskych vedcov použitie vašej metódy len na malé čísla, zhruba v rovnakom poradí, pre ktoré funguje Schnorrov algoritmus. Napriek tvrdeniam, že bol prekročený limit veľkosti, zatiaľ neboli poskytnuté žiadne dôkazy ani podrobnosti. V praxi sa metóda ukazuje na faktor 48-bitových celých čísel pomocou 10-qubitového kvantového počítača.
Shorov algoritmus vážne spochybnil bezpečnosť informácií založených na kryptosystémoch s verejným kľúčom. Prelomiť široko používanú schému RSA-2048 si však vyžaduje milióny fyzických qubitov, čo výrazne presahuje súčasné technické možnosti. Tu uvádzame univerzálny kvantový algoritmus pre celočíselnú faktorizáciu kombináciou klasickej redukcie mriežky s kvantovým fuzzy optimalizačným algoritmom (QAOA).
Požadovaný počet qubitov je O(logN/loglogN), ktorý je sublineárny v celej bitovej dĺžke N, čo z neho robí doteraz najviac qubitový faktorizačný algoritmus. Algoritmus demonštrujeme experimentálne faktorizáciou celých čísel až do 48 bitov s 10 supravodivými qubitmi, čo je najväčšie celé číslo v kvantovom zariadení. Odhadujeme, že na napadnutie RSA-372 pomocou nášho algoritmu je potrebný kvantový obvod s 2048 fyzickými qubitmi a hĺbkou tisícov. Naša štúdia ukazuje veľký prísľub na urýchlenie aplikácie dnešných hlučných kvantových počítačov a pripravuje pôdu pre faktorizáciu veľkých celých čísel s realistickým kryptografickým významom.
Spomína sa, že predpoklad, že 372 fyzických qubitov bude stačiť na faktorizáciu kľúča RSA-2048, je teoretický, takže je veľmi pravdepodobné, že kvantová metóda založená na Schnorrovom algoritme má rovnaké problémy so škálovaním a nefunguje pri faktorizácii čísel. .
Ak sa problém so škálovaním naozaj vyrieši, bezpečnosť kryptoalgoritmov založených na zložitosti faktoringu veľkých prvočísel bude narušená nie z dlhodobého hľadiska, ako sa očakávalo, ale už dnes.
Nakoniec, ak máte záujem dozvedieť sa o tom viac, môžete si podrobnosti prečítať v nasledujúci odkaz.