|
Cesta kryptologie do nového tisíciletí: Od NESSIE ke
kvantovému počítači
19.09.2000 - Dnes vás čeká poslední část
našeho 4dílného seriálu o historii kryptologie, která se poprvé objevila v
temném dávnověku a která nyní češe zasloužené ovoce několikatisícového
vývoje. A právě ony triumfy budou náplní dnešního dílu, kde se budeme
věnovat žhavé současnosti. A ta je opravdu velice zajímavá, poslední dva
roky totiž kryptologie nabývá stále více na vážnosti a to zejména díky
Internetu. Neboť je to právě ona a její algoritmy (elektronický podpis,
asymetrické šifrování), které umožňují bezpečné placení po Síti.
Kryptologie již tak dávno není jen akademickou záležitostí, ale začíná
být zajímavá i po obchodní stránce a je jedno, jestli chcete vytvořit
neprůstřelnou šifru a nebo naopak nějakou zlomit. V každém případě se
jedná o velice ceněnou informaci, za kterou jsou někteří ochotni zaplatit
opravdu zajímavé částky.
Zlomové roky 1999--2000
Odborná veřejnost na konci 90. let je již dostatečně sebevědomá. Cítí,
že dospěla do situace, kdy je schopna konkurovat pečlivě střeženým
tajemstvím agentur velkých mocností. Již se neobjevují slabé šifrové
systémy, které ještě v polovině 90. let byly předkládány veřejnosti jako
bezpečné (např. Crypt, Rot13, SuperKey, N-Code). Odborná veřejnost umí
velice dobře a rychle ocenit kvalitu určitého systému. V produktech
Microsoftu (Word, Excel), Lotusu, WordPerfectu se však stále používají
nekvalitní šifrové systémy, které lze lehce rozbít. Postupně je Microsoft
sice nahrazuje za kvalitní šifru, ale z důvodu vývozních omezení je
oslabuje úpravou klíče na délku pouhých 40 bitů. Takto úmyslně upraveným
algoritmům se říká slabá kryptografie. Mimo území USA a Kanady se tak
stále v těchto produktech nacházejí slabé šifrové produkty. Toto je ovšem
výhodná situace pro evropské komerční firmy, které se snaží obsadit
evropský trh svými produkty. Americké velké firmy se snaží donutit vládu
USA k omezení
vývozních restrikcí, ale ta neustupuje. Komerční produkty vybavené
kvalitními symetrickými algoritmy (např. 3DES, CAST, RC4, Twofish) a
asymetrickými algoritmy (RSA, algoritmy na bázi diskrétního algoritmu,
algoritmy na bázi eliptických křivek) se začínají vyrábět a vyvážet nejen
v Německu, Francii, Anglii, Finsku, ale i u nás. Česká firma Decros
úspěšně vyváží své produkty nejen do Evropy, ale i do Asie. Firma AEC se
stává průkopníkem v použití asymetrické kryptografie na bázi eliptických
křivek. Produkty se stávají bezpečnými a začínají je "prodávat" již jiné
vlastnosti -- uživatelská přítulnost, kvalita klíčového hospodářství apod.
Květen 1999 je pro Českou republiku určitým ohodnocením naší vyspělosti
v této oblasti. Výbor IACR v roce 1997 rozhodl, že konference Eurocrypt
1999 se bude konat v Praze. Na konferenci je profesorem Shamirem
předvedeno optické zařízení Twinkle, které je schopno zrychlit jednu z
fází faktorizace velkých čísel a dochází tak k faktickému ohrožení klíčů
RSA o délce 512 bitů. O Shamirově přednášce se píše po celém světě,
informaci otiskuje i NewYork Times. Teprve tehdy se v několika českých
novinách objevuje zmínka o konferenci.
V srpnu 1999 pak bylo skutečně dosaženo vytouženého cíle, bylo rozbito
číslo ze souboru RSA s délkou klíče 512 bitů (155ciferné dekadické číslo).
Dodnes však nebyl přechod na klíče délky 1 024 bitů (doporučená bezpečná
délka klíčů pro RSA nejméně do roku 2002) důsledně proveden.
V létě 1999 německá vláda vydává prohlášení, ve kterém jasně
proklamuje, že na dobu dvou let ruší všechny restrikce v používání silné
kryptografie a dává celému světu najevo, že chce zaujmout rozhodující
pozici v evropském trhu s kryptografií.
Tlak amerických firem, které přicházejí o miliony dolarů, nakonec slaví
úspěch. V listopadu 1999 dochází k prvnímu uvolnění vývozních restrikcí a
další uvolnění následuje v lednu 2000. S konečnou platností je tak uvolněn
export šifrovacích algoritmů ze Spojených států (včetně zdrojových textů).
NESSIE
Jak již jsme se zmínili, na jaře roku 2000 se provádělo důkladné
hardwarové vyhodnocení algoritmů -- kandidátů AES.
Především evropská veřejnost však není úplně jednotná v hodnocení
kandidátů, v procesu výběru kandidátů a jejich hodnocení, a vznikly proto
v jejich kruzích určité rozpaky. Možná, že právě tento moment byl jedním z
faktorů nové aktivity v rámci Evropské unie, kde vznikla vlastní
iniciativa na výběr vhodných kryptografických modulů.
Jedná se o projekt NESSIE (New European Schemes for Signature,
Integrity, and Encryption) programu IST Evropské komise (http://cryptonessie.org/).
NESSIE je tříletý projekt, který byl zahájen 1. ledna 2000 a oficiálně
vyhlášen v květnu na konferenci Eurocrypt 2000. Jednotlivé moduly budou
vytvářeny na základě veřejných návrhů a rovněž tak vyhodnocení těchto
návrhů proběhne otevřenou a transparentní cestou.
Celkem se jedná o celý systém kryptografických primitivů (blokové
šifry, synchronní proudové šifry, samosynchronizující se proudové šifry,
autentizační kódy zpráv -- MAC, hashovací funkce, jednosměrné hashovací
funkce, pseudonáhodné funkce, asymetrická schémata pro šifrování,
asymetrická schémata pro digitální podpis, asymetrická schémata pro
identifikaci). Nejedná se tedy jako v projektu NIST o výběr standardu
pouze pro symetrický blokový algoritmus (AES), ale o výběr standardů pro
celou oblast kryptografie.
V rámci každé třídy budou existovat dvě bezpečnostní úrovně (normální a
vysoká), s výjimkou blokových šifer, kde bude ještě třetí úroveň
(historická-normální). To znamená, že např. blokové šifry vysoké
bezpečnostní úrovně mají pracovat s bloky textu v délce 128 bitů a s
klíčem nejméně v délce 256 bitů. Blokové šifry normální bezpečnostní
úrovně pracují rovněž s bloky otevřeného textu v délce 128 bitů a musejí
mít klíč dlouhý nejméně 128 bitů. Zmíněná třetí úroveň ponechává možnost
existence blokových šifer, které pracují s bloky otevřeného textu v délce
64 bitů (jako je tomu u většiny současných algoritmů). Délka klíče i u
této třetí úrovně však musí být minimálně 128 bitů.
První kolo končí v září 2000. Do tohoto data mají být odevzdány výchozí
návrhy.
Jedním ze základních cílů projektu je také posílit pozice evropského
kryptografického průmyslu v návaznosti na výsledky evropského výzkumu.
Zdroje
Prošli jsme se dějinami kryptologie od starověku po dnešní dobu.
Shrneme-li celý několikatisíciletý vývoj, máme nyní k dispozici
matematickou a informační teorii. Kryptologie se stala uznávanou vědou,
která se z kanceláří tajných služeb přesunula do laboratoří velkých
počítačových firem a na akademickou půdu. Přestala být tajemstvím.
Kryptologii je možné studovat. Základní kurzy jsou dostupné i pro naše
studenty na Masarykově univerzitě v Brně, na Matematicko-fyzikální fakultě
UK v Praze nebo na ČVUT. Byly zrušeny vývozní a jiné administrativní
překážky. Legislativa upravuje použití elektronických podpisů. Vědci umí
navrhnout bezpečné šifrovací algoritmy, které se liší spíše jen parametry
implementačními (rychlost, nároky na paměť) než bezpečnostními. Jsou
vypracovávány a přijímány mezinárodní standardy a normy. Zdá se, že vývoj
je v podstatě ukončen.
Teoretické hrozby současné kryptografii
Je vůbec něco, co může ohrozit současné symetrické nebo asymetrické
algoritmy mimo hrubou sílu -- mimo zvyšující se výpočetní potenciál?
Zvyšujícímu se výpočetnímu potenciálu, který má kryptoanalytik k
dispozici, se dá lehce čelit zvětšováním klíčů. Současné používané délky
klíčů 128 bitů by měly při zachování rychlosti vývoje výpočetní techniky
(zdvojnásobení výkonu zhruba každé dva roky) odolat desítky let. Autoři
Lenstra a Verheul na základě hluboce sofistikované analýzy docházejí
přitom k poměrně velice přísným doporučením pro rok 2020 (aby bezpečnost
elektronické informace byla garantována pro období 20 let); symetrické
klíče by měly mít minimálně délku 86 bitů, modul RSA minimálně 1 881 bitů,
analogicky i modul pro diskrétní logaritmus, pro eliptické křivky by měla
být minimální délka klíče 161 bitů.
Nyní zdánlivě odbočíme. CMI (Clay Mathematics Institut of Cambridge)
vyhlašuje na konferenci v Paříži 24. 5. 2000 sedm matematických problémů
tisíciletí. Současně je připraven fond se sedmi miliony dolary. Za řešení
každého z problémů je vypsána odměna jeden milion dolarů. Neočekává se, že
budou vyplaceny příliš brzy. První z problémů má velice jednoduchý název:
"P versus NP." Problém vychází z teorie složitosti. Složitost algoritmu je
dána výpočetním výkonem nárokovaným pro jeho realizaci. Často se hodnotí
dvěma proměnnými -- časovou nebo prostorovou náročností. Obecně se
výpočetní složitost algoritmu vyjadřuje "velkým" O -- řádem (Order) --
hodnoty výpočetní složitosti. Bude-li například T=O(n), pak zdvojnásobení
velikosti vstupu zdvojnásobí dobu zpracování; takový algoritmus nazveme
lineární. Je-li složitost na n nezávislá, píšeme O(1). Doba zpracování
algoritmu se při zdvojnásobení vstupu nezmění. Bude-li T=O (2n ), pak
zvětšení velikosti vstupu o 1 bit prodlouží dobu zpracování na dvo
jnásobek. Algoritmy mohou být z hlediska složitosti kvadratické,
kubické apod. Všechny algoritmy typu O(nm ) se nazývají polynomiální.
Třída P potom obsahuje všechny algoritmy, které mohou být řešeny v
polynomiálním čase.
Dále definujme Turingův stroj jako konečný automat s nekonečnou
čtecí-zapisovací páskovou pamětí. Čtenář si může představit klasický
domácí počítač, ale rozšířený o nekonečnou paměť. Třídu NP definujeme jako
všechny problémy, které mohou být řešeny v polynomiálním čase pouze
nedeterministickým Turingovým strojem: tj. variantou normálního Turingova
stroje, která může provádět odhady. Stroj odhaduje řešení problémů -- buď
tak, že metodou pokusů hádá správné řešení nebo tak, že paralelně provede
všechny pokusy -- a výsledky těchto pokusů prověřuje v polynomiálním čase.
Třída NP zahrnuje třídu P, protože jakýkoliv problém řešitelný v
polynomiálním čase deterministickým Turingovým strojem je také řešitelný v
polynomiálním čase nedeterministickým Turingovým strojem. Jestliže všechny
problémy NP jsou také řešitelné v polynomiálním čase deterministickým
strojem, pak NP = P. Otázka platnosti P = NP je ústředním nevyřešeným
problémem teorie výpočetní složitosti. Nyní se z naší zdánlivé odbočky
vrátí
me k samotným základům současné kryptografie. Kdyby někdo prokázal, že
P = NP, pak bychom většinu toho, na čem je založena současná moderní
kryptologie, mohli odepsat. Znamenalo by to, že pro všechny symetrické
problémy existuje kryptoanalytický (luštitelský) algoritmus, který je
časově polynomiální. Pro lepší pochopení jen podotkneme, že útok hrubou
silou je "nesrovnatelně" horší -- jeho složitost je tzv.
superpolynomiální. V takovém případě by naše neschopnost řešit algoritmy
typu 3DES a AES v rozumném čase znamenala jen to, že se nám zatím
nepodařilo najít vhodný luštící algoritmus. Většina současných odborníků
se však domnívá, že rovnost tříd problémů P a NP neplatí. Vyplacení
jednoho milionu dolarů matematikovi v případě, že dokáže nerovnost tříd P
a NP (a tím zároveň dokáže, že současné blokové algoritmy jsou opravdu
bezpečné), není ve světle právě popsaných skutečností přehnaně vysoké
ocenění.
Je zde ještě jedna cesta, která může ohrozit pracně dostavěnou budovu
kryptografie nebo alespoň některou z nejdůležitějších částí. 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 Shor prokázal existenci kvantového polynomiálního algoritmu pro
řešení diskrétního algoritmu a úlohu faktorizace 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 (RSA, Diffie-Hellman), které jsou
založeny na obtížné řešitelnosti úlohy faktorizace a úlohy diskrétního
logaritmu (tyto úlohy nepatří do třídy NP problémů, ale jen do speciální
třídy těžce řešitelných problémů). Konstrukce kvantového počítače podle
některých odborníků není takovou utopií, jak by se na prvý pohled mohlo
zdát. Někteří experti odhadují, že doba k faktické realizaci by mohla být
kolem dvaceti let.
Na úplný závěr se vrátíme zpět do poloviny našeho roku 2000. Jaký dopad
může čtenář osobně očekávat od celého tohoto vývoje ? Nastala doba, kdy
softwarové a hardwarové firmy mohou tvořit na základě standardů a norem
bezpečné aplikace. Pokud firmy vyřeší bezpečné a uživatelsky jednoduché
uchovávání klíčů, pak se nebude muset čtenář bát, že produkty, které nějak
prokáží svoji shodu s těmito celosvětovými standardy (na základě validace,
certifikace apod.) jsou děravé. Bezpečné kryptografické produkty (společně
s právními akty -- zákony, vyhláškami) povedou k nebývalému rozšíření
kryptografie. Zatímco aplikovaná kryptologie byla dříve výsadou tajných
služeb, armád a diplomacie, stává se během posledních deseti let věcí
veřejnou a současně i výnosným obchodem. Zahajuje svoje masové tažení za
všemi uživateli výpočetní techniky. Pojmy jako státní informační systém,
e-business, e-commerce, e-obchodování, elektronický notář, kvalifikovaný
certifikát, ochrana osobních dat a další se stanou samozřejmou součástí
našeho jazyka a jejich realizace bude možná právě díky kvalitním
kryptografickým produktům a právnímu zajištění.
Zajímavé odkazy:
* http://www.aec.cz/ -- zajímavé texty
věnované šifrovaní, určitě si pak přečtěte firmou vydávaný bulletin
* http://www.decros.cz/Security_Division/Crypto_Research/publikace.htm
-- stránky další známé české firmy obsahují také řadu cenných
materiálů
*http://www.fi.muni.cz/usr/staudek/vyuka/security/P017.html
-– řada zajímavých textů určená k výuce vysokoškolských studentů
* http://www.mujweb.cz/veda/gcucmp/
-- domovské stránky GCUCMP(Group of Cryptology Union of Czech
Mathematicians and Physicists), kromě řady informací od autora tohoto
textu se můžete přihlásit k odběru e-zinu Crypto-World
* http://www.mujweb.cz/veda/bitis/
-- stránky BITIS (Sdružení pro bezpečnost informačních technologií a
informačních systémů), informace o veřejně pořádaných seminářích
* http://www.obluda.cz/crypt.htm
-- řada informací, včetně zajímavých odkazů
* http://www.pgp.cz/ -- stránka
věnovaná známému standardu PGP
* http://www.cw.cz – kromě denního
zpravodajství si můžete stáhnout Seriál “Bezpečnost pro všechny, soukromí
pro každého”
|