Šifrovanie

Šifrovanie
Nie je to tak dávno, kedy bolo šifrovanie zložkou len akčných filmov, armádnych akcií, tajných služieb a rôznych  špionáží. V súčasnosti sa však šifrovanie stáva našim každodenným spoločníkom. Napríklad komunikácia v bankovníctve, ako je prezeranie účtov cez Internetbanking prebieha šifrovane. Taktiež komunikácie cez mobilné telefóny GSM prebiehajú šifrovane. Tieto malé detaily si ako bežný používatelia vôbec neuvedomujeme.
So zavedením šifrovanej komunikácie súvisel aj vznik nových vedeckých odborov, ktoré sú kryptografia a kryptoanalýza. Kryptografia sa zaoberá tvorbou šifier, kým kryptoanalýza sa zaoberá samotným lúštením rôznych šifier. Obidve vedy sú zahrnuté vo vednom odbore kryptológia.
Mojím cieľom v tejto práci je prejsť historickým vývojom šifier a šifrovacích systémov, rozdeliť spôsoby šifrovania, vysvetliť niektoré jednoduchšie postupy šifrovania a tiež, hlavne pri najmodernejších šifrách, ukázať na využitie matematiky v praxi.

1.História
1.1 Starovek
Šifrovanie je tak staré ako stará je dovednosť ľudstva písať. To nás posiela približne 4000 rokov do minulosti do starovekého Egypta a Mezopotámie. Zatiaľ čo Egypťania používali len jednoduché utajovanie informácií ako napríklad zamenenie skupiny hieroglifov za jeden. V Mezopotámii neskôr začali zamieňať písmená za foneticky podobné. Prvá skutočná mechanická šifra pochádza z antického Grécka. Využili ju spartskí stratégovia a tento šifrovací systém dostal názov Skytalé, používajúci dve palice rovnakého priemeru. Pri šifrovaní sa okolo palice obmotal kus plátna, tak aby sa jednotlivé vrstvy čiastočne prekrývali, následne sa na ne napísala správa. Po odmotaní, látka obsahovala len nečitateľné časti písmen. (obr.1) Správu si mohol prečítať len majiteľ palice s presne rovnakým priemerom ako prvá palica. V roku 360 p.n.l. Aineias Taktikos napísal dielo „Taktika“, kde v jednej časti uviedol 16 rôznych  šifrovacích metód. Jedna z nich je založená na podobnom princípe ako morzeovka. Niektoré sú vysvetlené ako nahradzovanie znakov gréckej abecedy číslami. Je to vlastne spôsob manipulácie s údajmi v dnešnej kryptografii.

Okolo roku 50 pred naším letopočtom bola vytvorená asi najznámejšia šifra. Šifra Júlia Ceasara- Ceasarova šifra. Ide o substitučnú metódu, kedy sa písmeno abecedy nahradilo písmenom nasledujúcim. Takto sa môže vytvoriť množstvo šifier, závisí to však od veľkosti posunu písmen. Napríklad „ahoj“ pri veľkosti posunutia n=3 (n= hodnota posunu) by v Ceasarovej šifre vyzeralo „dkrm“. V tej dobe Ceasarova šifra predstavovala vrchol kryptografie a bola prakticky nerozlúštiteľná.

1.2 Stredovek
V stredoveku sa začala písať čoraz viac kníh, ktoré sa venovali kryptológii. Prvá z prác bola od Leona Battista Albertiho. Jeho dielo má 25 strán, ktoré napísal v západnej Európe. Táto práca obsahuje množstvo lúštiteľských postupov na základe jazykových schopností, taktiež roztriedenie systémov šifrovania, objav polyalfabetickej substitúcie a šifrovanie kódov. K substitúcii Alberti vytvoril šifrovací disk, ktorý sa skladal z dvoch otáčavých kotúčov znázorňujúce zašifrované a otvorené znaky. Medzi prvé tlačené knihy zaoberajúce sa kryptológiou patrí kniha od benediktínskeho mnícha Johannesa Trithemiusa. V jeho piatej knihe „Polygraphiace libri sex“ bola zavedená tabuľka „tabula recta“, ktorá je základom pre polyalfabetické šifry. V roku 1553 vyšla brožúra „La cifra“ popisujúca kryptosystém, ktorého základom je tajný kľúč. Týmto tajným kľúčom bola veta alebo slovo, ktoré sa opakovane písalo nad otvorený text. Každé písmeno otvoreného textu bolo potom  šifrované abecedou. Pri tomto šifrovaní sa používala Trithemiusová tabuľka. V tomto systéme už význam a úloha kľúča vystupujú do popredia. Jeden a ten istý systém je možné podľa potreby variabilne meniť. Tento systém bol základom pre vznik kľúča, ktorým je samotná správa. V roku 1586 tento systém navrhol Francúz Blaisede Vigenere v knihe „Traicté des Chiffres“. (obr. 2)  Navrhol tu autokľúč. Je to kľúč, ktorý sa sám reprodukuje. Vignere použil ako kľúč len jedno písmeno, zašifroval ním prvé písmeno otvoreného textu a výsledné písmeno šifrového textu použil ako nasledujúce písmeno kľúča. Kľúč sa teda vytváral automaticky.
 
1.3 Novovek
V novoveku sa čoraz viac začali využívať šifrovacie prístroje. Ponúkali jednoduchý spôsob šifrovania a dešifrovania. Zaručili tým ďalší rozvoj kryptológie. Prvým strojom z tohto obdobia je Jefferesonov valec. (obr. 3) Tento valec sa skladá z 26 rovnakých koliesok, ktoré sú nasunuté na spoločnú os a tým vytvárajú valec. Na obvode každého kolieska sú napísané všetky písmená abecedy v rôznom poradí. Pri šifrovaní sa jednotlivé kolieska proti sebe otáčajú tak, že nakoniec dávajú vo zvolenom riadku na obvode valca požadovanú správu. Každé koliesko bolo očíslované a mohli byť menené alebo prehadzované. Neskôr však Edgar Alan Poe predniesol myšlienku, že ak je ľudský rozum schopný vymyslieť nejakú šifru, dokáže ju teda aj rozlúštiť. Týmto vznikla jedna z najzákladnejších otázok kryptológie- otázka bezpečnosti šifier. Táto otázka je aktuálna dodnes.

Ďalším mechanizmom je Fleissnerova mriežka. Ako prvý ju popísal Fleissner Von Wostrowitz. Je druhou najznámejšou mechanickou pomôckou po sprarťanských drevených paliciach. Vo štvorci nxn políčok vystrihnutých nxn/4 políčok tak, aby pri postupnom otáčaní o 90 stupňov vzniknuté otvory ukazovali vždy iné políčka. Po vyplnení všetkých okienok sa mriežka otočila o 90 stupňov. Nakoniec na papieri vznikol štvorec súvislo vyplnený písmenami. Celý šifrovaný text sa z neho vypisuje po riadkoch. Túto mriežku využila aj nemecká armáda v prvej svetovej vojne, kedy ju jedného času používala ako poľnú šifru. V roku 1917 GilbertVernam zostrojil polyalfabetický šifrovací stroj, ktorý bol schopný používať náhodný a neopakujúci sa kód. Tento systém je dodnes známy ako jediný teoreticky bezpečný kryptosystém. Do stroja sa vkladala dierkovaná páska s otvoreným textom spolu s ďalšou dierkovanou páskou, na ktorej bol náhodne vydierkovaný kľúč. Výhodou tohto stroja bolo, že šifrovanie aj dešifrovanie prebiehalo rovnako. Tento systém ostáva bezpečným za podmienok, ak je kľúč rovnako dlhý ako šifrovaná správa a používa sa iba raz.

V čase vojny sa začali šifrovacie stroje používať častejšie. Najznámejšia je asi nemecká Enigma, ktorá mala predchodcu v prístroji Huga Alexandra Kocha, ktorý zapísal svoj patent šifrovacieho stroja založeného na rotoroch. (obr. 4) O pár rokov neskôr predal tento patent nemeckému inžinierovi Arthurovi Scherbiusovi, ktorý ho vylepšil a nazval ho Enigma. V roku 1923 bola prinesená na trh ako komerčné zariadenie na poštovom kongrese v Berne. V týchto časoch v USA začala existovať kriminálna kryptológia ako reakcia na šifrovanie správ podsvetím. V súčasnosti kriminálna kryptológia predstavuje dôležitú úlohu v boji proti zločinu.

Najznámejšie využite matematiky v kryptológii pochádza od LesteraHilla. V roku 1929 navrhol polygramovú šifru, v ktorej n-gram otvoreného textu (napríklad n-tica písmen) je prevedená na n-gram šifrovaného textu. Písmená sú očíslované od 0 po 25 n-gram je číselný vektor. Kľúčom je invertibilná matica A s rozmermi nxn a šifrovanie prebieha podľa vzťahu ŠT= A*OT.
Šifrovanie je spojené aj s dešifrovacími postupmi. Pri dešifrovaní sú známe mená ako Marian Rejewski, Alan Turing a GordonWelchman, ktorí dešifrovali kód Enigmy. S dešifrovaním musíme spojiť aj meno ako WilliamFriedman, ktorý prelomil kód stroja PURPLE, ktorý používala japonská vláda.

2.Šifrovanie
2.1 Symetrické šifrovanie
Princíp symtrického šifrovanie je založený na tom, že odosielateľ aj prijímateľ správy zdieľajú tajný kľúč , ktorým bola správa odosielateľom šifrovaná a ktorým príjemca túto správu dešifruje. Pred prvou výmenou správ sa partneri musia dohodnúť na spoločnom tajnom kľúči. Medzi prvé symetrické šifrovacie algoritmy patrí DES (DataEncryption Standard), ktorý bol patentovaný v decembri 1976 v USA. Bol to hardvérový šifrátor, ktorý využíva 56 bitový tajný kľúč na šifrovanie 64 bitových blokov dát a v rámci bloku každý výstupný bit šifrátora je závislý na každom vstupnom bite. Koniec tohto algoritmu bolo zverejnenie práce „DifferentialCryptanalysis“, v ktorej bolo popísané ako môže byť táto šifra prelomená. V súčasnosti sa ešte využíva modifikovaná verzia algoritmu DES pod názvom "Triple Des, 3-DES", ktorý pracuje s dvomi alebo tromi 58 bitovými tajnými kľúčmi. Správa sa najprv kryptuje 1. kľúčom podľa DES, dešifruje sa podľa 2. kľúča, a nakoniec sa šifruje podľa prvého alebo tretieho kľúča v závislosti na tom, či používame dvoj alebo trojkľúčový 3-DES. V posledných rokoch vzniklo niekoľko riešení na náhradu šifry DES, z ktorých za zmienku stojí algoritmus IDEA (IdealDataEncryptionAlgorithm). IDEA aplikuje šifru s tajným kľúčom dĺžky 128 bitov na 16 bitový blok dát a pritom zachováva závislosť výstupu od vstupu v rámci 64 bitového bloku. Známe sú ešte symetrické kryptovacie algoritmy ako CAST, Blowfish a RC4.
 
2.2 Asymetrické šifrovanie
Prvé asymetrické šifrovacie algoritmy sa objavili v 70. rokoch nášho storočia. Sú založené na jednoduchej myšlienke: správa je dešifrovaná iným kľúčom než bola šifrovaná. Každý z komunikujúcich partnerov vlastní dvojicu kľúčov, jeden tajný tzv. privátny a jeden verejný. Správa je zakódovaná verejným kľúčom, ktorý je distribuovaný všetkým partnerom dotyčnej osoby, ale len táto osoba môže správu dekódovať svojim privátnym kľúčom. Úloha privátneho a verejného kľúča je symetrická. Ak si označíme V funkciu využívajúcu verejný kľúč, P funkciu pre privátny kľúč a x informáciu na kódovanie, tak platí, že P(V(x))=x a V(P(x))=x. Reprezentantmi asymetrických algoritmov sú RSA (Rivest-Shamir-Adleman) a DH (Diffie-Hellman), respektíve ElGamalovavarianta DH algoritmu. Algoritmus je matematicky založený na Fermatovej vete z teórie čísiel a na fakte, že je mimoriadne ťažké zistiť deliteľov veľkých čísiel.

2.2.1 Asymetrické šifrovanie v praxi
Spočiatku mali asymetrické šifry jeden zásadný problém – rýchlosť. Na vtedajších počítačoch neboli schopné dostatočne rýchlo pracovať. Postupom času sa situácia zlepšovala, ale stále bolo nepohodlné pomocou asymetrickej šifry šifrovať celý dokument. Preto sa dokument šifroval pomocou rýchlejšej symetrickej šifry a kľúč k symetrickej šifre sa zašifroval pomocou asymetrickej šifry. Takto pracuje aj program PGP (Prettygoodprivacy – v preklade Celkom dobré súkromie), ktorý je voľne prístupný na internete.

2.3 Hashovacie funkcie
2.3.1 Čo je to hash?
Hash je jedno veľké číslo (väčšinou s veľkosťou rádovo 2^128– 2^160), ktoré
jednoznačne identifikuje dokument a jeho obsah. Môžeme to prirovnať k odtlačku
prstu u človeka. Dokument na hash premieňa tzv. hashovacia funkcia, označme si ju
H. Jej vstup označme M a jej výstup ako H(M). M môže mať ľubovoľnú veľkosť, od
niekoľkých bajtov až po stovky gigabajtov. A H(M) bude mať vždy veľkosť
charakteristickú pre danú hashovaciu funkciu (2^128– 2^160).

2.3.2 Hashovanie
  Neoddeliteľnou súčasťou tvorby digitálneho podpisu sú hashovacie funkcie, ktoré ľubovoľne dlhý reťazec znakov transformujú na reťazec pevnej dĺžky, nazývaný tiež odtlačok prsta - fingerprint. Hashovacie funkcie pôvodne boli vyvinuté na ukladanie a vyhľadávanie údajov veľkých databánk a na základe dosiahnutých výsledkov ich s obľubou využíva aj kryptografia. Problém tejto funkcie je v tom, že síce zistí príliš veľkú zmenu, no napríklad vymenenie dvoch alebo troch prvkov medzi sebou výsledok funkcie nezmení. Veľmi dôležitou aplikáciou hashovacích funkcií je overovanie hesiel vo viacpoužívateľských operačných systémoch. Na túto operáciu sa používa hashovacia funkcia MD5. Keď používateľ zadá heslo, hashovacia funkcia vytvorí tzv. „messagedigest“ (označujeme ním výstup hashovacej funkcie). Ak súhlasí s messagedigestom uloženým v systéme, autentifikácia prebehne úspešne a používateľ je prihlásený do systému. V systéme však nie sú nikdy uložené heslá, ale iba ich messagedigesty. Takže sa nedajú žiadnym spôsobom dešifrovať. Hashovacia funkcia je jednosmerná a stráca údaje, dá sa len overiť, či z dvoch textov vznikne rovnaký messagedigest.
 
2.4 Šifrovanie v každodennom živote
Občas si pri práci s internetom môžeme všimnúť, že miesto adresy „http://xxx.yy“ máme adresu „https://xxx.yy“. Značí to, že komunikácia medzi nami a naším počítačom prebieha šifrovanie pomocou protokolu SSL (vo svojom vnútri pracuje približne ako PGP – dohodne sa kľúč pomocou asymetrickej šifry a potom šifruje dáta symetrickou šifrou). Toto sa využíva hlavne v službách, kde je nutné zaručiť bezpečnosť informácii posielaných medzi klientov a serverom (napr. internet banking). Taktiež sa niekedy pri emailovej komunikácii môžeme stretnúť s použitím digitálneho podpisu, hlavne pri komunikácii na vyšších úradných miestach.

3.Iné šifry

3.1 Šifra prasacích chlievikov
Šifra prasacích chlievikov je jednoduchá monoalfabetická substitučná šifra. K tejto šifre nie je ani potreba veľa vysvetľovať, pretože je vcelku jednoduchá. Bez problémov sa ju môžeme naučiť naspamäť a pre tých čo ju nepoznajú vyzerá zložitá už len preto, že nenahradzujeme písmeno otvorenej abecedy iným písmenom, ale iným znakom. (obr. 5)

Príklad: zašifrujeme napríklad jednoduché slovo „ahoj“ (obr. 6), každé písmeno nahradíme znakom z obrázku číslo 5

3.2 Šifra ADFGVX
Táto šifra bola jednou z najslávnejších vojenských šifier. Nemecká šifra, ktorá bola zavedená v roku 1918. Šifru prvýkrát dešifroval francúzsky kryptoanalytik Georges Painvin. Šifrovanie sa začína nakreslením mriežky 6x6, do ktorej náhodne vyplníme 26 písmen a 10 číslic. Prvá vec, ktorú urobíme bude to, že pre každé písmeno v mriežke nájdeme inú pozíciu. (obr. 7) Napríklad 8 bude nahradené AA, P bude nahradené AD. Ako príklad použijeme správu „stretneme sa o 7h“.

	A	D	F	G	V	X
A	8	p	3	d	1	n
D	l	t	4	o	a	h
F	7	k	b	c	5	z
G	j	u	6	w	g	m
V	x	s	v	i	r	2
X	9	e	y	0	f	q

(obr. 7) Mriežka ADFGVX
Otvorený text:  s  t   r   e  t   n  e   m  e   s  a  o   7  h
1. Štádium šifrovania:  VD DD VV XD DD AX XD GX XD VD DV DG FA DX

Dostali sme monoalfabetickú substitučnú šifru, ktorá by sa dala ľahko dešifrovať pomocou frekvenčnej analýzy. Druhým štádiom ADFGVX je transpozícia. K nej je potrebné kľúčové slovo, na ktorom sa dohodnú príjemca s odosielateľom. Zoberieme si teda napríklad slovo „ahoj“. Toto slovo sa skladá zo 4 písmen, takže aj tabuľku si urobíme 4x6 políčok, tak, že najskôr napíšeme písmená kľúčového slova na hornú radu novej mriežky. Následne pod ňu napíšeme do niekoľkých riadkov pod seba zašifrovaný text z prvého štádia. (obr. 8) Stĺpce mriežky sa potom usporiadajú tak, aby písmená kľúčového slova boli v abecednom poradí. Konečný zašifrovaný text sa získa tak, že postupujeme dole po každom stĺpci a písmená zapíšeme v novom poradí.

Teraz zapíšeme šifrové znaky z tabuľky v poradí od hora nadol a dostaneme výsledný šifrový text, ktorý vyzerá nasledovne: V V D X X D F F V D DD V A D D X X D G X D X A G V D D. Konečný zašifrovaný text sa potom pošle morzeovkou a príjemca šifrovací proces obráti tak, aby dostal späť pôvodný text. Celý šifrovací text je zložený iba zo šiestich písmen (t.j. A, D, F, G, V, X), pretože tie označujú riadky a stĺpce pôvodnej mriežky 6x6. Ľudia sa často pýtajú, prečo boli za označenie vybraté práve tieto písmená, a nie napríklad A, B, C, D, E, F. Odpoveď znie, že A, D, F, G, V, X sa navzájom výrazne líšia v Morseovej abecede, takže výber písmen minimalizuje behom prenosu riziko chýb.

Záver
V mojej práci sa mi podarilo  zachytiť historický vývoj šifrovanej komunikácie od počiatkov v antike až po súčasnosť. Poukázala som na základné rozdelenie šifrovania a snažila som sa vysvetliť postupy niektorých jednoduchých šifier. Ukázalo sa, že kryptografia a kryptoanalýza mali významný vplyv aj na vývoj vojnových udalostí. Taktiež sa ukázalo, že v súčasnom živote má kryptológia významné postavenie.