1 Komprimace a šifrování Mgr. Tomáš Foltýnek, Ph.D., Ing. Jan Přichystal, Ph.D.2 2 Obsah Obsah Cíl studia 3 Úvod 3 Využití komprimace a šifrování 4 Po...
Mgr. Tomáš Foltýnek, Ph.D., Ing. Jan Přichystal, Ph.D.
2
Obsah
Obsah Cíl studia
3
Úvod
3
Využití komprimace a šifrování
4
Poučení
5
Návaznost
5
Poděkování
5
Teorie informace
6
Úvod do kompresních algoritmů
11
Komprese multimediálních dat
19
Úvod do kryptologie
30
Historie kryptografie a kryptoanalýzy do konce druhé světové války
34
Substituční šifry
46
Generování náhodných čísel
54
Transpoziční šifry. Superšifrování
56
Symetrická kryptografie
57
Asymetrická kryptografie
64
Digitální podpis
67
Hashování
74
Steganografie
78
Šifrování v mobilní komunikaci
84
Kvantová kryptografie
93
Zájmová kryptografie
95
Slovníček pojmů Test
101 1
Obsah
Cíl studia Cíl studia Cíle studia předmětu Komprimace a šifrování je ”Orientace v oblasti teorie informace a komprimace, seznámení s metodami kryptografie a kryptoanalýzy”. Podrobněji jsou cíle specifikovány jako: • ovládat základní pojmy z teorie informace a dokázat je aplikovat • mít přehled o obecných technikách neztrátové a ztrátové komprese dat • vědět, jak lze komprimovat text, obraz, zvuk, video • znát základní pojmy z oblasti kryptologie • mít přehled o historii kryptologie • znát základní způsoby šifrování - metody substituce a transpozice textu • vědět, jak fungují moderní symetrické a asymetrické metody a na jakých matematických předpokladech stojí jejich bezepčnost • vědět, jak funguje inffrastruktura veřejných klíčů a znát princip digitálního podpisu • vědět, co je to steganografie a znát běžně používané steganografické techniky • mít povšechný přehled o možnostech kvantové kryptografie • dokázat poznatky aplikovat v praxi • některou z oblastí komprimace či kryptologie prostudovat do hloubky Prostředky k dosažení těchto cílů jsou při prezenčním studiu účast na přednáškách a cvičeních a samostatná práce na projektu. Při distančním studiu to jsou studium tohoto učebního materiálu, ale i aktivní vyhledávání dalších studijních zdrojů a stejně jako v případě prezenčního studia samostatná práce na projektu.
Úvod Úvod Předmět Komprimace a šifrování kombinuje dvě oblasti informatiky, které spoolu zdánlivě nesouvisí. Jak si však ukážeme, a jak nám (snad) dojde v průběhu studia, jejicch souvislost je větší, než se na první pohled zdá. Potřeba komprimovat (snižovat objem) čehokoliv je stará stejně jako potřeba cokoliv uskladňovatt či dopravovat. Pokaždé, když si balíme batoh na výlet, zamýšlíme se nad každou z věcí, zda ji skutečně budeme na výletě potřebovat, či zda bychom se bez ní neobešli. Stejně tak je tomu i v případě dat. Kompresní algoritmus se u každých dat rozhoduje, zda jsou skutečně potřeba všechny, či zda je nelze uložit nějakým jiným způsobem, který by vylučoval zbytečnou nadbytečnost, a který by při nižším objemu dat garantoval, že z nich bude možné později obnovit data původní. Kompirmaci využíváme pro úsporu kapacity záznamových médií a pro úsporu přenosového pásma při datové komunikaci. Jak ukazují zkušenosti, nezáleží na velikosti záznamového média. Čím větší médium máme, tím více dat shromažďujeme, tím později data promazáváme, tím později na disku uklízíme. Nedostatek prostoru tak dříve či později stejně přijde. Kompresní algoritmy byly potřeba v době, kdy každý člověk nosil v tašce sadu disket o kapacitě 1,44MB a vystačil si s nimi. Kompresní algoritmy jsou potřeba i dnes, kdy každý může mít v hodinkách 1000 disket a na disku, který je velký jako malý bloček, může mít uložené filmy pro týden nepřetržitého přehrávání či hudbu na celý rok. Studium kompresních algoritmů nám prozradí, jak je možné, že lze objem dat snižovat při zachování jejich informační hodnoty. Prozradí nám také, jak je možné, že minuta hudby může mít méně než jeden megabyte a jak je možné, žee hodinu filmu uložíme na běžné CD. Poté, co se naučíme základní principy kompresních algoritmů, vrhneme se na studium kryptologie, která zabírá více než 2/3 tohoto předmětu. Jak si ukážeme, byla to právě potřeba dešifrovat, která stála během druhé světové války u zrodu prvních počítačů. Lámání šifer hrubou silou vyžaduje vykonávání velkého množství triviálních matematických operací, což je věc jako stvořená pro elektronická zařízení. Později se ukázalo, že rychlé zpracovávání dat lze využít i jinak a postupem času se z prvních počítačů majících výkon jako lokomitava (jež bylo třeba chladit dvěma leteckými motory) vyvinuly osobní a kapesní počítače. Výpočetní výkon potřebný k rozlomení německé Enigmy tak dnes máme v malé krabičce, kterou stačí napájet energií chůze či slunečními paprsky.
3
4
Obsah Potřeba šifrovat je stará stejně jako lidská civilizace. Odnepaměti spolu lidé soupeří o mmajetek či moc a s tím souvisí potřeba předávání informací tak, aby nikdo nepovolaný nezjistil jejich obsah. Velmi blízko je i potřeba předávání informací tak, aby cestou nebyly změněny, nebo abychom byli přinejmenším schopni tuto změnu detekovat. V době, kdy jsou počítače všude, kdy jejich prostřednictvím nakupujeme, platíme, komunikujeme s bankami či úřady, je požadavek na zabezpečení soukromí oprávněný dvojnásob. Nikdo z nás by patrně nebyl rád, kdyby se každý mohl podívat na náš bankovní účet či s ním dokonce manipulovat. Stejně tak různé instituce, se kterými přijdeme do kontaktu požadují jistotu, že ten, s kým komunikují, jsme skutečně my a ne nikdo jiný. Nejen důvěrnost dat, ale i jejich celistvost, původnost a prokazování totožnosti. To vše jsou úkoly kryptografie. Postupně se seznámíme se všemi. A jak je to se slibovanou souvislostí mezi komprimací a šifrováním? Ukazuje se, že opakování je základ kryptoanalýzy. Jinými slovy všude tam, kde jsou nějaká nadbytečná data, je snadněší zašifrovaná data rozšifrovat. Komprimace nám snižuje nadbytečnost dat a snižuje tak riziko jejich dešifrování. Proto spolu tyto dvě disciplíny souvisí. Kryptografie se bez komprimace neobejde. A bez kryptografie se dnes neobejde nikdo z nás. Patří proto k dobrému vychování každého uživatele informačních a komunikačních technologií, mít o těchto technikách alespoń povšechný přehled. Každý, kdo se chce honosti vysokoškolským titulem spjatým s informatikou by však měl mít více, než jen povšechný přehled. Měl by chápat principy fungování těchto technik, jejich rizika a v neposlední řadě také dokázat posoudit jejich vhodnost pro různé aplikace. Snad k této dovednosti přispěje i kurz Komprimace a šifrování.
Využití komprimace a šifrování Využití komprimace a šifrování Komprimace i šifrování mají v době rozvoje techniky využití doslova na každém kroku. Potřeba komprimovat a šifrovat však není nic nového, co by se objevilo až s rozmachem výpočetní techniky. Touha po zmenšování objemu čehokoli je v lidské činnosti patrná odnemapěti, stejně jako potřeba utajování informací. V tomto kurzu poznáme, jak se v historii vyvíjely metody komprese a šifrování. Tuto znalost sice nevyužijeme přímo, ale nepřímo nám poslouží dvěma způsoby: • poznáme na ní základní principy fungování technik komprimace a šifrování, které jsou platné dodnes, • roztšíříme obzory svého vzdělání do oblasti, která je i mezi laiky velmi populární a kde dokážeme svými znalostmi zaujmout. To, co však využijeme přímo, bude popis v současnosti používaných technik. Dozvíme se, jak pracují kompresní algoritmy typu ZIP, BZIP, GZIP, atd. Dozvíme se, jak jsou uložená data v obrázcích typu GIF a JPG a jak je možné, že jsou tyto souborry tak malé. Dozvíme se, jak funguje MP2, MP3, MP4, čili jak ošálit lidské smysly, aby si nevšimly změny dat, která výrazně uspoří jejich velikost. Dále se dozvíme, co je to DES, AES, IDEA a jak funguje. Řekneme si, jak se vyměňují elektronické klíče přes nezabezpečené médium. Dozvíme se, jak pracuje algoritmus RSA a jak jej každý z nás může použít nejen k zašifrování důvěrných dat, ale i k elektronickému podpisu a tím prokázání autorství. Každý z nás by měl být schopen tyto principy později aplikovat v podniku, vv němž bude pracovat. Ukrývání zpráv do multimediálních dat je oblast, se kterou se v běžném životě setkáváme jen velmi málo. Pracovníkům tajných služeb či jiných bezpečnostních složek z nní však běhá mráz po zádech, neboť nemohou mít žádnou jistotu, že nevinně vypadající obrázek, který právě někdo nahrál na některou z mnoha veřejných galerií, neobsahuje ukrytý pokryn pro provedení teroristického útoku. Kvantová kryptografie je sice hudbou budoucnosti, otázkou však je, jak daleké budoucnosti. Kdo z nás si může být jistý, že se nástupu kvantové kryptografie nedožije? Až přijde, bude to revoluce v informačních technologiích a jen ten, kdo bude na tuto revoluci připravený, obstojí.
Zkuste se na dvě minuty zamyslet a podívat se po svém okolí. Kde všude vidíte něco, co používá šifrování? Nebo něco, kde jsou data komprimována?
Při pohledu na počítač je to snadné - HTTPS, SSL, PGP, SSH, SCP, SFTP, atd. Ale i v reál-
5
Obsah ném světě. Téměř každý má kreditní kartu, mobil, flashku, MP3 přehrávač., digitální fotoaparát. Svým způsobem i občanský průkaz, klíč, či celá naše osobnost velmi souvisí s šifrováním. Studium kryptologie otevírá poznání nejen informatikům, ale každému, kdo se chce dozvědět více o současném světě a o technologiích, které jím prostupují.
Poučení Poučení
Chytrý se učí pět let, hlupák to stihne za den. (vietnamské přísloví)
Návaznost Návaznost Ačkoliv teorie informace, komprimace i kryptografie jsou disciplíny velmmi úzce spjaté s matematikou, pro úspěšné studium tohoto textu je třeba mít, kromě všeobecného vzdělání nabytého na základní škole, pouze následující znalosti:
• • • •
vědět, co je to bit a byte vědět, co je to prvočíslo vědět, co je to zbytek po dělení dokázat umocnit dvě čísla
Je pravda, že jsou to všechno znalosti, které si minimálně každý nadprůměrně inteligentní jedinec již ze základní školy odnese. Přesto však doporučujeme, aby předměty typu Matematika I, nebo Výpočetní technika I (či jiný předmět seznamující se základními principy fungování počítačů), byly absolvovány ještě před studiem tohoto kurrzu.
Poděkování Poděkování Tato eLearningová opora vznikla za výrazné pomoci studentů PEF MZLU v Brně. Autoři děkují jmenovitě:
• Martě Vodové za zpracování podkladů pro kapitoly Asymetrická kryptografie a Digitální podpis
• Petru Sklenářovi za zpracování podkladů pro kapitolu Kvantová kryptografie • Mariánu Klangovi za zpracování podkladů pro kapitolu Historie kryptografie a kryptoanalýzy
• Petru Konečnému za zpracování podkladů pro kapitolu Hashovací funkce • Petru Chladilovi za zpracování podkladů pro kapitolu Metody kódování a komprese dat
• Roman u Kôrovi za vytvoření flashové aplikace pro Huffmannovo kódování • Petře Katovské a Martinu Juráňovi za zpracování podkladů pro kapitolu Steganografie • Tomáši Hanáčkovi za zpracování podkladů pro rozšíření kapitol o kompresních algoritmech
6
Obsah
Teorie informace Teorie informace Výměna informací s okolím nám umožňuje udržovat vlastní existenci. Proces zpracování informací je trvalý, nepřetržitý, ale ovlivnitelný. Zabezpečení informací je spojeno s lidským jednáním a je údělem celé společnosti, bez ohledu na vývojový stupeň materiálních podmínek. Problémy se zpracováním informací se prohloubily během 20. století. Svět je zavalen spoustou informací a neexistují lidé, kteří by je všechny byli schopni zpracovat nebo evidovat. Využívání a efektivní práce s informacemi vyžaduje o nich něco vědět. 1. 2. 3. 4.
Co jsou to informace? Co jsou relevantní informace? Jak je získáme a jak zhodnotíme jejich využitelnost? Jak se přenášejí a jak jsou uloženy?
Základní podmínkou úspěšnosti jednotlivců je permanentní osvojování nových znalostí vytvořených jinými a tvorba znalostí vlastních. Abychom byli připraveni, musíme mít dostatek informací o informacích a možnostech manipulace s nimi.
Pojem informace Název informace pochází z latinského informo, což znamená přanášet zprávu, oznámení, poučení. Otec kybernetiky Norbert Wiener označuje informaci jako to, co si vyměňujeme s vnějším světem, když se mu přizpůsobujeme a působíme na něj svým přizpůsobováním. Definic pojmu informace je velmi mnoho. Některé z nich jsou: Informace je obsah jakéhokoli oznámení, údaje o čemkoli, s určením pro přenos v prostoru a čase. V nejširším slova smyslu je to obsah vztahů mezi materiálními objekty, projevující se změnami těchto objektů. (Terminologický slovník informatiky) Informace je obsah zprávy, sdělení, objasnění, vysvětlení, poučení. (Slovník cizích slov) Informace jsou údaje, čísla, znaky, povely, instrukce, příkazy, zprávy apod. Za informace považujeme také podněty a vjemy přijímané a vysílané živými organismy. (Oborová encyklopedie VT)
Jak informace chápat? Informace – z hlediska kvalitativního (obsah sdělení, význam zprávy) tím se zabývá INFORMATIKA Informace – z hlediska kvantitativního (množství a jeho měření) tím se zabývá TEORIE INFORMACE
Teorie informace První publikace týkající se infromacem jejího přenosu a měření se objevily krátce po druhé světové válce. Jedním z důležitých vědců, který se touto problematikou zabýval, byl Claude Shannon. Claude Shannon stanovil základy teorie informace, definoval možnosti měření informačního množství zavedením pojmu entropie. Vyšel z předpokladu, že zprávy, které se přenášejí pomocí nějakého zařízení, patří do kategorie náhodných jevů. Formalizace je tedy založena na pravděpodobnostně-statistickém základu. Shannonova definice informace: Informace je míra množství neurčitosti nebo nejistoty o nějakém náhodném ději odstraněná realizací tohoto děje. Informace rozšiřuje okruh znalostí příjemce. Měření informačního množství Entropie – název vypůjčený z fyziky, použitý pro měření informačního množství. Jak kvantifikovat rozšíření okruhu znalostí příjemce? Pravděpodobnost jevu – spojeno s individuálními vlastnostmi příjemce (Shannon).
Obsah Jevy a jejich realizace Jev – náhodný proces s n možnými realizacemi (tah sportky, účast na přednášce, semafor na křižovatce apod.) Realizace jevu – jeden projev, získání výsledku (vytažení 6 čísel, konkrétní počet osob na přednášce, svítící zelená na křižovatce apod.) Předpokládejme například, že v národě je polovina žen a polovina mužů. Z toho 25% jsou blondýnky. Nyní někdo sdělí o neznámé osobě, že je to žena a má blond vlasy. Dále se dozvíte, že je vědeckou pracovnicí. To je poměrně cenná informace, protože takových blonýnek je asi jen 10%. Jsme schopni vyjádřit, kolik informace jsme v tomto rozhovoru obdrželi? Pravděpodobnost, že jsem potkal ženu je 1:2. Pravděpodobnost, že ta žena je blondýnka je 1:8 a že je zároveň vědec 1:80. 1 1 = 80 P (v) = P (zena) · P (blond) · P (vedec) = 21 · 14 · 10 Výpočet vlastní informace Pro výpočet obdržené vlastní informace je potřeba zabývat se entropií. Ta vyjadřuje míru nejistoty obsažené v nějakém náhodném ději. Přepokládejme tedy, že máme konečný počet vzájemně se vylučujících jevů, jejichž pravděpodobnosti výskytu jsou pi (x), . . . , pn (x). Entropii pak vyjádříme jako funkci těchto pravděpodobností. Požadované vlastnosti funkce pro výpočet množství informace • Jev X má n realizací, množství informace je funkcí n. • Je-li n = 1, jedná se o jev jistý, množství informace je rovno nule. • Jevy X a Y probíhající současně a nezávisle, p(x,y) = p(x) * p(y): množství informace je dáno součtem množství jednotlivých jevů: f(x,y) = f(x) + f(y) • Jev X má n realizací, jev Y má m realizací. Je-li m > n, pak chceme i f(m) > f(n) Funkce, která vyhovuje uvedeným podmínkám, je logaritmus. I(x) = log n Zde předpokládáme, že pravděpodobnost každé realizace je stejná. Má-li jev n realizací, pak můžeme psát p(x) = 1/n, odsud pak n = 1/p(x). Buď X množina výsledků náhodného děje, x výsledek realizace a p(x) pravděpodobnost tohoto výsledku. Každému x z X pak lze přiřadit reálné číslo I(x) nazývané vlastní informace o výsledku x, pro než platí: I(x) = − log p(x), (0 ≥ p(x) ≥ 1) Číslo I(x) představuje množství informace obsažené ve výsledku x. Základ logaritmu – principiálně není podstatný. Ale používají se logaritmy o základu 2. Pak dostáváme výsledek v bitech. Entropie Jak spočítat informační množství celého jevu? Pomůžeme si shrnutím všech vlastních informací jednotlivých realizací. Předpokládejme, že jev X má n realizací X = x1 , x2 , . . . , xn s pravděpodobnostmi p(x1 ), p(x2 ), . . . , p(xn ). Entropie H(X) P je dána určitou střední hodnotou vlastních informací všech realizací jevů: H(X) = − n i=1 p(xi ) · log p(xi ) Entropie zahrnující informační množství celého jevu se nazývá též úplná informace.
Kódování informace Základní podmínkou komunikace je vytvoření signálního komunikačního kanálu. Informaci je pro tento účel nutné transformovat, tj. vyjádřit v jiném jazyce s jinou abecedou. Přiřazení znaků jedné abecedy znakům jiné abecedy se nazývá kódování, inverzní postup pak dekódování. Předpis, který toto přiřazování definuje, se nazývá kód. Z hlediska optimalizace přenosu je vhodné aby každý přenášený signál obsahoval co nejmenší množství informace. Proto a také z důvodu omezení šumů používáme kódování informací. Kvalita kódování, redundance Z hlediska optimálního přenosu je efektivní kód, který obsahuje minimální počet informačních prvků, každý znak kódu tedy má maximální entropii. Kvantitativně je hospodárnost kódu vyčíslitelná redundancí (nadbytečností), podle vztahu: R = 1 − H/Hmax .
7
8
Obsah
H je zde entropií jazyka a Hmax je maximální entropie při použití téže abecedy (všechny znaky jsou stejně možné). Způsoby kódování Nejpoužívanější výstupní abecedou kódování je dvojková abeceda, tj. abeceda obsahující prvky 0 a 1. Rovnoměrné kódování – každému znaku je přiřazen stejně dlouhý kód. Obvykle je jednodušší, rychlejší na zpracování, ale méně hospodárné. Toto kódování totiž přiřazuje každému znaku abecedy stejně dlouhý kód bez ohledu na četnost jeho výskytu. Typickým představitelem je Baudotovo kódování Nerovnoměrné kódování – každému znaku je přiřazen jinak dlouhý kód. Pro konstrukci a zpracování je obtížnější, může však být maximálně hospodárné. Představiteli tohoto typu kódování jsou Shannon-Fanovo nebo Huffmanovo kódování. Příklady kódů Zdroj produkuje 4 znaky A, B, C, D. Předpokládáme pravděpodobnosti znaků: znak p1 (x) kód 1 kód 2 znak p2 (x) kód 1 kód 2 A
0,25
00
0
A
0,5
00
0
B
0,25
01
10
B
0,25
01
10
C
0,25
10
110
C
0,125
10
110
D
0.25
11
111
D
0.125
11
111
Shannon-Fanův algoritmus Je založeno na četnosti výskytu jednotlivých znaků abecedy. 1. Znaky uspořádáme sestupně podle pravděpodobnosti jejich výskytu. 2. Vypočteme kumulativní pravděpodobnosti. 3. Rozdělíme znaky do dvou skupin tak, aby jejich součtové pravděpodobnosti byly blízké, tj. v prvním kroku 0,5. 4. Krok 3 opakujeme tak dlouho, dokud existují vícečlenné skupiny znaků.
znak
p(x)
s
x1 x2 x3 x4 x5
0,30 0,24 0,20 0,15 0,11
1,00 0,70 0,46 0,26 0,11
skupiny 0
0 1 0
1 1
0 1
vysledek 00 01 10 110 111
Huffmanovo kódování Stejně jako Shannon-Fanovo kódování využívá četnosti jednotlivých znaků pro optimální zakódování. 1. Seřadíme pravděpodobnosti výskytu jednotlivých znaků sestupně pod sebe. 2. Sečteme poslední dvě pravděpodobnosti a vytvoříme nový sloupec pravděpodobností, kde ty dvě, které jsme sčítali nahradí jejich součet. 3. Všechny pravděpodobnosti v novém sloupci seřadíme sestupně podle velikosti a propojí se spojnicemi s hodnotami v původním sloupci. 4. Spojnice pravděpodobností p(xn−1 ) a p(xn ) se sjednotí, ale předtím přiřadíme p(xn ) bit kódového slova s hodnotou 1 a p(xn−1 ) bit s hodnotou 0. 5. Takto postupujeme, dokud se součet posledních dvou čísel nerovná 1. 6. Závěrečné kódování každého slova pak probíhá po spojnicích jako sbírání zapsaných bitů kódového slova tak, že jdeme po spojnicích a zapisujeme všechny bity, které po cestě potkáme. 7. Nakonec se celý zápis obrátí odzadu dopředu a výsledkem je kódové slovo pro danou událost.
9
Obsah
událost
p(xi )
kód
x1 x2 x3 x4 x5 x6 x7 x8 x9
0.35 0.15 0.13 0.09 0.09 0.08 0.05 0.04 0.02
00 010 011 101 110 111 1001 10000 10001
Výpočet kódu u vlastního textu je možné vyzkoušet pomocí následující aplikace: