Úvod

Šifra může být obecně cokoliv, co z čitelných dat dělá nějaká jiná takovým způsobem, že jdou zpátky rozšifrovat. Jakou šifru použijeme, záleží na situaci. Protože nám tentokrát jde o použití v počítači, budeme se zajímat o odpovídající šifry: založené na matematice, schopné pracovat s libovolnými daty a pokud možno neprolomitelné ani v situaci, kdy útočník zná zdrojový kód programu. Aby to dávalo smysl, k šifrování se navíc používá klíč, který se ve většině případů volí nějak náhodně. Útočník zná šifru, ale nezná klíč, takže by neměl být schopný číst zprávy.

Motivační otázky

Šifry založené na posuvu v abecedě

Máme zprávu nějaké délky a klíč nějaké délky, obojí je napsané písmeny, kterých je – dejme tomu – třicet. Jednoduchá a docela dobrá šifra je založená na tom, že klíč podle potřeby zopakujeme několikrát až do délky zprávy a pak odpovídající písmena zprávy a klíče sečteme podle jejich pořadí v abecedě. Pro rozšifrování stačí odečíst.

Pokud je zpráva několikrát kratší než klíč, dá se to rozlousknout tak, že délku klíče tipneme a zprávu rozdělíme na znaky, které jsou posunuté o stejný počet (padlo na ně stejné písmeno klíče). Jednotlivá písmena klíče pak jde často dohledat s nějakými obvyklými znalostmi o zprávě, třeba v případě lidského textu pomocí frekvenční analýzy. Když se to nepovede, možná jsme délku klíče tipli špatně.

Pokud jsou klíč a zpráva stejně dlouhé, klíč je náhodný a nepoužijete ho nikdy znovu, rozluštit to zákonitě nejde: ke každému výsledku se dá najít odpovídající klíč, takže nejde poznat, který výsledek je ten správný. Tomu se říká one-time pad. Nevýhoda je, že příjemce musí mít tentýž klíč k dispozici pro čtení zprávy a útočník klíč mít nesmí. Můžete například agentům v terénu rozdat flashdisky se šifrovacím klíčem pro jedno použití, každému jiný. Pro použití na Internetu to ale moc k ničemu není.

Nejjednodušší možná abeceda je binární: 0, 1. Stejně jako v případě jiných abeced se musí příliš velká čísla zatočit dokola, takže 1+1=0. Tomu se říká XOR-šifra.

Dvojité šifrování

Omlouvám se za omyl, schéma s dvojitým šifrováním, jak jsem ho popsal na hodině, nefunguje. Velký Bratr, vidí-li všechny zprávy, může totiž snadno zjistit oba šifrovací klíče a potom přečíst zprávu. Přesto tady pro úplnost píšu, jak schéma vypadalo.

Odesílatel vymyslí tajný klíč, zprávu s ním zašifruje a pošle. Příjemce si vymyslí jiný klíč, šifrovanou zprávu zašifruje znovu a vrátí zpátky. Odesílatel potom zprávu rozšifruje svým klíčem; výsledkem by měla být zpráva zašifrovaná jen klíčem příjemce, tak ji pošle a je hotovo.

Když ale použijeme šifru založenou na posuvu v abecedě, jdou oba klíče zjistit prostě odečtením první a druhé, resp. druhé a třetí zprávy. Složitější šifry, které tohle nedovolují, naopak ale nejde dešifrovat v opačném pořadí: zprávu by bylo potřeba dešifrovat nejdřív klíčem příjemce a potom klíčem odesilatele, takže to taky nebude fungovat. Vypadá to, že všechny známé šifry trpí jedním nebo druhým problémem.

Jiné symetrické šifry

V praxi se používá spousta šifer, které mají docela krátké klíče a přesto (si myslíme, že) je nikdo rozlousknout nedokáže. Nejznámější z nich je asi americká DES (Data Encryption Standard), dále třeba Blowfish a AES. Není za nimi nic moc vznešeného, jen hodně mixování dat tam a zpátky. Blowfish a DES jsou podobné: v každém kroku šifry se půlka dat (spolu s klíčem) použije k zašifrování druhé půlky a na střídačku se tenhle výpočet opakuje, nejčastěji šestnáctkrát pro obě strany. Bezpečné jsou proto, že je zatím nikdo rozluštit (jak se zdá) nedokázal.

Asymetrická kryptografie

Pro psaní a čtení šifrované zprávy se dají používat různé klíče. Jeden z nich označíme jako veřejný a opravdu ho dáme všem; druhý je soukromý a musíme na něj dávat pozor. Ani v tomhle případě nemáme bohužel matematický důkaz, ale zdá se, že některé výpočty jsou jednosměrné. Spoléháme tedy na to, že veřejným klíčem jde tedy zprávy jen psát, ale ne číst, a naopak.

Když chcete poslat někomu šifrovanou zprávu, potřebujete jeho veřejný klíč. K přečtení je potřeba soukromý klíč, takže to nedovede nikdo kromě zamýšleného příjemce (pokud si ten dává na svůj soukromý klíč pozor).

Nejslavnější asymetrická šifra je RSA (Rivest, Shamir, Adleman). Je založená na malé Fermatově větě, tedy umocňování v konečných tělesech. Z její podstaty vyplývá, že by nebyla bezpečná, kdyby někdo uměl rychle rozkládat obrovská čísla na součin prvočísel – zatím se ale zdá, že to rozumně rychle nejde. Čísla, o jakých se bavíme, jsou řádově 21000, tedy jednička a za ní tři sta nul. Násobit, sčítat a umocňovat ale taková čísla umíme přijatelně rychle. Podobně velká je také abeceda, ve které šifra pracuje; delší zprávy můžeme například nakrájet na kusy po patřičném počtu bitů.

Hashování

Výpočty, které nikdo neumí rychle počítat v opačném směru, jsou zajímavé i v jiných případech. (V předchozím odstavci jsme narazili na to, že násobit čísla velikosti 21000 jde rychle, ale zjistit z výsledku oba činitele trvá věky.) Například se dají použít k úspornému ověřování velkých dat tak, aby v nich nikdo nemohl změnit jediný bit.

Poznámky z dřívějška. Nemusíte znát podrobně, ale měli byste chápat, k čemu jsou hashovací funkce dobré.

Digitální podpisy a certifikáty

Digitální podpis

Některé asymetrické šifry jde obrátit a zveřejnit jen klíč, kterým se zprávy čtou (RSA to například umožňuje). Když klíč pro šifrování necháte v tajnosti, zaručí příjemcům, že jste šifrovanou zprávu psali vy.

V praxi často chceme, aby zprávu mohl číst kdokoliv (i bez veřejného klíče) a podpis byl jen jakási značka navíc, proto nepodepisujeme přímo zprávu, ale jen její hash. Ten bývá mnohem kratší. Potřebné výpočty jsou pak také výrazně úspornější.

Certifikáty

Žádná matematická konstrukce nám nedovede číst občanku a ověřit, že veřejný klíč opravdu patří k našemu jménu. Jedním způsobem, jak situaci vyřešit, je zřídit úřad (zvaný certifikační autorita), který bude klíče vydávat a potvrzovat. Udělá to tak, že k veřejnému klíči napíše jméno uživatele (nebo třeba adresu serveru, a podobně) a digitálně to podepíše svým klíčem. Problém je vlastně pořád tentýž, ale stačí pak mít zaručený jeden klíč úřadu, abychom se cítili bezpečně na celém Internetu. V praxi se ta první sada klíčů dodává jako součást operačního systému, spoléháme tedy na to, že do systému před instalací ani po ní nikdo zlovolně sáhnout nedokáže.

Bezpečnost na webu

Pro zabezpečené stahování webových stránek slouží protokol HTTPS (S na konci je důležité, znamená Secure). Zaručuje, že:

Když zadáte omylem jinou webovou adresu, vůbec nepoužijete protokol HTTPS anebo se nebude stránka šifrovaně přenášet celá, žádné záruky nemáte a může se stát cokoliv.


Zápisky jsem v hodině probral potud. Později možná ještě doplním další důležité odstavce.

PGP

Třešničky