MASARYKOVA UNIVERZITA V BRNĚ PEDAGOGICKÁ FAKULTA KATEDRA MATEMATIKY
Šifrování a teorie čísel Bakalářská práce
Brno 2015
Vedoucí bakalářské práce: RNDr. Karel Lepka, Dr
Vypracovala: Petra Kejíková
Anotace Bakalářská práce se zabývá šifrováním a matematickými teoriemi s tím spojenými. Cílem je nastínit, jaké metody šifrování se používají k ochraně dat v současnosti, ale jaké se používaly i v minulosti. V práci lze nalézt několik tisíc let staré šifry v podobě písma až po šifry vzniklé díky informačním technologiím. Jedna z kapitol je zaměřena na šifrovací metodu RSA, která je považována za jednu z nejbezpečnějších a nejsložitějších metod, přičemž je využívána k ochraně dat v bankách, ale i v armádě, kdy je používán veřejný RSA klíč o délce 1024 bitů.
Annotation The bachelor thesis deals with encryption and mathematical theories, related with encryption. The aim of the thesis is to outline which encryption methods are currently used for data protection and what methods were used in the past. Several thousand years old ciphers in the form of scripts and ciphers formed by information technologies can be found in this study. One of the chapters is dealing with RSA encryption method, that is considered by one of the safest and the most complex method, which is used by banks and military for the data protection. For example banks uses public RSA key length of 1024 bits.
Klíčová slova Kryptologie, kryptografie, šifra, teorie čísel, kongruence, permutace, veřejný klíč, metoda RSA, kódování
Key words Cryptology, Cryptography, cipher, number theory, congruency, permutation, public key, method RSA, coding
Bibliografický záznam Kejíková Petra. Šifrování a teorie čísel. Brno: Masarykova univerzita, Fakulta pedagogická, Katedra matematiky, 2015. Bakalářská práce. 50 s. Vedoucí práce RNDr. Karel Lepka, Dr.
Prohlášení Prohlašuji, že jsem závěrečnou bakalářskou práci vypracovala samostatně, s využitím pouze citovaných literárních pramenů, dalších informací a zdrojů v souladu s Disciplinárním řádem pro studenty Pedagogické fakulty Masarykovy univerzity a se zákonem č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon), ve znění pozdějších předpisů.
V Brně dne 15. listopadu 2015
……………………… Podpis studenta
Poděkování Ráda bych poděkovala panu RNDr. Karlu Lepkovi, Dr. za odborné vedení při zpracování bakalářské práce. Dále bych ráda poděkovala mým nejbližším za obrovskou podporu.
OBSAH ÚVOD
7
1
9
KRYPTOGRAFIE 1.1 Základní pojmy 1.2 Vývoj šifer a kryptologie 1.3 Česká kryptologie 1.4 Moderní kryptologie
2
MATEMATIKA, ZÁKLAD PRO ŠIFROVÁNÍ 2.1 Teorie čísel 2.2 Kongruence 2.3 Pravděpodobnost a statistika 2.4 Permutace
3
ŠIFROVÁNÍ POMOCÍ VELKÝCH PRVOČÍSEL – RSA 3.1 Šifrování veřejným klíčem 3.2 Bezpečnost RSA
4
KÓDOVÁNÍ V PŘÍRODNÍCH VĚDÁCH 4.1 Matematika 4.2 Fyzika 4.3 Chemie 4.4 Geografie 4.5 Biologie
9 11 21 22 25 25 30 32 33 34 35 38 41 41 43 44 45 46
ZÁVĚR
47
SEZNAM POUŽITÉ LITERATURY
48
SEZNAM OBRÁZKŮ
50
SEZNAM TABULEK
50
ÚVOD S šifrováním a kódováním se v současnosti setkáváme na každém kroku, aniž bychom si to uvědomovali. Snaha o uschování tajemství se objevuje už od dávných dob. A právě proto mě téma šifrování zaujalo, abych se jím zabývala ve své bakalářské práci. Ta je věnována historii šifrování, teorii čísel, metodě RSA a kódování v přírodních vědách. Každý člověk je zvědavý a je přirozené, že pokud víme, že má někdo nějaké tajemství, tak ho chceme odhalit. Co když se ale chceme s informacemi svěřit někomu, kdo není zrovna poblíž, a nechceme, aby se na tyto informace přišlo? Potom se snažíme tuto zprávu zašifrovat. Jestliže někdo nějakou zprávu zašifruje, text zprávy tedy musí být něčím zajímavý. A právě to je stimulem pro lidskou zvědavost. S častější potřebou využívat šifry se zvyšuje výzva pro autory šifer, jak vymyslet takovou, kterou by nikdo neprolomil. To však zároveň zvyšuje výzvu také pro luštitele, kteří se ji snaží rozlousknout. Asi každý z nás si již zkusil vyluštit křížovku či vyřešit nějakou hádanku. Mnozí si také jistě někdy přečetli knihu s detektivním příběhem. Šifry mohou mít zkrátka různou podobu a obtížnost. Některé jsou lehké, jiné prakticky nerozluštitelné. Kromě různých podob šifer máme také jejich různé použití. Základním je přenos informací z místa na místo a v dnešní době velmi důležitá ochrana dat. Jedním z dalších pak může být podpora logického, empatického a jazykového myšlení při užití šifer jako součásti volnočasových aktivit a her. Potřeba šifrovat je stará jako samotné písmo. První zmínky o šifrování můžeme nalézt už v Egyptě čtyři tisíce let zpátky. Impuls pro vznik a rozvoj šifer vidíme například u králů či generálů, kteří se snažili vládnout své zemi, svým armádám. Ti museli spoléhat na své komunikační systémy, díky kterým mohli posílat rozkazy do bitev. Avšak nemohli si být jisti, že zprávy nepadnou do nepovolaných rukou. Lidské společenství se nikdy nevyznačovalo jednotou, ba naopak každá skupina prosazovala své zájmy. Proto si země či království vynucovaly rozvoj prostředků k ochraně svých informací. S vývojem civilizace roste i složitost a dokonalost šifer. Tajná komunikace
7
však neprobíhala pouze v rámci vojenské komunikace, politických intrik či příprav atentátů. I docela obyčejní lidé potřebují sdělit někdy informace, které jsou určeny jen úzkému okruhu osob. Zpočátku se šifrovalo za pomoci pouhého přeskupování písmen abecedy. Už v 16. století však byly některé kódy tak složité a komplikované, že je skoro nešlo rozluštit. 2. světová válka byla velkým mezníkem pro šifrování. Tehdy vznikl zatím nejdokonalejší šifrovací stroj Enigma. Rozluštění zpráv německé Enigmy pomohlo k vítězství nad Německem. V dnešní době se setkáváme s šiframi na každém kroku. Každé zboží v obchodě má svůj čárový kód, díky kterému je urychleno placení. Díky počítačům je dnes takřka nemožné některé kódy rozluštit. Dokud nebude vynalezena nová generace počítačů, která by mohla dnešní šifrovací klíče prolomit, měla by být naše tajemství zachována. Bohužel však útoky hackerů jsou stále silnější a je možné, že i ty nejdokonalejší kódy budou zanedlouho prolomeny stejně tak, jako například za druhé světové války Enigma. Všechny kódy a šifry však nemusí být jen písemné. Šifry mohou mít různou formu. Například oheň zapálený v noci na kopci znamenal blížící se nebezpečí. Bílá vlajka je naopak symbolem míru. Mezi nejrozšířenější a nejznámější šifry patří Morseova abeceda, díky které jsme všichni schopni vyslat SOS. Jsou stovky způsobů, jak někomu předat zprávu, kterou má číst jen on. „Skoro všechny se přitom opírají o matematiku. Některé šifry využívají extrémně vražednou matematiku…“1
1
POSKITT, Kjartan. Šifry: od Caesara ke kreditním kartám, str. 6.
8
1 KRYPTOGRAFIE V této kapitole bakalářské práce bude vysvětlena kryptografie a s ní spojené základní pojmy. Dále si něco řekneme o vývoji kryptografie od starověku po současnost.
1.1 Základní pojmy Kryptografie poskytuje prostředky, jak ochránit data. Zabývá se tvorbou systémů zabezpečujících utajení zpráv před nežádoucí osobou. Tyto systémy se nazývají šifrovací systémy a ty mají svá pravidla neboli šifrovací klíče. Šifrovací klíč je krátká informace, kterou potřebujeme, abychom mohli začít s dešifrováním. Tento klíč by se měl velmi pečlivě střežit a neměl by se za žádných okolností dostat do špatných rukou. Obecný způsob, jakým je zpráva zakódována, se nazývá algoritmus. K dešifrování zprávy není algoritmus třeba znát. Šifra je obecné označení pro jakoukoli zprávu, kterou je nutné dešifrovat, abychom jí porozuměli. Jednotlivá písmena se zaměňují za symboly nebo se prohazuje jejich pořadí. Základní dělení šifer:2 1. Šifra symetrická – Komunikace probíhá na základě jednoho klíče, kterým se zpráva zašifruje i rozšifruje. Tento klíč se nazývá symetrický tajný klíč nebo jen tajný klíč. 2. Šifra asymetrická – Každý účastník má jeden klíč soukromý a jeden veřejný. Adresát svým soukromým klíčem dešifruje zašifrovanou zprávu, která byla zašifrována jeho veřejným klíčem. Veřejný klíč může být zveřejněn, jelikož jeho znalost nám při dešifrování nepomůže. Souvislosti mezi klíči zde jsou, avšak výpočetně je velmi složité a časově náročné tyto klíče poznat. Asymetrické šifrové algoritmy jsou využívány při vytváření elektronického podpisu.
2
GAJDOŠ, P., Asymetrická šifra RSA in Letní škola matematiky a fyziky, str. 29.
9
Dalším základním pojmem je kód. „Kódy nahrazují celá slova (nebo i krátké fráze) jinými slovy nebo skupinami písmen. Nemusí být nutně tajné, kupříkladu MAYDAY je známé mezinárodní kódové slovo, jež vysílají lodě či letadla, která se ocitnou v průšvihu.“3 Rozdíl mezi šifrou a kódem tedy rozeznáváme. Šifrovat znamená, že převádíme otevřený text na šifrový. Text se obvykle skládá z písmen národní či mezinárodní abecedy nebo číslic a znamének. „Pro převod abecedy otevřeného textu do abecedy šifrové existuje více než 400 000 000 000 000 000 000 000 000 (400 kvadrilionů) možností.“4 Po správném zašifrování dochází na druhé straně k dešifrování, které musí být přesné, aby byl text čitelný. Objevily se snahy o dešifrování bez pomoci klíče, a to pomocí hrubé síly. K šifrování a dešifrování je potřebná přesnost, vytrvalost, odhodlání, předvídavost nebo kupříkladu kombinační schopnosti. Luštěním šifrovacích klíčů se zabývá kryptologie, která se stala vědní disciplínou a je provozována díky poznatkům matematické statistiky, algebry a matematické lingvistiky. Dělí se na dvě oblasti, již zmiňovanou kryptografii a kryptoanalýzu, která zjišťuje, do jaké míry je šifra bezpečná. Steganografie je vědní disciplína, která se zabývá ukrytím komunikace. Dobře skrytá zpráva se pozná tak, když si jí pozorovatel ani nevšimne. Oblíbená forma utajené komunikace je použití neviditelných inkoustů. Ty znali už v 1. století Římané. Používali například šťávu z pryšce, která je po zaschnutí neviditelná, ale když se zahřeje, zhnědne. Používali také citrónovou šťávu či moč. „Vědec Giovanni Battista della Porta, který žil v 16. století, popsal, jak se roztokem kamence v octu dá napsat na vejce uvařené natvrdo zpráva, která na skořápce není vidět. Nápis ale pronikne skořápkou a po oloupání ho lze přečíst na bílku.“5 Ukrývání tajné komunikace najdeme už v 5. století před naším letopočtem u Peršanů při řecko-perské válce. Na dřevěné destičky byla vryta tajná zpráva a poté byla zalita voskem. Destičky se ale dostaly do rukou Řeků, kteří se tak mohli připravit na útok Peršanů. Jiný řecký panovník v téže době nechal oholit poslovi hlavu
3
POSKITT, Kjartan. Šifry: od Caesara ke kreditním kartám, str. 8. ADAMS, Simon. Šifry a kódy: od hieroglyfů po hackery, str. 27. 5 LUNDE, Paul. Tajemství kódů, str. 64. 4
10
a vytetovat na ni zprávu. Poté počkal, až hlava zase zaroste. Pak teprve poslal posla přes nepřátelskou linii. Když se dostal k adresátovi, nechal se pouze oholit, protože sám obsah zprávy neznal. U Číňanů známe použití hedvábí, na které se napsalo tajné sdělení, jež se poté smotalo do kuličky, pokrylo se voskem a nechalo se poslem spolknout. Hedvábí se používalo také za druhé světové války, kdy se na ně tiskly mapy, které si piloti schovávali do podpatků od bot. V případě sestřelení použili mapu k cestě do bezpečí.
1.2 Vývoj šifer a kryptologie V Mezopotámii kolem roku 3300 před naším letopočtem bylo psaní založeno na piktogramech. Jednalo se o kresby, které zobrazovaly slova či myšlenky. Představovaly univerzální kód, kterým se všichni lidé dorozumívali bez ohledu na odlišnost jazyků. Piktogramy vyrývali rákosovým hrotem do hliněných tabulek. Tak vzniklo klínové písmo (Obrázek 1), které bylo tvořeno rovnými čarami s klínovým průřezem. Ne vždy byly piktogramy k rozluštění pro nezasvěcené. „Klínové písmo starověkých Chetitů rozluštil český badatel profesor Bedřich Hrozný.“6 Na rozdíl od klínového písma se však nedokázala rozluštit tajná obrázková písma, například 4000 let staré písmo ze severní Indie. Má 400 znaků a není známo, co všechny znamenají. Avšak o kryptologii se v této době nejspíš nejednalo.7
Obrázek 1: Klínové písmo Zdroj: www.google.cz [online]
6 7
ADAMS, Simon. Šifry a kódy: od hieroglyfů po hackery, str. 18. ADAMS, Simon. Šifry a kódy: od hieroglyfů po hackery, str. 19.
11
První dokumenty, které měly utajit svůj obsah, jsou více víc než 2000 let staré. Už v této době můžeme vidět rozlišení dvou typů šifer: transpoziční a substituční. substituční Transpoziční šifry jsou takové šifry, ve kterých jsou písmena zprávy přeházená, u substituční jsou písmena nahrazena jinými písmeny, číslicemi či znaky. Tradice kódování se nejspíše nejspíš objevuje poprvé v antickém Řecku. Šifry byly velmi důležité ve vojenství a diplomacii. Řekové byli velmi vynalézaví jak ve vývoji matematiky, tak i ve vývoji kryptografie s ní spojenou. Zřejmě nejstarším kryptografickým přístrojem a nejstarší transpoziční šifrou je skytalé (Obrázek 2), 2 která byl využívána byla využíván ve Spartě od 7. století před naším letopočtem. Tento přístroj byl tvořen
Obrázek 2:: Skytalé Zdroj: www.google.cz [online]
Obrázek 3: Polybiův čtverec Zdroj: www.google.cz [online]
dřevěnou tyčí a omotaným koženým proužkem, na který byla byl napsána zpráva v řádcích. Bez správné tloušťky skytalé neměla zpráva žádný smysl. Posel si proužek vzal jako opasek a nikdo nic nic nepoznal. Fungování tohoto přístroje je na principu transpozice neboli promíchání otevřeného textu.8 Okolo roku 360 před naším let letopočtem opočtem napsal Řek ek Aineias Taktikos knihu Obrana opevněných míst, ve které uvádí 16 různých šifrovacích metod. Ty jsou zaměřeny na záměnu samohlásek například za tečky či číslice. V tu dobu byly v Indii vytvořeny základy znakové řeči, která je používána dodnes. Smysl byl však jiný. Používali ho obchodníci a lichváři, aby mohli mezi sebou dodnes. nenápadně komunikovat.9 Ve 2. století před naším letopočtem se setkáváme s Polybiovým čtvercem (Obrázek Obrázek 3).. Polybios seřadil písmena do čtverce a očísloval jejich řady a sloupce.
8 9
LUNDE, Paul. Tajemství ví kódů, str. 102. VONDRUŠKA, Pavel. Kryptologie, šifrování a tajná písma, str. 200.
12
Tento výtvor byl velmi ceněný a stal se základem pro další šifrovací systémy. Není však žádný důkaz, že by se čtverec používal i v praxi. Jméno autora zašifrujeme takto: POLYBIOS = 4135325412243544.10 Caesarova šifra (Tabulka 1) je pojmenovaná po římském diktátorovi Gaiu Juliu Caesarovi (100–44 př. n. l.). V roce 58 před naší letopočtem se Caesar ujal velení nad legiemi a vedl válku o Gálii. K utajení komunikace mezi svými vojáky vymyslel šifru na způsob substituce. Můžeme se o ní dočíst v jeho díle Zápisky o válce galské. Nerozluštitelná byla do té doby, dokud její princip neprozradil nepřátelům jeden z Caesarových lidí. Používaná je už tisíciletí, a používala se dokonce i v 1. světové válce, kdy pomocí ní šifrovalo vedení ruské carské armády jen s určitým pozměněním. Do textu byly vloženy „klamače“, které bylo zapotřebí před dešifrováním vyškrtat. Přesto byla snadno prolomena a to vedlo k porážce ruských vojsk u Tannenbergu ve Východním Prusku (dnešní Polsko) v září 1914.11 Caesarova šifra patří mezi substituční šifry. Její fungování je založeno na principu, kdy každé písmeno abecedy je nahrazeno jiným. Konkrétně se jednalo o posun o tři místa dopředu. Tabulka 1: Ceasarova šifra Zdroj: Vlastní zpracování
25
24
23
22
21
20
19
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
Pokud bychom písmena očíslovali od 0 do 25, můžeme Ceasarovu šifru matematicky vyjádřit pomocí přičítání čísla 3 modulo 26. Prakticky si ukážeme princip jednoduše: (15 + 3) mod 26 = 18. Zde jsme vzali písmeno P a zašifrovali ho na S. Číslo 3 hraje funkci klíče, který samozřejmě může být nahrazen jakýmkoli číslem k, aby platilo 0 < k < 26.
10 11
VONDRUŠKA, Pavel. Kryptologie, šifrování a tajná písma, str. 201. ŠKOPEK, Pavel. 3 šifry starověku in Epocha. Str. 45.
13
Obecně tedy pro Caesarovu šifru (možno s libovolnou délkou abecedy) s klíčem k platí: E: ci = (mi + k) mod 26, D: mi = (ci + k) mod 26, kde M = m0m1m2…ml značí původní zprávu (message), C = c1c2c3…cl zašifrovanou zprávu (ciphertext). E znamená šifrovací funkci (encryption), D zase dešifrovací funkci (decryption). Rozšifrováním zašifrované zprávy musíme zpět dostat původní text. V Indii se v pátém století používá kryptologie i mezi nižšími vrstvami, a to pro jiné účely než jen vojenské. Dokladem toho je známá učebnice erotiky Kámasútra. V části Smyslná žena se hned v úvodu dozvídáme o 64 radách pro ženy, které chtějí mít úspěch u mužů, mezi něž byla zařazena tato: „Osvojte si tajná písma a šifry nebo si vynalezte vlastní. Důležitá je také znalost nových způsobů mluvy, abyste mohla obratně měnit začátky a konce slov tak, jak právě potřebujete.“12 Dalším zásadním mezníkem ve vývoji kryptologie je 15. století, kdy byl objeven šifrovací systém polyalfabetické substituce, která využívá více neustále se střídajících šifrových abeced. Byla vynalezena Leonem Battistou Albertim. Ten sepsal stručnou práci, která se stala jednou z nejvýznamnějších prací v západní Evropě. Zde také můžeme najít první evropský systematický výklad luštění na základě frekvence a jazykových znalostí a použití zašifrovaných kódů.
12
VONDRUŠKA, Pavel. Kryptologie, šifrování a tajná písma, str. 204–205.
14
Polyalfabetická substituce měla zlepšit šifrování oproti dosud známé homofonní substituci. K rychlejšímu utajení zprávy sestrojil Alberti šifrovací disk (Obrázek 4), který je tvořen dvěma otočnými kotouči značícími otevřený a šifrový text.
Obrázek 4: Albertiho šifrovací disk Zdroj: www.google.cz [online]
Další významný počin v oblasti kryptologie vznikl u milánského fyzika, matematika, filosofa, astronoma a astrologa Girolamo Cardana. Byl autorem myšlenky autoklíče, který měl více zabezpečit šifru před rozluštěním. Bohužel jeho podání je nedokonalé, protože není jednoznačné. Proslavil se díky steganografické metodě, která se zakládala na mřížce (Obrázek 5), tj. šabloně, a do děr se napsala tajná zpráva. Bez šablony se pak dopsalo sdělení, aby se text tvářil jako obyčejný.13 Cardano doporučil, aby se zpráva opsala 3x za sebou, pokaždé otočená o 90°. Jedná se v podstatě o jednoduchou transpozici. Jestliže označíme polohu okna v mřížce n × n, n = 2k s pomocí řádku a sloupce, potom okno při otáčení umožní vyplnit následující pozice: (i, j) → (j, n – i + 1) → (n – i + 1, n – j + 1) → (n – j + 1, i), to znamená, že maximální počet oken v mřížce je n2/4 = k2.
13
VONDRUŠKA, Pavel. Kryptologie, šifrování a tajná písma, str. 222.
15
Lze sestrojit
=
různých mřížek poskytujících různé transpozice
14
otevřeného textu.
Obrázek 5: Šifrovací mřížka Zdroj: www.google.cz [online] Zdroj
V 16. století žil Francouz Blaise de Vigenére, který se zapsal mezi nejznámější kryptology vůbec. Sloužil u dvora vévody Navarrského. Dva roky působil jako diplomat v Římě a právě zde se poprvé setkal s kryptologií. Dnes známá Vigené Vigenérova rova šifra není ve skutečnosti dílem Vigenériho. Vigenére genére jen proslavil dílo Giovaniho Batisty Belasa, který se nedočkal nedočkal uznání kvůli nedostatečné komunikaci s vědeckou obcí. Základem Vigenérovy šifry je čtverec (Obrázek 6), který obsahuje všech 26 písmen abecedy. Každý řádek začínal posunem abecedy o jedno písmeno než řádek předchozí. K zašifrování a dešifrování je potřeba klíče. Původní čtverec však obsahoval 26 různých abeced. abeced. Do podoby nám známé šifry šifr ji předělal Johannes Trithemiem.
14
GROŠEK, O. a spol. Klasické šifry, str. 71. 71
16
Obrázek 6: Vigenérův rův čtverec Zdroj: www.google.cz [online]
Pokusme se zašifrovat spojení Vigenérova Vigen rova šifra za pomocí klíče „klíč“ „ (Tabulka Tabulka 2). První rvní řádek značí otevřenou abecedu, abecedu první sloupec značí písmena klíče. klíče Výsledný šifrový text je pak průsečík daného sloupce a řádku. Tabulka 2: Vigenérova Vigenérova šifra Zdroj: Vlastní zpracování
V
I
G
E
N
E
R
O
V
A
S
I
F
R
A
K
L
I
C
K
L
I
C
K
L
I
C
K
L
I
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
F
T
O
G
X
P
Z
Q
F
L
A
K
P
C
I
Na svoji dobu byla tato metoda šifrování příliš složitá, proto se začala používat až v 19. století. Do té doby se využívaly spíše jednodušší substituční šifry šifry. Disponuje velkým počtem klíčů, proto byla účinná a odolná vůči hrubé síle. Pokud bychom věděli klíč s 10 znaky, pak by existovalo dohromady 2610 možností klíčů. klíčů. Odolná je také proti frekvenční analýze. Jestliže je klíč složen z n různých písmen, pak písmeno může být zašifrováno do n různých možností. možností. Zde nám tudíž znalost četností k rozluštění
17
nepomůže. Klíčem může být známé slovo či věta, která se snadno zapamatuje. Což může na druhou stranu být také jistá nevýhoda, pokud by se v textu opakovaly určité shluky písmen. Vigenérova šifra byla dlouho nerozluštitelná. Charles Babbage ji náhodou vyluštil v roce 1853, avšak svůj výsledek nikde nepublikoval. O pár let později Friedrich Kasiski také šifru prolomil a s řešením se podělil roku 1863 v Berlíně. „Slabina Belasova systému, které se Babagge i Kasiski chytili, je algebraická a plyne z logické kombinace systematického opakování klíčového slova a statistického výskytu písmenných skupin v jazyce.“15 16. století bylo také známé příběhem Marie Stuartovny, která připravovala povstání a svržení anglické královny Alžběty. Kvůli nedokonalému šifrovému systému, který byl prolomen, k naplnění plánů nedošlo. Marie byla považována za nebezpečnou pro královský trůn, a proto byla popravena. Na svoji vlastní kůži poznala snadnou dešifrovatelnost soudobých šifer. Nevyužila ale jednoduchou substituční šifru, zkombinovala šifrovací abecedu s kódovými slovy. Další šifrovací stroj vynalezl americký prezident Thomas Jefferson mezi lety 1790–1800. Byl nejdokonalejším ve své době. Jefferson však dal svůj vynález stranou a používal dosud známé šifry, které byly oproti jeho šifrám opravdu nedokonalé. Znovuobjeven byl až v roce 1922 v Kongresové knihovně. Jeffersonův „šifrátor“ je tvořen základní osou, na kterou je navlečeno 36 disků. Na každém disku je napsána abeceda, tedy všech 26 písmen, avšak je proházená. Otevřený text se nastaví na válečku a opíše se jakýkoli ze zbývajících řádků. Tato šifra je již docela bezpečná, a proto také byla používána až do začátku 2. světové války. Šifry sehrály klíčovou roli ve 20. století v období první a druhé světové války. Zlepšení komunikace zajistil vynález rádia z roku 1894 a dřívější vynález telegrafu v roce 1832. Komunikace armád byla proto mnohem rychlejší, avšak byla dostupná úplně každému, a proto bylo šifrování naprosto nezbytné. V 1. světové válce byla schopnost anglické kryptologické jednotky zásadní pro vstup USA do války. Roku 1917 chtěli Němci začít ponorkovou válku v Atlantiku, 15
BERLOQUIN, Pierre. Skryté kódy a velkolepé projekty. Str. 193.
18
avšak báli se zapojení USA do války. Proto chtěli využít Mexiko, které by zaútočilo na Ameriku. Německý ministr zahraničí Arthur Zimmermann tedy poslal německému velvyslanci v Americe zašifrovaný telegram, aby vše domluvil s Mexikem. Zprávu však zachytili Angličané v čele s Williamem Hallem. Pokud by hned dali vědět americké straně, byla zde možnost, že by rozluštěnou zprávu brali jako podvod a Němci by věděli, že Angličané jejich šifru vyluštili. Proto vyslali do Mexika tajného agenta, který měl proniknout do tamní telegrafní služby a vytvořit kopii dešifrovaného telegramu. Díky zveřejnění této zprávy v americkém tisku USA vyhlásilo v dubnu 1917 válku Německu, což pomohlo k následné kapitulaci Německa. Němci až do 20. let netušili, že Britové jejich šifrování prolomili. Ono zjištění je dosti znepokojilo, a tak dali vzniknout nejlepšímu šifrovacímu stroji, který měl být zásadní pro 2. světovou válku. Stroj s názvem Enigma (Obrázek 7) považovali za dokonalý čili nerozluštitelný. Jejich smýšlení však bylo chybné, protože Enigma byla rozšifrována a tento fakt výrazně ovlivnil vývoj a závěr druhé světové války a předznamenal nástup éry počítačů.
Obrázek 7: Přístroj Enigmy Zdroj: www.google.cz [online]
19
První model Enigmy postavil německý vynálezce Arthur Scherbius již v roce 1918. Hitler byl díky Enigmě k neporažení. Německá armáda objednala přes 30 000 šifrovacích strojů, které byly velmi rychlé a téměř zamezily chybám člověka. Zpráva byla do stroje napsána v otevřeném textu a ten sám vytvořil text šifrový, který byl poslán rádiem. U adresáta byl naopak šifrový text zadán do stroje a ten sám a velmi rychle převedl do textu otevřeného. Nepřekonatelnost Enigmy byla v každodenní změně klíče. Německá armáda proto každý měsíc vytvořila knihu denních kódů. I když si nepřátelé Německa nechali zhotovit kopie Enigmy, kódové knihy jim známy nebyly. O prolomení Enigmy se snažili Poláci už ve třicátých letech minulého století. Díky Francouzům se mohli pustit do stavby repliky neprolomitelného stroje, jehož mechanismus vyžaduje matematické dovednosti. Jejich myšlenkami se nechal inspirovat nadaný britský matematik Alan Turing, který patřil do skupiny vědců kryptoanalytického centra v Bletchley Parku. Společně se svými kolegy se snažil vyzrát na mechanismus stroje. Čas na rozluštění byl velmi omezen, jelikož se nastavení Enigmy měnilo vždy o půlnoci, proto musel Turingův tým pracovat opravdu rychle. Pustil se do navrhování „bomb“, které měly analyzovat rozšířené nastavení rotorů Enigmy. „Turingův plán spočívající v tom, že „bomby“ budou pracovat vzájemně propojeny v řadě, aby se odhalily smyčky, byl schválen a bylo vyčleněno 100.000 liber na vytvoření tohoto uspořádání. Výsledkem velkého počtu vzájemně propojených bomb byl první programovatelný počítač na světě označený krycím názvem Jumbo.“16 Na začátku roku 1942 dešifrovalo Enigmu už 16 bomb a během jedné hodiny byly schopny dešifrovat všechny zprávy poslané ten den. Enigma obsahovala klávesnici, na kterou se psal otevřený text, dále tři rotory, což byly disky s abecedou a dohromady tvořily polyalfabetickou šifru, jeden reflektor, který jen vracel signál na rotory ke zpětnému průchodu, propojovací desky a panel žárovek. Operátor naklapal písmena zprávy, elektrickým proudem byly úhozy poslány přes propojovací desku a tři scramblery. Poté se elektrický proud vracel zpět jinou cestou do signální desky, kde rozsvítil žárovky označující šifrové písmeno. Poté se celá šifrová zpráva ještě zašifrovala do Morseovy abecedy a poslala přes rádio. Na druhé straně 16
LUNDE, Paul. Tajemství kódů, str. 121.
20
nastavili scramblery na stejnou polohu a vložili zašifrovanou zprávu. Elektrický proud opět vedl text přes propojovací desku a na signální desce svítily žárovky příslušných písmen. Pro větší komplikovanost se scramblery otáčely různou rychlostí a bylo je možno
nastavit
do
26
odlišných
pozic.
Ve
skutečnosti
má
Enigma
10 000 000 000 000 000 různých nastavení. Dalším vývojem byl počítač nazvaný Colossus, který byl skutečným předchůdcem dnešních počítačů. V Japonsku vynalezli taktéž svůj šifrovací stroj, Američany nazvaný Purpur, který jim pomohl k nadvládě v Tichomoří. Americkým kryptoanalytikům se nicméně podařilo sestrojit kopii Purpuru a dešifrovat zprávy. Z nich se dozvěděli o plánovaném útoku Japonců v prosinci 1941, avšak ve zprávě nenašli přesné místo a čas útoku. Ničivému náletu na Pearl Harbor se proto nedalo předejít, a tak USA vstoupilo do 2. světové války.
1.3 Česká kryptologie Prvním dochovaným dokumentem o šifrování v Čechách jsou pravděpodobně listy z Kostnice napsané Mistrem Janem Husem. Jednalo se o velmi jednoduchou šifru, kde zašifrovány byly pouze samohlásky, které byly nahrazeny následujícím písmenem v abecedě, například místo A napsal B, místo O napsal P. Mezi první významné počiny připisované na adresu českých kryptologů můžeme považovat ty z období 2. světové války. V předválečné kryptologii se nic zásadního nestalo. Šifrované zprávy proudily za 2. světové války mezi Londýnem a domácím odbojem, avšak Němci prováděli luštění. Česká kryptologie se vyvíjela až do sametové revoluce a i přesto, že většina komunikací byla zajišťována sovětskou technikou, naše úroveň byla vysoká. Po sametové revoluci se k samostudiu kryptologie rozhodlo několik desítek studentů vysokých škol v oblasti počítačové bezpečnosti. Žádná škola tento obor nevyučovala. Nyní se každý rok koná přes pět světových konferencí na téma kryptologie. Stále je ale nedostatek lidí vzdělaných v této oblasti, i když jsou potřební
21
v mnoha
různých
odvětvích,
například
v bankách,
u
mobilních
operátorů,
v komunikačním průmyslu apod. Co stále chybí, je česká terminologie. „Český kryptologický výzkum stále tvoří roztroušené a izolované ostrůvky, na tom jsme nic nezměnili, ale Češi jsou chytrý národ, takže za několik let může situace vypadat mnohem nadějněji.“17
1.4 Moderní kryptologie S nástupem počítačů přichází nová fáze vývoje kryptografie. Počítače velmi významně změnily způsob generování a prolamování šifer a klíčů. V této době se všichni stáváme kryptografy, abychom ochránili svoje soukromí. První přístroj v dějinách navrhl a postavil anglický matematik a inženýr Charles Babbage (1791–1871) v roce 1823, tento přístroj sloužil k řešení matematických úloh. Impulzem pro vynález počítače mu byly lidské chyby. „Dokud nebyly kalkulačky, byly pro hodnoty funkcí jako sinus, cosinus a logaritmus sestaveny speciální tabulky.“18 Avšak spočítat tyto hodnoty s přesností zabíralo opravdu neskutečné množství času. Proto chtěl Babbage sestrojit přístroj, který by spočítal hodnoty velmi rychle a hlavně přesně. Charles Babbage se nejvíce proslavil díky diferenčnímu stroji, který kvůli technickému omezení své doby vlastně nikdy nebyl dokončen. Poté navrhl vylepšenou verzi, která se dostala na svět až 20 let po jeho smrti. Londýnské Muzeum vědy v roce 1991 sestavilo rekonstrukci diferenčního stroje ve skutečné velikosti. Je složeno z 25 000 součástek, dohromady váží 15 tun, měří 2,4 metrů. „Babbage usoudil, že s využitím matematického postupu zvaného metoda konečných diferencí by jeho přístroj mohl vykonat všechny potřebné zdlouhavé výpočty v podstatě jenom prostřednictvím odčítání obrovského množství čísel a bez použití násobení.“19 Vytvořil soustavy s ozubenými kolečky, na kterých jsou vytištěné čtyři řady číslic od 0 do 9. Tato soustava koleček dala výsledek o 31 cifrách.
17
SINGH, S. Kniha kódů a šifer: tajná komunikace od starého Egypta po kvantovou kryptografii, str. 10. LUNDE, Paul. Tajemství kódů, str. 268. 19 LUNDE, Paul. Tajemství kódů, str. 268. 18
22
Psací stroj byl jeden z největších vynálezů v dějinách komunikace. První stroje, připomínající dnešní, přišly koncem 70. let 19. století. Byly ale uspořádány podle abecedy. První klávesnice QWERTY se objevila v roce 1874. Dalším vynálezem usnadňující komunikaci byl elektrický telegraf, který se postupně vyvíjel až k telefonu. Telefon změnil výrazným způsobem komunikaci na dálku. V posledních letech došlo k obrovskému rozvoji v oblasti informačních a komunikačních technologií. První mobilní telefony známe od 70. let minulého století, výrazně se zkrátila vzdálenost mezi lidmi, poslat zprávu na druhou stranu Země je mimořádně rychlé. V současnosti si bez mobilního telefonu neumíme představit ani den. Jen nemůžeme vědět, kdo si naše zprávy čte. Po téměř 100 letech od vynálezu diferenčního stroje se vyvinul první počítač k prodeji. Do oběhu šlo pouhých 6 počítačů, za dalších 50 let už se prodaly dvě miliardy počítačů, ze kterých je ještě necelá miliarda v oběhu i v současnosti. Nyní se počítače neustále zmenšují, zrychlují a postupně vylučují potřebu zásahu člověka. Kódování se často provádí za pomoci binárních čísel (kódů), ta se skládají ze samých nul a jedniček zvaných bitů. Písmena abecedy se ukrývají v pětimístných číslech, která tedy obsahují pouze výše zmíněné bity. Pro zápis pětimístného kódu (Tabulka 3) existuje 32 možností a máme 26 písmen a 10 číslic, proto k některým binárním kódům jsou přiřazena dvě písmena. Například: Tabulka 3: Přepis vybraných písmen do binárního kódu Zdroj: Vlastní zpracování
00001 = 1 00101 = 5 01001 = 9
01010 = a 01111 = f 10011 = j/k
11000 = p/q 11011 = t 11111 = y/z
Pro převod otevřeného textu na binární čísla můžeme využít kód ASCII (Tabulka 4). Tabulka 4: Přepis vybraných písmen a číslic do kódu ASCII Zdroj: Vlastní zpracování
0 ASCII
00110000 a
ASCII
01100001
1 00110001 e 01100101
2 00110010 k 01101011
23
5 00110101 r 01110010
8 00111000 u 01110101
9 00111001 z 01111010
Kód ASCII je nejpopulárnější kódovaný jazyk. Nazývá se podle zkratky z anglického Americký standardní kód pro výměnu informací. Každý znak ASCII se převádí na 8 bitů, proto může reprezentovat 256 znaků. Šifrování a kódování je v dnešním světě nezbytné ve více sférách. Zajišťují soukromí a bezpečí dat. Díky počítačům jsou šifry velmi propracované. Většina počítačů funguje právě na binárním kódu, což některým lidem může znepříjemnit práci a komunikaci s počítačem a programováním.
24
2 MATEMATIKA, ZÁKLAD PRO ŠIFROVÁNÍ S prudkým rozvojem kryptografie spojeným se vznikem prvních počítacích strojů ve 20. století se šifrování dostalo k matematikům. Proto se k vysvětlení a dalšímu pochopení neobejdeme bez znalosti teorie čísel, kterých se týká následující kapitola. Teorie čísel je velmi obsáhlá matematická disciplína, která se zabývá vlastnostmi především celých čísel. Jejich nejdůležitější vlastnosti byly známy již ve starověkém Řecku u pythagorejců, kde se učili o dělitelnosti čísel, prvočíslech či vzájemně nesoudělných číslech (Pythagorejská čísla x2 + y2 = z2). Eukleides ve 3. století před naším letopočtem ve své knize Základy definoval algoritmus pro nalezení největšího společného dělitele a dokázal, že prvočísel je nekonečně mnoho. Oblasti prvočísel se věnoval také Eratosthenes, který vytvořil tzv. Eratosthenovo síto pro vyhledávání prvočísel.
2.1 Teorie čísel Definice 2.1.1 Přirozená čísla jsou čísla 1, 2, 3, … Množinu přirozených čísel značíme
ℕ. ℕ = 1, 2, 3, … Dlouhou dobu se spekulovalo, jak přirozená čísla vůbec zavést. Až roku 1891 zformuloval italský matematik Giuseppe Peano čtyři axiomy, v nichž popisuje množinu přirozených čísel. Peanovy axiomy: A1. Existuje jedno jediné číslo, které není následníkem žádného předcházejícího přirozeného čísla. Takovým číslem je 1. A2. Každé přirozené číslo má právě jednoho následníka. A3. Každé přirozené číslo je následníkem nejvýše jednoho přirozeného čísla. A4. Každá množina, která obsahuje přirozené číslo 1 a kde každé přirozené číslo má i svého následníka, je množina přirozených čísel.
25
Na těchto axiomech vznikl základ pro důkazy matematickou indukcí. Nejprve musíme dokázat platnost tvrzení pro nejmenší přirozené číslo 1 (viz A1.). Poté předpokládáme platnost pro n a dokážeme platnost pro následníka n + 1. Definice 2.1.2 Celá čísla jsou všechna přirozená čísla, čísla k nim opačná a nula. Množinu celých čísel značíme ℤ.
ℤ = …-3, -2, -1, 0, 1, 2, 3, … Definice 2.1.3 Celá čísla jsou třídy ekvivalencí uspořádaných dvojic přirozených čísel (a; b), přičemž ekvivalence je definována: (a; b) ~ (c; d) ⟺ a + d = b + c. Věta 2.1.1 Relace ekvivalence je reflexivní, symetrická, tranzitivní. Důkaz: (a; b) ~ (c; d) 1. Reflexivní: (a; b) ~ (a; b) a+b=b+a 2. Symetrická: (a; b) ~ (c; d) ⇒ (c; d) ~ (a; b) a+d=b+c⇒c+b=d+a 3. Tranzitivní: (a; b) ~ (c; d) ⋀ (c; d) ∼ (e; f) ⇒ (a; b) ∼ (e; f) a+d=b+c⋀c+f=d+e⇒a+f=b+e Definice 2.1.4 Prvočíslo je přirozené číslo, které je dělitelné pouze jedničkou a sama sebou. Opakem prvočísla je číslo složené. Věta 2.1.2 (Základní věta aritmetiky) Každé přirozené číslo lze rozložit na součin konečného počtu kladných prvočísel, a to až na pořadí jednoznačně. Důkaz matematickou indukcí: Nejprve musíme zjistit, zda věta platí pro nejmenší přirozené číslo (pokud vynecháme 1) n = 2. Dále předpokládáme, že tvrzení platí také pro všechna přirozená čísla n, pak musíme dokázat, že platí také i pro n + 1. Číslo n může být prvočíslo nebo číslo složené. Pokud je číslo složené, předpokládáme, že
26
existuje součin n = r · s, kde r, s jsou přirozená čísla a platí pro ně vztah 1 < r, s < n. Jedná se buď o prvočísla, nebo o čísla složená, která jsou součinem opět dalších čísel, která jsou buď prvočísla, nebo čísla složená. S rozkladem se tedy pokračuje stále stejně, až nebude co rozložit, jelikož se dostaneme k prvočíslům. U každého čísla proto existuje prvočíselný rozklad, tvrzení platí obecně. Věta 2.1.3 Číslo p ∈ ℕ
je prvočíslo právě tehdy, když nemá žádného dělitele d
takového, že 1 < d ≤ .
Důkaz sporem: Nechť n = n1 · n2. Předpokládejme, že n1 > √ a n2 > √ . Pak ale n1 · n2 > √ · √ = n a to je spor. Tím je věta dokázána. Věta 2.1.4 Prvočísel je nekonečně mnoho. Důkaz sporem: Předpokládejme, že prvočísel je konečně mnoho. Máme tedy součin P = p1 · p2 · p3 · … · pi, který obsahuje všechna existující prvočísla. Nyní musíme najít takové prvočíslo, které není obsaženo v P. Pokud P zvětšíme o jedničku, vznikne nám nové číslo Q = p1 · p2 · p3 · … · pi + 1. Jak vidíme, číslo Q není dělitelné žádným prvočíslem ze součinu P, jelikož po vydělení vždy zůstane zbytek jedna. Může nastat, že číslo Q bude prvočíslo nebo bude dělitelné ještě větším prvočíslem, než je pi. Tím je věta dokázána. Definice 2.1.5 Nechť a, b ∈ ℤ. Řekneme, že a dělí b, značíme a | b, jestliže existuje x ∈ ℤ tak, že b = a · x. Číslo a se nazývá dělitel čísla b. Definice 2.1.6 Nechť a1, a2, …, an jsou celá čísla, t ∈ Z označíme jako společný dělitel
čísel a1, a2, …, an, jestliže t | ai, ∀i = 1, 2, …, n. Číslo d ∈ Z pak nazveme největším
společným dělitelem čísel a1, a2, …, an a značíme D(a1, a2, …, an). Jestliže d je společným dělitelem a1, a2, …, an a jestliže t je libovolný společný dělitel čísel a1, a2, …, an, pak platí t | d. Když D(a1, a2, …, an) = 1, říkáme, že čísla a1, a2, …, an jsou nesoudělná. Definice 2.1.7 Nechť a1, a2, …, an jsou celá čísla, N ∈ ℤ označíme jako společný
násobek čísel a1, a2, …, an, jestliže ai | N, ∀i = 1, 2, ..., n. Číslo M pak nazveme nejmenším společným násobkem čísel a1, a2, …, an a značíme M = n (a1, a2, …, an),
27
jestliže M je společným násobkem čísel a1, a2, …, an pro libovolný společný násobek N čísel a1, a2, …, an platí M | N. Věta 2.1.5 (O dělení se zbytkem) Nechť a, b ∈ ℤ /{0} jsou celá čísla. Pak existují
q, r ∈ ℤ taková, že
a = b · q + r, 0 < r < |b| Důkaz: Pokud a = 0, pak je tvrzení triviální a snadno zvolíme q = r = 0. Zbytek důkazu provedeme matematickou indukcí. Je-li a 0, pak pro a existují q, r ∈ ℤ, pro která a = q · b + r a 0 r < |b| = b. Pak a + 1 = q · b + (r + 1), kde r + 1 b. Pokud
r + 1 < b, pak je hotovo. Pokud ale r + 1 = b, potom a + 1 = q · b + b = (q + 1) · b + 0. Pokud předpokládáme a < 0, stejně jako v předcházejícím existují q´, r´ ∈ ℤ taková, že – a = q´· b + r´ a 0 r´ < b. Jestli r´= 0, snadno zvolíme q = - q´ a r = 0. Jestli r´ > 0, dejme q = - q´ - 1 a r = b – r´. Pak a = (- q´ - 1) · b + (b – r´) a 0 < (b – r´) < b. Věta 2.1.6 (Euklidův algoritmus) Nechť a, b ∈ ℤ /{0}. Pak existují celá čísla q0, q1, q2, …, qn, r1, r2, r3, …, rn taková, že rn = D(a, b) a platí: a = b · q0 + r1,
0 < r1 < |b|
b = r1 · q1 + r2,
0 < r2 < r1
. . .
ri−1 = ri · qi + ri+1,
0 < ri+1 < ri
. . .
rn−2 = rn−1 · qn−1 + rn,
0 < rn < rn−1
rn−1 = rn · qn Definice 2.1.8 Pro 0 ≠ n ∈ ℕ označme ϕ(n) počet všech čísel k, 1 ≤ k ≤ n takových, že D(k, n) = 1. Funkce ϕ se nazývá Eulerova funkce. Tj. ϕ(n)= │{k ∈ {1, …, n}; (k, n) = 1}│, kde symbol │.│označuje počet prvků. Z toho snadno zjistíme, že ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, ϕ(6) = 2, ϕ(7) = 6, …
28
Z definice Eulerovy funkce vidíme, že hodnoty pro n > 2 jsou sudé. Pokud je p prvočíslo, pak zřejmě ϕ(p) = p – 1 a ϕ(pm) = (p – 1)pm – 1 pro každé m ∈ ℕ. Pro nás je zajímavá hodnota Eulerovy funkce pro n = p · q, kde p a q jsou různá prvočísla. Číslo n je tedy dělitelné p i q a počet všech přirozených čísel menších než n je zřejmě p · q – 1. Zde je obsaženo p – 1 násobků q a q – 1 násobků p. Jsou vzájemně různé a soudělné s n, tedy ϕ(n) = (p · q – 1) – (p – 1) – (q – 1) = p · q – p – q + 1 = (p – 1) · (q – 1). Eulerova funkce má další důležitou vlastnost (implikaci): (k, n) = 1 ⇒ ϕ(k · n) = ϕ(k) · ϕ(n). Leonhard Euler (1707–1783) pomocí funkce ϕ zobecnil Malou Fermatovu větu i pro neprvočíselný modul. Pro nás má velký význam, neboť se o toto zobecnění opírá metoda RSA, kterou používá například americká armáda či banky. O zmíněné metodě se dozvíme více v následující 3. kapitole. Abychom mohli definovat Eulerovu-Fermatovu větu, musíme se nejdříve zmínit o kongruencích (modulo).
29
2.2 Kongruence Definice 2.2.1 Nechť m ∈ ℤ. Jestliže m | (a − b), říkáme, že a je kongruentní s b podle modulu m, značíme a ≡ b (mod m). Zde jsou některá pravidla pro počítání kongruencí: (Věta 2.2.1 – 2.2.4)20 Věta 2.2.1 Nechť a, b, c ∈ ℤ, m∈ ℕ. Pak platí: a ≡ a (mod m) (a ≡ b (mod m)) ⇒ (b ≡ a (mod m)) [(a ≡ b (mod m)) ∧ (b ≡ c (mod m))] ⇒ (a ≡ c (mod m)) Věta 2.2.2 Nechť a, b, c, d ∈ ℤ, m ∈ ℕ. Pokud a ≡ b (mod m) a c ≡ d (mod m), pak platí: (a + c) ≡ (b + d) (mod m) (a − c) ≡ (b − d) (mod m) a · c ≡ b · d (mod m) Věta 2.2.3 Nechť a, b, c ∈ ℤ, m ∈ ℕ. Nechť D(c, m) = 1, pak platí: a · c ≡ b · c (mod m) ⇒ a ≡ b (mod m) Věta 2.2.4 Nechť a, b ∈ ℤ, m, k ∈ ℕ. Pak a ≡ b (mod m) ⇒ a · k ≡ b · k (mod m).
Věta 2.2.5 (Malá Fermatova) Nechť x ∈ ℤ, p > 1 je prvočíslo, D(x, p) = 1. Pak: x p −1 ≡ 1
(mod p).
Důkaz: Nejprve ukážeme, že pokud jsou i a j dvě různá čísla z množiny {0, 1, …, p –1}, pak i·xj·x
(mod p).
20
Důkazy vlastností kongruencí můžeme nalézt například zde: VELEBIL, Jiří. Diskrétní matematika: Text k přednášce [online]. Str. 59-60.
30
Pokud by nastala rovnost, potom by muselo platit p | x · (i – j), ale podle předpokladu D(x, p) = 1, musí platit p | (i – j). Jedná se tedy o spor. Posloupnosti x, 2x, …, (p – 1) · x a 1, …, (p – 1) obsahují v ℤp stejná čísla a po vynásobení obou posloupností vidíme, že jsou si součiny rovny. Proto platí v ℤp.
a p – 1 (p – 1)! = (p – 1)! Neboť p je prvočíslo, pak D(p, (p – 1)!) = 1, a pak x p −1 ≡ 1
(mod p).
Věta 2.2.6 (Eulerova) Nechť x ∈ ℕ, p je prvočíslo: p > 1, D (x, p) = 1. Pak x ϕ(p) ≡ 1
(mod p).
Důkaz: Postupujeme obdobně jako u důkazu věty 2.2.5. Pro všechna čísla nesoudělná s p od 0 do p – 1 existuje inverze v ℤp. Podle definice Eulerovy funkce je přesně ϕ(p) různých invertibilních prvků, které označíme a1, a2, …, aϕ(p). Nejdříve můžeme ukázat, že pokud jsou i a j dvě různá čísla z množiny {0, 1, …, ϕ(p)}, pak ai · x aj · x (mod p). Pokud by nastala rovnost, potom by musela platit rovnost ai = aj, neboť podle předpokladu D(x, p) = 1. Jedná se tedy o spor. Posloupnosti a1x, a2x, …, aϕ(p)x a a1, …, aϕ(p) musí obsahovat stejná čísla. Jestliže vynásobíme členy obou posloupností v ℤp, pak je jasné, že jejich součiny jsou si rovny. Platí tedy xϕ(p) · a1 · … · aϕ(p) = a1 · … · aϕ(p) v ℤp. Jelikož má součin posloupnosti a1 · … · aϕ(p) inverzi v ℤp, pak
31
x ϕ(p) ≡ 1 (mod p).
Věta 2.2.7 (Eulerova-Fermatova) Pro x, n ∈ ℕ platí (x, n) = 1 právě, když x ϕ(n) ≡ 1 (mod n).
2.3 Pravděpodobnost a statistika Klasická definice pravděpodobnosti tvrdí, že všechny elementární jevy jsou stejně možné. Pravděpodobnost toho, že nastane jev A, pak vypočteme podle vzorce P(A) =
Ω
,
kde m(A) udává počet příznivých jevů a Ω) udává počet všech možných jevů. Pravděpodobnost se obecně označuje číslem od 0 do 1. Pokud jev může nastat, pak je pravděpodobnost 1, pokud nemůže nastat, pravděpodobnost je 0.
Definice 2.3.1. Nechť A a B jsou náhodné jevy a platí P(B) > 0. Podmíněnou pravděpodobnost jevu A za podmínky, že nastal jev B, definujeme vztahem: ǀ
∩
Definice 2.3.2 Druhy četností 1. Provedeme-li náhodný výběr o rozsahu n, mohou se některé hodnoty opakovat vícekrát. Počet výskytů ni hodnoty xi označujeme jako absolutní četnost hodnoty x i. 2. Je-li ni absolutní četnost hodnoty xi a n je rozsah náhodného výběru, potom: nazýváme relativní četnost hodnoty xi, -
100 #
nazýváme procentní relativní četnost hodnoty xi.
3. Komulativní absolutní četností rozumíme součet všech četností, které nepřevyšují hodnotu xi.
32
&
$ %
%'(
4. Komulativní relativní četností rozumíme součet všech relativních četností, které nepřevyšují hodnotu xi. &
%
$
%'(
2.4 Permutace Pojem permutace se řadí mezi základní pojmy v různých oblastech, jako je například kombinatorika, algebra, ale také i kryptografie. Definice 2.4.1 Nechť A = {1, …, n} je n-prvková množina. Permutací na množině A rozumíme libovolné uspořádání prvků množiny A, tj. libovolnou uspořádanou n-tici tvořenou právě všemi prvky množiny A. Permutace se zapisují následovně π )
1 π1
…
+, … π
kde první řádek určuje pozici v uspořádané n-tici a druhý nám dává prvky z množiny A, které se na řečené pozici nachází. 1 … - se nazývá identita a označuje idn, resp. 1. Permutace 1 … … π - π.( tvoří inverzní prvek k permutaci π. …
Permutace ,
π1
,
1
U klasických šifer se setkáváme se zobrazeními mezi dvěma konečnými množinami P, C: - Zobrazení „na“ (surjekce): / : P → C, jestliže má každý prvek z C alespoň jeden vzor (∀1 ∈ 2 ∃4 ∈ 5 64 1)
- Prosté zobrazení (injekce): přiřazuje různým vzorům různé obrazy. ∀74(, 49 ∈
5 :41 42 ⇒ 641 642
- Bijekce: je zobrazení prosté a surjektivní, tj. ǀPǀ = ǀCǀ
33
3 ŠIFROVÁNÍ POMOCÍ VELKÝCH PRVOČÍSEL – RSA Dosud jsme se setkali pouze s šiframi symetrickými, které využívají k šifrování i dešifrování stejného klíče. Tento druh šifrování může být bezpečný, avšak pokud se klíč dostane do rukou nepřátel, pak je tajná komunikace prozrazena. Díky této skutečnosti zde nastává otázka, jak se vyvarovat prozrazení. Výsledek zkoumání byl postaven na komunikaci o dvou klíčích s názvem asymetrická šifra. Pro připomenutí: Asymetrická šifra znamená, že každý účastník komunikace má klíč soukromý a veřejný. K šifrování používá veřejně známý klíč, proto zašifrovat zprávy může kdokoli, ale odšifrovat už může jen ten, kdo má tajný dešifrovací klíč. Mezi asymetrické šifry řadíme asi nejznámější metodu, která je nazvána podle autorů (Rivest, Shamir, Adelman) a byla objevena 4. dubna 1977. Základ se však nachází už v 18. století u Leonharda Eulera, který definoval teorie, na kterých je RSA založeno. Kvůli cenzuře publikací v oblasti kryptografie od NSA (Národní bezpečnostní agentura USA) čekal článek o RSA na uveřejnění 8 měsíců. Díky vlastnosti dvou klíčů je metoda RSA jednou z nejbezpečnějších, což znamená, že ze znalosti veřejného klíče nejde odvodit tajný klíč k dešifrování. Vyplývá to z tzv. jednosměrné funkce, ke které sice inverzní funkce existuje, ale vypočítat ji je nesmírně pracné a časově náročné. „Matematický popis metody RSA vlastně vynalezli W. Diffie a M. E. Hellman již v roce 1976 tím, že zavedli pojem tzv. jednosměrné funkce.“21 Jejich práce se spíše věnovala bezpečnosti digitálních podpisů. Definice 3.1 (Jednosměrná funkce) Nechť A a B jsou nějaké podmnožiny celých čísel. Pak funkci f: A → B nazveme jednosměrnou, jestliže pro každé x ∈ A je „snadný“ výpočet funkční hodnoty f (x), avšak pro libovolnou hodnotu y z oboru hodnot f(A) = {y ∈ B; ∃ x ∈ A: y = f(x)} je „velice obtížné“ (technicky neproveditelné) najít x
∈ A tak, aby platilo
21
KŘÍŽEK, M. a spol. Kouzlo čísel. Str. 178.
34
y = f(x) f nebo f(x) ≡ gx (mod p), kde p je velké prvočíslo, g je primitivní kořen modulo p a 0 ≤ f (x) < p je zbytek. Metoda RSA, RSA, která se opírá o Eulerovu-Fermatovu Eulerovu Fermatovu větu (2.2.7), je využívána k bezpečnému přenosu tajných dat v bankách nebo také v americké armádě.
3.1 Šifrování veřejným klíčem V oblasti moderní kryptografie se setkáváme s následujícím označením pro účastníky komunikace: Alice a Bob. Jsou to dvě fiktivní postavy, mezi kterými probíhá komunikace (Obrázek 8). 8) Do o konce 70. let minulého století se používalo pouze označení „osoba A“, „osoba B“. B“. Někdy můžeme najít ještě Carol a Evu (odvozeno z „eavesdropper“ = špion). Eva není zapojena do systému. Pokud by dostala kopii veřejného klíče, může poslat zašifrované zprávy stejně jako Bob Alici. Avšak není v jejích možnostech zprávu dešifrovat. V tom je bezpečnost metody RSA.
Obrázek 8: Schéma RSA Zdroj: www.google.cz [online] Zdroj
35
Předpokládejme, že si chtějí Alice a Bob vyměnit zašifrovanou zprávu. Vyměňují si zprávy menší než předem dané velké přirozené číslo N. Postup je následující:22 1. Zpráva se nejdřív musí převést na řetěz číslic z přirozených čísel. Alice si zvolí dvě různá 100–200ciferná prvočísla pA a qA, která mají následující vlastnost: nA = pA · qA > N. Pak je potřeba vybrat číslo eA, které je nesoudělné s ϕ(nA) = ϕ(pA · qA) = (pA – 1) · (qA – 1), kde eA je šifrovací exponent. Počítači trvá tato operace pouhou sekundu, ale zpětné rozložení na dva prvočinitele by trvalo mnohem déle, než je stáří vesmíru. Poté musí Alice spočítat inverzi čísla eA v ℤ< = s označením dA, což je dešifrovací exponent. Nakonec Alice zveřejní svůj veřejný klíč KE,A = (nA, eA), ale svůj soukromý klíč KD,A = (nA, dA) si musí nechat pro sebe. 2. Postup z Bobovy strany je stejný. Vygeneruje si veřejný klíč KE,B = (nB, eB) a soukromý klíč KD,B = (nB, dB). 3. Bob zná veřejný klíč Alice KE,A = (nA, eA) a pokud chce poslat Alici přirozené číslo z, musí si spočítat x = > ?= v ℤ = , kde x je zašifrovaná zpráva. Číslo x < nA a platí x ≡ > ?= (mod nA).
4. Alice zjistí x tak, že spočítá v ℤ = mocninu 4 @= = z.
z ≡ 4 @= (mod nA).
Věta 3.1.1 Jestliže eA ∈ ℕ je nesoudělné s ϕ(nA), pak existuje právě jedno dA ∈ ℕ menší než ϕ(nA) takové, že e · d ≡ 1 (mod ϕ(nA)). Příklad pro ilustraci:23 Předpokládejme, že Bob chce poslat zprávu SOS. Pokud každému písmenu v abecedě přiřadíme číslo od 1 do 26, pak nám vyjde SOS = 191519 = z. Zašifrovat
22 23
VELEBIL, Jiří. Diskrétní matematika: Text k přednášce [online]. Str. 93 KŘÍŽEK, M. a spol. Kouzlo čísel. Str. 177.
36
zprávu můžeme ale jinými způsoby, například se text převede do ASCII binárních číslic. Nechť si Alice zvolí dvě prvočísla, například pA = 491 a qA = 701. Potom nA = pA · qA = 491*701 = 344 191 a ϕ(nA) = ϕ(pA · qA) = (pA – 1) · (qA – 1) = 490·700 = 343 000. Poté si vybere číslo eA = 3, které je nesoudělné s ϕ(nA). Zprávu z zašifrujeme na x následovně x ≡ > ?= (mod nA) x ≡ 1915193 (mod 344 191) x = 224 717. Z Eulerovy funkce (viz 2.1.8) si připomeneme vztahy: ϕ(p) = p – 1 a ϕ(pm) = (p – 1) · pm – 1, kde p je prvočíslo a m ∈ ℕ. Další důležitou vlastností Eulerovy funkce je implikace: (k, n) = 1 ⇒ ϕ(k · n) = ϕ(k) · ϕ(n). Těchto dvou vztahů můžeme využít pro výpočet d. Při jejich opakovaném užití a po prvočíselném rozkladu dostaneme: ϕ(ϕ(n)) = ϕ(343 000) = ϕ(23 · 53 · 73) = ϕ(23) ϕ(53) ϕ(73) = 4 · 100 · 294 = 117600. Z Eulerovy-Fermatovy věty (2.2.7) plyne implikace (e, ϕ(n)) = 1 ⇒ e ϕ(ϕ(n)) ≡ 1 (mod ϕ(n)). Nyní využijeme vztahu (věty 3.1.1) e · d ≡ 1 (mod ϕ(nA)) a dostaneme vyjádření pro dešifrovací exponent d < ϕ(nA) d ≡ d · e ϕ(ϕ(n)) ≡ e · d · e ϕ(ϕ(n)) – 1 ≡ e ϕ(ϕ(n)) – 1 (mod ϕ(n))
37
d ≡ 3117599 (mod 343000) d = 228667. Pak zpětně dosadíme do rovnice z ≡ 4 @= (mod nA) z ≡ 224717228667 (mod 344191) z = 191519, což nám dává po odšifrování SOS.
3.2 Bezpečnost RSA RSA a její bezpečnost spočívá na doposud nedokázaných hypotézách. Není výpočetně možné faktorizovat dostatečně velké číslo n (součást veřejného klíče). Součinitele znají pouze autoři čísla n. Pokud chce někdo rozluštit RSA, narazí na problém složitosti faktorizace. Avšak dokázáno to není. „Je to paradox! Ti počítačoví vědci, kteří založí poměrně velmi jednoduše aplikovatelnou šifru na nejtěžším matematickém problému (problém rance), prohrají, protože šifra je rozbita jinak než přes složitý problém. A naopak ti, kteří poměrně složitě realizovatelnou šifru založí na nedokázaných předpokladech, vytvoří světový standard!“24 Autoři RSA se vsadili o 100 USD, že nikdo nerozšifruje jejich text zašifrovaný metodou
RSA
s veřejným
exponentem
e = 9007
a
modulem
n = 1143816257578888676692357799761466120102182967212423625625618429357 06935245733897830597123563958705058989075147599290026879543541. Dále bylo řečeno, že modul je součinem 64ciferného a 65ciferného prvočísla. Jeden z autorů Rivest vypočítal, že rozklad čísla n faktorizační metodou na prvočinitele by trval 40 000 000 000 000 000 let.25 Ale v dubnu roku 1995 se podařilo roznásobit 129ciferné číslo, jelikož metody faktorizace prošly neuvěřitelným rozvojem. Zde se nabízí otázka, zda tento fakt bude mít nějaký vliv na bezpečnost RSA.
24 25
KLÍMA, Vlastimil. Utajené komunikace (Šifra RSA): Šifrový šampión in Chip. Str. 138. KLÍMA, Vlastimil. Utajené komunikace (Šifra RSA): Šifrový šampión in Chip. Str. 138.
38
Věta 3.2.1 (O bezpečnosti RSA) Předpokládejme, že číslo n je součinem dvou neznámých různých prvočísel p a q. Znalost těchto prvočísel je ekvivalentní znalosti čísla φ (n). Důkaz: Jestliže známe prvočíselný rozklad n = p · q, snadno se pak dostaneme k Eulerově funkci ϕ(n) = (p – 1) · (q – 1). Pokud ale známe ϕ(n), tak pro sudé n je
jednoduché přijít na prvočíselný rozklad p = 2, q = . Ale při lichém n musíme najít 9
prvočísla p a q. Víme, že ϕ(n) = (p – 1) · (q – 1) = n + 1 – (p + q) (p + q) = n + 1 - φ(n), p · q = n. Z předchozích vztahů vidíme, že prvočísla p a q jsou kořeny kvadratické rovnice. Jelikož počítáme s lichým číslem n, číslo p + q musí být sudé, proto jej označíme 2 · r. Z toho nám vyplývá kvadratická rovnice ve tvaru x2 – 2 · r · x + n = 0 s kořeny p= q
9#AB √C#A D .C# 9
9#A . √A D .C# 9
= r + √E 9 F
= r – √E 9 F .
Ilustrační příklad:26 Máme dáno n = 51 937 a ϕ(n) = 51 460. Nyní můžeme dosadit do rovnice ϕ(n) = (p – 1) · (q – 1) = n + 1 – (p + q) 51 460 = 51 937 + 1 – (p + q) (p + q) = 478 p · q = 51 937.
26
VELEBIL, Jiří. Diskrétní matematika: Text k přednášce [online]. Str. 93
39
Následně sestavíme kvadratickou rovnici x2 – 478 · x + 51 937, odkud už můžeme vypočítat kořeny p a q. p = 239 I √2399 F 51937 p = 311 q = 239 F √2399 F 51937 q = 167. Věta 3.2.2 (O korektnosti RSA) Pokud je x = > ?= v ℤ = , pak 4 @= = z v ℤ = . Důkaz: Nejprve si označme > ?= @= = z*. Naším úkolem je dokázat rovnost z = z* v ℤ = . Jelikož v ℤ< = platí rovnost eA · dA = 1, existuje přirozené číslo k takové, že eA · dA = 1 + k # L . Poté platí z* = > ?= @= = >(B%#< = = z.
40
4 KÓDOVÁNÍ V PŘÍRODNÍCH VĚDÁCH Základní rozdíl mezi šifrováním a kódováním vězí v tom, že při šifrování používáme tajný klíč, díky kterému zprávu můžeme zašifrovat či odšifrovat. Kdežto kódování je transformace jedné formy textu do formy jiné. Použitím této transformace se má usnadnit komunikace mezi lidmi, která je veřejná a pro všechny známá (například Morseova abeceda, genetický kód, kód SOS, …). Již od starověku se vědci a matematici snažili vytvářet nástroje k řešení a definování metod zdánlivě nedefinovatelného. Chtěli popisovat abstraktní pojmy a pochody ve fyzice, chemii, biologii, matematice či v oblasti času nebo zvuku. Výsledkem jejich snažení bylo vytvoření jednotných univerzálních jazyků, které usnadňují dorozumívání vědců po celém světě. Příkladem mohou být značky prvků periodické soustavy nebo například matematický symbol pro Ludolfovo číslo π. S nástupem dešifrovacích technik, které jsou založené na matematických a lingvistických metodách (například na frekvenční analýze), vyšlo najevo, že velká většina substitučních šifer je díky nim rozšifrovatelná. Tyto metody zajistily také nové techniky pro moderní kryptografické systémy po vzniku výpočetní techniky. Do té doby mnohé ze substitučních šifer zůstaly nerozluštěny.
4.1 Matematika „Matematika je čistě abstraktní vědou. Používá se k popisu procesů vyvolávajících fyzikální jevy, které by jinak zůstaly nepopsatelné. Matematici vytvořili vlastní „šifrovaný“ jazyk složený ze znaků, symbolů a čísel, pomocí něhož vyjadřují své myšlenky. Matematika je vnitřně propojena s kryptografií.“27 Speciálně geometrie se snaží popisovat fyzický svět, který nás obklopuje. Hledala cesty, jak popsat délky a velikosti věcí a také vztahy mezi nimi. Eukleidés vytvořil kolem roku 300 před naším letopočtem dílo s názvem Základy, kde shrnul dřívější poznatky řeckých matematiků a filosofů. Mimo jiné ji obohatil o vlastní poznatky z oblastí jako teorie čísel nebo optiky. Mnoho důležitých vzorců známe již od
27
LUNDE, Paul. Tajemství kódů, str. 158.
41
pythagorejců. Ti definovali vlastnosti dvoudimenzionálních a třídimenzionálních forem a k nim základní principy, které jsou dodnes platné. Popsali především vlastnosti čtverců, krychlí, trojúhelníků a kružnic a jejich algebraické vyjádření. • Pythagorova věta (Obrázek 9) popisuje vztah mezi délkami stran pravoúhlého trojúhelníku. Spojuje znalosti o čtvercích a trojúhelnících, a tím poskytuje cesty pro stovky dalších důkazů v oblasti matematiky. Obsah čtverce sestrojeného nad přeponou pravoúhlého rovinného trojúhelníku je rovna součtu obsahů čtverců nad jeho odvěsnami. Celá tato dlouhá matematická věta je zakódována následovně: c2 = a2 + b2. Všem na světě je dobře známá, jelikož je součástí osnov matematiky na základní škole. Proto nemusíme znát jazyk, abychom se matematicky domluvili v cizí zemi. Na obrázku můžeme vidět grafické znázornění:
Obrázek 9: Pythagorova věta Zdroj: www.google.cz [online]
Obrázek 10: Kosinova věta Zdroj: www.google.cz [online]
Zobecněním Pythagorovy věty lze definovat kosinovu větu (Obrázek 10). U kosinovy věty nepracujeme s pravoúhlým trojúhelníkem, nýbrž s obecným: c2 = a2 + b2 – 2ab cos γ. • Jako jiný příklad kódu v matematice uvedeme zlatý řez: „Pythagorejský objev Zlatého řezu poskytl základní harmonický poměr, který se odráží nejen v diatonické stupnici hudební harmonie, ale ukazuje se též jako ideální
42
proporce v architektuře či v kompozici malby. Zlatý řez vychází z poměru mezi čtvercem, kružnicí a obdélníkem.“28 • Dalším velmi známým matematickým kódem může být transcendentní číslo π (pí). Číslo π nelze zapsat v desítkové soustavě uzavřeným zápisem a je propojeno s vlastnostmi kruhu. Každý ví, že se při počítání obvodu a obsahu kruhu neobejdeme bez znalosti čísla π. Jeho hodnota na 50 desetinných míst je tato: 3,14159265358979323846264338327950288419716939937510. • Převratným objevem v oblasti matematiky byl pojem „Karteziánských souřadnic“ od francouzského vzdělance Reného Descarta. Díky němu lze popsat polohu bodu ve vztahu k přímkám a plochám. Ač se to nezdá, matematika se po stovky let vyjadřovala pomocí vět. Postupně se však začala zkracovat, až do dnešní podoby vypadající jako šifrový jazyk. • Imaginární jednotka se definuje jako odmocnina z mínus jedné. Rozšiřuje obor reálných čísel ℝ na obor komplexních K. √F1 = i • Matice se využívá k transformaci čísel a vektorů. Usnadňuje práci při počítání soustav rovnic o několika neznámých. Matice je zobrazení nad tělesem T {1, 2, …, k}
×
{1, 2, …, i} → T, kde k označuje počet sloupců, i označuje počet
řádků. N A2,2 = , P
O P
4.2 Fyzika I vědci v oblasti fyziky vytvořili speciální jazyk k vysvětlení a popsání fyzikálních jevů. Jak velký je metr? Jak dlouhá je hodina? Jakou rychlostí jdeme? To vše popisuje fyzika, speciálně obor mechanika. Základy položili opět staří Řekové, kteří se snažili pochopit působení sil ve vesmíru. Některé jednotky veličin mají svoji definici, která 28
LUNDE, Paul. Tajemství kódů, str. 154.
43
bývá neuvěřitelně složitá, proto jsou definice zakódovány v jednoznačný a jednoduchý pojem. Některé fyzikální pojmy: • Sekunda – „Doba trvání 9 192 631 770 period záření, které odpovídá přechodu mezi dvěma hladinami velmi jemné struktury základního stavu atomu 133Cs.“29 • Metr – „Metr je délka, kterou urazí světlo ve vakuu za 1/299 792 458 s.“30 • Světelný rok – „Astrofyzikální jednotka – vzdálenost, kterou urazí světlo za rok, tj. za 365,25 pozemských dní: 9 460 730 472 580 800 m.“31
4.3 Chemie Počátky moderní chemie můžeme najít ve středověku u alchymistů. Ti se snažili najít a proměnit „kámen mudrců“ ve zlato. Začali zkoumat vlastnosti látek, které znali. Později poznávali prvky, ze kterých je složen celý vesmír. Těchto prvků bylo tolik, že nezbylo nic jiného, než vytvořit nový „kódovaný jazyk“. Ve zkratce tak mohli vyjadřovat všechny prvky a jejich funkce. Soustavu všech prvků můžeme dnes najít v Periodické tabulce prvků (Obrázek 11), kterou vytvořil v roce 1869 Rus Dimitrij
Obrázek 11: Periodická soustava prvků Zdroj: www.google.cz [online]
29
LUNDE, Paul. Tajemství kódů, str. 157. LUNDE, Paul. Tajemství kódů, str. 157. 31 LUNDE, Paul. Tajemství kódů, str. 154. 30
44
Mendělejev. Má své specifické uspořádání, tvoří ji prvky v 18 sloupcích (skupinách) a 7 řadách (periodách). Prvky jsou zařazeny do tabulky podle počtu valenčních elektronů. Už na základní škole, ale i v průběhu celého života se seznamujeme s chemickými šiframi. Každý z nás zná alespoň pár chemických vzorečků, kterými se vyjadřují některé sloučeniny. Ve zkratce popisují molekulární strukturu látky. Pro příklad si připomeneme některé nejznámější sloučeniny: • CO2 – oxid uhličitý, obsahuje jeden atom uhlíku a dva atomy kyslíku • NaCl – chlorid sodný, je tvořen atomem sodíku a atomem chloru • H2SO4 – kyselina sírová, je z atomu síry, dvou atomů vodíku a čtyř atomů kyslíku • NH3 – čpavek neboli amoniak, je složen z atomu dusíku a tří atomů vodíku
4.4 Geografie „Kartografie je jedním z nejoblíbenějších systémů kódování informací, které kdy byly vynalezeny. Kartografie jako způsob popisu složitosti světa, který nás obklopuje, a to ani nemluvě o satelitním polohovém systému GPS a dokonalosti virtuálního globu Google Earth, je ve své pružnosti a informační bohatosti nedostižná.“32 Mapy nám chtějí sdělit, jak se dostaneme z jednoho místa na jiné. Obsahují neskutečné množství informací, které se rozlišují graficky pomocí různých nástrojů, jako jsou mřížky, čáry, symboly, odstíny a další. Důležité je také měřítko, v jakém se vzdálenost udává. Ke každé mapě náleží legenda (Obrázek 12), která udává kódovaná slova objevující se v mapě. U mnoha kultur z dávných dob můžeme vidět, jak se snažili popisovat krajinu. Nejstarší malby se objevují na skalách či v jeskyních. Na všech těchto malbách zkoušeli zachytit či zakódovat krajinné prvky a překvapivě jsou si tato zobrazení velmi podobná. Během 500 let se formovaly různé konvence, jak graficky popsat okolní svět. Moderní technologie už si umí pohrát se skutečnostmi tak podrobně, že dokáží detailně vytvořit povrch zemského reliéfu.
32
LUNDE, Paul. Tajemství kódů, str. 164.
45
Obrázek 12: Příklad mapy s legendou Zdroj: www.google.cz [online]
4.5 Biologie V oblasti biologie se setkáváme s taxonomickým „kódem“ neboli biologickou organizací všech forem života na Zemi, abychom poznali sebe i své příbuzné druhy. Je neskutečné množství živých i neživých forem přírody, které existují. O jejich pochopení, jak fungují, jaké jsou jejich vzájemné vztahy, se snažili vědci již od antiky. Až v 18. století se podařilo švédskému přírodovědci Carlu von Linnému navrhnout systém klasifikace organismů, který se zakládal na fyzických podobnostech. Tomuto systému se věnoval také Charles Darwin a propracoval se ke genetickému kódu, který je nejzákladnější. Tento kód najdeme v každém organismu, v DNA. Dává rozkazy, jak budeme vypadat, jak se budeme chovat a především, jak má pracovat celé naše tělo. Cílem výzkumu DNA má být porozumění, zda máme nějaké shodné znaky se zvířaty či rostlinami. Dosud jsme se bavili o kódech, které vynalezli lidé. Kód DNA je ale výtvorem přírody. DNA je jakýsi stavební plán člověka, je nám daný a díky němu je každý z nás unikátní. Nikde na světě nenajdeme dva lidi se stejnou DNA. Proto se jeho rozluštění řadí k největším úspěchům vědecké činnosti. „DNA všech živých tvorů na světě je podobná. Patrně je tomu tak proto, že se všichni vyvinuli z nejranější formy života na zemi – z bakterie.“33
33
ADAMS, Simon. Šifry a kódy: od hieroglyfů po hackery. Str. 73.
46
ZÁVĚR Cílem této bakalářské práce bylo uvědomění si, jak matematika souvisí s kryptologií. Problematika šifrování je opravdu velmi obsáhlé téma, přesto není moc žádaná. Pokud se někdo vyloženě nezajímá o ochranu dat, pak se k tématu stěží dostane. Proto dalším záměrem této práce je podnítit zájem veřejnosti o šifry. V první kapitole jsme se dozvěděli o počátcích a vývoji šifrování. Dostali jsme se až k vynálezům jako je počítač a mobilní telefon. Navíc už víme, že sem patří i obor steganografie, který se zabývá ukrýváním zprávy například v textu, neviditelným inkoustem nebo třeba v hlasové zprávě. Také jsme si shrnuli vývoj české kryptologie, která ve světě není nijak významná. Druhá kapitola byla věnována matematickým definicím a větám, na kterých je šifrování založeno. Pro nás měla nejdůležitější význam Eulerova funkce, na které je postavena moderní metoda šifrování RSA, která je zmíněna ve třetí kapitole. RSA vznikla na základě jednosměrné funkce a existence dvou klíčů, veřejného a soukromého. A poslední kapitola se věnuje stručnému shrnutí kódových jazyků v přírodních vědách. Ve všech oborech se vytvořil specifický kódovaný jazyk. Na základní škole není o problematice teorie šifrování ani zmínka, přestože se s kryptologií, jak jsme již poznali, setkáváme na každém kroku. S šiframi se školáci mohou potkat při různých hrách, a to především na táborech. Mezi nejznámější substituční šifry můžeme zmínit Morseovu abecedu, semaforovou a vlajkovou abecedu, polský kříž, zlomkovou šifru. K transpozičním šifrám řadíme hadovky. Používáním těchto i již zmíněných šifer by se mohly ozvláštnit hodiny matematiky, staly by se zábavnější a jistě zajímavější i pro odpůrce matematiky. Luštění šifer podporuje logické myšlení, spolupráci ve skupinách, představivost a tvořivost.
47
SEZNAM POUŽITÉ LITERATURY LUNDE, Paul. Tajemství kódů: [nahlédněte do světa skrytých poselství: ilustrovaný průvodce znameními, symboly, šiframi a tajnými jazyky]. České 1. vyd. Praha: Svojtka & Co., 2013, 279 s. ISBN 978-80-256-0978-1 ADAMS, Simon. Šifry a kódy: od hieroglyfů po hackery. 1. vyd. Praha: Slovart, 2003, 96 s. ISBN 80-7209-503-x POSKITT, Kjartan. Šifry: od Caesara ke kreditním kartám. 1. vyd. V Praze: Egmont, 2009, 157 s. ISBN 978-80-252-1213-4 KIMPTON, Diana. Mazané kódy. 1. vyd. V Praze: Egmont, 2005, 156 s. ISBN 80-2520236-4 VONDRUŠKA, Pavel. Kryptologie, šifrování a tajná písma. 1. vyd. Praha: Albatros, 2006, 340 s. ISBN 80-00-01888-8 GAJDOŠ, Petr. Asymetrická šifra RSA in Letní škola učitelů matematiky a fyziky. Ústí nad Labem: Univerzita J. E. Purkyně v Ústí nad Labem, 2008. ISBN 978-80-7414-1218 SINGH, Simon. Kniha kódů a šifer: tajná komunikace od starého Egypta po kvantovou kryptografii. 1. vyd. v českém jazyce. Praha: Dokořán, 2003, 382 s. ISBN 80-86569-187 BERLOQUIN, Pierre. Skryté kódy a velkolepé projekty: tajné jazyky od starověku po současnost. 1. vyd. Praha: Knižní klub, 2011, 375 s. ISBN 978-80-242-2847-1 GROŠEK, Otokar, Milan VOJVODA a Pavol ZAJAC. Klasické šifry. 2. vyd. Bratislava: Nakladateľstvo STU, 2011, 214 s. ISBN 978-80-227-3486-8 HANŽL, Tomáš, Radek PELÁNEK a Ondřej VÝBORNÝ. Šifry a hry s nimi: kolektivní outdoorové hry se šiframi. 1. vyd. Praha: Portál, 2007, 198 s. ISBN 9788073671969 JANEČEK, Jiří. Rozluštěná tajemství: luštitelé, dešifranti, kódy a odhalení. 1. vyd. Praha: XYZ, 2006, 268 s. ISBN 80-86864-54-5
48
KŘÍŽEK, Michal, Lawrence SOMER a Alena ŠOLCOVÁ. Kouzlo čísel: od velkých objevů k aplikacím. 1. vyd. Praha: Academia, 2009, 365 s., [8] s. barev. obr. příl. ISBN 978-80-200-1610-2. ŠKOPEK, Pavel. 3 šifry starověku: Vojenské rozkazy i tajemství Bible in Epocha: svět na vaší dlani. Praha: RF Hobby, 2010, č. 21, s 44-45. ISSN 1214-9519. KLÍMA, Vlastimil. Utajené komunikace (Šifra RSA): Šifrový šampión in Chip: počítačový magazín. Praha: Vogel Publishing, 1995, č. 4, s. 136-138. ISSN 1210-0684. KLÍMA, Vlastimil. Utajené komunikace (Nejrozsáhlejší počítačový experiment na Internetu): Internet a RSA in Chip: počítačový magazín. Praha: Vogel Publishing, 1995, č. 6, s. 174-175. ISSN 1210-0684. VELEBIL, Jiří. Diskrétní matematika: Text k přednášce [online]. 2007 [cit. 12. září 2015]. Dostupný na World Wide Web:
49
SEZNAM OBRÁZKŮ Obrázek 1: Klínové písmo
11
Obrázek 2: Skytalé
12
Obrázek 3: Polybiův čtverec
12
Obrázek 4: Albertiho šifrovací disk
15
Obrázek 5: Šifrovací mřížka
16
Obrázek 6: Vigenérův čtverec
17
Obrázek 7: Přístroj Enigmy
19
Obrázek 8: Schéma RSA
35
Obrázek 9: Pythagorova věta
42
Obrázek 10: Kosinova věta
42
Obrázek 11: Periodická soustava prvků
44
Obrázek 12: Příklad mapy s legendou
46
SEZNAM TABULEK Tabulka 1: Ceasarova šifra
13
Tabulka 2: Vigenérova šifra
17
Tabulka 3: Přepis vybraných písmen do binárního kódu
23
Tabulka 4: Přepis vybraných písmen a číslic do kódu ASCII
23
50
