aneb Když matematici znervózní

Článek publikovaný veteránem vědecké kryptografie tvrdí, že šifra RSA byla zničena. Naštěstí to zatím vypadá, že nebyla.

Milí čtenáři, tak se hned vyskytlo další zajímavé a vědecké téma. Dokonce téma mně hodně blízké, protože přesně tímto matematickým problémem jsem se zabýval na postgraduálním studiu (ach, to už je dávno!).

Máme teď v matematice menší pozdvižení s možnými praktickými důsledky pro celý svět – tedy pokud by šlo o bezchybné výsledky. Ale nějaké chyby v tom článku jsou, takže to vypadá, že místo dalekosáhlého objevu jde spíše o roztržitost starého matematika (77 let), který už nedokáže postřehnout problémy ve své vlastní práci.

Nebylo by to poprvé, něco podobného se dokonce stalo nedávno. Roku 2018 prohlásil tehdy 89letý profesor Atiyah, že dokázal Riemannovu hypotézu – leč ve skutečnosti nedokázal. Ačkoliv byl Atiyah borec oceněný Abelovou cenou, jeho důkaz byl chybný.

*****************************

Co se tedy stalo teď?

Claus Peter Schnorr je Němec, uznávaný veterán kryptografického oboru, který už je zhruba deset let v důchodu. V nově vydaném článku “Fast Factoring Integers by SVP Algorithms” tvrdí, že pomocí něčeho, čemu se říká mříže (lattices), dokáže rychle faktorizovat čísla. Jinými slovy, že předhodíte-li mu dlouhé číslo n, které není prvočíslem, najde v rozumném čase jeho prvočíselné dělitele. Pokud by vás zajímalo, co se v praxi myslí pojmem “dlouhé číslo”, představte si něco kolem tisícovky decimálních číslic.

To zní jako naprosto umělý problém, který se nemůže dotýkat reálného života zde na Zemi ani okrajově a se kterým si hrají jen podivní jedinci v odlehlých koutech obskurních kateder. Ve skutečnosti by takový objev znamenal v počítačovém světě otřes se značnými dopady. On totiž na tom, že ty dělitele rychle najít neumíme, stojí šifrovací systém zvaný RSA, který vznikl už roku 1977 a rozlezl se od té doby všude.

Výpis soukromého a veřejného RSA klíče pro dálkový přístup k počítači pomocí SSH

Dost velká část zabezpečení internetového provozu stála a stojí právě na RSA, čili právě na praktické nemožnosti rychle faktorizovat nějaké dlouhé n zpátky na jeho prvočinitele p, q. Kdyby ten algoritmus někdo prorazil, odtajnila by se (a to i zpětně do minulosti) hromada zpráv, které měly zůstat skryty, neoprávněné osoby by se mohly připojovat k cizím serverům jako administrátoři, některé digitální podpisy by de facto pozbyly platnosti, zjednodušilo by se šíření malwaru (falešným podpisem)… Zkrátka, následovala by katastrofa; lev by se popásal s beránkem, Britney Spears by se naučila zpívat bez playbacku apod.

No, dělám si legraci, ale asi by to žádná velká legrace nebyla. Už jenom těch pár jedinců, kteří by se pokusili na dálku pohrabat v bankách nebo všelijakých státních či soukromých databázích, by mohlo nadělat dost škody. Natož pak, kdyby se do toho pustily špionážní složky různých velmocí ve větším měřítku, což ony by určitě udělaly.

*****************************

Naštěstí to po první vlně rozruchu opravdu vypadá, že pár klíčových odhadů (horních mezí) je v Schnorrově článku špatně. Bohužel lidí, kteří by se dostatečně do hloubky zabývali teorií mříží, je velmi málo. Navíc ten obor samotný je dost složitý na to, abyste se v něm nevyznali během hodiny, i kdybyste byli odborníkem na něco příbuzného. Tím pádem je dokonce i valná většina matematické obce odkázána na to, až někdo, kdo se v mřížích vyzná, důkladně pročte dvanáctistránkový článek a najde v něm různé hnidy.

Pár lidí už to udělalo, včetně jednoho chlapíka jménem Leo Ducas, který nejen, že skutečně ovládá teorii mříží, ale ještě navíc umí solidně programovat (kterážto kombinace je opravdu vzácný). Ten hned zkusil Schnorrův nový postup převést do počítače a zatím mu nefunguje moc dobře – rozhodně ne tak, aby se šifra RSA dala považovat za zlomenou. Ty výše zmíněné chyby jsou podle všeho podstatné a profesor Schnorr byl ve svém názoru, že právě zničil jeden z nejdůležitějších kryptografických algoritmů světa, příliš optimistický. Stejně jako před pár lety sir Atiyah s jeho útokem na Riemannovu hypotézu.

That said, je možné, že ty chyby jsou opravitelné. První důkaz Velké Fermatovy věty od Andrewa Wilese měl v sobě také chybu, jejíž oprava trvala rok, ale nakonec se povedla. Pokud by někdo dokázal udělat podobné opravy ve Schnorrově článku, bylo by zase veselo.

V tomhle moderním, technologickém a propojeném světě zkrátka nikdy nevíte, kde si kdo “uvaří polévku z netopýra” a vypustí ven něco, co změní celou planetu. A ne vždy to musí mít podobu reálného viru. K další globální panice by úplně stačil hezký nový algoritmus z teorie čísel.

*****************************

Hudební epilog

****************************************
ZAPOMENUTÉ PŘÍBĚHY 3
Už potřetí budeme s Marianem Kechlibarem zkoumat zákoutí historie, která unikají pozornosti. Neskrývají se v nich velké dějinné události, spíš tam nalezneme zůstatky lidských příběhů. Jsou to stopy lidí, kteří prošli světem v dobách dávných anebo docela blízkých. Jeden příběh za druhým je fascinujícím dílkem skládačky v obraze světa, ve kterém žijeme v blahoslavené nevědomosti.
Knihu si můžete objednat na této adrese.

Převzato z Kechlibar.net se souhlasem autora