Kryptografické algoritmy a faktorizace velkých čísel

Bankovní institut vysoká škola Praha Katedra matematiky, statistiky a informačních technologií

Kryptografické algoritmy a faktorizace velkých čísel Diplomová práce

Autor:

Radek Pospíšil Informační technologie a management

Vedoucí práce:

Praha

Ing. Vladimír Beneš

duben, 2013

Prohlášení

Prohlašuji, že jsem diplomovou práci zpracoval samostatně a v seznamu uvedl veškerou použitou literaturu. Svým podpisem stvrzuji, že odevzdaná elektronická podoba práce je identická s její tištěnou verzí, a jsem seznámen se skutečností, že se práce bude archivovat v knihovně BIVŠ a dále bude zpřístupněna třetím osobám prostřednictvím interní databáze

elektronických

vysokoškolských prací.

V Praze, dne

Radek Pospíšil

Poděkování Na tomto místě bych rád poděkoval svému vedoucímu práce Ing. Vladimíru Benešovi za vstřícný přístup při vypracovávání této práce. Dále děkuji RNDr. Přemyslu Jedličkovi, Ph.D. za poskytnutí a udělení souhlasu k použití pracovního materiálu k jeho připravované knize Faktorizace velkých čísel. Poděkování patří také společnosti IT4 s.r.o. za poskytnutí prostoru pro vytváření, testování a umístění zdrojových kódů pro účely této práce.

Anotace Tato práce zpracovává nejzákladnější principy šifrování, z kterých kryptografie historicky vychází. Pojednává o důvodech šifrování a o směru, jakým se kryptografie od svého vzniku ubírá. Popisuje některé principy faktorizace velkých čísel a jejich využití v kryptografii. Názornou formou na příkladech demonstruje algoritmy, které těchto základních principů využívají, a poskytuje tak na šifrování jiný úhel pohledu. Výsledkem práce jsou ukázkové skripty a názorné příklady, které přispívají k lepšímu pochopení základních principů šifrování, díky čemuž si může čtenář uvědomit některá rizika a chyby z kryptografie vyplývající. Klíčová slova:

kryptografie, faktorizace, šifra, frekvenční analýza, steganografie

Annotation This work deals with the basic principles of coding from which cryptography historically proceeds. It is about the reasons of coding and the direction which cryptography goes from its establishment. It describes some principles of big numbers factorization and its usage in cryptography. This work demonstrates illustratively algorithms which use these basic principles and it also provides a different point of view on coding. The result of this work are sample scripts and illustrative examples which help to better understanding of basic coding principles and thanks to it the reader can realize some dangers and mistakes coming from cryptography. Key words:

Cryptography, Factorization, Cipher, Frequency analysis, Steganography

Obsah Úvod ........................................................................................................................................... 7 1

Historie šifrování................................................................................................................ 9 1.1

2

Historické důvody potřeb šifrování a jejich první použití .............................................. 9 Základní principy šifrování a kryptoanalýzy ................................................................... 12

2.1

Popis základních metod šifrování ................................................................................. 12

2.1.1

Substituční šifry .................................................................................................... 12

2.1.2

Transpoziční šifry ................................................................................................. 15

2.1.3

Symetrické šifry.................................................................................................... 16

2.1.4

Asymetrické šifry ................................................................................................. 16

2.2

Principy nejznámějších šifer......................................................................................... 17

2.2.1

Caesarova šifra ..................................................................................................... 17

2.2.2

Šifrování podle konverzní tabulky ....................................................................... 18

2.2.3

Vigenérova šifra ................................................................................................... 19

2.2.4

ADFGX ................................................................................................................ 22

2.3

První kryptografické systémy ....................................................................................... 24

2.3.1

Zimmermannův telegram ..................................................................................... 24

2.3.2

Šifra ADFGX........................................................................................................ 25

2.3.3

Enigma ................................................................................................................. 25

2.3.4

JN-25 .................................................................................................................... 26

2.3.5

Kód Navajo ........................................................................................................... 27

3

Faktorizace velkých čísel ................................................................................................. 28 3.1

Faktorizace v kryptografii ............................................................................................ 28

3.1.1

Privátní a veřejný klíč ........................................................................................... 28

3.1.2

Vazba mezi privátním a veřejným klíčem ............................................................ 29

3.2

Časová složitost ............................................................................................................ 31

3.3

Faktorizační algoritmy.................................................................................................. 32

3.3.1

Zkusmé dělení ...................................................................................................... 32

3.3.2

Pollardova ρ metoda ............................................................................................. 33

3.3.3

Pollardova ρ - 1 metoda ........................................................................................ 34

3.3.4

Williamsova p+1 metoda ...................................................................................... 35

3.4

Nejjednodušší faktorizační skript ................................................................................. 35 5

3.5

Prolomení veřejného klíče ............................................................................................ 39

3.6

Budoucnost faktorizace v kryptografii ......................................................................... 41

4

Techniky bezpečného šifrování ....................................................................................... 44 4.1

Metody a zásady bezpečného šifrování ........................................................................ 44

4.1.1

Základní všeobecná pravidla ................................................................................ 44

4.1.2

Bezpečnost hesel .................................................................................................. 46

4.1.3

Délka klíče ............................................................................................................ 48

4.1.4

Náhodná čísla ....................................................................................................... 49

5

Využití znalosti slabých stránek ...................................................................................... 52 5.1

Útoky proti šifrám ........................................................................................................ 52

5.1.1

Útoky se změnou bitů ........................................................................................... 52

5.1.2

Útoky hrubou silou ............................................................................................... 53

5.1.3

Četnost útoků proti šifrám .................................................................................... 55

6

Kryptografické algoritmy a software ............................................................................... 57 6.1

Příklady algoritmů a zdrojových kódů jednoduchých šifer .......................................... 57

6.1.1

Caesarova šifra ..................................................................................................... 57

6.1.2

Šifrování podle konverzní tabulky ....................................................................... 59

6.2

Příklady algoritmů v šifrovacím softwaru .................................................................... 63

6.2.1

Šifrovací algoritmus AES (Rijndael).................................................................... 64

6.2.2

Šifrovací algoritmus Serpent ................................................................................ 64

6.2.3

Šifrovací algoritmus Twofish ............................................................................... 64

6.3

Porovnaní metod šifrování z pohledu rychlosti ............................................................ 64

Závěr ......................................................................................................................................... 67 Seznam použité literatury ......................................................................................................... 69 Tištěné publikace ................................................................................................................... 69 Internetové zdroje .................................................................................................................. 69 Příloha č. 1 - Kompletního znění Zimmermannova telegramu .................................................. 1 Příloha č. 2 - Řada prvních 1229 prvočísel ................................................................................ 1

6

Úvod Kryptografie je dnes již vědní disciplínou, na kterou se klade v oblastech uchovávání informací a komunikace veliký důraz. S ohledem na rychlý růst nároků na výpočetní techniku je logické, že stejným tempem roste i potřeba chránit svá data. Informace jsou cenným artiklem, a je tedy nezbytné, je chránit mimo jiné i před nežádoucím zveřejněním, nebo přístupem třetích osob. Jedním ze způsobů, jak data před touto hrozbou chránit, je využití kryptografie. Kryptografie však není konečným a dokonalým řešením tohoto velmi složitého problému. Mnohdy je i u počítačově gramotných lidí slyšet názor, že mají-li svá data chráněna některým z kryptografických systémů, udělali pro jejich bezpečnost maximum, a tak se nemůže nic stát. Smutnou pravdou však je, že tento názor zcela odporuje realitě a mnohdy naopak přispívá k vytváření bezpečnostních incidentů. Přirovnal bych to k situaci, kdy si majitel objektu pořídí pancéřové dveře a klíče od nich schová pod rohožku. V počítačovém prostředí pak takovýto klíčem pod rohožkou může být například heslo k přístupu na kryptované svazky napsané na lístečku přilepeném na monitoru, nebo privátní klíč uložený na ploše příslušného uživatele. S kryptografií je to podobné. Nejsou-li splněny základní bezpečnostní podmínky, sama kryptografie bude k ochraně dat, ať už její síla bude jakákoli, neúčelná. V některých případech může být dokonce až kontraproduktivní, protože jak si v následujících kapitolách ukážeme, téměř každé zvýšení bezpečnosti přináší snížení uživatelského komfortu, nebo alespoň další pracovní výkony navíc. Mimo těchto efektů pak může mít chybné použití kryptografie ještě jeden mnohem zásadnější. Pokud je uživatel využívající kryprografické systémy přesvědčen, že je samotné jejich použití bezpečné pro jeho data, zpravidla otupí jeho opatrnost a vytváří tak chybnými rozhodnutími další příležitosti jak ještě více ohrozit svá data. Příkladem toho může být například vytváření přístupů do vnitřní sítě, tím pádem i k interním datům, pomocí kryptovaných tunelů. Je-li pak „klíč pod rohožkou“, ohrozili jsme tak svá data několikanásobně, neboť k nim umožňujeme případný přístup mnohem větší skupině eventuálních útočníků. Kapitoly, které se této problematice věnují, mají za úkol odpovědět na otázku, jaká rizika kryptografie přináší a jak jim předcházet. Kořeny kryptografie sahají do doby stovky let před naším letopočtem. V úvodních kapitolách se proto krátce zastavíme u historie a důvodů potřeb šifrování. Více nás však bude zajímat, jak tyto základní principy šifrování přispěly k vývoji kryptografie jako takové. Přes tyto principy 7

se za pomoci názorných příkladů a ilustrací přeneseme až do kapitoly, kde pojednáme o jednom z moderních přístupů ke kryptografii. Tento přístup je postaven na skutečnosti, že je v dnešní době jednou z neodlučitelných součástí kryptografie výpočetní technika. Výkonné počítače umožňují lepší výpočetní výkon pro šifrování, avšak také vyšší hrozbu prolomení šifry. Proto je k šifrování využíván matematický princip, který je i za využití vysoce výkonných počítačů stále těžko řešitelný. Tímto principem je faktorizace velkých čísel. Faktorizace velkých čísel je velmi náročná matematická disciplína a je jen logickým důsledkem, že je této vlastnosti využíváno v kryptografii. Na metodách, které budeme v těchto kapitolách popisovat, bude patrné, jaký význam faktorizace v kryptografii má. Uvedeme si názorný skript, který demonstruje procesy probíhající při faktorizaci i s popisem jeho činnosti, výhod a nevýhod, z čehož vyplyne odpověď na otázku, zda je faktorizace velkých čísel to nejlepší řešení pro kryptografii. Cílem této práce je: „Shrnutí dosavadních poznatků v kryptografii, upozornit na rizika a chyby při užití kryptografie a programování internetových aplikací. Ukázky vlastních algoritmů. Odhad dalšího vývoje kryptografie“. Pro účely dosažení tohoto cíle vznikly skripty v jazyce PHP, které mají za úkol přispět k lepšímu pochopení základních principů šifrování, díky čemuž si pak může čtenář lépe uvědomit některá rizika a chyby z kryptografie vyplývající. Tyto skripty jsou také ve své funkční podobě k dispozici na internetových adresách, které jsou u skriptů uvedeny, aby bylo možno jejich další použití v testování, nebo případném rozšíření. Pro účely této práce jsem volil názorné příklady doplněné skripty, na kterých jsou demonstrovány některé ze základních šifrovacích i dešifrovacích metod. Předpokladem je, že jednotlivé procesy znázorněné konkrétním skriptem umožní lépe pochopit souvislosti, které se v popisovaných oblastech dějí. Skripty použité v této práci jsou psány v programovacím jazyce PHP (Hypertext Preprocessor, dříve Personal Home Page). Tento jazyk jsem zvolil hned z několika důvodů. Tím hlavním je, že výsledný kód je možné kromě běžného zobrazení přímo v práci prezentovat i jako funkční skript přístupný na internetu. To vidím jako výrazné pozitivum, neboť tento způsob prezentace je velmi efektivní i s ohledem na to, že nepodléhá hrozbám virové nákazy, jak by tomu mohlo být u spustitelných programů. Další nespornou výhodou tohoto způsobu prezentace je fakt, že skripty pro svůj běh využívají hardware webového serveru a nehrozí tedy případný problém s kompatibilitou hardwaru.

8

1

Historie šifrování

1.1 Historické důvody potřeb šifrování a jejich první použití Už v době kdy byla západní civilizace teprve na počátku svého vývoje, docházelo k situacím, které byly pro člověka a jeho existenci tak důležité, že probíhali první pokusy o šifrování důležitých zpráv. Konkrétně se uvádí jako první doložený pokus o předání tajné zprávy do období Řecko-Perských válek, tedy do roku 480 př.n.l., kdy Řekové obdrželi velmi důležitou informaci o termínu, kdy se perský král Xerxes vydá na válečné tažení, jehož cílem bylo mimo jiné vypálení Athén jako odplata za jejich podporu při iónském povstání. V pravém slova smyslu zde ještě nešlo o skutečné šifrování, jako spíše pouze o přenesení důležité informace v utajeném stavu. Podle dostupných informací se totiž jednalo o použití voskových tabulek, které byly obvykle vyrobeny ze dřeva a opatřeny voskovou vrstvou, do níž se zpráva zaznamenala. Autor zprávy, Demaratus spartský král, však nevepsal informaci do vosku, ale vosk z tabulek nejprve odstranil a text zaznamenal přímo do dřeva. Po té, tabulky opět opatřil voskovou vrstvou tak, aby navodily dojem, že se jedná o psací tabulky nepoužité. Touto metodou dokázal přenést tajně informaci ke svému adresátovi což, jak se později ukázalo, bylo zlomové pro obranu Řecka a zároveň i pro položení základů demokracii celé západní civilizace. Díky této zprávě se mohl Leonidas spartský král postavit spolu s athénským vojskem na odpor perské armádě ve známé bitvě u Thermopyl. V dnešní době bychom tento způsob předání zpráv zařadili do oboru steganografie, nebo-li systém utajení komunikace, ale v době 480 př.n.l se jednalo pouze o další způsob, jak získat informační převahu. Příkladem prvního opravdového šifrování je uváděna šifra, která byla použita o více než 400 let později. Principem této šifry bylo jednoduché nahrazování písmen za jiná. Jednalo se o tak jednoduché šifrování, že se dokonce k převodu znaků nepoužívala ani konverzní tabulka, která by šifře poskytla vyšší míru složitosti a tím tedy i obtížnosti k dešifrování. Této šifře pojmenované podle svého vynálezce se říká Caesarova šifra. Gaius Julius Caesar narozen 100 př.n.l. byl nejen římský vojevůdce ale také i politik, který si dobře uvědomoval cenu informace. V politice starověké říše byly intriky na běžném pořádku, a tak musel dobrý politik ovládat mimo jiné i umění dostupné informace dobře využít a zároveň uchránit před svými soky. To bylo zřejmě také tím hlavním motivem k vynalezení této primitivní šifry. Je třeba si ale uvědomit, že šifra musí být alespoň tak dobrá, jak dobří jsou její potenciální

9

kryptografové. Protože nemůžeme v období antiky mluvit ani o vysoké gramotnosti natož pak o vyspělé kryptografii, je zřejmé, že i takto jednoduchá šifra měla ve své době svůj veliký přínos. Z uvedených příkladů lze vyvodit, kde vznikala potřeba šifrování a jak praktické a důležité bylo tento dnes už vědní obor rozvíjet. Speciálním případem šifrování, který z hlediska vzniku spadá mezi již zmíněnou Caesarovu šifru a šifru Vigenérovu, které se budeme věnovat později, je takzvaný Voynichův kód. Jedná se o záhadnou zašifrovanou knihu pojmenovanou podle svého objevitele Wilfrida Michaela Voyniche (česky též Vojnič), jejíž původ se odhaduje do období mezi roky 1404 až 1438. Speciálnost tohoto kódu je především v tom, že nebyl dosud přes úsilí mnohých kryptografů dešifrován a existují dokonce pochyby, zda se vůbec jedná o smysluplný text. Na základě struktury kódu viz obr. 1.1 však může být vyvozen jeden ze závěrů, že jedná-li se opravdu o šifru, bude její princip založen na otevřeném textu, který je zašifrován některou z forem nahrazení znaků. Stejně jako u metody nahrazování znaků podle konverzní tabulky, je při luštění tohoto kódu velkou komplikací i fakt, že není znám jazyk, ve kterém by mohl být text napsán.

Obr. 1.1: Ukázka Voynichova kódu (vytvořeno ze zdroje [4])

Přestože se kód zatím nepodařilo dešifrovat, nemusí to nutně znamenat, že se jedná o podvrh. Podobně i mayské písmo dlouho odolávalo svému oživení, až se ho nakonec podařilo rozluštit. Mimo jiné k tomu přispěl i objev, že může být jedna slabika, zastupující jednu fonetickou hodnotu, zapsána velkým počtem na první pohled různých znaků. Jinými slovy systém mayského písma obsahuje variabilní složku, která při znovuoživení způsobovala svým luštitelů veliké komplikace. Není vyloučeno, že právě i Voynichův kód nějakým způsobem využívá variabilní složky, jak je tomu i u Vigenérovy šifry. Základní principy Vigenérovy šifry položil Leon Battista Alberti už v 15. století. Tato verze šifry už sice měla variabilní složku posunu, ale ta byla dána pouze použitím dvou sad abecedy. Došlo tím sice ke zvýšení 10

složitosti šifry, avšak do její finální podoby s variabilní složkou podle klíče ji dovedl až v 16. století diplomat Blaise de Vigenère. Jednalo se opět o substituci znaků v otevřeném textu, který vycházel z Caesarovy šifry, ale jejím převratným prvkem, který tuto šifru posouvá o generaci výše, byla právě variabilní složka posunu podle zvoleného klíče. Převratným milníkem v kryptografii zaznamenal vynález počítače. Ten umožnil vytvářet sofistikovanější šifry, protože dovolil provádět mnohem náročnější výpočty při šifrování, resp. dešifrování. Na druhou stranu to samozřejmě znamenal nástroj pro kryptografy, kteří se snažili nové šifry prolomit. Tento nekonečný souboj přetrvává až dodnes a je zřejmě omezen pouze lidskou fantazií a technickými prostředky. Jak v pozdějších kapitolách ukážeme, šifry, které byly založeny na neznalosti šifrovacího algoritmu, pomalu ustoupí a nahradí je šifry, které svou výpočtovou složitostí nepodlehnou, ani při odhalení jejich základních principů.

11

2

Základní principy šifrování a kryptoanalýzy

2.1 Popis základních metod šifrování Metod jak šifrovat je veliké množství. Přispívá k tomu i fakt, že prolomením jedné šifry, nastoupí na její místo šifra nová. Dalším důležitým aspektem, který zvětšuje množství šifer, je, že většina šifer vzniká v přísném utajení a cíleně pro jeden konkrétní účel. Tyto šifry jsou pak využívány pouze jednou skupinou a i v případě jejich nahrazením šiframi silnějšími jsou drženy v tajnosti, neboť by jejich zveřejnění mohlo přispět k prolomení šifer z nich vycházejících. Ty nejjednodušší šifry však i vycházejí z těch nejzákladnějších principů. Pouze do nich přidávají určitá vylepšení, která se snaží udělat šifru silnější, nebo personalizační prvky, které mají za úkol šifru přizpůsobit konkrétní osobě či skupině.

2.1.1 Substituční šifry Jednou z prvních a nejjednodušších metod jak skrýt otevřený text je substituce, nebo-li náhrada znaků za jiné. Tato náhrada znaků může probíhat třemi základními principy podle toho, jak je nakládáno se znakovými sadami použitými pro substituci. Monoalfabetické šifrování Jejím prvním a nejznámějším zástupcem je již zde zmiňovaná Caesarova šifra. Tyto šifry obecně využívají k substituci vlastních znaků, nebo jinak řečeno, používají jednu znakovou sadu. Náhrada znaků je tedy prováděna vždy v rámci jedné abecedy např. „A“ za „B“ a „B“ za „C“. Výhodou těchto systému je jednoduchost, naproti tomu je jejich nevýhodou snadnější dešifrování. Nejslabším místem je fakt, že každý znak má svůj stabilní ekvivalent, což lze využít k prolomení metodou četnosti znaků.

12

Homofonní šifrovací systémy Hlavní nedostatky monoalfabetického šifrování řeší homofonní šifrovací systémy tím, že používají k substituci jednoho znaku více možností. To v praxi znamená, že chceme-li nahradit znak „A“ nahradíme ho znakem „B“,“2“ nebo „#“. Substituce tak vlastně využívá více znakových sad. Zašifrování slova „Kryptografie“ pak může podle konverzní tabulky viz obr. 2.1 vypadat podle právě zvoleného substitučního znaku různými způsoby jako například „n$b3wrju9i8h“ nebo „&u-s?*j$d
Obr. 2.1: Šifrování slova „kryptografie“ podle konverzní tabulky (zdroj: vlastní úprava) Podle některých teorií kryptologů zabývající se dešifrováním již zmíněného Voynichova kódu, využívá tato šifra hned tři znakové sady. Prakticky by to znamenalo, že mateřské znaky, jsou nahrazeny umělým písmem a to takovým způsobem, že například lichá stránka používá jednu umělou znakovou sadu, stránka sudá druhou a některé stránky dokonce obě. Přitom zřejmě obě znakové sady vycházejí ze stejného grafického základu, ale měly rozdílný význam. To by byl prvek, který by do jednoduché substituce zaváděl další významné posílení. Umělých písem je celá řada, z nich budou uvedeny ještě dva zastupující příklady. Prvním z nich je jedna z verzí thébského písma, nazývaná též čarodějnické písmo viz obr. 2.1, které se dodnes používá, zřejmě pro navození tajemného efektu, u současných „mágů“.

Obr. 2.2: Verze Thébské (Čarodějnické) abecedy (vytvořeno ze zdroje [4])

13

Druhým příkladem umělého písma, pro účely této práce zajímavého především z estetického hlediska pro svou odlišnost, je na obr. 2.3 vyobrazeno písmo Sindhi pocházející z jedné z pakistánských provincií Sind.

Obr. 2.3: Písmo Sindhi (vytvořeno ze zdroje [4])

Z hlediska kryptografie je však jednoduchá substituce stále jen jednoduchou substitucí a nezáleží na tom, zda je použito některé ze známých znakových sad, nebo některé z umělých písem. V případě, že máme dostatečné množství textu, takzvané kritické množství, můžeme metodou četnosti znaků odvodit, který znak je který a to ať už je text psán klínovým písmem či smyšlenými symboly. To ovšem neplatí v případě, že je šifrován umělým písmem umělý jazyk. V takovém případě nemáme informace o tom, jakou strukturu jazyk má a jaký princip zápisu slov používá. Představme si například situaci, že si vytvoříme vlastní jazyk, kde bude slovo „BUMAU“ znamenat „Válka“. Dále použijeme umělé písmo kde „B“ nechť je „#“, „UM“ nechť je „$“ a „AU“ nechť je „@“. Zašifrované slovo „Válka“ pak bude vypadat jako „#$@“. Pokud na zašifrovaný text ještě použijeme jednoduchou substituci, získáme tvar, který s původním slovem nebude mít zdánlivě nic společného. Tím se šifra, za jistých okolností, stane neprolomitelnou, resp. k jejímu prolomení budeme mít velmi málo informací. Polyalfabetické substituční šifrovací systémy Tyto kryptosystémy svou sílu šifry zvyšují použitím více monoalfabetických šifer. [1] Čím je těchto dílčích šifer více, tím vyšší míru zabezpečení výsledná šifra poskytuje. V tomto případě je možné využít jedné abecedy, která má pouze jiným způsobem setříděné znaky. 14

Způsob, jakým jsou jednotlivé znakové řady používány, je stanoven na základě zvoleného logického systému. Může to být například jednoduché cyklické střídaní řad, nebo složitější určení, která řada má být v kterém kroku použita. Zvolíme-li nejjednodušší způsob střídání řad, tedy cyklicky, výsledný tvar šifrovaného slova „Kryptografie“ podle konverzní tabulky viz obr. 2.4 bude mít tvar „neksvljefira“ oproti tvaru „nubswrjudilh“ při použití pouze první substituční řady.

Obr. 2.4: Šifrování slova „kryptografie“ polyalfabetickou metodou (zdroj: vlastní úprava)

Na první pohled je zřejmé, že dešifrování takovéhoto kódu bude podstatně náročnější. Přestože metoda, z které polyalfabetická šifra vychází, postačovala po celá dlouhá staletí, s rozvojem dekryptovacích metod, jako je frekvenční analýza nebo-li metoda četnosti znaků, byla

monoalfabetická

šifra

vytlačena

do

pozadí. Typickým

příkladem

rozvinuté

polyalfabetické šifry je Vigenérova šifra, [1] které se budeme podrobně věnovat v dalších kapitolách.

2.1.2 Transpoziční šifry Další metodou šifrování otevřeného textu jsou transpoziční šifry. Jejich princip, jak napovídá název, je odvozen od transpozice, [1] nebo změnu polohy znaků. Přesouvání znaků přitom probíhá podle předem stanoveného vzorce. Zvolíme-li například vzorcem prostou výměnu dvou sousedících znaků, pak slovo „Kryptografie“ zašifrujeme způsobem „KR“ za „RK“ atd. do tvaru „rkpyotrgfaei“. Na první pohled je zřejmé, že se v tomto konkrétním příkladě nejedná o silnou šifru, neboť i ze zašifrovaného textu lze uhodnout, o jaké slovo se jedná. Proto se vzorec pro transpozici znaků volí složitější. Zvolíme si tedy pro zašifrování textu „Kryptuji transpoziční šifrou“ transpoziční vzorec ve tvaru číselné hodnoty „7“. Výsledkem bude šifra ve tvaru „kioirtzfyrirpacotnnuusiajpsb“ z čehož je vidět, že původní text již není patrný.

15

Pro zašifrování jsme nyní postupovali tak, že jsme si nejprve otevřený text sepsali do tabulky o šířce klíče viz obr. 2.5. Zbylé buňky tabulky doplníme jinými znaky v našem případě „A“ a „B“. Po té jsme získali zašifrovaný text přímým opsáním z tabulky, tentokrát ale po sloupcích.

Obr. 2.5: Výsledek kryptování transpoziční šifrou věty „Kryptuji transpoziční šifrou“ klíčem „7“ (zdroj: vlastní úprava)

Při znalosti principu a hodnoty klíče je dešifrování jednoduchou záležitostí. Stačí si šifrovaný text sepsat opět do tabulky o rozměrech, které spočítáme z celkové délky šifrovaného text a hodnoty klíče. Tedy v našem případě podle výpočtu 28 / 7 = 4 bude rozměr tabulky 7 sloupců a 4 řádky. Text vepíšeme do sloupců a z řádků odečítáme výsledný text.

2.1.3 Symetrické šifry Podle toho jakým způsobem šifra používá ke svému šifrování a dešifrování klíč, můžeme dělení dále rozšířit z pohledu symetrie klíče. [1] Mluvíme-li o šifrách symetrických, myslíme tím, že je klíč pro šifrování shodný s klíčem pro dešifrování. Těmto šifrám se také jinak říká šifry klasické nebo také konvenční. Konkrétními příklady mohou být šifra Caesarova a šifrování transpoziční větou podle číselného klíče.

2.1.4 Asymetrické šifry Novodobá kryptografie využívá k šifrování klíče asymetrické. To znamená, že pro šifrování je použit jiný klíč, než pro vlastní dešifrování. Tyto dva klíče označujeme jako klíč veřejný a klíč soukromý. Přestože jsou oba klíče rozdílné, jeden vychází z druhého, neboť musí tvořit jedinečný pár. [1] Tato vlastnost však z nich nesmí být lehce zjistitelná, protože by se tím stala šifra lehce prolomitelná. [1] Soukromý klíč je určen pouze pro příjemce zprávy a je tedy

16

přísně střežen. Naproti tomu veřejný klíč je volně přístupný komukoli, kdo se účastní šifrované komunikace, neboť ten slouží pouze pro šifrování. Z principu tohoto šifrovacího algoritmu by nemělo být možné (při splnění určitých podmínek, kterým se budeme věnovat v dalších kapitolách) za jeho pomoci šifru prolomit.

2.2 Principy nejznámějších šifer 2.2.1 Caesarova šifra Principem této prastaré šifry je substituce znaků v otevřeném textu, aby byl navozen dojem, že se jedná o nesmyslný nebo nečitelný text. Náhrada přitom probíhá pouhým posunutím každého znaku o určitý předem dohodnutý a pro celé šifrování pevně stanovený počet. [1] Posun je možný o libovolný počet v intervalu 1 až 25 za předpokladu, že používáme abecedu o počtu 26-ti znaků. V době vzniku této šifry se ale obvykle používal pouze posun o tři znaky, neboť měnit tento obvyklý posun nedávalo příliš smysl. Při pochopení principu šifrování je totiž dešifrovací postup i při neznalosti posunu velmi jednoduchý, ať už je jakýkoli. Před ukázkou jak prolomit Caesarovu šifru si ale nejprve předvedeme vlastní šifrování pomocí této metody viz obr. 2.6. Například pro zašifrování slova „kryptografie“ s posunem o 3 postupujeme tak, že k písmenu „K“ nalezneme ekvivalent posunutím se v abecedě o tři, čím získáme písmeno „N“. Dalším krokem je stejným způsobem určení ekvivalentů pro písmena „R“ až „E“. Výsledkem tedy bude zašifrovaný text „kryptografie“ ve tvaru „nubswrjudilh“. Nevýhoda této šifry je patrná i na takto krátkém textu. Například znak „R“ otevřeného textu má vždy stejný ekvivalent, v našem případě znak „U“, díky čemuž můžeme ze znalosti četnosti znaků v daném jazyce snadno vysledovat, o jaké písmeno by se mohlo ve skutečnosti jednat. Takovéto úvahy jsou však potřebné až u šifer pomocí konverzní tabulky, protože dešifrování Caesarovy šifry, jak si ukážeme, je velmi snadné.

Obr. 2.6: Šifrování slova „kryptografie“ Caesarovou šifrou s posunem 3 (zdroj: vlastní úprava)

17

Pro odšifrování celého textu si nejprve vybereme jedno slovo z šifry, které bude mít pokud možno více znaků, abychom se vyhnuli případným záměnám možných výsledků. Pro jednoduchost volíme slovo „nubswrjudilh“ z předchozí ukázky šifrování. Po té nám postačí jen několik málo pokusů, v našem případě maximálně 25, k získání čísla, o které je text posunut. Posuneme znaky šifrovaného slova o jeden zpět, čímž vytvoříme z písmena „N“ písmeno „M“, z písmena „U“ písmeno „T“, až se dostaneme k výslednému slovu „mtarvqitchkg“. Protože toto slovo nedává v předpokládaném jazyce logický smysl, celý postup opakujeme s vyšším posunem, dokud nezískáme některé smysluplné slovo, v našem případě tedy „kryptografie“. Pokud jsme takto zjistili posun pro vzorové slovo a víme, že je posun stejný pro celou šifru, není už žádný problém dešifrovat zbylý text.

2.2.2 Šifrování podle konverzní tabulky Vyšší bezpečnost šifrovaného textu oproti Caesarově šifře poskytovalo nahrazování znaků podle konverzní tabulky. Princip je téměř stejný s tím rozdílem, že znaky nejsou nahrazovány pouhým posunutím v řadě abecedy, ale jsou zaměňovány podle předem sestavené konverzní tabulky. Tato metoda má oproti Caesarově šifře výhodu ve vyšší míře utajení textu, oproti tomu avšak již nestačí oběma stranám znát pouze číslo, o které je text posunut. Obě strany nyní musejí vlastnit platnou konverzní tabulku, což zvyšuje riziko odhalení v případě, že by byla tabulka u jednoho z aktérů šifrované komunikace nalezena. V případě šifrování slova „kryptografie“ by pak například podle konverzní tabulky viz obr. 2.7 měla výsledná šifra tvar „jkcbqeakdnmh“.

Obr. 2.7: Šifrování slova „kryptografie“ podle konverzní tabulky (zdroj: vlastní úprava)

Na první pohled je výsledek podobný jako u předchozího principu. Prolomení šifry je ale v tomto případě mnohem složitější, neboť k odhalení podoby konverzní tabulky již nestačí jedno slovo a několik málo pokusů. Pro dešifrování bez znalosti konverzní tabulky je nutné pracovat s textem jako celkem a mít informace o konkrétním jazyku, ve kterém je text psán. Ze znalosti četnosti písmen a slov, která lze vytvořit, je možné vydedukovat možný obsah a opakovanými pokusy konverzní 18

tabulku doplnit. Za předpokladu, že je text psán například anglicky, můžeme hledat často používané krátké slovo „or“, které bude podle konverzní tabulky, viz obr. 2.7 ve tvaru „EK“. Slov, které tomuto vzoru odpovídají, bude samozřejmě více. Tuto možnost postupně vyloučíme dalšími kroky, když budeme odvozené konverzní znaky aplikovat na jiná častá slova jako například na slovo „road“. Z prvního pokusu víme, že „E“ se může rovnat písmenu „O“ a „K“ písmenu „R“. Pak pro ověřením našeho tipu můžeme hledat v zašifrovaném textu tvar „kedw“. Pokud je slovo v textu opravdu obsaženo, potvrdili jsme s velkou pravděpodobností část konverzní tabulky. Tímto postupem můžeme dojít k odhalení úplné konverzní tabulky. Pokud však kryptograf nezná jazyk textu, stává se dešifrování několikanásobně složitější, neboť musí postupy aplikovat na všechny dostupné jazyky a doufat, že najde použitý jazyk co nejdříve. V moderní kryptografii by však tento zdlouhavý postup nahradil výpočetní výkon počítačů, jak bude později ilustrováno na konkrétním skriptu.

2.2.3 Vigenérova šifra Tato šifra svým principem plně vychází z Caesarovy šifry. [1] Posun zde ale není pevně definován konkrétním číslem, nýbrž je měněn podle předem zvoleného textového klíče. Pro získání kódu, který bude vykazovat co nejméně systémově opakující se složky, bylo žádoucí využívat variabilitu posunu pokud možno co největší. Toho se docílilo zvolením dlouhého klíče. V tomto případě šlo o klíč v podobě slova. Pokud bychom chtěli šifrování a dešifrování provádět co nejrychleji, jsme stále v 16. století, volili bychom posun jednoduchý a zapamatovatelný například 123. Tím by ale trpěla míra bezpečnosti takto zašifrovaného textu a proto bylo nutné volit klíč, podle kterého se prováděl posun, složitější. K tomu, aby se dalo pracovat i s takto složitými klíči, sloužil jako pomůcka takzvaný Vigenérův čtverec viz obr. 2.8. [1]

19

První řádek tabulky je v tomto případě složen ze znaků anglické abecedy. Další řádky jsou pak konstruovány tak, že každý následující je podle principu Caesarovi šifry posunut o jeden výše. Tyto řádky jsou pak od jedné očíslovány v prvním sloupci. Poslední řádek je přitom posunut o tolik znaků, kolik jich je v použité abecedě. Přestože poslední řádek vlastně posunut není, neboť posun roven počtu znaků abecedy je stejný jako posun o 0 znaků, je pro šifrování touto metodou stejně důležitý.

Obr. 2.8: Vigenérův čtverec (zdroj: vlastní úprava) 1

1

Barevné zvýraznění v tabulce viz obr. 2.8 je určeno pro lepší přehled při ukázce šifrování Vigenérovou šifrou pomocí klíče „BLAISE“ viz níže

20

Vlastní šifrování probíhá tak, že je zvoleno klíčové slovo, podle kterého se bude posun variabilně měnit. Pro náš případ zvolíme klíč ve tvaru „BLAISE“ a kódovat budeme větu „Kryptujme Vigenérovou šifrou“. Nyní si pro lepší přehled sepíšeme klíčové slovo a kódovanou větu do tabulky viz obr. 2.9.

Obr. 2.9: Příprava pro šifrování Vigenérovou šifrou textu „Kryptujme Vigenérovou šifrou“ pomocí klíče „BLAISE“ (zdroj: vlastní úprava)

První řádek obsahuje klíč opisovaný cyklicky za sebou do délky šifrovaného textu, řádek druhý je vyplněn textem a třetí řádek je připraven pro výslednou šifru. Nyní postupujeme tak, že zjistíme jaký posun provedeme pro první písmeno našeho šifrovaného textu tedy pro „K“. Tomu odpovídá písmeno „B“ našeho zvoleného klíče, které je ve Vigenérově čtverci viz obr. 2.8 na řádku označeném číslem „1“. Na základě této informace tedy provedeme posun o 1. Výsledný znak „L“ zapíšeme do třetího řádku tabulky viz obr. 2.10 a pokračujeme v šifrování.

Obr. 2.10: Výsledek šifrování Vigenérovou šifrou textu „Kryptujme Vigenérovou šifrou“ pomocí textového klíče „BLAISE“ (zdroj: vlastní úprava)

Všimněme si ve třetím řádku tabulky viz obr. 2.10 zvýrazněných písmen „O“ a jim odpovídajících znaků šifrovaného textu. Díky variabilnímu posunu bylo dosaženo, že tento znak zastupuje různá písmena konkrétně „G“ a „P“. Tento aspekt má za následek, že nelze pro dešifrování textu využít znalosti daného konkrétního jazyka jako například nejvyšší, resp. nejnižší četnost znaků a podobně. Vynecháním mezer a převodem všech velkých písmen na malá, je tento efekt ještě více umocněn. Dešifrování takového kódu, za předpokladu že známe klíčové slovo použité pro určení posunu, je v principu stejné jako jeho šifrování a 21

nedělá tedy pro příjemce zprávy žádný větší problém. Jedinou komplikací může být zmíněné vynechání mezer a rozlišování velkých a malých písmen, což pro odeslání jednoduchých zpráv v 16. století zřejmě nebylo překážkou.

2.2.4 ADFGX Tato válečná šifra využívá principu substituce i transpozice. [1] Znaky otevřeného textu jsou nejprve postupně nahrazeny kombinací znaků „A“, „D“, „F“, „G“ a „X“. [1] Díky kombinaci znaků, je dosaženo pokrytí celé znakové sady šifrovaného jazyka. Přidáním znaku „V“ pak došlo k rozšíření znakové sady i o číslice. Po té je na takto zašifrovaný text aplikována metoda transpozice. Pro zašifrování textu „Kryptografie“ nejprve zvolíme šifrovací klíče. Pro substituci volíme „KRYPTO“ a pro transpozici „GRAFIE“. Pomocí prvního klíče vytvoříme substituční tabulku viz obr. 2.11 tak, že složíme do prvního řádku a prvního sloupce znaky „A“, „D“, „F“, „G“ a „X“. Po té to tabulky postupně vložíme substituční klíč, v našem případě „KRYPTO“ a doplníme tabulku zbývajícími znaky abecedy. Ty vkládáme postupně tak, jak je jejich pořadí v abecedě s tím, že vynecháváme písmena abecedy, která již byla použita v substitučním klíči. [1]

Obr. 2.11: Substituční tabulka šifry ADFGX s použitím klíče „KRYPTO“ (zdroj: vlastní úprava) 1

1

V tabulce viz obr. 2.11 je pro lepší přehlednost barevně odlišen použitý šifrovací klíč. Aby bylo možné sestavit tabulku ve čtvercovém tvaru, je vynechán znak „j“, který je v případě šifry ADFGX šifrován jako znak „i“.

22

Podle této substituční tabulky nyní vytvoříme tabulku konverzní viz obr. 2.12 a začneme s první fází šifrování otevřeného textu. Zašifrováním textu „Kryptografie“ tedy získáváme řetězec znaků „AA AD AF AD AX DA FF AD DD FD FX FA“.

Obr. 2.12: Konverzní tabulka šifry ADFGX vytvořená podle substituční tabulky viz obr. 2.11 (zdroj: vlastní úprava)

Další fází je aplikování transpoziční metody na výsledek substituční metody v předešlém kroku. Vytvoříme tabulku, která bude obsahovat klíčové slovo pro transpozici a naplníme ji řetězcem znaků získaným z předešlého kroku způsobem uvedeným v tabulce viz obr. 2.13.

Obr. 2.13: Příprava tabulky před transpozicí podle klíčového slova „GRAFIE“ (zdroj: vlastní úprava)

Nyní klíči „GRAFIE“ očíslujeme jednotlivé znaky na základě pořadí v abecedě. Pokud by klíč obsahoval shodná písmena, přednost v číslování má znak umístěný více vlevo. Po té přeskládáme klíč podle očíslovaného pořadí a s ním i celé sloupce.

Obr. 2.14: Výsledek transpozice podle klíčového slova „GRAFIE“ (zdroj: vlastní úprava)

Výsledek transpozice nyní přepisem znaků z tabulky po sloupcích viz obr. 2.14 převedeme do řetězce, [1] čímž získáváme zašifrované slovo „Kryptografie“ ve tvaru „AA FD DD AF AD AF AF AA XX AF DF DD“. Výsledný tvar kombinace substituce a transpozice vzbuzuje dojem, že se jedná o „opravdu“ o silnou šifru.

23

2.3 První kryptografické systémy Příchodem průmyslové revoluce došlo nejen k vynalézání nových průmyslových strojů, které by nahradili lidskou sílu po zdecimované civilizaci morovou epidemií, ale i k různým výpočetním

pomůckám.

To

umožnilo

vytvářet

stále

sofistikovanější

systémy,

které mechanickým způsobem uměly šifrovat a dešifrovat zprávy s čím dál složitějším algoritmem výpočtu. Největší potřeba těchto systémů byla samozřejmě opět ve válkách, protože se skrytá komunikace stávala rozhodujícím aspektem pro získání výhody nad nepřítelem. S objevením telegrafu se komunikace změnila ještě zásadněji. Umožnila přesun informací rychlostí a přesností jakou doposud nikdo nedokázal. To umožňovalo ještě více využívat informační kanály ve svůj prospěch, čímž ale vznikl i prostor pro odposlouchávání a tím zcizování informací pro svůj prospěch. Proto bylo opět nezbytné vyvíjet šifrovací algoritmy, které budou proti těmto útokům odolné.

2.3.1 Zimmermannův telegram V průběhu první světové války již byla šifrovaná komunikace běžnou záležitostí. V Německu ji v roce 1917 použil i tehdejší ministr zahraničí Arthur Zimmermann. Jeho telegram viz obr 2.15 (kompletní podoba v příloze č. 1) byl směřován na německé velvyslanectví v Mexiku. [1]

Obr. 2.15: Ukázka kódu Zimmermannova telegramu (zdroj [15])

Účelem této zprávy bylo vyprovokovat útok Mexika na Spojené státy pod příslibem navrácení území, které Mexiko ztratilo v roce 1848 ve válce právě se Spojenými státy. Pokud by se tak stalo, byly by Spojené státy zavlečeny do války na svém kontinentu a bylo pravděpodobné, že by tím pádem nemohli ovlivnit průběh války v Evropě a vypomoci tak Velké Británii 24

a Francii. V té době již ale v Británii operovala kryptografická organizace známá pod označením „Room 40“, které se podařilo zprávu zachytit a dešifrovat. To mělo samozřejmě pro německý plán fatální důsledky, neboť byla dešifrovaná zpráva doručena americké vládě, jejíž reakcí bylo schválení vstupu do války v Evropě. [1]

2.3.2 Šifra ADFGX Rok po Zimmermannově telegramu začala německá armáda využívat novou šifru nazvanou podle znaků, které šifrovaný text obsahoval. Byli jimi znaky „A“, „D“, „F“, „G“, „X“ a později ve vylepšené verzi ještě „V“. Zvolené znaky byly vybrány s ohledem na jejich odlišnost při vysílání Morseovou abecedou, takže i při zhoršených podmínkách bylo možné šifru opravit a následně dešifrovat. Protože ADFGX a později i z ní vycházející ADFGVX kombinovala obě základní metody, tedy substituci a transpozici, věřili její stvořitelé, že se jedná o neprolomitelnou šifru. To se však ukázalo jako naivní, neboť obě verze šifry byly brzy prolomeny. [1]

2.3.3 Enigma Nejdůležitější uplatnění oboru kryptografie právě ve válečných konfliktech dokládá i jeden z nejznámějších šifrovacích zařízení druhé světové války. Přestože se Enigma využívala ve druhé světové válce, jednalo se o německý elektromechanický šifrovací stroj, vynalezený Arthurem Scherbiusem a patentovaný už v roce 1918 viz obr. 2.16. [1]

Obr. 2.16: Schéma části šifrovacího stroje Enigma (vytvořeno ze zdroje [7])

25

Důvodem proč byl stroj nasazen až dvacet let poté, byla především jeho cena. Autor opět věřil, že se jedná o neprolomitelnou šifru a tak ho nechtěl poskytnout levně. Německá armáda však byla dlouho přesvědčena, že jejich aktuální šifry jsou dostatečně silné a nákup odkládala. Když se v roce 1923 dozvěděla, že britské námořnictvo umí jejich používané šifry lehce prolomit, byla nucena situaci rychle řešit. Řešením tedy bylo plošné nasazení Enigmy jak ve vojenském sektoru, tak i ve všech státních organizacích. [1] Zařízení mělo vzhled psacího stroje a jeho principem byl šifrovací mechanizmus složený ze soustavy ozubených kol. Určitá z nich byla opatřena dvaceti šesti kontakty, které po pootočení mechanismu, vyvolaným stiskem písmena, vytvářely konkrétní spojení s určitým znakem. Protože se jednalo o nastavitelné a vyměnitelné převody, verze pro německé námořnictvo disponovala dokonce osmi koly, bylo dosaženo velmi variabilní šifry. Přesto všechno se nakonec i šifrování Enigma povedlo prolomit. [1] Zásluhy za to se připisují britskému týmu pod vedením matematika Alana Turingema, avšak v poslední době se objevují hlasy, že hlavní zásluhy na prolomení Enigmy mají kryptologové z Polska. [6]

2.3.4 JN-25 Dalším příkladem šifry druhé světové války je systém „Japanes Navy 25“ používaný japonským námořnictvem. Principem šifrování byl přenos unikátních pětimístných čísel, přičemž každé z nich bylo zašifrováno a zastupovalo jedno slovo. Pro přiřazení slova k danému číselnému kódu sloužila první kniha, nebo-li slovník, která obsahovala na třicet tři tisíc slov a pro zašifrování sloužila druhá kniha obsahující číselné vzory pro substituci. Pro případ kdy bylo potřeba zašifrovat slova, která nebyla obsažena ve slovníku, byly číselné kódy přiřazeny i jednotlivým písmenům. K vlastnímu šifrování a dešifrování byly tedy potřebné dvě knihy, kterými museli disponovat obě strany komunikace. První kniha obsahovala zmíněný slovník slov podle kterých se text zakódoval do řady pětimístných čísel. Samotná substituce slov za číselné kódy však nebyla dostatečně silná šifra a proto se na tato čísla ještě aplikovalo šifrování podle druhé knihy. Ta konkrétně obsahovala očíslované strany se sloupci s náhodnými, opět pěticifernými, kódy. Pro šifrování se zvolil klíč z této knihy tím způsobem, že se náhodně zvolila strana, sloupec a řádek. Tento klíč pak byl odeslán s vlastní šifrovanou zprávou, která vznikla odečítáním jednotlivých cifer z kódů vzniklých substitucí podle první knihy s ciframi obsaženými v kódech na pozici, jež udával tento náhodně zvolený klíč. Tuto šifru se podařilo prolomit kryptology amerického námořnictva už roku 1940. Přestože se díky 26

neznalosti kompletního slovníku v první knize dařilo dešifrovat pouze menší procento celé zprávy, přispělo to i tak k výraznému ovlivnění dění v bojích druhé světové války. [1]

2.3.5 Kód Navajo Tento způsob šifrování se dá zařadit spíše do alternativních metod. Nevýhodou klasických šifrovacích metod používaných v letech druhé světové války, byla relativně dlouhá doba šifrování a dešifrování. Oproti tomu systém Navajo byl schopen celý proces zašifrovaní, přenesení a dešifrování běžně velké zprávy provést za přibližně dvacet vteřin. Principem tohoto šifrování bylo využití jazyka kmene Navajo, který vykazoval ve své struktuře unikátní prvky. Jednalo se o specifický jazyk, kterým uměla mluvit pouze uzavřená komunita členů kmene Navajo a několik málo vyvolených. Tým tvořený z rodilých mluvčích jazykem Navajo byl cvičen v používání vojenské telekomunikační techniky a učen kódovém slovníku, který obsahoval na tři sta slov viz obr. 2.17. [1] SHIPS BATTLESHIP

TOH-DINEH-IH LO-TSO

SEA FORCE WHALE

AIRCRAFT

TSIDI-MOFFA-YE-HI

BIRD CARRIER

SUBMARINE

BESH-LO

IRON FISH

MINE SWEEPER

CHA

BEAVER

DESTROYER

CA-LO

SHARK

TRANSPORT

DINEH-NAY-YE-HI

MAN CARRIER

CRUISER

LO-TSO-YAZZIE

SMALL WHALE

MOSQUITO BOAT

TSE-E

MOSQUITO

Obr. 2.17: Výňatek z kódového slovníku (zdroj [12]) 1

I přesto, že se pak tato kódová slova už jen překládala do jazyka Navajo a vysílala přímo bez jakéhokoli dalšího šifrování, měl tento způsob tajné komunikace veliký úspěch. Kód Navajo nebyl japonskou armádou za druhé světové války prolomen a tak mohl být úspěšně nasazen i v dalších válkách, kde prolomení odolal také. [1]

1

Sloupce viz obr. 2.17 jsou uvedeny v pořadí anglický název, překlad Navajo, kódové slovo pro anglický název

27

3

Faktorizace velkých čísel

Faktorizace je velmi náročná matematická disciplína. Smyslem faktorizace jsou procesy, které převádějí čísla o velkém počtu cifer na čísla složená ze součinů jejich faktorů. Jinými slovy řečeno, jedná se o rozklad velkých čísel na prvočísla, tedy čísla beze zbytku dělitelná pouze sama sebou nebo číslem jedna. Tento rozklad je přitom vždy jednoznačný, tedy zpětným procesem dojdeme vždy k původnímu číslu. Právě díky této skutečnosti a dále i díky tomu, že je takovýto rozklad netriviální problém, nalezla faktorizace v moderní kryptografii své místo.

3.1 Faktorizace v kryptografii Složitost problému faktorizace velkých čísel je s výhodou využívána v kryptografii. V roce 1978 díky této skutečnosti vytvořili Ronald Rivest, Adi Shamir a Leonard Adlemann kryptovací systém RSA. [14]

3.1.1 Privátní a veřejný klíč Pro přenesení zprávy z bodu A do bodu B se postupuje tímto principem. Bod B coby strana, která je příjemcem zprávy, vygeneruje pár klíčů. Jeden klíč je generován jako veřejný a je tedy k dispozici všem členům komunikace. Tento veřejný klíč tedy může být odeslán veřejnou cestou, neboť jeho zachycení není reálnou hrozbou pro vlastní šifrovanou komunikaci. [14] Je ale vhodné podotknout, že tvrzení o neexistenci reálné hrozby, je třeba brát s ohledem na současné znalosti a technologie, neboť je velmi pravděpodobné, že bude v blízké budoucnosti problém faktorizace vyřešen takovým způsobem, že se stane tento způsob šifrování z hlediska bezpečnosti nevhodný. Jinými slovy řečeno, pokud se podaří vyřešit problém faktorizace velkých čísel, tak aby bylo možné určit rozklad velkých čísel na prvočísla v dostatečně krátké době, bude šifrování na principu faktorizace prolomeno. Veřejný klíč je tedy odeslán do bodu A. Odesílatel nyní pomocí tohoto veřejného klíče zašifruje zprávu. Zašifrování zprávy může tímto způsobem udělat každý, kdo se chce této

28

komunikace zúčastnit a má přístup k veřejnému klíči. Zpráva je pak odeslána příjemci do bodu B. Příjemce zprávy nyní použije druhou část párového klíče, kterou uchoval v tajnosti, neboť se jedná o privátní klíč. Protože je tento klíč vygenerován jako pár k veřejnému klíči a mají tedy oba klíče mezi sebou určitou vazbu, může být pomocí něj zpráva dešifrována. Jinými slovy, zprávu může dešifrovat pouze ten, kdo má privátní klíč párovaný k veřejnému klíči, kterým byla zpráva zašifrována. [14]

3.1.2 Vazba mezi privátním a veřejným klíčem Čím je dána zmíněná vazba mezi privátním a veřejným klíčem? Pro použití metody RSA je stěžejním předpokladem, že není možné v „užitečné době“ z veřejného klíče odvodit klíč privátní a tím zprávu dešifrovat. „Užitečnou dobou“ přitom myslíme čas, který by musel k odvození privátního klíče uplynout, přičemž by byla zpráva stále aktuální, resp. by informace v ní měla stále nějakou hodnotu. Je asi zřejmé, že informace o tom, že bude zítra ráno v 6:00 veden útok na obrané linie nepřítele, nebude mít za 10 let přílišnou cenu. To je docíleno u kryptografického systému RSA právě neznalostí způsobu jak rychle a efektivně provádět faktorizaci velkých čísel. Názornou ukázku komunikace na konkrétním příkladu nyní popíšeme v jednotlivých krocích. Krok jedna až tři zahrnuje generování klíčů a krok čtyři až šest vlastní komunikaci. [14] Pro úplnost dodejme, že: -

a ≡ b (mod n) značí, že a a b mají stejný zbytek po dělení n, tedy že a − b je dělitelné n, [9] 1

-

symbol mod značí matematickou operaci modulo, jedná se o zbytek po celočíselném dělení, například rovnici a mod 4 = 1 splňují čísla a = l, 5,9 atd. [1]

1

Symbol ≡ se nazývá kongruence a čte se: „je kongruentní s ... (s modulem ...)“ [9]

29

V ukázkovém příkladu nechť je bod A odesílatel zprávy (Alice) a bod B příjemce zprávy (Bob). 1) Bob si nejdříve vybere dvě dostatečně velká prvočísla p a q, která vynásobí a získá číslo n = p . q. 2) Poté začne počítat dvě celá čísla d a e tak, že za e si zvolí náhodné číslo, které je nesoudělné s číslem (p – 1)(q – 1). Dále musí vypočítat d z výrazu ed ≡ 1 mod (p – 1)(q – 1). 3) Následuje zaslání veřejného klíče Alici jako páru čísel { e, n }. 4) Vytvoření zprávy M∈ℤn. 5) Nyní Alice zašifruje zprávu pomocí veřejného klíče jako C = M e mod n. 6) Tu pak zašle Bobovi, který na základě znalosti svého utajeného privátního klíče dešifruje jako M = C d mod n a potom převede zpět do textové podoby. [14] Nyní bod jedna až šest aplikujeme na konkrétní číselné hodnoty. Pro názornost volíme malá prvočísla 11 a 13. Bob při generování klíče použije například pro p = 11 a pro q = 13. Pak podle bodu 1) je n = p . q = 143. Za e nechť je zvoleno číslo 7, které splňuje podmínku, viz bod 2), tedy že je nesoudělné ve smyslu (p – 1)(q – 1) a současně menší než toto číslo. Pak d . 7 ≡ 1 mod 120 je d = 103. V tento okamžik je vytvořen veřejný klíč (7, 143) a klíč privátní (103, 143). Veřejný klíč je odeslán veřejnou cestou do bodu A, pomocí něhož provede Alice šifrování textu. Pro naše účely zašifrujeme pouze písmeno x, kterému bude dle konverzní tabulky odpovídat číslo 16. Potom C p = 167 mod 143 = 3. Po přijetí šifrované zprávy v bodě B provede Bob dešifrování privátním klíčem jako M = 3103 mod 143 = 16, čemuž podle konverzní tabulky odpovídá písmeno x. [14] Z uvedeného příkladu je patrné, jakou roli hraje právě faktorizace velkých čísel v bezpečnosti této šifry. Protože je předpoklad, že čísla použitá pro generování privátního a veřejného klíče jsou velká prvočísla, pro n se doporučuje alespoň délka 128 bitů, prolomení hrubou silou je velmi nepravděpodobné. K prolomení šifry by bylo nutné rozložit součin p . q, nebo-li určit z kterých dvou prvočísel je klíč složen. V případě získání této informace, což je dnes vzhledem ke složitosti faktorizace stále ještě velmi složité, by bylo vypočtení d už jen jednoduchým úkonem. [14]

30

3.2 Časová složitost Pro řešení úloh rozkladu velkých čísel na prvočísla je důležitým kritériem časová a paměťová náročnost těchto procesů. V případě řešení těchto úloh za pomoci výpočetní techniky se tato složitost označuje termínem asymptotická složitost. Vyjadřuje způsob chování daného algoritmu v závislosti na tom, jaká je velikost zpracovávaných dat. Tato kritéria se rozdělují do tříd složitosti. Nejčastějším hlediskem pro určení časové složitosti je určení tohoto faktoru v jeho nejhorším případě. Toto hledisko se oproti průměrné časové složitosti určuje snadněji. [5] „Pokud je časová složitost f(N) polynom, hovoříme o polynomiálně omezených algoritmech. Takové problémy, které řeší nějaký polynomiální algoritmus, patří do tzv. třídy P. Pokud pro daný problém neexistuje polynomiálně omezený algoritmus, který řešení nalezne, ale

existuje

polynomiálně

omezený

algoritmus,

který

řešení

ověří,

hovoříme

o nedeterministicky polynomiálních problémech. Problémy, které řeší nedeterministický algoritmus, patří do třídy NP (např. problém obchodního cestujícího, splnitelnost formule výrokové logiky a mnoho dalších). Jednou z největších současných otevřených otázek teoretické informatiky je problém, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není.“ [5] Z kapitol věnujících se historii šifrování vyplývá poznatek, že první pokusy o šifrování se opíraly o pokud možno velmi jednoduché výpočty a hlavní sílu šifry určoval způsob, jak byl prostý text ve výsledném šifrovaném textu dobře ukryt. Pokud tedy došlo k odhalení principu, jaký šifra používala, prolomit vlastní šifru už nebylo nijak složité. Pozdější šifry tuto slabou stránku řešily kombinováním různých metod a zvyšováním podílu výpočtů pro šifrování, resp. dešifrování. To se ale v době počítačů stalo nedostatečné a tak se logicky přesouvá pozornost k šifrám, které tomuto vývoji odolají. Časová složitost je tedy velmi důležitým prvkem v moderní kryptografii.

31

Mezi typické příklady časové složitosti patří: -

O(1) skok na prvek v poli dle indexu,

-

O(log2 N) vyhledání prvku v seřazeném poli metodou půlení intervalu,

-

O(N) vyhledání prvku v neseřazeném poli lineárním (sekvenčním) vyhledáváním,

-

O(N log N) seřazení pole prvků s definovanou nerovností (např. reálná čísla podle velikosti, např. algoritmem Mergesort),

-

O(N2) diskrétní Fourierova transformace (DFT) počítaná přímočaře podle definice; sčítání dvou matic velikosti NxN,

-

(aspoň) O(2N) přesné řešení problému obchodního cestujícího (či jiného NP-úplného problému hrubou silou). [5]

3.3 Faktorizační algoritmy Způsobů jak faktorizovat velká čísla je relativně mnoho avšak s rostoucí kvalitou algoritmů roste i jejich matematická složitost. Proto se pro účely této kapitoly omezíme jen na obecné seznámení s nejjednoduššími metodami.

3.3.1 Zkusmé dělení Tato metoda se řadí mezi nejjednodušší metody rozkladu na prvočísla vůbec. Principem zkusmého dělení je cyklické dělení rostoucími čísly. Cyklus je ukončen v okamžiku, kdy je nalezen dělitel. Sofistikovanější algoritmus pracuje s připraveným seznamem prvočísel menších než odmocnina z N, přičemž jsou pokusy o nalezení dělitelnosti N prováděny pouze s těmito prvočísly. Složitost této metody je pak určena vztahem P . exp(log p), kde P je polynom a p je nejmenším dělitelem N. Podle toho, zda je metoda aplikována za použití seznamu prvočísel nebo bez něj, je P dáno jako: -

za použití seznamu je P ∈ O(logN),

-

bez použití seznamu je P ∈ O(log N . log p). [8]

32

V případě součinu dvou velkých prvočísel nastává nejhorší případ, tedy nevyšší složitost, za situace, kdy tento součin N je složen z prvočísel, která jsou přibližně stejně velká. Pak je složitost dána vztahem O(log2 N) . exp(1/2 log N). Z toho vztahu vyplývá, že je zkusmé dělení exponenciální algoritmus, nebo-li časová náročnost roste exponenciálně s velikostí čísla N. [8] Exponenciálně rostoucí složitost je i v době moderních počítačů stále ještě problém, proto se hledají sofistikovanější metody, které tyto procesy podstatně urychlují. Pro jejich použití je ale vhodné znát informace na základě kterých je metoda zvolena. Přesto je ale metoda zkusmého dělení v některých případech s výhodou využívána a to zejména když o rozkládaném čísle N nemáme žádné informace a velikost faktoru je trojciferné nebo menší.

3.3.2 Pollardova ρ metoda Tato metoda byla objevena v roce 1975 Johnem Pollardem. [13] Její praktické využití je pro rozkládání složených čísel s malým faktorem. [13] Pro přiblížení principu této metody se omezíme na omezenou citaci z materiálů připravované knihy „Faktorizace velkých čísel“ Přemysla Jedličky viz zdroj. [8] „Vezměme si náhodnou funkci f : ℤn → ℤn, pro nějaké n ∈ ℤ, a náhodné číslo a ∈ ℤn. Zkoumáme, jak budou vypadat iterované obrazy prvku a, tj. prvky f i(a). Budeme-li postupné iterace prvku a spojovat úsečkami a pokud začneme v levém dolním rohu papíru, dostaneme obrázek, který graficky připomíná řecké písmeno ró. Ony totiž tím, že je množina ℤn konečná, musí existovat čísla M a P (vezměme ta nejmenší možná), že f M(a) = f M+P(a). Pochopitelně, pak bude platit i f M+i(a) = f

M+P+i

(a), pro každé i ≥ 0. Číslo P se nazývá perioda funkce f a

číslo M je preperioda funkce f. Pollardova ρ metoda faktorizace (odkud se vzalo p jsme již nastínili) je založena na předchozím pozorování. Předpokládejme, že n je dělitel čísla N (ne nutně prvočíselný), kterého ještě neznáme (ale chceme nalézt). Zvolíme nějaké f : ℤn → ℤn a budeme počítat iterace nějakého prvku a ∈ ℤn, než nalezneme nějaká i, j taková, že fi (a) = f j(a). Ovšemže ty iterace můžeme počítat pouze teoreticky, ve skutečnosti přece číslo n neznáme! Ve skutečnosti výpočet probíhá v ℤn. Zvolíme nějaké g ∈ ℤn [X] a tím že g je polynom a n dělí N, bude platit že kdykoliv x = y (mod n), pak i g(x) = g(y) (mod n). Můžeme tedy definovat f jakožto projekci polynomu g modulo n. Zvolíme náhodné b ∈ ℤn a nazveme a

33

projekci prvku b mod n. Označíme bi = gi(b) a nazveme ai jejich projekce modulo n (takže ai = f i(a)). Jak poznáme, že pro nějaká i a j platí ai = aj ? Poznáme to tak, že bi = bj (mod N) a tedy číslo n dělí (bi — bj,N). Bylo by ale příliš nákladné testovat všechny možné dvojice i a j, lepší je hledat, kdy nastane ai = a2i.“ [8] Protože neznáme rozkládané číslo n nedokážeme zaručit, že funkce f je zcela průměrnou funkcí z ℤn do ℤn. Tato skutečnost komplikuje výpočet složitosti Pollardova algoritmu. Počítáme proto pouze složitost obvyklou, tedy za předpokladu, že jsou perioda i preperioda funkce f řádově odmocninou z n. Obvyklou složitostí tohoto algoritmu je pak dán výrazem P . exp( l/2 log p), kde P je polynom, nebo-li mnohočlen, a p je nejmenší dělitel čísla N. Za těchto podmínek má tedy algoritmus v nejhorším případě složitost danou výrazem P . exp(1/4 log N). [8] Po té, co byl tento algoritmus představen, byl ještě vylepšen Richardem Brentem. Počet porovnání zůstal sice stejný, neboť se předpokládá, že se pravděpodobně jedná o nejmenší možný počet, ale Brent přišel na to, že postačuje testovat zda ai = a2k – 1, kde k je nanejvýše takové, kdy 2k ≤ i. Tím zjistil, že nemusí kontrolovat všechna ai a může se omezit na testování intervalu (3/2 . 2k, 2 . 2k). [8]

3.3.3 Pollardova ρ - 1 metoda Tato metoda je založena na Malé Fermatově větě a p-1 ≡ 1 (mod p), pro p prvočíslo a každé a ∈ ℤp*. Předpokladem využití této metody je, že sice neznáme prvočíslo p coby dělitele čísla N, ale známe číslo x splňující podmínku x ≡ k (p – 1) . (mod N). Potom platí, že ax ≡ 1 (mod p). To dokážeme odhalit tím, že ax – 1 má společného dělitele s N. Pokud má být tato podmínka splněna musí být číslo p - 1 ve speciálním tvaru. [8] „Mějme přirozené číslo B. Přirozené číslo x se nazývá B-hladké, pokud každé prvočíslo dělící x je menší nebo rovno B. Číslo x se nazývá B-mocné, pokud pk ≤ B, kdykoliv pk dělí x a p je prvočíslo.“ [8] Tato metoda tedy spoléhá na to, že alespoň jeden prvočíselný dělitel čísla N, má tu vlastnost, že p - 1 je B-mocné pro dostatečně malé B. Jedná se tedy o specifický algoritmus, který má omezené použití právě s ohledem na tuto vlastnost. Avšak v případě splnění podmínky p - 1 se jedná o velice efektivní algoritmus, který není vhodné při podceňovat například 34

při konstrukci klíče RSA. Pokud tedy chceme zabránit prolomení klíče RSA, je nutné při jeho konstrukci dbát na to, aby žádné z prvočísel, které tvoří součin čísla N, nemělo vhodnou hodnotu p – 1. [8]

3.3.4 Williamsova p + 1 metoda Tato metoda faktorizace je přímým následovníkem Pollardovy p - 1 metody. Přestože Williams nebyl sám, kdo odhalil toto zobecnění, nicméně byl prvním, kdo sestavil algoritmus tak, že dokáže nalézt rozklad u čísel, na která nebyla Pollardova metoda p - 1 vhodná. Nevhodnost Pollardovy metody u těchto čísel byla dána velkou časovou náročností. [8] „Tak jako je p - 1 metoda založena na tom, že ℤp* má p - 1 prvků, je p + 1 metoda založena na výpočtu v GF(p2)* / ℤp*, což je grupa o p + 1 prvcích. To znamená, že pokud máme α ∈ GF(p2)*, pak αp+1 padne do prvotělesa.“ [8]

3.4. Nejjednodušší faktorizační skript Jako příklady rozkladu čísel na prvočíselný součin si uvedeme několik výstupů ze skriptu viz obr. 3.1. Skript pracuje na jednoduchém principu, kdy ve smyčce while testuje zda je zbytek po dělení roven nule. Tato vnořená smyčka pak běží ve smyčce for, která se provádí, dokud je odmocnina zbytku po dělení větší nebo rovna hodnotě nejmenšího prvočísla, tedy 2. Budeme-li tedy měnit vstupní proměnnou skriptu viz obr. 3.1 získáme prvočíselné rozklady, které budou pro příslušná čísla vypadat takto: 9 = 3*3, 273 = 3*7*13, 13065 = 3*5*13*67, 14958141203 = 17*59*113*271*487, 93084257327692683 = 3*13*151*277*443*457*521*541 , 614889782588491410 = 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47 .

35

Rozklad čísla probíhá ve smyčkách a počet smyček roste s velikostí rozkládaného čísla. Pro malá čísla bude tedy tento algoritmus pracovat správně a rychle avšak s růstem velikosti čísla se bude stávat nevhodný, neboť náročnost rozkladu, jak jsme popsali v předešlých kapitolách, roste exponenciálně k velikosti rozkládaného čísla. Dalším zásadním problémem při pokusu o rozklad větších čísel za pomoci tohoto skriptu bude omezení programovacího jazyka PHP, který neumožňuje pracovat s velkými čísly.

Obr. 3.1: Ukázka skriptu pro rozklad na součin prvočísel (vytvořen za pomoci zdroje [10]) 1

1

Skript viz obr. 3.1 je k dispozici na adrese http://skola.rwm.cz/bivs/faktorizace.php, kde je možné jeho funkci ověřit v rozsahu hodnot 4 až 999 včetně

36

Na ukázkových příkladech prvočíselných rozkladů je na první pohled patrné, že vstupní čísla pro rozklad nejsou volena náhodně, ale jsou zkonstruována z prvočísel tak, aby byl výsledný rozklad z estetického hlediska co nejúhlednější a příklad se tak stal co nejnázornější. Vstupní hodnota posledního ukázkového příkladu je tvořena součinem prvních patnácti prvočísel. Pro vytvoření takovéhoto typu čísla může posloužit skript viz obr. 3.2.

Obr. 3.2: Skript pro generování prvočísel a vytvoření čísla z jejich součinu (zdroj: vlastní úprava) 1

1

Skript viz obr. 3.2 je k dispozici na adrese http://skola.rwm.cz/bivs/prvocisla.php

37

Skript na obr. 3.2 pracuje s řadou prvočísel, kterou si nejprve sám vygeneruje. Velikost takto vytvořené řady prvočísel je teoreticky omezená pouze časem potřebným pro výpočet a prostředky počítače. Tento skript je však omezen rozsahem vstupních hodnot 4 až 999 včetně. Spodní hranice je nastavena z logiky rozkladu, kdy nemá smysl rozkládat již nerozložitelná prvočísla 3 a 2. Přestože je skript schopen zpracovávat relativně veliká čísla, je nastavena horní hranice i s ohledem na možné záškodnické pokusy o přetížení serveru. Pro účely této práce skript vytváří pouze řadu složenou z prvočísel do hodnoty 10000, která obsahuje 1229 členů (viz příloha č. 2). Protože je v jazyce PHP omezena velikost proměnných, výsledné číslo je složeno pouze ze součinu prvních 130ti prvočísel. 528846684810196189470720354849006601835585728726051656256762696884909054540 360612840774718845718811273169972140571557169655746898366251405332726751506 848391957916809132555647584867973504084846017633734902622545084683379256367 259058735592982155044860191076433526396897580630991930559563765237450174942 4128 = 2*3*5*7*11*13*17*19*23*29*31*37*41*43*47*53*59*61*67*71*73*79*83*89*9 7*101*103*107*109*113*127*131*137*139*149*151*157*163*167*173*179*181*191*1 93*197*199*211*223*227*229*233*239*241*251*257*263*269*271*277*281*283*293* 307*311*313*317*331*337*347*349*353*359*367*373*379*383*389*397*401*409*419 *421*431*433*439*443*449*457*461*463*467*479*487*491*499*503*509*521*523*54 1*547*557*563*569*571*577*587*593*599*601*607*613*617*619*631*641*643*647*6 53*659*661*673*677*683*691*701*709*719*727*733 Pokud bychom chtěli vyzkoušet, jak si skript viz obr. 3.1 poradí s faktorizací malých náhodných čísel v určitém intervalu, nahradili bychom ve skriptu statickou hodnotu přidělovanou do proměnné $n hodnotou generovanou generátorem náhodných čísel v našem případě funkcí Rand. Několik výsledných rozkladů by pak mohlo vypadat například takto: 4962424464989 = 4962424464989, 9573711668141 = 443*919*2089*11257, 1170998795889 = 3*3*13*1879*5326523, 8572913146112 = 2*2*2*2*2*2*2*2*7*4783991711. To už ale nedostáváme ve výstupu skriptu tak „uhlazené“ rozklady, protože algoritmus při rozkladu touto metodou mnohdy narazí na veliká prvočísla, která neumí dále zpracovat. 38

3.5 Prolomení veřejného klíče V předchozích kapitolách byl předveden princip, jakým způsobem probíhá šifrovaná komunikace za pomoci privátního a veřejného klíče a jakou roli zde hraje metoda faktorizace. Za pomocí skriptu viz obr. 3.3 demonstrujeme, jak jednoduché by bylo prolomit toto šifrování, pokud by byla tato metoda aplikována na nedostatečně velká čísla.

Obr. 3.3: Skript pro rozložení generovaného součinu prvočísel (zdroj: vlastní úprava) 1

1

Skript viz obr. 3.3 a obr. 3.4 je k dispozici na adrese http://skola.rwm.cz/bivs/rsa.php

39

K prolomení šifry využívající metodu faktorizace velkých čísel by bylo nutné rozložit součin p . q, nebo-li určit z kterých dvou prvočísel je klíč složen. Pro demonstraci takového prolomení skript v úvodní části vygeneruje řadu prvočísel až do hodnoty 100000. Z této řady pak generátorem náhodných čísel rand vybere dvě náhodná prvočísla. Aby byla vybraná prvočísla pokud možno co největší, je výběr proveden z horních 10% hodnot. Skript je ošetřen smyčkou while, v které se provádí opakovaný výběr druhého prvočísla v případě, že je druhý výběr shodný s výběrem prvním. Součinem těchto dvou náhodných prvočísel získáváme hodnotu n. Jedním z výstupů skriptu viz obr. 3.3 pak může být například: p = 97453, q = 97847, n = p . q = 9535483691. Hodnotu n následně rozložíme skriptem pracujícím na stejně jednoduchém principu jako skript viz obr. 3.1. Ten zpět rozloží číslo n na součin dvou prvočísel: 9535483691 = 97453*97847 za pouhých 0.0262548923492 sec. Na rychlosti zpracování tohoto konkrétního případu, je velmi dobře vidět, jak jednoduché by bylo prolomení šifry využívající faktorizaci, kdyby nebyla k vygenerování klíče použita dostatečně velká čísla. Čas běhu skriptu byl přitom měřen pouze v části, kde se provádí vlastní rozklad, neboť měřením běhu celého skriptu by byly výsledky s ohledem na časovou náročnost generování prvočíselné řady značně zavádějící. Pro urychlení této výpočetně náročné části by bylo vhodným řešením předem vypočítat řadu prvočísel až do velikosti, se kterou by bylo dále pracováno a následně tuto konečnou řadu prvočísel uložit do databáze. Aby bylo možné využít skript viz obr. 3.3 k měření rychlosti této jednoduché metody rozkladu na prvočísla, byl doplněn o příkazy viz obr. 3.4.

Obr. 3.4: Doplnění skriptu příkazy pro měření doby běhu (zdroj: vlastní úprava)

40

Modifikovaný skript viz obr. 3.3 a obr. 3.4 byl použit také pro měření časové složitosti faktorizace pro různé velikosti vstupních hodnot. Tento test si kladl za cíl odpovědět na otázku, zda je možné i na rozkladu malých čísel prakticky prokázat exponenciální časovou složitost faktorizace.

Obr. 3.5: Měření časové složitosti faktorizace prováděné skriptem viz obr. 3.3 (zdroj: vlastní úprava)

Vstupní hodnoty skriptu byly zvoleny v rozsahu 1000 až 10000000. Tyto hodnoty vyjadřovaly, jak maximálně veliké může být prvočíslo použité v součinu. Byla tedy splněna podmínka zadání, že měření proběhne na malých číslech. Naměřené hodnoty byly zapsaný do tabulky a vyneseny do grafu viz obr. 3.5. Závěrem testu je konstatování, že výsledky měření se i na takto malých číslech shodují s tvrzením, že časová složitost faktorizace roste exponenciálně s velikostí rozkládaných čísel.

3.6 Budoucnost faktorizace v kryptografii Úloha faktorizace velkých čísel má v moderní kryptografii své nezastupitelné místo. Použitím této náročné matematické metody může tedy kryptografie eliminovat rizika prolomení šifrování, která plynou z možnosti použití výpočetního výkonu pro útoky hrubou silou. Jak bylo v předešlých kapitolách ukázáno, časová náročnost prolomení šifry za použití faktorizace velkých čísel pro tento typ útoku roste exponenciálně. Proto se za určitých předpokladů zdá 41

být tato metoda jako stvořená pro kryptografii. Otázkou však je, jak tato metoda obstojí v dalších letech, protože podle empirického pravidla je pravděpodobné, že výpočetní výkon počítačů stále poroste. Pokud bude tento růst pokračovat tempem viz obr. 3.6, tak jak ho předpověděl v roce 1965 spoluzakladatel společnosti Intel Gordon Moore, tedy, že se výkon procesorů zdvojnásobí každé dva roky [11], nebudete to pro faktorizaci znamenat v blízké budoucnosti žádné velké riziko.

Obr. 3.6: Vývojový graf počtu transistorů v časovém rozmezí 1971 až 2008 (zdroj [11])

Toto navyšování výpočetního výkonu lze vyvážit například zvětšením velikosti klíče, neboť i jeho malé zvětšení, resp. součinu prvočísel, z kterých je složen, zvýší při exponenciální charakteristice nárůst časové složitosti natolik, aby dokázala pokrýt tento rostoucí trend. To bylo popsáno a měřením demonstrováno viz obr. 3.3.

42

Z výše uvedeného by se tedy mohlo zdát, že i do budoucna je faktorizace velkých čísel výborným kandidátem pro využití v kryptografii a že tedy zůstane dlouhou dobu nejvhodnější metodou. Na to se však nelze spoléhat, protože se už dnes objevují nové teorie, jak metody faktorizaci velkých čísel zdokonalit a provádět tak rozklad velkých čísel na prvočísla v mnohem kratších časech. Tyto snahy zřejmě nejsou hnány touhou po prolomení šifrování založeném na využití faktorizace. Faktem však zůstává, že případný zásadní úspěch v řešení těchto úloh bude mít fatální následky pro kryptografii. Proto je nezbytné stále hledat nové principy, které by případně tuto dnes významnou metodu kryptografie mohly jednou nahradit.

43

4

Techniky bezpečného šifrování

4.1 Metody a zásady bezpečného šifrování Moderní kryptografie se opírá o mnoho aspektů, které jako celek tvoří celkovou sílu šifrování. I zde tedy platí, že řetěz je tak silný, jak je silný jeho nejslabší článek. Použitím kryptografie ještě neznamená, že jsou data v bezpečí. Jednoduchým názorným příkladem může být PIN napsaný na platební kartě, nebo klíč od bezpečnostního zámku pod rohožkou. Síla zabezpečení pak může být libovolně veliká, ale při porušení základních pravidel je zbytečná.

4.1.1 Základní všeobecná pravidla Pro kryptografii více než v jiných oborech platí, že je důležité při vytváření kryptografických systémů dodržovat všeobecná pravidla. Přestože se kryptografie jako vědní obor stále vyvíjí, tato základní pravidla jsou až na malé úpravy, zejména s ohledem na technologii, platná dnes stejně jako před sto lety. Například v minulé století je definoval August Kerckhoffs takto: -

systém má být, když ne teoreticky, tak aspoň prakticky nerozluštitelný,

-

odhalení systému nemá způsobit těžkosti korespondentům,

-

šifrovací klíč má být lehce zapamatovatelný a lehce změnitelný,

-

zašifrovaný text má být přenositelný telegrafem,

-

šifrovací přístroj nebo dokument má být přenositelný a obsluhovatelný jednou osobou,

-

šifrovací systém má být lehký, bez dlouhého seznamu pravidel a bez přehnaných nároků na duševní činnost. [2]

Pro úplnost je vhodné objasnit, proč autor mezi svá pravidla zařadil i to, že odhalení systému není nebezpečné, viz bod 2. August Kerckhoffs byl totiž jedním z prvních, kdo rozlišoval výraz kryptografický systém od výrazu kryptografický klíč. [2] Tak jak bylo ukázáno v předešlých kapitolách, síla některých šifer je přímo spjata se sílou utajení vlastního principu šifry. Pokud tedy budeme šifrovat substituční metodou o pevném posunu znaků, bude pro nás vyzrazení této informace zničující, neboť jen znalost samotného principu povede k rychlému

44

prolomení šifry. To však neplatí u šifer, které využívají šifrovacího klíče. Autor tohoto pravidla tedy jinými slovy říká, že pokud je kryptografický systém udělán dobře, za předpokladu, že nedojde k prozrazení šifrovacího klíče, nemusí být odhalení vlastního kryptografického systému problém. Modernější kritéria, která posuzují kvalitu kryptografického systému, podal otec matematické kryptografie Claude Shannon takto: -

spolehlivost: Myslí se spolehlivost ve smyslu odolnosti proti prolomení šifry. Existují například systémy, u kterých ani při znalosti klíče nemáme jistý předpoklad, že při daných technických možnostech můžeme přijatou zprávu rozluštit.

-

objem klíče: Vzhledem k tomu, že se klíč (v klasických systémech) musí mezi komunikujícími stranami vyměnit bez komprimace, je snaha, aby byl co nejmenší.

-

složitost operace šifrování a dešifrování: Míra složitosti je relativní a její hodnocení v první řadě závisí na tom, za jakých okolností šifrujeme a jaký stupeň bezpečnosti přitom chceme zajistit.

-

šíření chyb: Existují šifrovací metody, ve kterých šifrování znaku anebo skupiny znaků je odvislé od šifrování některých předchozích znaků. V takových systémech pak může mít chyba vážné důsledky na dešifrování textu; v nejhorším případě je nutné odeslat zprávu opakovaně.

-

zvětšení šifrovaného textu: Existují šifrovací systémy, ve kterých se text po zašifrování zvětší. Jedním z cílů této metody může být porušení statické charakteristiky zašifrovaného textu. Prodlužování textu však může být na druhou stranu nežádoucí z jiných důvodů, například z důvodu omezené propustnosti přenosového kanálu. [2]

Praxe těchto pravidel vytvořila nesčetně, stačí si rozpomenout na rozluštění kódu z druhé světové války ADFGXV, který principiálně vycházel z jeho předešlé verze ADFGX. Toto pravidlo by pak mohlo například znít: „Netvořme kryptografické systémy úpravou jiných systémů, když si nejsme jisti, zda není tento systém již prolomen“.

45

Pro úplnost však uveďme ještě jednu skupinu pravidel, která se zaměřuje na vlastní používání kryptografických systémů. Mezi základní pak patří: -

nevysílat stejný text šifrovaný různými způsoby,

-

zabránit používání stereotypních a velmi pravděpodobných slov a frází,

-

omezit používání typických kombinací písmen, interpunkčních znamének a používání mezer mezi slovy. [2]

4.1.2 Bezpečnost hesel Ať už se jedná o šifrovací nebo jiné aplikace v mnoha případech je vyžadováno zadání hesla. Heslo však na základě požadavku jeho použití musí splňovat určitá kriteria. Protože je stanovení hesla s rozmachem mechanismů pro útoky „hrubou silou“ čím dál důležitějším tématem, mnoho aplikací a systémů si tento problém řeší sami. Pomocí nastavení pak lze v takovýchto aplikacích stanovit přísná pravidla pro zadávání nového hesla. Avšak při nevhodném chování uživatele, je i toto opatření neúčinné. Příkladem takového nebezpečného chování může být například opsání hesla z názvu monitoru, nebo jiné periferie, nebo, ještě horší, napsaní hesla na papírek a schování ho pod podložku pod myš. Ve své praxi jsem se s tímto jednáním setkal mnohokrát. Délka hesla Nejzákladnější kritérium správného hesla je jeho délka. S počtem znaků v hesle roste i počet kombinací čímž se zvedá odolnost takového hesla. Pokud je heslo krátké, je lehce prolomitelné „hrubou silou“ nebo-li „brute force“. Existuje relativně velké množství volně přístupných programů, které tímto způsobem útoky provádějí. V principu se jedná o jednoduchý program pracující v cyklických pokusech o přihlášení na základě stanovených podmínek. Tím nejjednodušším způsobem je pokus o přihlášení zkoušením všech možných kombinací, které lze ze zadaných znaků vytvořit. V takovém případě pak stačí pouze zadat jaké kombinace znaků má program pro přihlašování používat, tedy například jen čísla nebo jen znaky anglické abecedy apod., od jakého počtu znaků má začít a kde se má o přihlášení pokoušet.

46

Pokud není cílový systém chráněn například maximálním počtem chybných přihlášení, nebo ip adresou z které je přihlášení možné, je pak už jen otázka času, kdy program správnou kombinaci hesla nalezne. Hesla podle existujících slov Druhým způsobem prolomení hesla může být kombinace předešlého postupu s použitím slov podle zadaného slovníku. V takovém případě zadáme programu cestu ke slovníku obsahující klíčová slova, která předpokládáme, že se v heslu mohou vyskytovat. Předpoklad může být postaven na znalosti osoby, která heslo vytvořila, nebo na znalosti četnosti slov používaných v heslech pro danou lokalitu. Takové slovníky samozřejmě existují a jsou dokonce i děleny podle zájmového zaměření. Je pak na místě předpokládat, že člověk zabývající se například myslivostí, bude mít v hesle obsaženo slovo právě z této oblasti. Jednou z největších chyb pak je použít v hesle křesní jméno, nebo ještě hůře jméno svého syna či dcery. Slovník jmen je při útocích „brute force“ využíván jako první a nutno říci, že ve velké míře s úspěchem. Za zmínku také stojí, že slovník nejpoužívanějších hesel obsahuje tak banální hesla jako jsou například: „heslo“, „superman“, „qwerty“ a nebo i „******“. Silná hesla Z výše uvedených zásadních chyb při vytváření hesel můžeme rekapitulovat, jak by tedy mělo správné heslo vypadat: -

délku volit v závislosti na požadované síle minimálně však osm znaků,

-

nevolit běžná slova, jména ani jinak lehce odvoditelná slova,

-

nevolit slova přímo spojená s pracovním místem, nebo osobou uživatele,

-

hesla nezapisovat ani neukládat na přístupných místech,

-

hesla skládat z kombinací čísel, malých a velkých písmen abecedy,

-

používat v heslech speciální znaky jako například #, @, ? apod.

Tato pravidla jsou většinou již řešena politikou jednotlivých systémů, ale někdy se jedná o pouhé doporučení. Pak je pouze na uživateli zda se jimi bude řídit. V případě, že slabým heslem ohrozí pouze svůj soukromý emailový účet, není slabší heslo takový problém, avšak například u administrátorských účtů může být toto jednání fatální. 47

4.1.3 Délka klíče V případě ochrany dat pomocí klíče je důležitým kritériem zvolení odpovídající délky klíče. Kratší klíč poskytuje snazší útok na jeho prolomení a naopak. Na klíče, které jsou použité v různých šifrovacích algoritmech se však útočí různými způsoby a proto nelze délku klíče stanovit direktivně správně pro všechny možné metody. [3] Například pro útoku na většinu symetrických klíčů je využívána metoda hrubé síly, kdy musí potenciální útočník otestovat všechny možné kombinace, z kterých je možné klíč sestavit. Ale v případě asymetrické šifry jako je RSA, musí útočník vypočítat rozklad čísla pomocí metody faktorizace velkých čísel. [3] Přístup k pokusu o prolomení šifry je tedy odlišný a proto i velikost klíče je doporučena jiná. „Vzhledem k tomu nemůžeme říci, že by třeba 112bitový algoritmus 3DES byl méně bezpečný než 512bitový RSA – protože útoky jsou proti nim vedené různým způsobem. V tomto konkrétním případě je možné 512bitový klíč RSA rozložit na prvočinitele rychleji, něž metodou hrubé síly prolomit heslo ze 12bitového prostoru klíčů algoritmu 3DES.“ 1 Proto je pro ochranu symetrických klíčů za pomoci asymetrických klíčů potřeba volit správnou délku klíče. Chybná délka jednoho z klíčů umožňuje prolomení toho druhého a naopak. Pro správné určení vzájemné velikosti klíče může sloužit tabulka viz tab. 4.1, která vychází z návrhu internetového standardu „Determining Strengths For Public Keys Used For Exchanging Symmetric Keys“. [3]

Tab. 4.1: Tabulka ekvivalentních velikostí klíčů (zdroj [3])

1

HOWARD, Michael a David LEBLANC. Bezpečný kód [3], str. 278

48

Z tabulky je možné vyčíst informaci, která například říká, že potřebujeme-li pomocí algoritmu RSA ochránit symetrický klíč o velikosti 80bitů, měl by mít příslušný RSA klíč délku alespoň 1228 bitů. V případě, že by byl RSA klíč menší, bylo by případný útok snazší vést právě na něj, neboť by jeho síla byla menší než síla 80bitového symetrického klíče. [3]

4.1.4 Náhodná čísla Většina aplikací pro své šifrování využívá náhodná čísla. Ta jsou použita například pro generování náhodných hesel, nebo šifrovacích klíčů. Správně zvolený šifrovací klíč je stěžejní pro celé šifrování. Vygenerovat náhodná čísla v něčem tak strukturovaném jako je počítač založený na dvojkové soustavě je relativně veliký problém. Lidské rozhodování je ovlivňováno mnoha okamžitými faktory, ale počítačové rozhodování má přísná pravidla. Pokud do nich nezasáhne nepředvídatelná událost, zachová se vždy na základě předvídatelného algoritmu. Vygenerovaná náhodná čísla mají proto často problém, že jsou předvídatelná. Rand Základním generátorem obsaženým v běžných knihovnách programovacích jazyků je generátor náhodných čísel na principu lineární kongruentní funkce. Při použití této funkce rand například v jazyce PHP dochází ke generování náhodných čísel tak, že každé nové číslo je generováno na základě toho předešlého. Pokud mluvíme o kvalitním generátoru náhodných čísel, měl by splňovat tyto základní kritéria: -

generovaná čísla jsou rovnoměrně rozdělena,

-

hodnoty nesmí být předvídatelná,

-

jeho cyklus je dostatečně dlouhý, nebo-li je schopen generovat ze svého oboru hodnot velké množství těchto náhodných hodnot. [3]

Běžné funkce rand však silně nevyhovují druhému bodu podmínky, tedy nepředvídatelnosti a proto se tyto funkce v kryptografii nedoporučuje používat. [3]

49

Jako důkaz tohoto tvrzení může sloužit jednoduchá ukázka skriptu viz obr. 4.1. Tento skript použil pro generování náhodných čísel stejnou výchozí hodnotu. V tomto případě se jedná o číslo 99999 tedy srand(99999).

Obr. 4.1: Ukázka použití funkce rand pro generování náhodných čísel (zdroj: vlastní úprava)

Dále pro ilustraci na obrazovku vypíše ve smyčce for tři hodnoty. Výstupem tohoto skriptu tedy budou tři číselné řady: -

59 64 47 97 42 72 20 11 80 32,

-

41 64 76 55 78 8 55 1 10 50,

-

37 26 89 21 21 49 3 88 6 18,

které se správně, podle očekávání, vzájemně liší, neboť jsou generovány generátorem náhodných čísel. Avšak spouštěním skriptu opakovaně zjistíme, že jsou generovány stále stejné řady. Jak je to ale možné, když se ony tři číselné řady liší? Není snad správný předpoklad, že bude jiná i ta čtvrtá, pátá a další? Ano je, ale jen pokud generátor náhodných čísel rand pracuje kontinuálně, tedy generuje každou další řadu z té předešlé. Opakovaným spouštěním skriptu však nastavujeme stejné počáteční podmínky pro generování a tak musí být výsledek vždy stejný. Chyby, které jsou způsobené přehlédnutím této skutečnosti, mohou být fatální. Jako jeden za všechny uveďme příklad, kdy jedna z prvních verzí internetového prohlížeče Netscape Navigator používala ke generování klíčů v protokolu SSL generátor náhodných čísel na principu lineární kongruentní funkce. To mělo za následek předvídatelnost vygenerovaných náhodných čísel čímž bylo celé SSL (Secure Sockets Layer) zabezpečení zbytečné. [3]

50

CryptGenRandom K vyřešení těchto rizik je proto nutné využívat kvalitnější generátory náhodných čísel. Jedním z nich může být například CryptGenRandom, který je obsažen ve všech platformách Windows. Tento generátor splňuje všechny tři zmíněné podmínky. Navíc tento generátor umožňuje zvyšovat entropii, tedy neuspořádanost, generovaných čísel vložením vlastního bufferu dat. Krom těchto výhod má konkrétně tento generátor ještě jednu formální. Splňuje totiž normu FIPS 140-1. [3] „Americká norma FIPS 140-1 (Federal Information Processing Standard) je prostředkem pro ověření kvality kryptografických produktů výrobce. Tato norma definuje standardní implementaci několika běžně používaných kryptografických algoritmů a dále popisuje postup, který posuzuje, jestli daný produkt implementuje algoritmy podle stanovených norem.“ 1 Splnění této normy je nezbytné v případě, že software využívající kryptografické algoritmy, bude prodáván federální vládě Spojených států. Funkce rand, uvedená v předešlé části této kapitoly, toto schválení nemá, naproti tomu novější funkce CryptGenRandom dodávaná v systémech Windows 2000 a novějších již ano. [3]

1

HOWARD, Michael a David LEBLANC. Bezpečný kód [3], str. 272

51

5.

Využití znalosti slabých stránek

5.1 Útoky proti šifrám Jak je z předešlých kapitol patrné, kryptografie je velmi komplikovaný a náročný obor, na který jsou kladeny velmi vysoké nároky. S nárůstem složitosti šifer však vzniká i prostor pro jejich případné chyby nebo slabiny a tím i pro příležitosti útoku na ně. Ne všechny útoky vždy směřují pouze na prolomení šifer a získání šifrovaného obsahu. Některé útoky jsou vedeny pouze za účelem poškodit šifrovaný obsah, což může být v některých případech ještě nebezpečnější. Znalostí způsobů jak na šifry útočit však získáváme určitou výhodu, protože se díky ní můžeme těmto kritickým slabinám lépe bránit.

5.1.1 Útoky se změnou bitů Tento útok se změnou bitů (bit-flipping attack) je aplikován na takzvané proudové šifry. Jedná o druh šifer, které ke svému šifrování i dešifrování využívají principu zpracování jedné jednotky po druhé. Jednotkou se v tomto případě nejčastěji rozumí bajt. [3] Tento typ útoku je umožněn právě proto, že při zpracování proudovým způsobem je nemožné odhalit, zda nebyla šifra v době mezi odesláním a přijmutím změněna. Riziko změny jednotlivých bitů šifry je pak ještě vyšší v případě, kdy je znám formát zprávy. Víme-li například, že zpráva nese v hlavičce časové razítko ve standardním formátu yyyy-mm-dd h:i:s je pak velmi snadné změnit určitý počet bajtů a ve zprávě tak datum pozměnit. [3] Tímto způsobem však dá útočit i například na zašifrované datové či konfigurační soubory programů. Pokud je tímto způsobem proveden útok na konfigurační soubor, který má být zabezpečen proti změnám ze strany uživatele, opakovanou změnou bajtů a následným vyhodnocením změn v běhu programu, lze velice úspěšně pozměnit běh programu v rozporu se záměry autora.

52

Obrana proti útokům se změnou bitů Jedním ze způsobů jak se bránit tomuto druhu útoku je využití hašovací funkce (hash). Tato funkce vytváří otisk vstupních dat o pevné velikosti. To znamená, že pomocí haše dokážeme vytvořit například 128 bitový otisk několikanásobně větších souborů. To se v kryptografii také s výhodou využívá například při podepisování, neboť je mnohem rychlejší pracovat s malým otiskem než s celým dokumentem o velikosti v řádech megabajtů. V našem případě však haš využijeme k tomu, abychom provedli otisk šifrované zprávy a tento otisk odeslali se zprávou. Díky tomu si pak může příjemce ověřit, že zpráva nebyla změněna, neboť jedna ze základních vlastností haše je, že otisk souboru je jedinečný. Pak tedy porovnáním otisku došlé zprávy a otisku přijatého lehce odhalíme případnou bitovou změnu dat. [1] Pokud se zamyslíme na popsaným principem, můžeme namítnout, že útočník dokáže zprávu změnit na bitové úrovni a vygenerovat nový haš, který ke zprávě připojí. Tato hrozba je opravdu reálná a řeší ji haš klíčový. [1] „Klíčovaný haš (keyed hash) je takový haš, který obsahuje nějaká tajná data, tedy data známá jen odesílateli a příjemci zprávy. Zpravidla jej vypočteme hašováním prostého textu, zřetězeného s nějakým tajným klíčem, nebo z informací odvozených od tohoto klíče. Bez znalosti klíče nemůžeme správný klíčovaný haš vypočítat.“ 1 Z definice je patrné, jakou výhodu klíčový haš oproti běžnému haši má. Jednoduše řečeno, pokud útočník nezná heslo, nedokáže vygenerovat nový haš a tak není schopen zprávu změnit, aniž by to nemohl příjemce odhalit.

5.1.2 Útoky hrubou silou V kapitole „Techniky bezpečného šifrování“ viz str. 44 bylo popsáno, jakým způsobem probíhají útoky hrubou silou. V případě útoků na přihlašovací údaje se jedná o útoky, které využívají možnosti opakovaných pokusů. Pokud tedy systém, který je napaden tímto způsobem útoku umožňuje nekonečný počet opakovaných pokusů, je velmi pravděpodobné, že takový systém tomuto útoku podlehne. V případě útoku na šifrovaná data, nebo šifrovanou komunikaci je princip podobný. Šifrovaná data se program snaží cyklicky dešifrovat se systematicky generovaným klíčem. 1

HOWARD, Michael a David LEBLANC. Bezpečný kód [3], str. 292

53

Obrana proti útokům hrubou silou Pokud se chceme bránit tomuto typu útoku v případě uživatelských účtů, je mnohdy obrana relativně jednoduchá. V každém případě je důležité dodržovat zásady bezpečných hesel tak jak bylo již dříve popsáno. V kombinaci se správnou bezpečnostní politikou systému se jedná o silný obranný mechanismus. Samotné silné heslo dokáže útok hrubou silou minimálně zdržet na tak dlouhou dobu, dokud nedojde ke změně hesla, neboť doba potřebná na prolomení hesla roste exponenciálně k síle hesla. Změna hesla v daných intervalech by přitom měla být součástí každé silnější bezpečnostní politiky. Je zřejmé, že změna hesla má pro uživatele efekt snížení uživatelského komfortu, ale v případě zabezpečení důležitých systému je toto omezení nezbytné. Dalším velice jednoduchým a přitom efektním způsobem, jak tomuto útoku čelit, je omezení lokality, ze které je uživatelům přihlášení umožněno. V některých případech to není možné, protože nelze přesně definovat lokality, které mají být pro přihlášení povoleny. To může být spojeno například s tím, že je do systému nutný přístup i z mobilních zařízení, která nemají pevná nastavení, ale jsou jim nastavení přidělována dynamicky. V některých případech však lze tento problém řešit přístupem přes zabezpečené VPN tunely, které simulují přístup z lokální sítě. Posledním jednoduchým způsobem jak ztížit útok hrubou silou na uživatelské účty je omezení počtu přihlášení. Taková omezení lze nastavovat podle různých úrovní zabezpečení od intervalů mezi chybným přihlášením až po zablokování účtu. Každopádně i omezení opakovaně chybného přihlášení v řádech desítek velice efektivně přispěje k odražení útoku cyklickým přihlašováním generovaných hesel. Každé takové opatření přispívá k bezpečnosti uživatelských účtů na úkor uživatelského komfortu a proto je nutné zvážit, jakou bezpečnostní politiku je třeba zvolit v závislosti na požadovaném zabezpečení. Výběr správné míry zabezpečení by měl být vyvážen s možnými riziky a s použitelností systému. Jinými slovy, dokonale zabezpečený systém, který je pro své bezpečnostní prvky obtížně použitelný, sice poskytuje vysokou míru bezpečnosti, avšak jeho praktická využitelnost bude minimální.

54

5.1.3 Četnost útoků proti šifrám Položme si nyní otázku, proč se útoky proti šifrám dějí a jaké můžeme do budoucna očekávat jejich četnosti. Jak již bylo mnohokrát řečeno, s vývojem výpočetní techniky roste i její využití a proto je i nárůst dat logickým důsledkem. Veliké množství dat, které je generováno různými systémy, se uchovává pouze pro potřeby případných incidentů. Takovými daty jsou například záznamy z bezpečnostních kamer, záznamy telefonních hovorů, logy systému a podobně. Přestože se většinou jedná o interní data, která je nutné chránit před přístupem třetích osob, není přímo nezbytné k tomu vynakládat veliké úsilí. Mnohdy je dostatečně silným zabezpečením pouhé zálohování na nosiče, které se uchovávají například ve firemním trezoru. U tohoto typu dat tedy nehrozí vysoké riziko zneužití, například při jejich odcizení po cestě z kanceláře do trezoru a hlavně je jejich zneužití jednorázové a většinou lehce dohledatelné, kdo za tuto hrozbu nese zodpovědnost. To je dáno například organizačním schématem společnosti. To ovšem neplatí u dat, která jsou například výsledkem generátoru klíčů a hesel. Tato data je nutné chránit maximálním způsobem, neboť jejich zneužití může mít fatální následky. Tato data umožňují přístup k dalším datům, jako jsou například citlivé údaje o zaměstnancích, klientech, bankovních účtech a jejich transakcích apod. Tato data jsou velmi cenná a proto také velmi žádaná. Cena těchto dat je vyčíslitelná a proto není divu, že se za jejich získání opravdu platí. Není zřejmě žádným tajemstvím, občas se takové zprávy objeví v mediích, že si některé státy platí počítačové experty, kteří mají za úkol útočit na bezpečnost systémů jiných států a získávat tajné informace. Slovní spojení kybernetická špionáž tak už není výhradou fantastických filmů, ale tvrdá realita. Dalším aspektem, který přispívá k vyššímu riziku útoků na šifry, je fakt, že je stále více počítačově gramotných lidí, kteří tyto útoky dokáží praktikovat. Obecně se útočníci dají rozdělit do několika skupin. Jedna skupina jsou počítačový nadšenci, kteří z dostupných zdrojů získají informace o slabinách nebo přímo chybách některých ze systémů a podle těchto informací popřípadě přímo návodů útoky provádějí. Tato skupina lidí je většinou motivována pouze svým nadšením realizovat se a je jen otázkou jak dokáží skutečně škodit. Těmto útokům se však dá relativně efektivně bránit tím, že administrátor systému pečlivě hlídá aktualizace daného systému, protože výrobce takového systému se snaží případné chyby co nejdříve opravovat. Druhou skupinou útočníků jsou lidé, kteří problematice opravdu rozumí

55

a dokáží chyby systému odhalit. Ti jsou pochopitelně mnohem nebezpečnější, neboť dokáží využít chyby dříve, než má výrobce systému možnost chybu opravit. Každý výrobce kryptografického systému by proto v ideálním případě měl mít několik takových „hackerů“, kteří se budou snažit systém prolomit a odhalovat tak možné slabiny. Velkým problémem je ovšem fakt, že žádné oficiální „hackerovské“ školy neexistují a specialisté v této oblasti vznikají tím, že své zkušenosti získávají pácháním nelegální činnosti. Odpověď na položenou otázku tedy zní: „Útoky na kryptografické systémy jsou motivovány snahou získat informační převahu a jejich četnost bude mít rostoucí trend.“

56

6

Kryptografické algoritmy a software

6.1 Příklady algoritmů a zdrojových kódů jednoduchých šifer 6.1.1 Caesarova šifra Caesarova šifra je jednou z prvních zaznamenaných šifer pocházející z doby téměř 100 př.n.l. a jedná se o velmi jednoduchou substituční šifru. Pro šifrování a dešifrování touto metodou stačilo mít napsanou abecedu a očíslovat si jednotlivé znaky s určitým posunem. Pak podle této jednoduché substituční tabulky přepisovat znak po znaku a vytvářet tak šifrovaný, resp. dešifrovaný text. Je pravděpodobné, že zkušený kryptograf dokázal takto jednoduchou šifru dešifrovat i bez použití této substituční tabulky velmi rychle. Na obrázku viz obr. 6.1 je uveden příklad, jak by mohl vypadat zdrojový kód v programovacím jazyku PHP, který používá ke svému šifrování Caesarovu šifru. Vstupem skriptu je otevřený text vložený do proměnné $veta_in a výstupem obsah proměnné $veta_out, který na konci skriptu vypisujeme příkazem print. Posun nechť je ten, jež se využíval obvykle, tedy $posun=3 a abeceda nechť je složena pouze ze znaků písmen bez diakritiky. Nyní skript ve smyčce for provádí jednoduchou substituci znak po znaku příkazem preg_match. Ukázkový skript řeší velká a malá písmena a zachovává mezery mezi slovy což je ale pouze estetická záležitost pro názornost. Ve skutečnosti se velká písmena zapisovala jako písmena malá a mezery včetně všech interpunkcí se vynechávaly. To vše s cílem co nejvíce zmást případného nežádoucího příjemce zprávy. Výsledkem ukázkového skriptu viz obr. 6.1 je řetězec znaků: „Whqwr vfulsw srxclyd n xnubwl whawx ylfh mdn gyd wlvlfh ohw vwdurx vliux, nwhurx srxclydo Jdlxv Mxolxv Fdhvdu!“

57

Pokud bychom provedli úpravy, které byly v době používání této šifry obvyklé, vypadal by náš výstupní řetězec takto: „whqwrvfulswsrxclydnxnubwlwhawxylfhmdngydwlvlfhohwvwdurxvliuxnwhurxsrxclydojdlx vmxolxvfdhvdu“. Přestože je opticky výsledná šifra vždy jiná, pro prolomení tento aspekt není vůbec rozhodující, neboť struktura výstupu zůstává neměnná. To dokládá dříve uvedené tvrzení, že změna posunu z obvyklých 3 na libovolně jiné číslo, nedělá šifru v žádném ohledu silnější.

Obr. 6.1: Příklad zdrojového kódu pro šifrování Caesarovou šifrou se substitučním posunem 3 znaky (zdroj: vlastní úprava) 1 1

Skript viz obr. 6.1 je k dispozici na adrese http://skola.rwm.cz/bivs/caesar.php, kde je možné měnit parametrem v adrese substituční posun znaků

58

6.1.2 Šifrování podle konverzní tabulky I v tomto případě je základním principem šifrování jednoduchá substituce znaků, avšak oproti substituci s pevným posunem je zde k určení zástupného znaku využívána konverzní tabulka. Výsledný šifrovaný text má z optického hlediska velmi podobnou strukturu jako šifra Caesarova, nicméně prolomení takové šifry je podstatně složitější. Nyní nestačí pouhé vyzkoušení posunu o jeden až n znaků, ale je nutné odvodit celou konverzní tabulku. Ta může být libovolně zamíchaná, čímž zvyšuje sílu šifry. Opět je třeba brát na zřetel, že tento typ šifry je pro dnešní dobu naprosto nedostačující, ale v době jejího vzniku poskytovala relativně vysokou míru bezpečnosti. Skript pro šifrování podle konverzní tabulky Jako názorný příklad skriptu, který šifruje podle konverzní tabulky se vrátíme k Voynichově kódu. Jedna z teorií, která hovoří o rozluštění této šifry, vychází z toho, že se jedná o substituční metodu znaků, která v šifrovaném textu vynechává samohlásky. Autorem této teorie z roku 1978 je John Stojko, který přišel s tvrzením, že je text psán starou ukrajinštinou za použití umělé abecedy. [4] Tato pravděpodobně chybná teorie, poskytne dobrou příležitost pro vytvoření skriptu, který bude provádět substituci znaků podle konverzní tabulky. Na obrázku viz obr. 6.2 je ukázka jednoduchého skriptu, který zpracovává přepis textu strany 25r z původní knihy Voynichova rukopisu1, do formátu FGS. Prakticky probíhá přepis tak, že se podle zvolené konverzní tabulky přepisuje z původní knihy umělý znak po znaku do textového souboru. Mluvíme-li však o původní knize, nemáme na mysli originál, který je uložen v knihovně vzácných tisků a rukopisů na Yaleské univerzitě ve Spojených státech, ale o její digitální podobě.2 Formát FGS volíme proto, že se jedná o jeden z nejčastěji používaných formátů používaný kryptografy Voynichova kódu k dalšímu počítačovému zpracování. Nespornou výhodou tohoto formátu pro přepis je také fakt, že využívá podobnosti znaků a je tím pádem velmi dobře pro přepisovatele zapamatovatelný. Například znak podle tohoto formátu přepisuje jako „A“, znak

jako „8“,

se

jako „R“ a podobně. Někdo by

mohl namítnout, že by bylo jednodušší pro přepis využít některý z OCR systémů, tedy systém optického rozpoznávání znaků (Optical Character Recognition). V tomto případě by však tato metoda selhávala a vykazovala vysokou chybovost, protože jsou pravděpodobně při psaní 1

LENKOVÁ, Jitka. Voynichův rukopis [4] str. 25r

2

LENKOVÁ, Jitka. Voynichův rukopis [4] str. 1v – 116r

59

Voynichova rukopisu použity různé rukopisy. Mnohdy je i při jejich detailním pozorování problém některé znaky od sebe rozeznat. Ukázka textu tohoto umělého písma byla již ilustrována viz obr. 1.1 str. 10. Do skriptu viz obr. 6.2 vstupuje text ve formátu FGS v proměnné $voy_veta a je dále zpracováván substitučními funkcemi preg_replace. V prvním kroku dochází k převodu do formátu Currier, což je vlastně pouze zjednodušená forma formátu FGS, která je v některých případech výhodnější pro další počítačové zpracování.

Obr. 6.2: Příklad zdrojového kódu pro šifrování dle konverzní tabulky (zdroj: vlastní úprava) 1

1

Skript viz obr. 6.2 je k dispozici na adrese http://skola.rwm.cz/bivs/voynichkonv.php

60

Ve druhém kroku dochází k převodu Currier formátu do html tagů kvůli zpětné kontrole, zda přepis opticky odpovídá originálu viz obr. 6.3. K tomuto kroku bylo nezbytné nejprve vytvořit obrázky celé znakové sady tohoto rukopisu.

Obr. 6.3: Převod přepisu textu Voynichova rukopisu do tagů html (zdroj: vlastní úprava)

V posledním kroku dochází k převodu substitučními funkcemi preg_replace formátu Currier, tentokrát do formátu podle Johna Stojka. Je samozřejmě nutné brát tuto ukázku s rezervou, neboť se jedná o přepis azbuky do latinky. Nicméně i tak nevykazuje výsledný převod přesvědčivé výsledky což pro účely této práce není důležité. cpvlkc rvpc kbžj ptc pvkc kbžj vpvlkc hščhvlkc rc votovr pvr prtc pvotopc pbzr švk pv pc tpc ptbž švotopc švotopc phhrhhr phhbr r pbž kbžj pbž kbž kpptc pvpitic cotophc pitivr r pbj pbžj švotopbž švotophbžj kpbž pitibž kbžj kbžj pitibž švotobžj vtbl pvotobžj kbzr votobzzr votovrc Skript na prolomení šifry podle konverzní tabulky Skript viz obr. 6.4 je pravým opakem předešlého příkladu. Velmi jednoduchým způsobem se snaží o prolomení substituční šifry metodou hrubé síly. Tato metoda pracuje na principu opakovaných pokusů s postupně vytvářenými kombinacemi. V případě útoků na hesla uživatelských účtů se generují hesla, kterými se program snaží přihlašovat, dokud nenalezne heslo správné. V případě pokusu o prolomení substituční šifru bude skript generovat všechny možné kombinace substitučních tabulek, které bude aplikovat na zašifrovaný text tak dlouho, dokud nenalezne některá existující slova. Informaci zda se jedná o existující slovo získá ze slovníku, který může být uložen v databázi.

61

Část skriptu, která generuje všechny možné kombinace, je pro její rozsáhlost vynechána stejně jako i načítání slovníku do pole, které není pro ukázku podstatné.

Obr. 6.4: Příklad zdrojového kódu pro prolomení substituční šifry (zdroj: vlastní úprava) 1

Do skriptu vstupuje šifrovaný text v proměnné $zasifrovane_slovo, který je dále zpracováván ve smyčce for o počtu tolika cyklů, kolik je vygenerováno variant konverzních tabulek. Při 26-ti znacích abecedy se bude jednat o fact(26) kombinací tedy o 403291461126605635584000000 cyklů. Z toho čísla je zřejmé, že tento typ útoku vyžaduje relativně hodně výpočetního výkonu, neboť samotné vygenerování takovéhoto počtu substitučních tabulek bude náročné. Podstatné snížení náročnosti výpočtů můžeme provést tím, že dešifrujeme jen malou část šifrovaného textu a generujeme substituční tabulky jen se znaky, vyskytujícími se právě v tomto výběru.

1

Skript viz obr. 6.4 je k dispozici na adrese http://skola.rwm.cz/bivs/konvtab.php

62

Například při pokusu o prolomení vzorového textu v proměnné $zasifrovane_slovo tedy budeme pracovat jen s 11-ti jedinečnými znaky, což ve výsledku znamená o fact(26 - 11) tedy o 1307674368000 méně cyklů. Je tedy nanejvýš důležité volit v těchto procesech správné výběry a postupy. V této smyčce probíhají dva základní procesy: -

převod šifrovaného textu podle vygenerované konverzní tabulky,

-

porovnání převedeného textu podle slovníku.

Slovník je v naší ukázce prezentován malým polem obsahujícím několik vybraných slov. To je také druhý způsob jak dramaticky snížit náročnost výpočtů při běhu takovéhoto skriptu. Je samozřejmě rozdíl, zda ve vnořené smyčce for pracujeme se slovníkem o obsahu stovek slov nebo jen s jeho malým výběrem, o kterém předpokládáme, že by měl být některý z jeho prvků v šifrovaném textu obsažen. V ideálním případě použijeme jen slova o počtu znaků, odpovídající počtu šifrovaného slova. To však lze jen za předpokladu, máme-li informaci o tom, že šifrovaný text skutečně obsahuje pouze jedno slovo. V případě, že skript převede podle některé z vygenerovaných konverzních tabulek šifrovaný text na slovo, které nalezne ve slovníku, vypíše zprávu o nalezeném výsledku.

6.2 Příklady algoritmů v šifrovacím softwaru V současné době je již na trhu velké množství softwaru, které se zaměřuje na šifrování citlivých dat. Tyto programy využívají různé šifrovací algoritmy, nebo jejich kombinace, které pak operují v kaskádě. Pro ilustraci a další rozbor bude použit software TrueCrypt. [16] Jedná se o takzvaný otevřený software (open-source), který je k dispozici zdarma a to pro platformy Windows, Mac OS X i Linux. Jeho další výhodou je velký výběr šifrovacích algoritmů, který je možné volit podle charakteristiky použití. Při požadavku vysoké bezpečnosti jsou k dispozici až tři kaskádově operující algoritmy a naopak je možné při potřebě rychlého šifrování volit šifrovací algoritmy samostatné.

63

6.2.1 Šifrovací algoritmus AES (Rijndael) Jméno této šifry je složeninou počátečních písmen celého názvu „Advanced Encryption Standard“. Jedná se o algoritmus, který vzešel z veřejné soutěže v roce 1997, jež si kladla za cíl nalézt nový algoritmus, který by nahradit šifrovací algoritmus DES. Ten byl totiž v té době již velmi kritizován za reálnou možnost jeho prolomení. To se také potvrdilo v roce 1998 vytvořením programu, který tuto šifru za použití 56 bitového klíče dokázal dešifrovat za dobu přibližně šedesáti hodin. Vítězem této soutěže a tedy i nositelem nového jména AES se stal algoritmus Rijndael od tvůrců Joana Deamena a Vincenta Rijmena. Mezi největší výhody AES patří rychlost a jednoduchá implementace v softwarovém i hardwarovém prostředí. Odhadovaná životnost tohoto algoritmu je přibližně 30 let. [1]

6.2.2 Šifrovací algoritmus Serpent Tento algoritmus zveřejněný v roce 1998 umožňuje šifrovat pomocí klíče o délce až 256 bitů, přičemž může být klíč volen libovolně. Z hlediska výpočtů se tato šifra řadí mezi náročnější a proto je při softwarovém použití pomalejší. Její praktické využití se hodí spíše pro hardwarové šifrování. [1]

6.2.3 Šifrovací algoritmus Twofish Šifra publikovaná v roce 1998 využívající klíč o délce až 256 bitů. Opět se jedná o výpočetně náročnější šifru, která je vhodná spíše pro hardwarové nasazení. [16] Úroveň bezpečnosti lze jen těžko posoudit, protože je její návrh velmi komplikovaný a nelze tedy tento algoritmus objektivně porovnávat s dalšími ze stejných pohledů. [1]

6.3 Porovnaní metod šifrování z pohledu rychlosti Rychlost algoritmů je hned po bezpečnosti jednou z nejdůležitějších vlastností. Jednoduchou logikou lze usoudit, že čím je šifra náročnější na výpočetní výkon, tím bude náročnější i její dešifrování, ale také i případné prolomení. V některých případech je však rychlost algoritmu upřednostněna na úkor bezpečnosti a to především tam, kde se šifruje velký objem dat, nebo šifrování probíhá v reálném čase.

64

Příkladem může být šifrovaná hlasová komunikace, kde pomalejší šifrovací algoritmus způsobí zpoždění přenášených dat. V takovém případě i zpoždění řádově v milisekundách může být velkým problémem a proto je nutné volit vhodné šifrovací algoritmy. Pro porovnání byl proveden rozbor výše popsaných algoritmů z pohledu rychlosti šifrování a dešifrování. K získání údajů o jejich reálné rychlosti byl použit nástroj „test rychlosti“, který je implementován v programu TrueCrypt.1 Testování může probíhat na testovacím souboru o zvolené velikosti 100KB až 1GB. S velikostí souboru roste přesnost měření, ale také i časová náročnost. Pro účely této práce byla zvolena velikost souboru 100MB. Výsledkem měření jsou hodnoty uvedené v tabulce viz obr. 6.5, které vyjadřují, kolik MB dat bylo zašifrováno, resp. dešifrováno za sekundu.

Obr. 6.5: Porovnání šifrovacích algoritmů z pohledu rychlosti, množství zašifrovaných, resp. dešifrovaných dat v jednotkách MB/s (zdroj: vlastní úprava)

Nejrychlejším z porovnávaných algoritmů je s velikým náskokem šifrovací algoritmus AES. Jeho průměrná hodnota dosáhla stejných hodnot jak pro šifrování, tak i pro dešifrování. V případě algoritmu Serpent je rozdíl mezi šifrováním a dešifrováním cca 3% a u Twofish dokonce 8%. Tato nesymetrie je však pro rozhodování o použití šifrovacích algoritmů zanedbatelná, pouze lze z této skutečnosti odvodit závěr, že proces šifrování a dešifrování zřejmě probíhá odlišným způsobem.

1

Program TrueCrypt je dostupný na adrese http://www.truecrypt.org [16]

65

Zajímavější výsledky poskytuje měření algoritmů v jejich vzájemných kombinacích. Ať už se jedná o kombinaci dvou nebo tří šifer, operují v kaskádě. [16] To znamená, že je na šifrovaná data aplikován nejprve jeden šifrovací algoritmus a teprve po té se data šifrují druhým, resp. dalším šifrovacím algoritmem. Každý z nich využívá svůj vlastní klíč, přičemž jsou tyto klíče na sobě nezávislé.

Obr. 6.6: Porovnání kombinací šifrovacích algoritmů z pohledu rychlosti, množství zašifrovaných, resp. dešifrovaných dat v jednotkách MB/s (zdroj: vlastní úprava)

Z grafu a tabulky viz obr. 6.6 je patrné, že kombinace dvou šifrovacích algoritmů, konkrétně AES-Twofish, je jen zanedbatelně pomalejší než, samotný algoritmus Twofish. To je dáno tím, že šifrování algoritmem AES je nepoměrně rychlejší, než šifrování algoritmem Twofish. Proto je použití jejich kombinace velice výhodné. Ze stejného důvodu jsou minimální rozdíly i mezi kombinacemi Serpent-Twofish a Serpent-Twofish-AES. Přidáním třetího šifrovacího algoritmu AES tak může být pouze pozitivem ke zvýšení bezpečnosti šifrovaných dat. Z hodnot v tabulkách viz obr. 6.5 a obr. 6.6 je tedy možné na základě požadovaného zabezpečení a rychlosti šifrování snadno rozhodnout, jaký šifrovací algoritmus nebo jejich kombinaci zvolit. Tyto testy byly prováděny v paměti RAM a nebyly proto ovlivněny rychlostí média, na které by byla data v reálném případě zapisována, resp., z kterého by byla data čtena. Proto je vhodné před vlastní volbou šifrovacího algoritmu nejprve získat informace o tom, jakou rychlostí bude technicky možné s daty nakládat.

66

Závěr V této práci se autor zabýval kryptografií od svého vzniku až po dnešní moderní metody za použití výpočetního výkonu počítačů. Kryptografie má velmi bohatou historii, protože zaujímá důležité místo ve strategii lidského přežití. Je součástí evoluce člověka od doby, kdy byl schopen uchovat informaci a cítil potřebu tuto informaci ochránit před ostatními. Hlavním principem evoluce je, že přežijí jen ti nejsilnější, k čemuž kryptografie ve smyslu tohoto pojetí jistě přispěla. Účelem této práce nebylo vytvořit dějepisné dílo, ale ukázat podstatu kryptografie a zamyslet se nad důvody jejího vzniku. Také proto se úvodní kapitoly zabývaly historií šifrování jen velmi málo a cílily svoji pozornost především na její základní principy. Pro přiblížení těchto základních principů byly pro účely této práce vytvořeny názorné příklady, za jejichž pomoci je možné v praxi vidět původní šifry, tak jak byly používány stovky let před naším letopočtem. Na těchto příkladech je patrné, že odhalením a pochopením principů, kterých tyto šifry využívají, se tyto metody šifrování stávaly velmi zranitelné, což vedlo k jejich neustálému zdokonalování a zesložiťování. Tím chtěl autor ukázat, jakým směrem se kryptografie od svého vzniku ubírala a jakým směrem se bude zřejmě muset dále ubírat. Autor je přesvědčen, že v době kde je výpočetní technika založena na dvou logických hodnotách, tedy true a false, bude stále složitější vymyslet takový algoritmus, který se stane absolutně neprolomitelný. Dokonce si odvažuje tvrdit, že pokud nebude výpočetní technika pracovat na jiném než dvojkovém principu, nebude takový algoritmus existovat nikdy. Jinými slovy řečeno, bude vždy reálná šance, že bude v budoucnu taková šifra prolomena. To, že již v minulosti bylo prolomeno mnoho „neprolomitelných“ šifer, bylo uvedeno na konkrétních příkladech a je tedy na základě této zkušenosti troufalé o kterékoli šifře tvrdit, že je neprolomitelná. Jedním ze způsobů jak vytvořit, netvrďme tedy „neprolomitelnou“, ale řekněme raději „v dnešní době těžko prolomitelnou“, šifru, je použití faktorizace velkých čísel. Této metodě se práce věnovala v kapitole „Faktorizace velkých čísel“, kde bylo uvedeno několik jednodušších principů faktorizace a její uplatnění v kryptografii. Autor ukázal na konkrétních příkladech výsledky faktorizace za pomoci funkčního skriptu, který využívá jednu z nejjednodušších metod. Na zdrojovém kódu skriptu mohl čtenář detailně rozpoznat procesy, které se při činnosti tohoto algoritmu dějí. Zmínil se také o jedné z nejzákladnější vlastnosti

67

faktorizace, která umožňuje její využití v kryptografii, tedy o časové náročnosti. Na závěr těchto kapitol se autor zamýšlel nad budoucím významem této metody pro kryptografii. Dále se tato práce věnovala konkrétním kryptografickým algoritmům a softwarům, které tyto kryptografické systémy využívají. Tentokrát se ale zaměřila na konkrétní procesy, které v nich probíhají, což bylo opět demonstrováno na autorových vlastních funkčních skriptech. Protože bylo jedním z cílů této práce poukázat na možné chyby vedoucí k bezpečnostním incidentům, uvedl v této kapitole také ukázkový skript, kterým předvedl, jak snadné může prolomení jedné z nejjednodušších šifer být. Účelem v žádném případě nebylo poskytovat návod jak provádět útoky na jednoduché šifry, ale poukázat na hrozby, které slabé šifrování přináší. V této části práce byly také uvedeny nejznámější šifrovací algoritmy používané v softwarech pro ochranu dat před přístupem třetích osob. Pomocí zvoleného software byly tyto algoritmy porovnány z pohledu rychlosti šifrování, resp. dešifrování a z těchto měření pak odvozeny závěry. Tato práce si kladla za hlavní cíl přiblížit základní principy kryptografie tak, aby si čtenář pochopením těchto principů uvědomil možná rizika plynoucí z užití kryptografie, ať už se jedná o šifrovanou komunikaci, nebo uchovávání informací. Vývoj kryptografie se do dnešního dne nezastavil a zřejmě ani nikdy nezastaví, a tak výčet možných chyb, které mohou v těchto souvislostech nastat, by byl podle názoru autora nesmyslný. Proto vidí uvědomění si možných úskalí kryptografie jako jedinou cestu k tomu, jak těmto chybám s možnými fatálními následky předcházet. Z této práce by si měl čtenář odnést dojem, že kryptografie není všemocná, ale že je pouhým nástrojem, jak dojít ke svému cíli, tedy k účinné ochraně svých dat a informací.

68

Seznam použité literatury Tištěné publikace [1]

BITTO, Ondřej. Šifrování a biometrika aneb tajemné bity a dotyky. Vyd. 1. Kralice na Hané: Computer Media, 2005, 168 s. ISBN 80-866-8648-5.

[2]

GROŠEK, Otokar a Štefan PORUBSKÝ. Šifrovanie: Algoritmy, metódy, prax. Praha: Grada, 1992, 268 s. ISBN 80-854-2462-2.

[3]

HOWARD, Michael a David LEBLANC. Bezpečný kód: [techniky a strategie tvorby bezpečných webových aplikací]. Vyd. 1. Brno: Computer Press, 2008, 895 s. ISBN 97880-251-2050-7.

[4]

LENKOVÁ, Jitka. Voynichův rukopis, aneb, Nejzáhadnější kniha světa: faksimile Voynichova rukopisu, vycházející při příležitosti 100. výročí jeho objevení W.M. Voynichem. Bratislava: CAD Press, c2012, 176, 116v, 116r s. Enigma. ISBN 978-8088969-600.

Internetové zdroje [5]

Asymptotická složitost. In: Wikipedie: Otevřená encyklopedie [online]. 2013 [cit. 2013-03-19]. Dostupné z: http://cs.wikipedia.org/wiki/Asymptotická složitost

[6]

Enigmu jsme tenkrát rozluštili my, tvrdí Polsko a chystá rezoluci. In: idnes.cz [online]. 2012 [cit. 2013-02-21]. Dostupné z: http://zpravy.idnes.cz/kdo-rozlustil-sifru-ze-strojeenigma-dsx-/zahranicni.aspx?c=A121009_113722_zahranicni_im

[7]

German Patents: DE383594 / 12 February 1922. In: cryptomuseum.com [online]. 6.8.2012 [cit. 2013-02-21]. Dostupné z: http://www.cryptomuseum.com/crypto/enigma/patents/files/DE383594.pdf

[8]

JEDLIČKA, Přemysl. Faktorizace velkých čísel: Kapitola z připravované knihy. In: Česká zemědělská univerzita v Praze: Technická fakulta [online]. 2012 [cit. 2013-03-22]. Dostupné z: http://tf.czu.cz/~jedlickap/a/faktorizace.pdf

69

[9]

Matematický symbol: Kongruence. In: Wikipedia: Otevřená encyklopedie [online]. 2013 [cit. 2013-03-22]. Dostupné z: http://cs.wikipedia.org/wiki/Matematický_symbol

[10] MIČKA, Pavel. Faktorizace: Kód. In: Algoritmy.net: příručka vývojáře [online]. 2011 [cit. 2013-03-18]. Dostupné z: http://www.algoritmy.net/article/111/Faktorizace [11] Mooreův zákon. In: Wikipedie: Otevřená encyklopedie [online]. 2013 [cit. 2013-04-08]. Dostupné z: http://cs.wikipedia.org/wiki/Mooreův_zákon [12] Navajo Code Talkers' Dictionary. In: History.navy.mil [online]. 2012 [cit. 2013-02-21]. Dostupné z: http://www.history.navy.mil/faqs/faq61-4.htm [13] Pollard's rho algorithm. In: Wikipedia: Otevřená encyklopedie [online]. 2013 [cit. 2013-03-25]. Dostupné z: http://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm [14] RSA kryptografie veřejného klíče. In: Matematická sekce Matematicko-fyzikální fakulta Univerzita Karlova v Praze [online]. 2001 [cit. 2013-03-22]. Dostupné z: http://www.karlin.mff.cuni.cz/~holub/soubory/qc/node23.html [15] Telegram Zimmermanna, czyli jak Niemcy sprowokowali USA do wypowiedzenia im wojny. In: histmag.org [online]. 2012 [cit. 2013-02-21]. Dostupné z: http://histmag.org/Telegram-Zimmermanna-czyli-jak-Niemcy-sprowokowali-USA-dowypowiedzenia-im-wojny-6282 [16] TrueCrypt: Downloads. TrueCrypt: free open-source on-the-fly encryption [online]. 2013 [cit. 2013-04-03]. Dostupné z: http://www.truecrypt.org

70

Příloha č. 1 Kompletního znění Zimmermannova telegramu

1

Příloha č. 2 Řada prvních 1229 prvočísel 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557 563 569 571 577 587 593 599 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691 701 709 719 727 733 739 743 751 757 761 769 773 787 797 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887 907 911 919 929 937 941 947 953 967 971 977 983 991 997 1009 1013 1019 1021 1031 1033 1039 1049 1051 1061 1063 1069 1087 1091 1093 1097 1103 1109 1117 1123 1129 1151 1153 1163 1171 1181 1187 1193 1201 1213 1217 1223 1229 1231 1237 1249 1259 1277 1279 1283 1289 1291 1297 1301 1303 1307 1319 1321 1327 1361 1367 1373 1381 1399 1409 1423 1427 1429 1433 1439 1447 1451 1453 1459 1471 1481 1483 1487 1489 1493 1499 1511 1523 1531 1543 1549 1553 1559 1567 1571 1579 1583 1597 1601 1607 1609 1613 1619 1621 1627 1637 1657 1663 1667 1669 1693 1697 1699 1709 1721 1723 1733 1741 1747 1753 1759 1777 1783 1787 1789 1801 1811 1823 1831 1847 1861 1867 1871 1873 1877 1879 1889 1901 1907 1913 1931 1933 1949 1951 1973 1979 1987 1993 1997 1999 2003 2011 2017 2027 2029 2039 2053 2063 2069 2081 2083 2087 2089 2099 2111 2113 2129 2131 2137 2141 2143 2153 2161 2179 2203 2207 2213 2221 2237 2239 2243 2251 2267 2269 2273 2281 2287 2293 2297 2309 2311 2333 2339 2341 2347 2351 2357 2371 2377 2381 2383 2389 2393 2399 2411 2417 2423 2437 2441 2447 2459 2467 2473 2477 2503 2521 2531 2539 2543 2549 2551 2557 2579 2591 2593 2609 2617 2621 2633 2647 2657 2659 2663 2671 2677 2683 2687 2689 2693 2699 2707 2711 2713 2719 2729 2731 2741 2749 2753 2767 2777 2789 2791 2797 2801 2803 2819 2833 2837 2843 2851 2857 2861 2879 2887 2897 2903 2909 2917 2927 2939 2953 2957 2963 2969 2971 2999 3001 3011 3019 3023 3037 3041 3049 3061 3067 3079 3083 3089 3109 3119 3121 3137 3163 3167 3169 3181 3187 3191 3203 3209 3217 3221 3229 3251 3253 3257 3259 3271 3299 3301 3307 3313 3319 3323 3329 3331 3343 3347 3359 3361 3371 3373 3389 3391 3407 3413 3433 3449 3457 3461 3463 3467 3469 3491 3499 3511 3517 3527 3529 3533 3539 3541 3547 3557 3559 3571 3581 3583 3593 3607 3613 3617 3623 3631 3637 3643 3659 3671 3673 3677 3691 3697 3701 3709 3719 3727 3733 3739 3761 3767 3769 3779 3793 3797 3803 3821 3823 3833 3847 3851 3853 3863 3877 3881 3889 3907 3911 3917 3919 3923 3929 3931 3943 3947 3967 3989 4001 4003 4007 4013 4019 4021 4027 4049 4051 4057 4073 4079 4091 4093 4099 4111 4127 4129 4133 4139 4153 4157 4159 4177 4201 4211 4217 4219 4229 4231 4241 4243 4253 4259 4261 4271 4273 4283 4289 4297 4327 4337 4339 4349 4357 4363 4373 4391 4397 4409 4421 4423 4441 4447 4451 4457 4463 4481 4483 4493 4507 4513 4517 4519 4523 4547 4549 4561 4567 4583 4591 4597 4603 4621 4637 4639 4643 4649 4651 4657 4663 4673 4679 4691 4703 4721 4723 4729 4733 4751 4759 4783 4787 4789 4793 4799 4801 4813 4817 4831 4861 4871 4877 4889 4903 4909 4919 4931 4933 4937 4943 4951 4957 4967 4969 4973 4987 4993 4999 5003 5009 5011 5021 5023 5039 5051 5059 5077 5081 5087 5099 5101 5107 5113 5119 5147 5153 5167 5171 5179 5189 5197 5209 5227 5231 5233 5237 5261 5273 5279 5281 5297 5303 5309 5323 5333 5347 5351 5381 5387 5393 5399 5407 5413 5417 5419 5431 5437 5441 5443 5449 5471 5477 5479 5483 5501 5503 5507 5519 5521 5527 5531 5557 5563 5569 5573 5581 5591 5623 5639 5641 5647 5651 5653 5657 5659 5669 5683 5689 5693 5701 5711 5717 5737 5741 5743 5749 5779 5783 5791 5801 5807 5813 5821 5827 5839 5843 5849 5851 5857 5861 5867 5869 5879 5881 5897 5903 5923 5927 5939 5953 5981 5987 6007 6011 6029 6037 6043 6047 6053 6067 6073 6079 6089 6091 6101 6113 6121 6131 6133 6143 6151 6163 6173 6197 6199 6203 6211 6217 6221 6229 6247 6257 6263 6269 6271 6277 6287 6299 6301 6311 6317 6323 6329 6337 6343 6353 6359 6361 6367 6373 6379 6389 6397 6421 6427 6449 6451 6469 6473 6481 6491 6521 6529 6547 6551 6553 6563 6569 6571 6577 6581 6599 6607 6619 6637 6653 6659 6661 6673 6679 6689 6691 6701 6703 6709 6719 6733 6737 6761 6763 6779 6781 6791 6793 6803 6823 6827 6829 6833 6841 6857 6863 6869 6871 6883 6899 6907 6911 6917 6947 6949 6959 6961 6967 6971 6977 6983 6991 6997 7001 7013 7019 7027 7039 7043 7057 7069 7079 7103 7109 7121 7127 7129 7151 7159 7177 7187 7193 7207 7211 7213 7219 7229 7237 7243 7247 7253 7283 7297 7307 7309 7321 7331 7333 7349 7351 7369 7393 7411 7417 7433 7451 7457 7459 7477 7481 7487 7489 7499 7507 7517 7523 7529 7537 7541 7547 7549 7559 7561 7573 7577 7583 7589 7591 7603 7607 7621 7639 7643 7649 7669 7673 7681 7687 7691 7699 7703 7717 7723 7727 7741 7753 7757 7759 7789 7793 7817 7823 7829 7841 7853 7867 7873 7877 7879 7883 7901 7907 7919 7927 7933 7937 7949 7951 7963 7993 8009 8011 8017 8039 8053 8059 8069 8081 8087 8089 8093 8101 8111 8117 8123 8147 8161 8167 8171 8179 8191 8209 8219 8221 8231 8233 8237 8243 8263 8269 8273 8287 8291 8293 8297 8311 8317 8329 8353 8363 8369 8377 8387 8389 8419 8423 8429 8431 8443 8447 8461 8467 8501 8513 8521 8527 8537 8539 8543 8563 8573 8581 8597 8599 8609 8623 8627 8629 8641 8647 8663 8669 8677 8681 8689 8693 8699 8707 8713 8719 8731 8737 8741 8747 8753 8761 8779 8783 8803 8807 8819 8821 8831 8837 8839 8849 8861 8863 8867 8887 8893 8923 8929 8933 8941 8951 8963 8969 8971 8999 9001 9007 9011 9013 9029 9041 9043 9049 9059 9067 9091 9103 9109 9127 9133 9137 9151 9157 9161 9173 9181 9187 9199 9203 9209 9221 9227 9239 9241 9257 9277 9281 9283 9293 9311 9319 9323 9337 9341 9343 9349 9371 9377 9391 9397 9403 9413 9419 9421 9431 9433 9437 9439 9461 9463 9467 9473 9479 9491 9497 9511 9521 9533 9539 9547 9551 9587 9601 9613 9619 9623 9629 9631 9643 9649 9661 9677 9679 9689 9697 9719 9721 9733 9739 9743 9749 9767 9769 9781 9787 9791 9803 9811 9817 9829 9833 9839 9851 9857 9859 9871 9883 9887 9901 9907 9923 9929 9931 9941 9949 9967 9973

1