Navrhují způsob dešifrování klíčů RSA-2048
Skupina vědci z různých vědeckých center a univerzit Chinos navrhl jsemn nový způsob optimalizacer proces faktorizace klíčových parametrů RSA v kvantových počítačích.
Podle vyšetřovatelů, metoda, kterou vyvinuli, umožňuje použití kvantového počítače s 372 qubity k dešifrování klíčů RSA-2048. Pro srovnání, IBM Osprey, aktuálně nejvýkonnější kvantový procesor, obsahuje 433 qubitů a do roku 2026 plánuje IBM postavit systém Kookaburra se 4000 XNUMX qubity.
Za zmínku stojí metoda je zatím jen teoretická, nebyl v praxi testován a mezi některými kryptografy vyvolává skepsi.
Šifrování RSA je založeno na operaci umocňování velkého počtu modulů. Veřejný klíč obsahuje modul a stupeň. Modul je tvořen na základě dvou náhodných prvočísel, která zná pouze vlastník soukromého klíče. Kvantové počítače umožňují efektivně řešit problém rozkladu čísla na prvočinitele, pomocí kterých lze syntetizovat soukromý klíč z veřejného.
Zatím věřilo se, že vzhledem k současnému vývoji kvantových počítačů, klíče RSA o velikosti 2048 bitů nelze dlouhodobě prolomitProtože používá klasický Shorův algoritmus, kvantový počítač s miliony qubitů vyžaduje spoustu času na faktorování 2048bitového klíče RSA.
Metoda navržená čínskými výzkumníky tento předpoklad zpochybňuje. a pokud se to potvrdí, umožní to prolomit klíče RSA-2048 nikoli v systémech vzdálené budoucnosti, ale v již existujících kvantových počítačích.
Metoda je založena na Schnorrově rychlém faktorizačním algoritmu. navržený v roce 2021, který umožňuje drastické snížení počtu operací při výběru na konvenčních počítačích. V praxi se však ukázalo, že algoritmus je pro prolomení skutečných klíčů málo užitečný, protože fungoval pouze pro klíče RSA s malými hodnotami modulo (celé číslo, které je třeba rozložit na prvočísla). Algoritmus byl shledán neadekvátním pro faktorizaci velkých čísel. Čínští vědci tvrdí, že pomocí kvantových metod dokázali obejít omezení Schnorrova algoritmu.
Skepticismus od některých kryptografů je způsobeno skutečností že článek čínských vědců dokazuje použití vaší metody pouze na malá čísla, zhruba ve stejném řádu, pro který funguje Schnorrův algoritmus. Navzdory tvrzení, že byl překročen limit velikosti, zatím nebyly poskytnuty žádné důkazy ani podrobnosti. V praxi je metoda ukázána faktorem 48bitových celých čísel pomocí 10qubitového kvantového počítače.
Shorův algoritmus vážně zpochybnil bezpečnost informací založených na kryptosystémech s veřejným klíčem. Prolomení široce používaného schématu RSA-2048 však vyžaduje miliony fyzických qubitů, což je značně nad rámec současných technických možností. Zde uvádíme univerzální kvantový algoritmus pro celočíselnou faktorizaci kombinací klasické redukce mřížky s kvantovým fuzzy optimalizačním algoritmem (QAOA).
Počet požadovaných qubitů je O(logN/loglogN), což je sublineární v celé bitové délce N, což z něj dělá doposud nejšetřivější qubitový faktorizační algoritmus. Algoritmus demonstrujeme experimentálně faktorováním celých čísel o velikosti až 48 bitů s 10 supravodivými qubity, což je největší celé číslo faktorizované v kvantovém zařízení. Odhadujeme, že ke zpochybnění RSA-372 pomocí našeho algoritmu je zapotřebí kvantový obvod s 2048 fyzickými qubity a hloubkou tisíců. Naše studie ukazuje velký příslib urychlení aplikace dnešních hlučných kvantových počítačů a připravuje cestu pro faktorizaci velkých celých čísel realistického kryptografického významu.
Je zmíněno, že předpoklad, že 372 fyzických qubitů bude stačit k faktorizaci klíče RSA-2048, je teoretický, takže je velmi pravděpodobné, že kvantová metoda založená na Schnorrově algoritmu má stejné problémy se škálováním a nefunguje při faktorizaci čísel. .
Pokud se problém se škálováním skutečně vyřeší, pak bude bezpečnost kryptoalgoritmů založená na složitosti faktoringu velkých prvočísel podkopána nikoli v dlouhodobém horizontu, jak se očekávalo, ale již dnes.
Nakonec, pokud vás zajímá, že se o tom můžete dozvědět více, můžete se podívat na podrobnosti v následující odkaz.