Hlavní navigace

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

Pavel Vondruška 27. 12. 2001

V samotném závěru roku 2001 byla publikována následující zpráva: "San Jose, Kalifornie, 19.prosince, vědci z IBM (Almaden Research Center) předvedli na 7-mi qubitovém kvantovém počítači Shorův algoritmus".

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

Našli jste v článku chybu?

15. 7. 2005 12:31

Hynek Urban (neregistrovaný)
4 roky pote: Pan Klima mel pravdu, titulek "Konec roku 2001 přinesl i konec současné kryptografie!" byl skutecne ponekud zkreslujici.

"Co se týká nadpisu článku... již jsem se dříve vyjádřil, že měl upoutat a přilákat čtenáře (viz předchozí diskuse)." - hm, a co je na tomhle principu nebulvarniho?

19. 1. 2002 1:07

herian (neregistrovaný)

...nebo v únoru:))

Lupa.cz: Google měl výpadek, nejel Gmail ani YouTube

Google měl výpadek, nejel Gmail ani YouTube

Root.cz: Vypadl Google a rozbilo se toho hodně

Vypadl Google a rozbilo se toho hodně

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Lupa.cz: Slevové šílenství je tu. Kde nakoupit na Black Friday?

Slevové šílenství je tu. Kde nakoupit na Black Friday?

DigiZone.cz: Česká televize mění schéma ČT :D

Česká televize mění schéma ČT :D

Lupa.cz: Propustili je z Avastu, už po nich sahá ESET

Propustili je z Avastu, už po nich sahá ESET

Podnikatel.cz: EET zvládneme, budou horší zákony

EET zvládneme, budou horší zákony

DigiZone.cz: NG natáčí v Praze seriál o Einsteinovi

NG natáčí v Praze seriál o Einsteinovi

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET

Lupa.cz: Není sleva jako sleva. Jak obchodům nenaletět?

Není sleva jako sleva. Jak obchodům nenaletět?

Podnikatel.cz: 1. den EET? Problémy s pokladnami

1. den EET? Problémy s pokladnami

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Podnikatel.cz: Prodává přes internet. Kdy platí zdravotko?

Prodává přes internet. Kdy platí zdravotko?

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu