O.S.E.L. - Šifrovací algoritmus RSA prolomen!
 Šifrovací algoritmus RSA prolomen!
Katastrofu v oblasti asymetrických šifer způsobila neuronová síť, která se naučila faktorizovat čísla. Bezpečnost algoritmu RSA je založena na tom, že dostatečně velké číslo neumíme v rozumném čase rozložit na součin prvočísel. Nyní se však podařilo najít elegantní způsob, jak s pomocí neuronové sítě faktorizovat dokonce větší čísla, než jaké používá RSA.


 

Zvětšit obrázek
Schema faktorizace: Na výstupu sítě nejsou jednotlivé bity prvočísel reprezentovány jako logické hodnoty 0/1, nýbrž jako analogový výstup.

Neuronová síť vyniká v tom, že dokáže odhalit i ten nejdivočejší vztah mezi vstupem a výstupem. V první fázi probíhá trénink: krmíte síť dvojicemi dat vstup - správná odpověď (v našem případě číslo - rozklad) a necháte ji, aby se sama naučila jejich závislost. Po jisté době je síť schopna dát správnou odpověď i na vstup, který nikdy předtím neviděla. Čím déle probíhá trénink, tím přesnější jsou odpovědi, zcela přesný výsledek však síť z principu nedá nikdy (chceme-li po ní například sečíst 1+1, tak po chvilce tréninku dostaneme odpověď, že to je "něco mezi 1.8 a 2.2").
 

 

 


Vypadá to, že taková chyba prvočíselný rozklad znemožňuje, ale naštěstí (ke smůle RSA) se dá jednoduše obejít.  Na výstupu sítě totiž nejsou jednotlivé bity prvočísel reprezentovány jako logické hodnoty 0/1, ale jako analogový výstup. Pokud je analogová hodnota výstupu blízko nuly, prohlásí se tento bit za nulu (a totéž pro jedničku). Tím jsme získali velké množství "správně" nastavených bitů prvočísla - a zbývá prověřit již jen hodnoty, které leží "někde mezi 0 a 1". To zvládne klasický algoritmus hrubé síly, pro který "předchroustaná" data z neuronové sítě představují mnohem menší porci než kdybychom kombinovali celé původní číslo.
 

 

Prahové hodnoty - co ještě považovat za nulu, co za jedničku a co za neurčitost - si program nastavuje dynamicky. Nejprve zkusí málo otevřené okno. Pokud prvočíselný rozklad nenajde hned, otevírá okno stále více a přibírá do hry další nerozhodné bity.

Zvětšit obrázek
„Dešifrovací“ nervová síť profesorky Hokum Eyewash

Úspěch záleží samozřejmě na stupni "vzdělání" neuronové sítě. Na slušně naučenou síť stačí malé okénko a rozklad se najde rychle. Navíc je síť trénovaná velmi specificky - pouze na součin 2 prvočísel. Ostatní případy nás nezajímají, čímž ušetříme spoustu času.
 

Symetrické algoritmy (DES, Triple DES, AES, apod.) jsou pro neuronovou síť v porovnání s RSA směšně jednoduché, je tu ale jedna zvláštnost. U RSA získáme neuronvým útokem klíč v čisté podobě, kdežto při útoku na DES nikoliv. Místo DES klíče máme natrénovanou síť, která je schopna šifrovat i dešifrovat data (takže nás neznalost klíče netrápí).
 

Kryptologie je věčná hra na kočku a na myš. Lékem na popsaný typ útoku je prodloužit RSA klíč, aby se tímto způsobem nedal zjistit. Neuronová síť je však nepředvídatelná a nikdo nezaručí, že takový klíč odolá. Potíže přinese i uložení dlouhých klíčů, obzvláště do zařízení s omezenou pamětí, typu šifrovacích tokenů, smart karet apod. O výpočetních problémech ani nemluvě: generování a ověření velkých prvočísel, samotné šifrování, atd.
Každá mince má však dvě strany a o využití neuronových sítí k posílení bezpečnosti šifer ještě uslyšíme.


Pramen: Bioscience, 1, 4, 2006
https://www.bio.sci.osaka-u.ac.jp/bio_web/lab_page/ogura/research.html

 


Poznámka redakce: Pokud se vám obsah tohoto příspěvku nějak nezdál, měli jste pravdu. Jeho platnost vypršela dnem jeho zveřejnění a jeho význam odpovídá rubrice ve které je zařazen.


Autor: Jindřich Solovej
Datum:01.04.2006 02:06