Konec roku 2001 přinesl i konec současné kryptografie!

Toto není jen obyčejná zpráva o zdařeném vědeckém pokusu. Toto je ve skutečnosti ohlášení výsledku zásadního významu. Pravděpodobně by to mohlo znamenat i konec klasické asymetrické kryptografie a vše co s tím souvisí – šifrování, elektronického podepisování atd. Vysvětleme si několik základních pojmů a podívejme se, co se vlastně tak převratného stalo.

Asymetrická kryptografie je založena na této základní myšlence: každý subjekt má svůj tajný (soukromý) klíč a k němu veřejný klíč. Tajný klíč je určen k zašifrování a veřejný klíč k odšifrování. Brzy po zveřejnění tohoto teoretického schématu asymetrické kryptografie (1978) se objevuje první šifrový systém založený na této myšlence. Vžil se pro něj název RSA (zkratka z prvých písmen tvůrců systému Rivest, Shamir a Adelmann). Tento systém je založen na obtížném matematickém problému – faktorizaci velkých čísel (rozkladu čísla na prvočísla). Nejlépe si to vysvětlíme na následujícím jednoduchém příkladě. Zkuste najít celočíselné dělitele čísla 268294849. Jsou jimi dvě prvočísla 15733 a 17053. Zatímco vynásobení těchto dvou čísel je velice jednoduchým úkonem, vyhledání rozkladu součinu na tato dvě čísla vyžaduje relativně dost času a práce. Pokud se vám podaří faktorizovat tzv. modul asymetrické šifry RSA, pak z veřejného klíče již snadno dopočítáte soukromý (tajný) klíč.

V srpnu 1999 bylo dosaženo v této oblasti velkého úspěchu, bylo faktorizováno číslo ze souboru RSA s délkou klíče 512 bitů (155-ti ciferné dekadické číslo). K tomu však bylo zapotřebí spolupráce tisíce počítačů. Zvětšení modulu o 1 bit znamená zdvojnásobení složitosti problému. Modul délky 1024 se proto na dlouhou dobu považuje za dostatečně bezpečný. Odborníci nepředpokládají výrazný pokrok v číselné teorii, tj. nalezení nového, zatím neznámého algoritmu na faktorizaci (dnes se za nejúčinnější považuje rozkladový algoritmus GNFS, který vytlačil donedávna používaný algoritmus kvadratického síta). O historii rozkladů nesnadno rozložitelných čísel ze souboru RSA viz: http://www.rsa­security.com.

Současné asymetrické algoritmy může ohrozit neustálé zvyšování výpočetního potenciálu (větší kmitočet procesorů, levnější paměť, možnost propojení většího počtu počítačů). Má to jeden háček, zvýší-li se výpočetní potenciál, dá se odpovídajícím způsobem zvětšit délka příslušného modulu. Při zdvojnásobení výkonu výpočetní techniky zhruba každé dva roky se dá podle známých expertů Lenstry a Verheula předpokládat, že v současné době doporučené moduly délky 1024 by měly odolat nejméně do roku 2020.

Je zde ještě jedna možnost jak rozbít asymetrickou kryptografii, nebo přesněji, jak faktorizovat velká čísla. Toto nebezpečí se nazývá kvantový počítač. Na rozdíl od klasického počítače, kde bit má jen dva stavy, u kvantového počítače je základem přenosu informace kvantový bit (qubit). Qubit může být podle kvantové mechaniky v lineární superpozici dvou klasických stavů. Heisenbergův princip neurčitosti formuluje základní vlastnosti tohoto qubitu. Východiskem algoritmů zatím hypotetického kvantového počítače jsou tzv. unitární transformace pracující s vektory qubitů. Na rozdíl od transformací probíhajících v klasickém počítači jsou unitární transformace vždy reversibilní, tj. vždy existuje možnost jít algoritmem pozpátku. V roce 1994 Peter Shor (AT&T) prokázal existenci kvantového polynomiálního algoritmu pro řešení diskrétního algoritmu a pro faktorizaci velkých čísel.To znamená, že pokud se zdaří konstrukce kvantového počítače, bude nutné přestat používat v podstatě všechny současné systémy s veřejným klíčem, které jsou založeny na obtížné řešitelnosti úlohy faktorizace a úlohy diskrétního logaritmu. Konstrukce kvantového počítače se však zdála v roce 1994 ještě utopií. Odborníci na kvantovou kryptologii byli na kryptologických konferencích považováni za futurology a jejich vystoupení byla brána jako příjemné osvěžení. Časem se společnost kvantových expertů oddělila od společnosti kryptologů a začala pořádat vlastní konference. Velké společnosti a bohaté státy začaly tento výzkum tučně financovat a dostavily se i prvé úspěchy. V roce 1998 byla demonstrována faktická možnost sestavit kvantový počítač (University of California Berkeley). Světlo světa spatřil 2-qubitový počítač – první kvantový počítač na světě! V roce 1999 dr.Chuang z IBM předvedl možnost realizovat (nějak se bráním slovu naprogramovat) Groverův algoritmus na rychlé vyhledávání v databázích a to na 3-qubitovém počítači. V srpnu 2000 byl realizován 5-ti qubitový počítač.

Po delší odmlce přišla naprosto senzační zpráva – vědcům z IBM (Almaden Research Center) se podařilo zrealizovat na 7-qubitovém počítači Shorův algoritmus pro faktorizaci! Při demonstraci bylo předvedeno rozložení čísla 15 na činitele 5 a 3. K „programování“ byly použity radiové pulsy a k detekci výsledku byla použita nukleární magnetická resonance (NMR). Kvantový počítač se „skládal“ z pěti atomů fluoru a dvou atomů uhlíku.

Samozřejmě kvantové počítače mají svá úskalí a řadu problémů, které brání jejich rychlému rozvoji (schopnost správně inicializovat qubity, schopnost správně měřit výsledek a měřením neovlivnit aktuální stav, atd.).

Pokus demonstroval, že je pravděpodobně pouze otázkou času (a peněz!), kdy bude možné na kvantovém počítači řešit faktorizaci modulů, které se používají v asymetrické kryptografii. Toto by prakticky znamenalo konec všech v současné době používaných asymetrických algoritmů. Závěrem připomeňme, že na asymetrické kryptografii je založen i digitální podpis – elektronický podpis. Celá složitě budovaná infrastruktura PKI, certifikační autority, příslušná legislativa – tj. harmonizace zákonů o elektronickém podpisu a využití elektronických podpisů pro právní úkony – to vše by bylo zbytečné. Tedy přesněji řečeno nepoužitelné při využívání současných podpisových schémat.

Není vyloučeno, že velké firmy již nějakou dobu vědí své, a proto se očekávaný boom v oblasti PKI stále nekoná, stále chybí velké projekty a velcí PKI vendoři mají velké existenční problémy. Baltimor (vůdčí výrobce softwaru pro certifikační autority) propouští své zaměstnance a cena jeho akcií klesá.

Jistě bude velice zajímavé sledovat, co nového v této oblasti přinese rok 2002.

Problémy v oblasti PKI:
http://www.in­fosecuritymag­.com/articles/oc­tober01/colum­ns_logoff.shtml

K tématu kvantové realizace Shorova algoritmu najdete další informace např. zde:
Demonstrace algoritmu v IBM:
http://www.re­search.ibm.com/re­sources/news/20011219_q­uantum.shtml

Shorův algoritmus:
http://crypto­me.org/shor-nature.htm

Související novinové zprávy:
http://www.ny­times.com/2001/12­/20/science/20QU­AN.html
http://www.wi­red.com/news/techno­logy/0,1282,49­268,00.h