s e r i á l y a č l á n k y >
Část 26 - CW 36/97
Antonín Beneš
Dovolili bychom si na tomto místě upozornit ctěného P. T. čtenáře, že k mnohým otázkám, kterých se tento přehled pouze dotýká, se seriál vrátí ve svých následujících dílech. Berme toto pojednání jako zběžný průzkum území.
Abychom si rozuměli
Předpokládejme, že jsme se dohodli na nějakém způsobu zápisu (nebo chcete-li kódování) myšlenek. Za tímto účelem používáme znaky jisté abecedy. V první fázi jsou všechny myšlenky popsány způsobem, který je obecně srozumitelný. Tomuto zápisu budeme nadále říkat otevřený text (plaintext). Pro jednoduchost budeme dále zápis myšlenky označovat slovem zpráva.
Šifrovací algoritmus otevřenému textu přiřadí odpovídající zašifrovaný text (ciphertext). Zašifrovaný text přitom není nic jiného, než jiné kódování stejné zprávy. Toto kódování má ovšem tu příjemnou vlastnost, že je srozumitelné pouze omezenému okruhu čtenářů zprávy. Poněkud nepřesně lze říci, že zatímco k přečtení otevřeného textu vystačíme se znalostí způsobu kódování, k přečtení zašifrovaného textu potřebujeme navíc ještě další informaci. Této informaci říkáme klíč.
Formálněji řečeno je šifrovací algoritmus parametrické zobrazení, které otevřenému textu přiřazuje odpovídající zašifrovaný text. Aby bylo možno zašifrovaný text jednoznačně převést zpět do podoby otevřeného textu (dešifrovat), musí toto zobrazení být injektivní. Parametrem zobrazení je klíč. Volbou klíče vybereme jedno konkrétní "mapování" prostoru otevřených textů do prostoru zašifrovaných textů. Poznamenejme ještě, že abeceda otevřeného textu a abeceda zašifrovaného textu mohou být
obecně různé.
"Tvrdý chlapi používají tvrdý algoritmy"
Jaké má vlastnosti kryptograficky silný šifrovací algoritmus? Tak především -- jím popisované mapování otevřených textů na odpovídající zašifrované texty je co nejkomplikovanější. Změny v otevřeném textu by měly ústit v co nejnáhodnější změny výsledné šifry. Tuto vlastnost nazýváme zmatení (confusion).
Další důležitou vlastností je difuze. V průběhu šifrování je třeba zajistit, aby pokud možno každá část zašifrovaného textu závisela na každé části původního plaintextu. V takovém případě i malá změna otevřeného textu vyvolá změnu celého zašifrovaného textu, což ztěžuje analýzu.
Je nutné, aby algoritmus měl dostatečně velký prostor klíčů. Výsledek práce dobrého algoritmu musí při všech standardních statistických testech vypadat jako náhodná posloupnost -- jako tzv. bílý šum. Algoritmus by měl být dobře definovaný a verifikovatelný, neměl by klást omezení na vlastnosti otevřeného textu.
Další požadavek je poněkud v rozporu s požadavkem difuze: algoritmus by neměl propagovat chyby při šifrování, či komunikaci a ovlivňovat tak další tok informace. Zajímavou vlastností je tzv. interval jedinečnosti (unicity distance). Tato veličina říká, jak dlouhý zašifrovaný text již má s vysokou pravděpodobností pouze jeden možný způsob dešifrování. Platí čím větší, tím lepší.
Bezpečnost šifrovacího algoritmu by neměla záviset na jeho (ne)znalosti. Naopak, je velmi vhodné, aby autoři nový algoritmus předložili k veřejné oponentuře. Znakem kvality algoritmu nejsou tvrzení jeho tvůrců, ale schopnost odolávat
úsilí mnoha odborníků z celého světa.
Krajní meze
Pod pojmem bezpečnost šifrovacího algoritmu rozumíme jeho odolnost vůči úsilí neautorizované strany o získání přístupu k otevřenému textu, nebo ještě lépe ke klíči, na základě jemu dostupných informací. Některé metody, které k tomu může používat, jsou uvedeny dále.
Ideální případ představuje absolutně bezpečný algoritmus. Takový algoritmus zaručuje, že není možné na základě zachycené šifry zjistit původní otevřený text. Docílit popsané vlastnosti je však mimořádně obtížné, i když ne nemožné. Mnohdy se musíme spokojit pouze s efektivně bezpečným algoritmem. Zde je pravděpodobnost, že se útočníkovi podaří otevřený text získat v rozumném čase, dostatečně malá. To znamená, že problém nalezení otevřeného textu je algoritmicky řešitelný, ale díky nárokům na čas a výpočetní výkon prakticky nerealizovatelný.
Pokud má útočník zachytivší zašifrovanou zprávu stejnou naději na nalezení původního otevřeného textu, jako by měl bez této informace a tato pravděpodobnost odpovídá pravděpodobnosti výskytu tohoto otevřeného textu, hovoříme o perfektním utajení (perfect secrecy). Zachycení zašifrované zprávy v tomto případě útočníkovi nijak neprospěje v jeho úsilí rozluštit šifru.
Při posuzování bezpečnosti či kvality šifrovacích algoritmů je nutné vzít v úvahu dobu a prostředí jejich vzniku, stejně tak jako oblast zamýšleného nasazení. Mnohé z dnes snadno zlomitelných algoritmů mohly být v době svého vzniku velmi kvalitními a bezpečnými šiframi. Nasazení výpočetní techniky odsunulo do pozadí téměř všechny starší algoritmy. Zvyšování výkonu počítačů v dnešních dnech přináší zkázu algoritmu,
který zašifroval nejvíce dat ze všech -- DESu.
Bylo, nebylo
Jedním z prvních, o kom se dovídáme, že se úspěšně poměřil s problémem šifrování, nebyl nikdo menší, než Julius G. Caesar. Jeho myšlenka byla velmi jednoduchá. Každé písmenko zprávy nahradil písmenem, které je v abecedě o tři místa dále (A -> D ... Z -> C). Tento šifrovací algoritmus je speciálním případem monoalfabetické substituce. Všechny podobné algoritmy nahrazují každý znak abecedy otevřeného textu znakem jiné abecedy. Slabina těchto algoritmů spočívá ve faktu, že různé znaky mají různou pravděpodobnost výskytu. Je tedy snadné určit přiřazení nejfrekventovanějších znaků a ostatní doplnit tak, aby text dával smysl. Výrazné zlepšení nepřinesl ani nápad rozdělit zprávu na několik stejných částí a na každou z nich aplikovat monoalfabetickou substituci. U této tzv. polyalfabetické substituce není složité určit počet použitých substitucí na základě analýzy výskytu opakujících se řetězců v zašifrovaném textu.
Namísto nahrazování znaků jinými se můžeme pokusit dostatečně zamíchat pořadím jednotlivých znaků. Tyto tzv. permutační šifry se vyskytovaly v mnoha podobách. Jednoduchým modelem permutační šifry je matice, do které po řádcích zapíšeme zprávu. Opsáním matice po sloupcích vznikne zašifrovaný text. Lehkou obměnou tohoto postupu je proužek papíru, který navineme na váleček. Poté zapíšeme zprávu po řádcích ve směru podélné osy válečku. Po rozvinutí je na proužku zašifrovaná zpráva. K jejímu přečtení potřebujeme váleček odpovídající tloušťky. Analýzou digramů a trigramů (dvoj- a trojznakové skupiny) však lze zlomit i tyto šifry.
Postupem času docházelo k neustálému zlepšování šifrovacích algoritmů. Nekorunovanými králi mezi šifrovacími algoritmy používanými před nástupem počítačů byly rotorové stroje, z nichž nejslavnější je Enigma. Elektrický impulz z klávesnice po úvodním permutaci realizované svorkovnicí je veden přes soustavu různou rychlostí se otáčejících rotorů s kontakty na výstupní konzoli. Způsob zašifrování vstupního znaku je tedy dán zapojením svorkovnice a všech rotorů a jejich aktuálním nastavením.
Historie nám po sobě též zůstavila absolutně bezpečnou šifru -- Vernamovu šifru. Tento algoritmus šifruje tím způsobem, že otevřený text kombinuje, například pomocí operace XOR, s náhodnou neopakující se sekvencí stejné délky, jako původní zpráva. Dešifrování se provádí opětovným zkombinováním zašifrovaného textu se stejnou náhodnou posloupností.
Pokud však je náhodná posloupnost použita dvakrát, ztrácí šifra svoji absolutní bezpečnost. Aby se tomuto předešlo, měli šifréři k dispozici bloček s lístky popsanými náhodnou posloupností znaků. Po zašifrovaní zprávy byl lístek zničen aby nemohl být omylem použit znovu. Odtud označení této šifrovací metody one-time pad. Dodejme ještě, že použití textů z knih na místě náhodné posloupnosti rovněž vede ke ztrátě absolutní bezpečnosti, neboť sekvence znaků přirozeného jazyka nemá náhodné rozložení.
Lidé v minulosti používali nepřeberné množství různých šifrovacích algoritmů. Pouze jejich výčet by patrně přesáhl rozměry tohoto článku. Uvedený výběr pouze shrnuje nejčastěji používané principy, a to ani zdaleka ne všechny. Společným rysem všech je malá velikost prostoru klíčů či příliš jasná korelace mezi otevřeným a výsledným
zašifrovaným textem.
Z historie do žhavé současnosti
Nástup počítačů a elektronické zpracování informací s sebou přinesly obrovský rozvoj šifrovacích algoritmů a mnoha dalších nových odvětví kryptografie. Tím, že proces šifrování převzaly stroje, odpadl požadavek na jednoduchost a pochopitelnost algoritmu, aby jej mohl realizovat člověk. Kryptografie dnes nejsou jen vlastní šifrovací algoritmy, ale též problematika správy šifrovacích klíčů, kryptografické protokoly, kryptografické hašovací funkce atd. Velmi důležitá je otázka generování pseudonáhodných čísel či posloupností. Změnily se i samotné šifrovací algoritmy. Dnes jich používáme mnoho druhů, přičemž každý z nich má specifický okruh nasazení.
Pokud algoritmus zpracovává svůj vstup bit po bitu, hovoříme o proudové šifře. Proudové šifry jsou vhodné k šifrování sériových linek či přenosových kanálů, kde data jsou přenášena postupně po malých částech. Většina algoritmů však zpracovává svůj vstup po blocích jisté délky. Ty nazýváme blokové šifry. Výsledkem jejich práce jsou bloky zašifrovaného textu. Šifrování jednotlivých bloků je přitom naprosto nezávislé. To však není vždy žádoucí a proto byly vypracovány metody, jak vnést určitou míru závislosti do šifrování jednotlivých bloků.
V úvodu jsme se zmínili, že k šifrování a dešifrování potřebujeme mimo jiné též jakousi dodatečnou informaci zvanou klíč. V závislosti na tom, zda k oběma těmto operacím používáme stejného klíče či nikoliv, hovoříme o symetrických, resp. asymetrických šifrách. Pokud používáme rozdílného klíče, označujeme tyto klíče jako šifrovací, resp. dešifrovací klíč. Klíč používaný zároveň pro obě operace bývá nazýván konvenčním klíčem. Na počátku 70. let vznikly systémy s veřejným klíčem. Jde o asymetrické šifrovací algoritmy, které mají tu vlastnost, že jeden z klíčů -- veřejný klíč -- může být zveřejněn. Z jeho znalosti není možné odvodit druhý -- tajný -- klíč.
Poměrně rozšířená je nesprávná domněnka, že systémy s veřejným klíčem odstraňují problémy s distribucí klíčů a s navazováním šifrované komunikace. To, bohužel, není pravda. Pouze namísto starostí o utajení klíče musíme řešit neméně závažné otázky integrity a autenticity veřejného klíče, jinak bychom se vystavovali hrozbě "man-in-the-middle" útoku (kdy obě strany nevědomky komunikují skrze zákeřného prostředníka). Pravdou je, že komunikační systém používající algoritmy s veřejným klíčem pracuje s menším množstvím klíčů (jeden pár na uživatele), než symetrické systémy, které potřebují jeden klíč na každou dvojici komunikujících. Skutečnou výhodou systémů s veřejným klíčem je možnost vytvářet veřejně ověřitelné elektronické podpisy. To lze za použití symetrických algoritmů zvládnout pouze s pomocí třetí nezávislé strany -- arbitra.
Přestože s použitím algoritmů s veřejným klíčem lze zvládnout vše, co dokáží symetrické algoritmy, neznamená to, že by symetrické šifry neměly své místo na slunci. Jejich výhodou je značná rychlost, měřeno počtem provedených instrukcí na jeden zašifrovaný bajt. Naopak algoritmy s veřejným klíčem lze disjunktně rozdělit na ty, které jsou bezpečné, a na ty, které jsou rychlé. Častým řešením proto bývá hybridní systém, kde algoritmy s veřejným klíčem jsou použity pro ustanovení konvenčního klíče a pro elektronické podpisy, a symetrické algoritmy se používají pro šifrování přenášených uživatelských dat.
Šifrovací algoritmy již neplní pouze svoji prvotní funkci utajování informací, ale jsou též používány pro zajištění integrity a též i dostupnosti dat. Elektronicky podepsaný nebo i jen zašifrovaný dokument lze nepozorovaně poškodit daleko složitěji, než by to bylo možné v případě otevřeného textu. Utajení dat nepřímo napomáhá jejich dostupnosti, neboť vylučuje možnost selektivních útoků.
Oblíbeným tématem dnešních dnů je problematika správy klíčů pro šifrovací algoritmy. Nejde již jen o otázky distribuce klíčů a jejich uložení. Řeší se protokoly, které v rámci jisté podskupiny uživatelů vytvoří prostřednictvím nechráněných linek sdílený -- tzv. konferenční klíč, umožňující účastníkům konference bezpečnou komunikaci, které nemůže rozumět nikdo jiný.
Zajímavým druhem šifrovacích algoritmů jsou prahová schémata. Namísto toho, abychom zprávu hezky spořádaně zašifrovali vcelku a tak ji udrželi v tajnosti, můžeme ji rozložit na několik částí, z nichž žádná sama o sobě nedává smysl. Původní zprávu můžeme získat opětovným složením těchto částí. Kouzlo spočívá ve faktu, že ke složení původní
zprávy nemusíme použít všech, ale pouze několika částí.
Cože, kaše?
Všimněme si, že až doposud jsme se drželi reverzibilních operací. Co jsme si zašifrovali, to jsme vždy dokázali i rozšifrovat. Někdy nám však nejde o informaci samotnou, ale spíše o fakt její existence. Jindy je naopak vhodné rozsáhlou zprávu "srazit" na co nejmenší kousek dat, který však dobře závisí na každé části zprávy. A někdy dokonce nechceme, aby bylo možné provést dešifrování. To všechno jsou případy, kdy je vhodné použít kryptografické hašovací funkce. Výsledkem jejich práce je řetězec pevné délky, který dobře závisí na původní zprávě.
Hašovacích funkcí používáme v systémech se symetrickými šifrovacími algoritmy k zajištění autenticity a integrity zpráv. V systémech s algoritmy s veřejným klíčem slouží ke zrychlení tvorby elektronických podpisů. Jsou velmi vhodným prostředkem pro ochranu hesel a přístupových frází. Rozdělení hašovacích funkcí a stručný popis způsobu jejich
použití byl podán v článku o integritě.
Náhoda je dřina
Jakkoli se svět topí v chaosu, kryptografové se potýkají s hrubým nedostatkem nedeterminismu. Šifrovací klíče, inicializační vektory hašovacích funkcí, vycpávací zátěž, to vše musí být náhodné hodnoty. Nezbývá nám, než algoritmicky generovat náhodu.
Nevýhodou všech algoritmických generátorů je, že se po nějakém čase zacyklí. Tuto dobu nazýváme periodou generátoru. Snahou samozřejmě je, aby perioda byla co nejdelší. Navíc požadujeme, aby generátor nebyl predikovatelný, tzn., aby na základě znalosti předchozích výstupů nebylo možno odhadovat jeho příští hodnoty.
Nejběžnější, avšak zcela nevhodný, je kongruenční generátor pracující dle vztahu
Xi = (aXi-1+b) mod m
Oblíbené jsou generátory založené na posuvných registrech se zpětnou vazbou. Ty fungují tak, že první bit je XORován s bity na pozicích daných vybírací sekvencí (tap sequence). Následně se obsah registru posune o jednu, první bit je výstupem generátoru a na uvolněné místo je zapsán výsledek XORu. Posuvné registry lze pro dosažení ještě lepších vlastností kombinovat (viz obr. 3). Velmi kvalitní generátor je tzv. RSA generátor pracující podle předpisu
Xi = Xei-1 mod n
Výstupem je nejnižší bit řetězce Xi.
Dobrý generátor náhodných čísel je velmi důležitá věc, neboť s nekvalitním klíčovým materiálem je i ten nejlepší
šifrovací algoritmus naprosto bezbranný.
Jak být v klidu
Co dnes považujeme za bezpečný šifrovací algoritmus?
Za samozřejmost považujeme, že algoritmus je dobře navržen. To znamená, že neexistuje netriviální metoda jeho zlomení, která by byla výrazně rychlejší než prosté vyzkoušení všech možných klíčů. Jinak řečeno, zlomení algoritmu je ekvivalentní vyřešení nějakého dostatečně složitého problému. V takovém případě se bezpečnost algoritmu opírá o velikost prostoru klíčů, nebo chcete-li -- o délku klíče. Délka klíče přibližně odpovídá logaritmu velikosti prostoru klíčů.
Činit odhady bezpečnosti je velmi ošemetné. Pro symetrické algoritmy typu DES je za hranici bezpečnosti považována délka klíče 56 bitů. Obecně se má za to, že superpočítače, kterými disponují některé rozvědky či vládní instituce, jsou schopny si s 256 klíči poradit během několika málo hodin. Pro asymetrické algoritmy založené na problému faktorizace velkých čísel (RSA), leží na hranici bezpečnosti klíče s délkou 512 bitů. Je to proto, že zde ke konstrukci klíčů používáme pouze prvočísel, která jsou řidší.
Chceme-li však zajistit bezpečnost našich dat i s výhledem do budoucnosti, musíme volit v případě symetrických algoritmů délku klíče alespoň 80, raději však 128 bitů. Pro asymetrický algoritmus RSA je třeba použít klíč o délce 1 024 nebo dokonce 2 048 bitů, u algoritmů pracujících s výpočty nad eliptickými křivkami vystačíme s cca 170 bity.
Noční můrou všech kryptografů je poskytování záruk na bezpečnost dat do budoucnosti. Výkon počítačů stále roste -- odhaduje se, že každé dva roky se ztrojnásobí. Daleko větší nebezpečí však představují technologické kroky. Mnohé útoky proti šifrovacím algoritmům lze velmi dobře paralelizovat. Internet, který spojil miliony počítačů po celém světě, dal vzniknout virtuálnímu stroji složenému z běžných počítačů, který před několika týdny pokořil DES. Pokud by se někomu podařilo postavit skutečně paralelní počítač třídy C2, dokázal by jeho pomocí rozesmutnit mnoho kryptografů na celém světě. Fungující kvantový Turingův stroj by znamenal konec RSA. Faktem zůstává, že uskutečnění těchto kroků nelze předpovídat. Je pouze téměř jisté, že nějaké nastanou. Někdy.
Nenechte si lhát
Vhodně použité kvalitní šifrovací algoritmy jsou schopny s velmi vysokou mírou jistoty zajistit utajení vašich dat před kýmkoliv. Tento fakt je trnem v oku některým, povětšinou vládním, organizacím po celém světě. Ty se snaží prosadit zákaz používání silných šifrovacích algoritmů přinejmenším v soukromé a komerční sféře. Necháme čtenářově úsudku, nakolik se za vznešenými pojmy, jako národní bezpečnost, stíhání zločinců apod., kterými obvykle argumentují, skrývá obyčejná touha moci špehovat.
Má člověk právo na své soukromí? Opravdu musí používat neznámý šifrovací algoritmus, o kterém ví pouze to, že po zadání správného hesla lze získat použitý šifrovací klíč? Podobné otázky je třeba si klást, neboť k nim v brzké době dojdou i naši zákonodárci. Právo na soukromí je zakotveno v Listině základních práv a svobod. Jedním z vedlejších efektů současného rozvoje techniky je však jeho výrazné omezování. Kryptografie by mohla tento trend poněkud vylepšit. Nedejme se proto ochudit o prostředky, které nám nabízí.
Kutilům vstup zakázán
Konstrukce šifrovacích (a hašovacích) algoritmů je velmi obtížná práce. Rozhodně by se do ní neměl pouštět někdo bez hlubokých znalostí problematiky, neboť pravděpodobnost neúspěchu je takřka rovna jedné. Bohužel, kryptografie je obor, kde se chyby neodpouštějí. Pokud svá data chcete udržet v tajnosti po dobu padesáti let a nepřítel zachytil vaši zašifrovanou komunikaci, nezbývá vám než věřit, že použitá šifra bude schopna celou tu dobu odolávat jeho úsilí. Nemůžete data o poločase přešifrovat bezpečnějším algoritmem.
Vzhledem k praktické nemožnosti podat důkaz o bezpečnosti je dobrá šifra věcí, která, podobně jako dobré víno, vzniká v průběhu dlouhých let. Až čas dá autorovi za pravdu
a uživatelům dodá důvěru v daný algoritmus