Student World

NESSIE je tříletý projekt, který byl zahájen 1. ledna 2000 a oficiálně vyhlášen v květnu na konferenci Eurocrypt 2000.
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 dvojná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í.

autor Pavel Vondruška