Hlavní navigace

Jak dlouho nám vydrží dnešní šifrovací metody?

Pavel Houser 17. 8. 2005

S pokrokem při řešení toho či onoho matematického problému se vždy objeví komentáře, že další úsilí matematiků nutně povede k prolomení současných šifrovacích technologií, radikálnímu snížení bezpečnosti a soukromí na Internetu či katastrofě pro bankovní sektor. Následující článek se pokusí o malé shrnutí a snad přinese i něco matematických perliček.

Na úvod drobná sebekritika. Tento článek nenapsal ani profesionální matematik, ani kryptolog, ale (dá-li se to tak říci) profesionální čtenář. Půjde tedy o text shrnující a vlastně ničím objevný, vše lze načíst či dohledat i jinde. Po vzoru Stephena Hawkinga, který radil vyhnout se při popularizaci vzorečkům, se také soustředíme na slovní výklad. Snad ale alespoň amatérští matematici či obecně hračičkové shledají následující text inspirativním.

Co je co
Faktorizace: Rozklad čísla na dvě prvočísla. Faktorizace čísla 15 znamená zjistit, že 15 = 3×5. Faktorizovat obrovská čísla je výpočetně náročné.

Výpočetní složitost: Závislost trvání výpočtu na velikosti vstupu. Ještě jinak – jak s růstem velikosti vstupu roste doba výpočtu. Problémy, jejichž výpočetní složitost roste se vstupem exponenciálně, se obecně pokládají za prakticky nezvládnutelné.

NP úplné problémy: Třída problémů, pro které není znám algoritmus řešící je v polynomiálně rostoucím čase (a všeobecně se předpokládá, že žádný takový algoritmus ani neexistuje). Pokud je ovšem nějaké řešení už známo, lze jeho platnost v polynomiálně rostoucím čase ověřit (do nedeterminismu a věštíren se nebude zaplétat). Do této třídy problémů spadá například obchodní cestující, splnitelnost či určení pravdivostní hodnoty logické formule. Jednotlivé NP úplné problémy jsou na sebe vzájemně převoditelné.

DNA počítač: Zařízení, v němž se výpočetní postupy realizují prostřednictvím toho, jak se jednotlivé molekuly DNA „hodí/párují“ k sobě.

Heuristika: Přibližný postup, jakási zkratka, nebo spíše intuitivní strategie, která s určitou pravděpodobností vede k řešení a má smysl tam, kde nelze použít rigoróznějších postupů (algoritmus není znám, byl by příliš pomalý apod.)

Prvočísla na hraní

Asymetrická kryptografie stojí obecně na tom, že určitá matematická úloha je různě obtížná podle toho, kterým směrem ji provádíme. U dnes zřejmě nejpoužívanější metody RSA je touto inverzní operací vynásobení dvou prvočísel (vcelku výpočetně zvládnutelná operace i pro hodně velká prvočísla) versus rozklad takto vzniklého čísla zpět na prvočísla. Rozkládané (neboli faktorizované) číslo má samozřejmě více cifer než oba činitelé (zhruba tolik cifer, jako oba činitelé dohromady), hlavním problémem je ale samotná náročnost faktorizace. Vlastní nasazení celé metody RSA při tvorbě šifrovacích klíčů se běžně vykládá tak, že prvočísla odpovídají soukromému klíči, zatímco výsledné složené číslo odpovídá klíči veřejnému – odborníci však upozorňují, že se jedná o představu zjednodušující.

Pro faktorizaci se každopádně zatím nepodařilo najít žádný klasický algoritmus fungující s polynomiální složitostí, třebaže v tomto směru bylo vyvinuto značné úsilí. Úloha je prozatím řešitelná pouze v čase exponenciálním (na rozdíl od násobení, které má kvadratickou složitost). Důvod, proč o faktorizaci existuje takový zájem, ovšem nespočívá jen v jejím významu pro kryptografii, ale spíše v jejím vztahu k prvočíslům. Prvočísla totiž už od starověku fascinují matematiky i nematematiky; ve druhém případě asi proto, že na rozdíl od jiných matematických problémů/objektů amatér v tomto případě obvykle alespoň chápe otázku.

A tak se už dlouho louskají takové rébusy, jako zda je každé sudé číslo větší než 2 součtem dvou prvočísel nebo zda existuje nekonečně mnoho prvočíselných dvojic (prvočísel lišících se od sebe o hodnotu 2). Velice elegantní a ne tak často citovaný je následující problém: Je součet posloupnosti převrácených hodnot prvočísel konvergentní, nebo divergentní? Lehké přiblížení: řada čísel 1 + 1/2 + 1/3 + 1/4… roste nade všechny meze, zatímco nekončená geometrická posloupnost 1 + 1/2 + 1/4 + 1/8… má součet konečný. Když si teď vezmeme takovouhle řadu převrácených hodnot pro prvočísla – 1/2 + 1/3 +1/5 + 1/7 + 1/11…, jak to dopadne? Mizí prvočísla z číselné osy dostatečně rychle, aby to stačilo na konvergenci?

Riemann a Indové

Předcházející otázka vlastně odpovídá problému po rozložení prvočísel na číselné ose. Kromě závěrů, které jsou triviální (asi ve smyslu, že prvočísel je nekonečno, ale jejich hustota klesá), existuje několik vět exaktních. Již dokázaná Gaussova věta (hustota prvočísel směrem do nekonečna zhruba odpovídá hodnotě 1/ln(n)) a Riemannova hypotéza, která dává prvočísla do souvislosti s určitou komplexní funkcí (označovanou jako dzeta).

Riemannova domněnka je zajímavá tím, že se dostala na Hilbertův seznam největších matematických oříšků pro 20. století – a jako jediná zůstala i na seznamu pro století 21. Jak ale vlastně Riemannova domněnka ohrožuje šifrování RSA?

Keith Devlin (česky od něj v nakladatelství Dokořán vyšla vynikající kniha Jazyk matematiky a připravují se také Problémy pro třetí tisíciletí, které vydatně posloužily jako inspirace k tomuto článku) vysvětluje, že Riemannova domněnka je vesměs pokládána za pravdivou a dokonce některé šifrovací technologie jsou funkční právě za předpokladu, že tato domněnka je pravdivá. Problém spočívá v něčem jiném. Devlin tvrdí, že při důkazu hypotézy budou nejspíš použity dosud neznámé metody. Kdo dokáže hypotézu, získá přitom nejspíš nutně značný vhled do toho, jak jsou prvočísla vlastně uspořádána. Nebezpečí pro kryptografii nepředstavuje tedy vlastní důkaz, ale spíše průvodní poznatky (podrobnosti).

Faktem ale je, že ani jakýsi mystický náhled na strukturu prvočísel není ještě žádnou zárukou efektivně prováděné faktorizace. To, zda dané číslo je prvočíslem, už totiž v polynomiálně rostoucím čase zjistit umíme (řešení nalezli tři indičtí matematici Agrawal, Kayal a Saxena.), to ale ještě neznamená, že složené číslo zvládneme také rozložit. Z tohoto hlediska se možná význam znalostí o prvočíslech pro faktorizaci trochu přeceňuje. Ba co víc – rychlejší vyhledávání prvočísel by dokonce mohlo zefektivnit naopak tvorbu dlouhatánských klí­čů.

Problém lze nastolit ještě z jiné strany. Představte si, že zjistíme, že faktorizace je přese všechno nějak řešitelná v polynomiálně rostoucím čase (nakonec většina matematiků se podle Devlina i dalšího popularizátora Iana Stewarta sice domnívá, že NP úplné problémy na polynomiální převést nepůjdou, ale taktéž jsou vesměs přesvědčeni, že faktorizace nespadá mezi NP úplné problémy). Najdeme tedy nějaký algoritmus s polynomiálně rostoucí složitostí. Pokud ale (podobně jako u prvočíselného testu) bude nejvyšší mocnina v polynomu rovna třeba 12, bezprostřední praktický přínos bude nulový. Počítejte chvíli, jen pro hodně hrubou představu: Dejme tomu, že na rozluštění klíče generovaného 1 sekundu bude potřeba také jedna sekunda. Pokud budeme klíč generovat den (3600×24 = 86.400 sekund), často potřebný k rozlomení šifry na stejném počítači bude při polynomu stupně 12 v řádu 10 na 50 let.

Jenže celý problém spočívá opět spíše v tom, jak to výše nastínil Devlin. Pro faktorizaci (ani pro testy prvočíselnosti) se dnes nepoužívá prosté prohledávání stavového prostoru, ale různě sofistikované heuristiky. Kdo by nalezl algoritmus pro faktorizaci vykazující polynomiální složitost, nespíš by při tom získal takové znalosti o celé proceduře, že by jako vedlejší efekt mohl přijít s extrémně rychlou heuristikou (taková kvadratická výpočetní náročnost by třeba byla zcela zničující, protože stejně složitá je i operace násobení – ne že by byl objev takové heuristiky pro faktorizaci jakkoliv pravděpodobný). A v tom je zřejmě jediné existující riziko, nikoliv však zanedbatelné.

DNA počítač

V tomto textu pomineme faktorizaci na kvantovém počítači, ale zaměříme se na řešení pomocí DNA počítače. Leonard Adleman přišel již v první polovině 90. let s možností, jak na DNA počítači efektivně řešit problém obchodního cestujícího. Když jsem se s tímto postupem poprvé seznámil, pocítil jsem silnou fascinaci a domníval jsem se, že právě tudy se bude ubírat řešení výpočetně náročných úloh. Zjednodušeně řečeno, DNA počítač fungoval tak, že ve větvících se úlohách reprezentovala jedna molekula určitou větev výpočtu. Pokud byl molekul přidán dostatečný počet (DNA pojme řádově více dat než současná elektronická média) a dokázali jsme najít metodu, jak správné řešení ze směsi vylovit, pak DNA počítač fungoval tak trochu jako orákulum.

V případě onoho obchodního cestujícího se molekuly reprezentující různá města a cesty ve směsi ve zkumavce všelijak propletly a pak stačilo vytáhnout ze směsi optimální cestu, která odpovídala nejkratší molekule a ta byla například současně nejlehčí, takže „vyplavala nahoru“ (velice zjednodušeně řečeno – samozřejmě bylo třeba ještě zařídit „maličkost“, totiž aby vzniklé řetězce vůbec odpovídaly podmínkám zadání, to jest třeba procházely všemi městy).

L. Adleman je mimochodem totožný s jedním z objevitelů šifrování RSA (ono A na konci zkratky). Přišlo mi zvlášť vykutálené, že právě on nyní přišel s technologií, která celou šifru učiní časem nepoužitelnou. V počátečním nadšení jsem se pokusil navrhnout, jak by se na DNA počítači dala realizovat i faktorizace. Bylo to poněkud naivní a v diskusi bylo celkem jasně ukázáno, proč by navržená metoda nemohla fungovat.

MIF16

Později jsem si však uvědomil, že není vůbec třeba vymýšlet speciální postup pro faktorizaci. Stačilo by efektivně řešit obchodního cestujícího. Všechny NP úplné problémy jsou na sebe totiž převoditelné, přičemž faktorizace lze realizovat jako určení pravdivostní hodnoty logické formule (převod je zde však jen jednosměrný). Mít skutečně efektivní DNA počítač, stačilo by tedy nejprve faktorizační úlohu převést do jazyka obchodního cestujícího, tento problém vyřešit a provést překlad zpět do jazyka původní úlohy. Vlastně by pro většinu výpočetně náročných úloh používaných v průmyslu ani nebylo třeba vytvářet DNA počítač úplně obecný (související problémy, v odkazovaném článku je bohužel několik chyb).

Jak se ale dnes zdá, i tohle všechno je jenom fantazírování. Pokud pomineme konspirační teorie, že totiž příslušný výzkum by byl realizován nějak tajně, pak je vidět, že využití DNA počítačů směřuje někam úplně jinam. Technické problémy činí tuto technologii pro skutečné výpočty zřejmě nevhodnou. Vývoj směřuje spíše k tomu, aby DNA počítače řešily problémy nějak zase svázané s biochemií, analyzovaly DNA a výhledově snad fungovaly jako molekulární strojky i přímo v živých organismech: velmi zajímavý projekt počítá třeba s tím, že by DNA počítač mohl diagnostikovat a ničit nádorové buňky, i zde se však s nasazením do praxe počítá v řádu 30 let. Je to určitě zajímavé a snad i životně důležité, obchodnímu cestujícímu to však cestu nenajde a šifry se tím také lámat nedají.

Anketa

Nástup kvantových počítačů:

Našli jste v článku chybu?
DigiZone.cz: Nova opět stahuje „milionáře“

Nova opět stahuje „milionáře“

Podnikatel.cz: Udělali jsme velkou chybu, napsal Čupr

Udělali jsme velkou chybu, napsal Čupr

Podnikatel.cz: Slevu na dani na EET neuplatní každý

Slevu na dani na EET neuplatní každý

Lupa.cz: Patička e-mailu závazná jako vlastnoruční podpis?

Patička e-mailu závazná jako vlastnoruční podpis?

Vitalia.cz: Tohle jsou nejlepší česká piva podle odborníků

Tohle jsou nejlepší česká piva podle odborníků

Lupa.cz: Další Češi si nechali vložit do těla čip

Další Češi si nechali vložit do těla čip

Měšec.cz: TEST: Vyzkoušeli jsme pražské taxikáře

TEST: Vyzkoušeli jsme pražské taxikáře

Podnikatel.cz: Takhle se prodávají mražené potraviny

Takhle se prodávají mražené potraviny

DigiZone.cz: Mordparta: trochu podchlazený 87. revír

Mordparta: trochu podchlazený 87. revír

Vitalia.cz: dTest odhalil ten nejlepší kečup

dTest odhalil ten nejlepší kečup

Lupa.cz: Jak se prodává firma za miliardu?

Jak se prodává firma za miliardu?

120na80.cz: Hrbatá prsa aneb mýty o implantátech

Hrbatá prsa aneb mýty o implantátech

DigiZone.cz: Pure má tři nové přijímače DAB

Pure má tři nové přijímače DAB

Vitalia.cz: Když bílkoviny, tak jíme ty nekvalitní

Když bílkoviny, tak jíme ty nekvalitní

Lupa.cz: Jak levné procesory změnily svět?

Jak levné procesory změnily svět?

120na80.cz: Na různou rýmu různá homeopatie

Na různou rýmu různá homeopatie

DigiZone.cz: Digi2GO: výborný základ, ale...

Digi2GO: výborný základ, ale...

Vitalia.cz: Muž, který miluje příliš. Ženám neimponuje

Muž, který miluje příliš. Ženám neimponuje

DigiZone.cz: Na jaká videa se vlastně díváme

Na jaká videa se vlastně díváme

Vitalia.cz: Voda z Vltavy před a po úpravě na pitnou

Voda z Vltavy před a po úpravě na pitnou