Š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
http://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.

Datum: 01.04.2006 02:06
Tisk článku

Lživé kameny z Marakéše - Gould Stephen Jay
 
 
cena původní: 399 Kč
cena: 319 Kč
Lživé kameny z Marakéše
Gould Stephen Jay
Související články:

New Horizons míjí Triton     Autor: Tomáš Petrásek (01.04.2011)
Smí Rakušané topit uhlím?     Autor: Igor Tureček (17.04.2008)
Ig Nobel ceny 2007     Autor: Josef Pazdera (06.10.2007)
Budou se děti jmenovat „@“,...?     Autor: Josef Pazdera (19.08.2007)
Přehrajte si své geny třeba na piáno     Autor: Jaroslav Petr (03.05.2007)



Diskuze:

To je apríl

Bob a Bobek,2006-04-03 19:04:49

Ale je to pěkně napsané. Díky!

Odpovědět

hezký nápad, ale je 1.4.

Q6,2006-04-02 00:10:42

Z překladu "zdroje" článku: If the fragment of the hippocampus which was adjusted from the rut/rat new life 仔 cerebrum supplies sufficient oxygen and nutrition, it is possible 1 month or more to continue to utilize. ... "Zdroj" zjevně nehovoří o faktorizaci.
/>
http://babelfish.altavista.com/babelfish/trurl_load?lp=ja_en&url=http%3A%2F%2Fwww.bio.sci.osaka-u.ac.jp%2Fbio_web%2Flab_page%2Fogura%2Fresearch.html

Odpovědět

profesorka Hokum Eyewash

Nesmysl,2006-04-01 22:29:54

Apríííl

Odpovědět

Neuronova sit

franta.vrata,2006-04-01 21:05:53

Tak na tohle jsem odbornik,po peti pivech vam rozsifruji cokoliv,cisla,pismena,rizek na taliri i nervy!

Odpovědět

No ja bych rekl...

Erix,2006-04-01 12:00:47

ze to je hezkej april! :)

Odpovědět

Gratuluji

Ccecil,2006-04-01 10:25:16

Před cca 5 lety jsem se zabýval něčím podobným. Určité výsledky byly, ale až tak dobré teda ne. Pokud je to pravdivé, tak gratuluji.

Odpovědět


Ccecile, ccecile !?

Katka,2006-04-01 11:46:22

Opět promluvil expert na neuronové sítě.. Jestli to, že neumíte pořádně sestavit a rozchodit (tu správnou a správně nastavenou) neuronovou síť, považujete za důkaz toho, že NS nefungují, měl byste se zamyslet nad svým důkazovým procesem. Já neumím řídit auto, takže auta nefungují. :P

Katka

Odpovědět


KATKO nejste trochu mimo?

Ccecil,2006-04-01 23:02:36

Já to myslel neironicky, ale zcela upřímně. Protože vím, jaký to byl problém. Takže jestli se to někomu povedlo,tak smekám. A tu hloupou poznámku si odpusťte.

Odpovědět




Pro přispívání do diskuze musíte být přihlášeni












Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace