Štítky článku: •  

Najdi ta dvě prvočísla, 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.

PrimeDecompositionExample.png

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 89-letý 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.

Q2AHK-1024x377.png
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.

Autorovo diskusní fórum ke článku najdete zde.

Píše pan Marian Kechlibar na kechlibar.net

Autor článku: | Vydáno: | Přečteno: 259 × | Prestiž Q1: 10,79

+19 plus Známkuj článek minus –0

Interní diskuse

Komentáře

Článek má 1 komentářů.

Pravidla pro diskutující

Přidáním komentáře souhlasíte s tím, že budete dodržovat základní pravidla slušné výměny názorů. Vítám jejich střet, ale snažte se je vždy vést v rámci kultivované debaty. Bude-li se někdo chovat jako sprostý nevychovanec, pokud bude urážet ostatní komentující, spamovat, nebo tapetovat diskuse zcela mimo téma článku, nebo ji zanášet reklamou, takové příspěvky nekompromisně zablokuji. Za deset porušení těchto pravidel budete z diskuse nekompromisně a navždy vyřazeni (včetně IP adresy). Na oplátku slibuji, že i kontroverzní příspěvky nebudu editovat, ani mazat. PeTaX

Napsat nový komentář
Jára

A co kvantový počítač? Ten by nedokázal prvočísla faktorovat?
Kdyby se dokázalo nějak zužitkovat nekonečnou přesnost, tak by čistě teoreticky mohl s určitou pravděpodobností faktorizaci rozlomit.

Nikdy jsem to neprogramoval a popravdě žádný skutečně plně kvantový počítač dosud neběží. Snad je hotový kvantový akcelerátor, který některé kvantové přechody umí využít.

0 | 0

Napsat nový komentář

Zbývá 2048 znaků.

Svobodný svět

Jen svoboda jednotlivce vede ke svobodné společnosti

top