Bankovní institut vysoká škola Praha Katedra informačních technologií
Kryptografické metody
Bakalářská práce
Autor:
Jakub Ježek Studijní obor bankovnictví, specializace správce IS
Vedoucí práce:
Jakub Ježek
Ing. Vladimír Beneš
Duben 2009
Prohlášení: Prohlašuji, že jsem bakalářskou práci zpracoval samostatně a s použitím uvedené literatury.
V Čelákovicích, 25. března 2009
Jakub Ježek
Za pomoc s touto prací, odborné vedení, trpělivost a hodnotné rady bych chtěl velmi poděkovat Ing. Vladimíru Benešovi.
Anotace Tato práce popisuje hlavní milníky vývoje kryptografických metod od starověkého Řecka a Říma přes Vernamovu šifru, legendární Enigmu, algoritmy RSA, DES, Blowfish, MD5 až po kryptografii kvantovou.V závěru se též zabývá vývojovými trendy v oblasti kryptografie.
Annotation This thesis describes cryptographic methods used from old Greek and Rome through Vernam’s cipher, legendary Enigma machine, algorythms like RSA, DES and 3DES, Blowfish, MD5 till quantum cryptography. At the end is estimating further cryptograpic methods.
Obsah: Úvod 1
2
1 Definice pojmů
1.1
Kryptologie, kryptografie, kryptoanalýza
2
1.2
Klíč, algoritmus
2
1.3
Symetričnost šifer
3
1.4
Proudové a blokové šifry
4
1.5
Transpoziční a substituční metody
4
Historie kryptografie
5
2.1
Egypt
5
2.2
Řecko
5
2.2.1
Skytala
6
2.2.2
Aeneus Tacticus
6
2.2.3
Polybiova šifrovací matice
7
2.2.4
Gaius Iulius Caesar
7
2.3
Johann Tritheim
7
2.4
Francis Bacon
8
2.5
Samuel Morse
8
2.6
Gilbert Vernam
8
2.7
Artur Scherbius
10
2.7.1 3
2
Princip šifrování
Součastná kryptografie 3.1
RSA
11 14 14
3.1.1
Tvorba klíčového páru
15
3.1.2
Šifrování zprávy
16
3.1.3
Dešifrování zprávy soukromým klíčem
16
3.2
DES a 3DES
17
3.2.1
Šifrování pomocí DES
18
3.2.2
Šifrovací funkce f(Rn,Kn)
20
3.2.3
Inicializační permutace (IP, IP-1)
21
3.2.4
Expanzní funkce E
23
3.2.5
Selektivní funkce S
24
3.2.6
Permutační funkce P
25
3.2.7
Key scheduler KS
26
3.3
Blowfish
3.3.1
Šifrovací algoritmus
29
3.3.2
Šifrovací algoritmus
30
3.3.3
Expanze klíče
30
3.4
MD5
3.4.1 4
Rozšíření zprávy
31 34
4.1.1
35
Polarizace fotonů
BB84
4.2.1
Závěr
31
Kvantová kryptografie
4.2
5
29
36 Popis algoritmu BB84
Vývojové trendy kryptografie
36 39 40
Úvod Představte si svět ve kterém neexistuje tajemství. Není tedy divu že již od nejčasnějších věků lidé vymýšleli jak si nějakou informaci zapsat, ale zároveň ji ochránit před čtením nepovolanými osobami. Lze tedy říci, že kryptografie a steganografie jsou staré jako lidstvo samo. Ruku v ruce se však s vývojem kryptografie začala vyvíjet i její sestra kryptoanalýza. Touha znát něčí tajemství a zneužít ho je jen o něco málo mladší než touha střežit si svá tajemství. Význam potřeby ochrany informací ještě více narůstal s obdobím válek. Sdělování strategických informací bezpečným kanálem rozhodovalo o výsledku bitvy. Není tedy divu, že největší rozkvět kryptografie i kryptoanalýza zažívala a zažívá v době válek. Skutečný kryptologický boom je v průběhu druhé světové války. Evropa a zejména Velká Británie, odříznutá od zásob a vyhladovělá, si nemůže dovolit ztráty v podobě potopených zásobovacích lodí. Proto v tzv. Bletchley parku vzniká největší kryptoanalytický trust v historii lidstva. Tisíce matematiků z celé Evropy soustavně pracují na jediném. Rozluštit Enigmu. Legendární německou šifru o kterou před válkou nikdo nejevil zájem. S nadsázkou lze tedy říci, že kryptografie i kryptoanalýzy je zodpovědná za dnešní vzezření světa.
1
1
Definice pojmů
Abychom mohli lépe proniknout do tajemného světa šifer, šifrování a dalších způsobů utajování zpráv bude vhodné nejprve utřídit si pojmy které usnadní naši další orientaci. Znalost těchto pojmů je velice nutná pro snadné porozumění dalšího textu a bez těchto znalostí bude čtenář doslova ztracen. Ačkoliv bude definice pojmů pro valnou většinu čtenářů spíše opakováním, může však sloužit i jako soubor základních definic pojmů týkajících se šifrování.
1.1
Kryptologie, kryptografie, kryptoanalýza
Rozdíly mezi kryptografií, kryptologií a kryptoanalýzou jsou především v oborech které tyto vědy popisují. Kryptologie je věda zabývající se vším co se šifer a šifrování týká. Má dva podobory, kterými jsou právě kryptografie a kryptoanalýza. Kryptografie je obor kryptologie který se zabývá způsoby šifrování a dešifrování zprávy. To znamená že do oboru kryptografie spadají algoritmy, šifrovací stroje, hardware potřebný pro šifrování zpráv, kryptografické protokoly apod. Kryptoanalýza je poměrně zajímavějším leč i náročnějším oborem kryptologie. Zkoumá totiž, jak ze zašifrované zprávy vyluštit otevřený text a to bez znalosti klíče či šifrovacího algoritmu. Toto se děje především prostřednictvím matematických metod, které se snaží se zašifrované zprávy vytvořit otevřený text. Další možností, jak ze zašifrované zprávy získat otevřený text nemá s kryptoanalýzou vůbec nic společného. Jde totiž o metody jakými jsou špionáž, úplatkářství a další nemorální, případně nezákonné praktiky.
1.2
Klíč, algoritmus
V kryptologii se klíčem rozumí sekvence znaků, který společně se zprávou vstupuje do šifrovacího algoritmu. Výstupem z tohoto algoritmu je buď šifrovaný text (v případě, že šifrujeme), nebo otevřený text (v případě, že dešifrujeme). Nezašifrovaný text se nazývá otevřený text (plain-text), zašifrovaný text potom cipher-text. Ke konverzi otevřeného textu na šifrovaný a naopak se používají různé kryptografické algoritmy a různé druhy klíčů. Algoritmus je vlastně sekvence matematických a jiných operací převádějící otevřenou zprávu na zašifrovaný text a naopak. Jaké matematické operace se použijí, záleží
2
především na typu zvolené šifry. Například základem Vernamovy šifry je binární operace XOR.
1.3
Symetričnost šifer
Jedním z pohledů, jakými lze roztřídit kryptografické metody je symetričnost šifer. Jednoduše lze říci, že u symetrických šifer se používá stejný klíč pro zašifrování a rozšifrování zprávy. Pokud se omezíme na komunikaci mezi dvěma body je použití symetrických šifer výhodnější, neboť jsou, co do výpočetní náročnosti, jednodušší a rychlejší. Naproti tomu v reálném světě potřebujeme komunikovat s větším množstvím protistran. Není žádoucí aby komunikace, kterou si posíláme s protistranou „A“ byla čitelná i protistranou „B“. Z tohoto požadavku vyplývá, že nemůžeme použít stejný klíč pro komunikaci s A i B. Pokud tedy potřebujeme komunikovat s dvěma protistranami potřebujeme dva klíče. Pokud by měli mezi sebou komunikovat i A a B. Situace s ještě více zkomplikuje. Budeme potřebovat 3 klíče. Obecněji je počet klíčů potřebných pro komunikaci „každý s každým“ dán vzorcem:
n
(n − 1) , 2
kde n je počet lidí komunikujících systémem „každý s každým“. Z tohoto vyplývá, že při větším počtu komunikujících stran narazíme na problém se správou šifrovacích klíčů. Například počet klíčů pro 10 navzájem komunikujících stran je 45. Tento problém řeší šifrovací algoritmy asymetrické. Fungují ne na principu jednoho klíče, ale na principu klíčového páru. Jeden z klíčů je veřejně přístupný. Proto se nazývá veřejný klíč. Pomocí veřejného klíče lze jakoukoliv zprávu zašifrovat. Komplementárním klíčem
k veřejnému klíči je soukromý klíč. Pomocí soukromého klíče lze zašifrovanou zprávu rozšifrovat. Aby byla zaručena bezpečnost nesmí být z veřejného klíče možné získat klíč soukromý a nesmí existovat možnost veřejným klíčem zprávu rozšifrovat. Podívejme se, jak probíhá komunikace mezi Alicí, Bobem a záškodnicí Evou1 s použitím asymetrické šifry: 1. Bob vygeneruje klíčový pár; soukromý klíč si uschová a veřejný dá k dispozici světu. 1
Alice a Bob jsou v kryptologii standardní jména komunikujících stran, Eva je standardní jméno narušitele, strany, která se snaží odposlouchávat, či rozšifrovávat zprávy.
3
2. Alice zašifruje zprávu pomocí Bobova veřejného klíče a veřejně ji předá Bobovi. Eva nezná Bobův soukromý klíč a tudíž zprávu nemůže rozšifrovat 3. Bob použije svůj soukromý klíč k rozšifrování a přečtení zprávy. Alicin veřejný klíč
Alicin soukromý klíč Zašifrovaná
Zpráva pro Alici
Zpráva pro Alici
zpráva
Obrázek 1: Asymetrické šifrování, vlastní schéma
Analogicky by probíhala odpověď Alici. Bob by použil Alicí vygenerovaný veřejný klíč a Alice svůj soukromý klíč pro přečtení zprávy. Pokud by Alice s Bobem chtěli komunikovat prostřednictvím symetrické šifry, museli by si nejdříve tajným kanálem předat šifrovací klíč. V tomto místě je slabina symetrické kryptografie.
1.4
Proudové a blokové šifry
Toto rozdělení šifrovacích algoritmů je z pohledu přístupu algoritmu k text, který se má zašifrovat, případně rozšifrovat. Proudové šifry (např. Vernamova šifra) je taková, která zpracovává data bajt, za bajtem; resp. bit za bitem. Naproti tomu blokové šifry jsou takové které zpracovávají text po blocích dat. Příkladem blokové šifry je algoritmus BLOWFISH, který zpracovává text po 64 B blocích.
1.5
Transpoziční a substituční metody
Transpoziční a substituční metody se od sebe odlišují přístupem k datům zprávy. Zatímco substituční metody pracují na principu nahrazování, ať znaků, tak bloků, otevřeného textu znaky, či bloky pozměněnými šifrovací funkcí na základě klíče, transpoziční metody znaky zprávy nemění, nýbrž mění pozici, na které se znak nachází. Transpoziční šifry jsou dnes nepoužívané neboť je lze velmi snadno analyzovat.
4
2
Historie kryptografie
Historie kryptografie a jejích algoritmů má zásadní vliv na vzhled dnešního světa. Už v dobách egyptských faraónů bylo žádoucí chránit důležité dokumenty před cizíma očima. Lidstvo pak velmi rychle pochopilo, jak zásadní a výhodná je ochrana dat před nepovolanými. Výhody kryptografie se naplno projevili již ve starém Řecku v období válek s Peršany. Jen díky kryptografii Řekové odrazili postup perských vojsk do Evropy v bitvách u Thermopyl, Salaminy a Plataea. Díky tomuto vznikly v Evropě podmínky pro vznik tradiční evropské civilizace. To je ale poněkud dávná historie. Z dob nedávno minulých vzpomeňme na legendární německý šifrovací stroj Enigma. Díky slepé důvěře německého velení v 2. světové válce v neprolomitelnost šifry a úsilí vynaloženém A. Turingem v Bletchley Parku se dařilo válečnou Evropu zásobovat z USA vojenským materiálem. Vzpomeňme také na další šifry, které ovlivnily podobu dnešního světa. Legendární je například kód Navajo používaný Američany v druhé světové válce v boji s Japonskem a ve válce ve Vietnamu. Existuje a existovalo obrovské množství mechanismů a algoritmů používaných pro utajování skutečností. Pojďme se nyní podrobněji podívat na historické milníky této krásné vědy.
2.1
Egypt
Egypt je kolébkou kryptografie. Staří Egypťané byli první, kteří začali používat primitivních kryptografických metod k ochraně dat. První používanou metodou bylo jakési deformování hieroglyfů. Psal se rok 1900 př.n.l. V podstatě šlo o primitivní substituční šifru. I přes svoji jednoduchost však byla v tehdejších dobách považována za bezpečnou.
2.2
Řecko
Skutečnými mistry starověké kryptografie byli Řekové.Schopnost předávat si bezpečné informace při válečných taženích byla pro jejich úspěch esenciální. První využití kryptografie je z dob válek starého Řecka s Persií.“ Demaratus, syn Aristona, zjistil termín, kdy král Xerxes vytáhne s armádou proti Řekům. Rozhodl se o tom své krajany informovat, seškrábal vosk ze dvou dřevěných psacích destiček a přímo na dřevo zprávu napsal. Tyto destičky opět zalil voskem, aby to při náhodné kontrole vypadalo, že nejsou použité. Když se zpráva dostala na místo určení, manželka krále Leonidase Gorgo odhalila a přečetla tajemství z destiček.“[1] Psal se rok 480 př.n.l.
5
2.2.1
Skytala
Skytala byla první masově nasazená kryptografická metoda v dějinách lidstva. Jednalo se o jednoduchou symetrickou transpoziční šifru. Pás kůže či papyru se šikmo navinul na tyč. Rovnoběžně s osou kolíku se na papyrus napsal text. Po odmotání z tyče byl text nečitelný. Čitelným se text stal až po opětovném namotání na tyč stejného průměru. Tyč vlastně představuje kryptografický klíč.
Obrázek 2: Skytala, 15.12.2008 Zdroj: http://upload.wikimedia.org/wikipedia/commons/5/51/Skytale.png
Pokusme se tedy detailněji podívat na možnosti kryptoanalýzy Skytaly. Protože Skytala se používala zejména ve vojenství, uvažujme otevřený text: „POMOC JSEM POD TĚŽKÝM ÚTOKEM“. Prvním krokem bude odstranění mezer z textu. Poté, na každý řádek napíšeme 6 znaků dostaneme 4 řádky textu. Po odmotání dostaneme zašifrovaný text: „PSTÚOEĚTMMŽOOPKKCOÝEJDMM“. Prolomit tuto šifru je však velmi jednoduché. Stačí číst první a pak každé čtvrté písmeno. Po dosažení konce začít od druhého písmena a opět číst každé čtvrté. Když dosáhneme posledního písmena v zašifrovaném textu, rozšifrování je u konce. Nicméně ve své době byla skytala velmi účinná metoda. 2.2.2
Aeneus Tacticus
Kolem roku 535 př.n.l. se v řecké armádě začal stále více projevovat vojevůdce Aeneus Tacticus. Je autorem dvacítky různých kryptografických algoritmů. Žádný z jeho algoritmů se nedočkal takového úspěchu, jaký měla Skytala. Podstatné však je, že poprvé začal rozdělovat kryptografické metody na transpoziční a substituční.
6
2.2.3
Polybiova šifrovací matice
Je primitivní substituční šifrovací metoda vyvinutá přibližně v letech 203-120 př. n. l. Využívá matici s vepsanou abecedou o velikosti 5 x 5 a jednotlivé znaky zprávu jsou zaměněny indexem řádku a sloupce v této matici. Tato šifra byla několikráte modifikovaná. Například původní zápis abecedy do matice se různě promíchával. Někdy se k popisu indexu nepoužívali jen číslice, ale i jiné znaky. Tato metoda se využívala i pro odesílání zpráv v noci. Ve dvou skupinách po pěti loučích se vždy zvedl patřičný počet loučí symbolizující řádek (pravá část) a sloupec (levá část). 2.2.4
Gaius Iulius Caesar
Jeden z nejmocnějších mužů antické říše byl přímo posedlý kryptografií. V průběhu života vyvinul velké množství kryptografických metod, avšak téměř žádná se nedochovala. Jeho nejslavnější Caesarova šifra byla transpoziční šifrou. Při šifrování se každé písmeno abecedy nahradilo písmenem o tři pozice za ním. Při dekretování pak o tři pozice před ním. Pokud se došlo ke konci abecedy, začalo se opět od začátku.
2.3
Johann Tritheim
V 16. století do kryptografie výrazně zasáhl svoji publikací Benediktinský opat Johann Tritheim. V roce 1508 publikoval knihu „Steganographiae“ v níž popsal principy svých šifer. Jedna ze šifrovacích metod spočívala v nahrazení každého písmene slovem začínajícím na toto písmeno z předem určené tabulky.
Obrázek 3: Johann Tritheim. Zdroj: http://fotothek.slub-dresden.de/fotos/df_0160001/df_0161530.jpg
7
2.4
Francis Bacon
Jedním z nejznámějších kryptologů středověku je Francis Bacon. Vynalezl šifru pro zabezpečení diplomatické korespondence založenou na tzv. bigramové substituci. Tato metoda, je dnes známá jako pětibitové binární kódování je stále používaná.
2.5
Samuel Morse
Samuel Morse vynalezl svoji Morseovu abecedu v roce 1832. Již tehdy byle konstruována pro přenos informací na dálku. Jednotlivé znaky abecedy jsou převáděny na dlouhé a krátké signály. Spolu s vynálezem telegrafu (ve stejném roce) šlo o zásadní vynález, který umožnil efektivně komunikovat na velké vzdálenosti. Poprvé byl text kódovaný Morseovou abecedou odeslán až v roce 1944.
2.6
Gilbert Vernam
„Gilbert Vernam, zaměstnanec AT&T v roce 1918 zdokonalil Vigenèreovu šifru.“[2] Tím vytvořil prokazatelně neprolomitelnou šifru. Neprolomitelné ovšem za určitých předpokladů. Vernamova šifra je symetrická proudová kryptografická metoda. Funguje na principu jednoduché binární operace XOR. Podívejme se na pravdivostní tabulku binární funkce XOR: A
B
A XOR B
1
1
0
1
0
1
0
1
1
0
0
0
Tabulka 1: Pravdivostní tabulka funkce XOR
Z pravdivostní tabulky je patrné, že pro bity se shodnou hodnotou je výsledná hodnota nulová; pro bity s rozdílnou hodnotou je výsledná hodnota 1. Nyní je jasná hlavní nevýhoda Vernamovy šifry. K zašifrování zprávy o n bitech je třeba klíč délky n bitů. Pokud vezmeme v úvahu, že jednou použitý klíč se již znovu nesmí použít, pak je jasné, že „spotřeba“ klíče pro Vernamovu šifru je značná. Toto je první předpoklad neprolomitelnosti Vernamovy šifry. Druhým předpokladem je, že se nesmí šifrovat stejná zpráva jiným klíčem. Podívejme se jak probíhá šifrování Vernamovou šifrou. Pro zjednodušení uvažujme, že Alice chce Bobovi předat otevřený text v binárním kódu „0111001010110010“. Alice a Bob si předem bezpečně předali klíč v binárním tvaru „1011000101001101“. Všimněme si, že otevřený text má stejnou délku jako šifrovací klíč 8
– 16 bitů. Jak víme, proudová šifra zpracovává otevřený text bit za bitem. Vernamova šifra není výjimkou. Pracuje v cyklech a v každém cyklu zpracuje bitovou operací XOR jeden bit z klíče a jeden bit z otevřeného textu. Výsledkem je jeden bit šifrovaného textu. Výsledek našeho příkladu je patrný z následující tabulky: Otevřený text
0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0
Klíč
1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1
Šifrovaný text 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 Tabulka 2: Šifrování pomocí Vernamovy šifry
Alice pošle šifrovaný text veřejným kanálem Bobovi. Bob použije šifrovanou zprávu a klíč, který si předem bezpečně vyměnil s Alicí k rozšifrování: Šifrovaný text 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 Klíč
1 0 1 1 0 0 0 1 0 1 0 0 1 1 0 1
Otevřený text
0 1 1 1 0 0 1 0 1 0 1 1 0 0 1 0
Tabulka 3: Dešifrování pomocí Vernamovy šifry
Jak je vidět šifrování i dešifrování textu je velice jednoduché a rychlé. Jediný problém Vernamovy šifry je ve způsobu bezpečného předávání šifrovacího klíče.
9
2.7
Artur Scherbius
Šifrovací přístroj Enigma byl patentován 23. února roku 1918 německým inženýrem Arturem Scherbiusem, který se po neúspěšném pokusu nabídnout tento svůj koncept k odkoupení německému námořnictvu a posléze také ministerstvu zahraničí, rozhodl prodat tento svůj patent firmě Gewerkschaft Securitas, jejíž dceřiná akciová společnost Chiffriermaschinen AG v roce 1923 poprvé sestrojila funkční prototyp tohoto přístroje.
Obrázek 4: Šifrovací stroj enigma. Zdroj: http://upload.wikimedia.org/wikipedia/commons/thumb/4/44/EnigmaMachine.jpg/449pxenigmaMachine.jpg
První prototyp, prototyp „A“ byl poprvé představen jako civilní stroj na kongresu Světové poštovní unie. Tento přistroj byl velice nepraktický, neboť jeho celková hmotnost přesahovala 50kg. Jeho objemnost a fakt, že obsahoval i psací stroj mu nepřáli velké úspěchy. Následující model pojmenovaný „B“ se konceptuálně příliš nelišil od modelu „A“. Tyto oba modely byly však velice odlišné od následujících verzí nejen rozměry a stavbou, ale také funkčností. V roce 1925 se začala vyrábět verze pro námořnictvo s názvem „Funkschlüssel C“, která vycházela z již dokonalejších modelů Enigmy „C“ a „D“. Tato verze už obsahovala reflektor, který bylo možno nastavit do čtyř různých pozic. Šifrování probíhalo na třech rotorech, které byly náhodně vybírány z pěti možných.
10
Dalším milníkem ve vývoji Enigmy se stal rok 1928, kdy 15. června německá armáda uvedla do výzbroje vlastní zdokonalený typ „Enigma G“, který byl později přejmenovaný na „Enigma I.“. Tento typ přístroje je znám také jako verze „Wehrmacht“2, byl používán hojně nejen německou armádou, ale také vládními organizacemi jednak před, ale hlavně v průběhu druhé světové války. Postupným přidáváním rotorů - jednak do přístroje, ale i do sady, ze které bylo možné rotory libovolně vybírat - se Enigma zdokonalovala, až do jedné z posledních verzí „M4“, kterou v roce 1942 začalo používat námořnictvo. Stroj Enigma přesně odpovídal tehdejším požadavkům na pečlivě synchronizovanou komunikaci, která byla nezbytná pro „Blitzkrieg“3. 2.7.1
Princip šifrování
Stroj Enigma se skládal z několika na první pohled viditelných částí – vstupní klávesnice, dále podsvícená písmena rozložená stejně jako ta na vstupní klávesnici, propojovací deska a tři (na některých variantách i více) zřetelně viditelné otvory, ve kterých byly umístěny rotory. Funkce jednotlivých částí je zřejmá a lze ji popsat na zjednodušeném případu: „Šifrant obdržel text, který bylo nutné odeslat, proto stiskl klávesu příslušného prvního písmene původní zprávy a na stroji se „rozsvítilo“ písmeno, které bylo šifrované. Toto písmeno si šifrant poznamenal a postupoval dále stejným způsobem i na druhém, třetím až posledním písmeni původní depeše. Šifrovaný text pak předal radistovi, který měl za úkol množinu písmen odeslat adresátovi na druhé straně otevřeného komunikačního kanálu. Adresátovi byla doručena zdánlivě nepřehledná změť písmen, nicméně náš adresát postupoval podle naprosto totožného algoritmu, jako náš šifrant. Kódovanou zprávu zadával písmeno po písmeni na vstupní klávesnici a na desce s písmeny mu postupně Enigma vypisovala zprávu původní.“ Ovšem pouze za předpokladu, že měly obě strany ten samý typ přístroje a jeho parametry byly totožně nastaveny. 2
Wehrmacht, neboli WH, neboli Wehrmachts Heer je označení pro německou armádu v období 2. světové války. Nejednalo se o zvláštní jednotky SS, nýbrž o regulérní pravidelnou armádu.
3
Blitzkrieg neboli „blesková válka“ byl způsob rychlého boje a postupu nacistických vojsk napříč Evropou při tažení za 2. světové války, který měl zajistit rychlé vítězství a ovládnutí klíčových oblastí dříve, než stačil protivník zareagovat.
11
Nastavení Enigmy bylo klíčové pro správné zobrazení původní zprávy. Oproti původní komerční verzi byla na vojenské Enigmě ještě výše zmíněná propojovací deska, na které šifrant libovolně propojil 2 písmena pomocí kabelů. Původně přístroj obsahoval těchto kabelů šest, později byl jejich počet kvůli složitosti ještě zvýšen na deset. Toto propojení bylo jen jedním ze základních nastavení šifrovacího přístroje.
Obrázek 5: Schéma rotoru enigmy. Zdroj: http://upload.wikimedia.org/wikipedia/commons/f/f3/Enigma_rotor_exploded_view.png
Přes propojovací desku procházel elektrický proud do zmíněných rotorů, nejprve přes statický vstupní kruh, dále třemi rotory, do kterých procházel přes tolik kontaktů (číslo 4), kolik je písmen na vstupní klávesnici – tj. 26. Tyto kontakty byly obsaženy uvnitř těchto rotorů. Rotory pak procházelo 26 navzájem izolovaných drátků (číslo 5), které spojovaly kontakty z jedné strany rotoru s kontakty na straně druhé (číslo 6). U každé série rotorů tak vytvářely jedinečnou permutaci. Na straně vysílače i přijímače musela být použita stejná sada rotorů pro bezchybné dešifrování. Po průchodu rotory proud tekl do takzvaného reflektoru, kterých bylo více typů. U vojenské verze je bylo možné umísťovat různými způsoby. Uvnitř tohoto reflektoru bylo 13 pevně daných propojení pomocí vodičů, které spojovaly vždy dva vstupní a výstupní kontakty. Následně se proud vracel zpět přes rotory a propojovací desku až se dostal do výstupní podsvícené klávesnice, kde se zobrazilo příslušné kódované písmeno.
12
Tento princip byl sice důmyslný, avšak ne příliš složitý na dešifrování. Proto měla Enigma v „rukávu“ ještě jeden trumf. Rotory se totiž po každém stisknutí klávesy na vstupu pootočily o 1/26 z celého úhlu 360°, to pomocí ozubených kol (číslo 10) připojených na jednotlivé rotory. Nebylo to ale vše,co rotory Enigmy dokázaly – pomocí malého kroužku (číslo 1),který byl na jednotlivé rotory také připojen se postupně spouštelo otáčení druhého a třetího rotoru poté,co prví rotor urazil určitý počet otáček. Tyto kroužky s malým zářezem určujícím, kdy se převedou rotace i na další rotory bylo možné také nastavovat. Tím se ještě zvýšil počet možných kombinací nastavení přístroje. Pro představu: 26 možných pozic zářezu na kroužku na 3 rotorech nám dává: 263 = 17576. Jak ale radisti a šifranti přijímající kódovanou zprávu rozšifrují? Jak vědí, jaké nastavení použila vysílající strana? Tento problém byl řešen jednak „denním klíčem“, neboli soustavou údajů uspořádaných v tabulce, které určovaly nastavení přístroje podle momentálního data v kalendáři. Šifrantovi na jedné i na druhé straně se tak stačilo podívat na aktuální datum a podle údajů v denním klíči nastavil přístroj tak, že propojil příslušná písmena na propojovací desce. A jako druhá pomůcka ke zjištění nastavení přístroje bylo odesláno prvních šest znaků bez šifrování pomocí rotorů, tato písmena byla kódována „pouze“ pomocí propojovací desky a určovala nastavení rotorů na straně odesílatele. Strana přijímatele si tak nastavila podle prvních 6 znaků své rotory a depeši následně bezchybně dešifrovala.
13
3
Součastná kryptografie
Samozřejmě je téměř nemožné popsat všechny dnes dostupné a používané šifrovací algoritmy, ale snažil jsem se vybrat od každého zástupce (blokových proudových symetrických, asymetrických, obousměrných i jednosměrných) jednoho významného zástupce. Co se rozdělení jednosměrné – obousměrné týče, jednosměrným algoritmem je z následujících pouze algoritmus MD5. Zástupci symetrických šifer jsou algoritmy Blowfish a DES, případně jeho zdokonalená verze 3DES. Asymetrickou šifrou je pak RSA.
3.1
RSA
RSA je v dnešní době nejrozšířenějším šifrovacím algoritmem. Jeho autory jsou R. Rivest A. Shamir a L. Adleman. Jedná se o nesymetrickou blokovou obousměrnou šifru. Její síla je v jednoduché myšlence a sice že součin dvou čísel je jednoduchá a rychlá operace, ale faktorizace součinu na prvočinitele je velmi náročná.
Obrázek 6: Autoři šifry RSA. Zdroj: http://casacaseycourtney.files.wordpress.com/2008/08/rsa1.jpg - upraveno.
14
Uvažujme součin n dvou velkých prvočísel p a q. Spočítat součin těchto dvou čísel je jednoduché, ale ze součinu zpětně získat prvočísla p a q je výpočetně nepoměrně složitější. Nyní využijeme našich známých Alice a Boba, abychom si na nich ukázali, co je třeba udělat k bezpečnému přenosu zprávy od Bobova k Alici. 3.1.1
Tvorba klíčového páru
Prvním úkolem Alice je vygenerovat si klíčový pár. Výsledkem budou dva různé klíče (RSA je asymetrická šifra). První, soukromý, si Alice ponechá. Tento jí bude sloužit k rozšifrování zprávy od Boba. Druhý, nazvěme jej veřejný dá Alice k dispozici Bobovi. Nemusí se obávat, že si klíč odposlechne záškodnice Eva, neboť jej nebude moci použít ani pro rozšifrování zprávy a ani pro vygenerování soukromého klíče (faktorizace čísla na prvočinitele je obtížná). •
Nejprve je třeba náhodně zvolit dvě dostatečně velká prvočísla p a q.
•
Jako druhý krok provedeme jejich součin a nazveme jej n.
•
Jako další krok je třeba spočítat hodnotu Eulerovy funkce φ(n) jako:
ϕ (n ) = ( p − 1)(q − 1) . •
Jako čtvrtý krok zvolíme celé číslo e takové, aby nebylo soudělné s hodnotou Eulerovy funkce φ(n) a zároveň bylo menší, než hodnota φ(n).
•
V dalším kroku je třeba nalézt takové celé číslo d, aby platilo: de = 1(mod ϕ (n ))
•
Nakonec, jestliže e je prvočíslo platí: d=
kde
r = ((e − 1)ϕ (n ))
(e − 2 )
(1 + rϕ (n )) , e
.
Soukromým klíčem je dvojice (n, d), kde n se nazývá modul a d je tzv. dešifrovací, či soukromý exponent. Veřejným klíčem je pak dvojice (n, e), kde e je šifrovací nebo veřejný exponent.
15
3.1.2
Šifrování zprávy
Bob si předem s Alicí (klidně i veřejně) dohodl, jak se text zprávy bude konvertovat na číslice a naopak. Jako první Bob převede svoji zprávu na čísla právě pomocí tohoto algoritmu. Nazvěme takto konvertovanou zprávu jako m. Přitom musí platit, že: m
číslo m pak Bob převede na šifrované číslo X takto:
X = m e mod n . Číslo X je pak možné předat veřejným kanálem Alici. Provést rozšifrování by pak pro Evu znamenalo nutnost faktorizovat součin n na prvočísla p a q a známým postupem vygenerovat číslo d. 3.1.3
Dešifrování zprávy soukromým klíčem
Bob pošle Alici šifrovanou zprávu X. Původní zprávu m získá Alice následujícím výpočtem:
m = X d mod n .
16
3.2
DES a 3DES
Data Encryption Standard. Šifra vyvinutá společností IBM v sedmdesátých letech na základě požadavku NSA (National security agency). Jde o symetrickou blokovou šifru s velikostí bloku 64bitů a 56bitovým klíčem. Algoritmus DES je v podstatě zdokonalení šifry Lucifer, též z produkce IBM. V USA byla od roku 1976 nasazena jako standard pro šifrování dat. Předpokládalo se, že DES bude bezpečný pro dalších cca 10 až 15 let. Podmínkou bylo že se šifra musí každých pět let podrobit zkouškám bezpečnosti. Její oblíbenost a množství v jakém byla nasazována rostla téměř geometricky. Mohutné množství implementace tohoto algoritmu však vedlo k problému, jak nahradit tento algoritmus něčím moderním a bezpečnějším. První spekulace o bezpečnosti algoritmu se objevili již v roce 1975. Na dlouho však zůstalo u spekulací. Největšími kritiky algoritmu DES byli Diffie a Hellman. Jejich kritika směřovala především na nedostatečnou délku klíče. Uvažovali, že k prolomení šifry stačí pouze vyzkoušet všechny kombinace šifrovacího klíče. V roce 1997 byla agenturou RSA vypsána kryptoanalytická soutěž s cílem prolomit šifru DES se znalostí začátku otevřeného textu a neznámým klíčem o délce 56 bitů. Vítězem se stal řešitelský tým DES challenge pod vedením R. Verbena. Využil distribuovaného výpočtu a postupu, který definovali Diffie a Hellman o 24 let dříve. S výpočetním výkonem roku 1999 stačilo k prolomení šifry méně než 24 hodin. Na konci roku 1999 bylo doporučeno, aby se přešlo z DES na její vylepšenou verzi 3DES (triple DES; trojitý DES). 3DES je trojnásobná aplikace DES algoritmu, pokaždé s jiným klíčem. Klíč šifry 3DES je tedy 168 bitů dlouhý. I když je algoritmus DES již vlastně minulostí, neboť jej lze snadno prolomit, jeho derivát 3DES je stále nasazován v mnoha aplikacích. Například Secure shell (ssh), shadow hesla v Unixu, šifrování uživatelských hesel v databázových serverech Sybase, Nortel VPN, apod.
17
3.2.1
Šifrování pomocí DES
Obrázek 7: Schéma šifrovacího algoritmu DES. Zdroj: http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
18
•
Nejprve se text, který chceme šifrovat případně dešifrovat rozdělí na bloky po 64 bitech. Poté každý blok prochází stejným algoritmem na jehož konci jsou bloky opět složeny do otevřeného či šifrovaného textu.
•
Dalším krokem každého bloku je průchod Inicializační permutací. Během této operace dochází k přesouvání jednotlivých bitů podle předem definovaného postupu. Výstup z inicializační permutace se nazývá Permuted input – permutovaný vstup.
•
Následně se blok dat rozdělí na dva subbloky; pojmenujme je L0 a R0. Každý subblok obsahuje 32 bitů vstupních dat.
•
Dále výpočet pokračuje v cyklech. Cyklů je celkem 16. o Blok L1 = R0 a o blok R1 = L0 ⊕ f ( R0 , K 1 ) ; atd. o Blok L16 = R15 a o blok R16 = L15 ⊕ f ( R15 , K 16 ) 4.
•
Bloky L16 a R15 jsou označovány jako preoutput.
•
Bloky preoutputu jsou složeny a prochází funkcí inverzní k inicializační permutaci (IP-1).
• 4
Výsledkem funkce IP-1 je zašifrovaný / otevřený text.
Symbol ⊕ reprezentuje celočíselné dělení součtu (jednotlivých bitů) L a R číslem 2.
19
3.2.2
Šifrovací funkce f(Rn,Kn)
V každé jednotlivé iteraci je subblok R předán šifrovací funkci. Šifrovací funkce funguje podle následujícího schématu. Každý R subblok o velikosti 32 Bitů nejprve prochází expanzní funkcí E. Ta jej rozšíří na 48bitů. Následuje ⊕ se subklíčem připraveným pomocí funkce key scheduler. Symbol ⊕ označuje operaci bitového sčítání po kterém následuje modulo 2. Tímto získám výsledný bit. Skupiny vždy 6ti bitů prochází funkcemi S1, S2, …, S8, tak že prvních šest bitů prochází funkcí S1, dalších šest bitů funkcí S2, atd. Nakonec bity 43 až 48 projdou funkcí S8. Každá z S funkcí má vstup o velikosti 6 bitů (celkem 48 bitů) a výstup o velikosti 4 bity (celkem 32 bitů). Zřetězený výstup S funkcí v pořadí S1 až S8 je vstupem do permutační funkce P. Výstupem z permutační funkce P je subblok dat Ln+1.
Obrázek 8: Schéma šifrovací funkce f(R,K). Zdroj: http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
20
3.2.3
Inicializační permutace (IP, IP-1)
Inicializační permutace má za úkol podle předem definovaného postupu rozmíchat bity v jednotlivých blocích textu. 58
50
42
34
26
18
10
2
60
52
44
36
28
20
12
4
62
54
46
38
30
22
14
6
64
56
48
40
32
24
16
8
57
49
41
33
25
17
9
1
59
51
43
35
27
19
11
3
61
53
45
37
29
21
13
5
63
55
47
39
31
23
15
7
Tabulka 4: Sekvence bitů v Inicializační permutaci IP.
21
Před výstupem je na zašifrovaný text použita funkce k inicializační permutaci inverzní tak, aby text po průchodu šifrovacím algoritmem byl opět správně seřazen. 40
8
48
16
56
24
64
32
39
7
47
15
55
23
63
31
38
6
46
14
54
22
62
30
37
5
45
13
53
21
61
29
36
4
44
12
52
20
60
28
35
3
43
11
51
19
59
27
34
2
42
10
50
18
58
26
33
1
41
9
49
17
57
25
Tabulka 5: Sekvence bitů v inverzní inicializační permutaci.
22
3.2.4
Expanzní funkce E
Expanzní primitivní funkce slouží k rozšíření bloku textu (resp. jeho poloviny) z 32 bitů na 48 bitů. Toto se prování prostým opakováním určitých bitů na předem stanovených pozicích. Mějme jednorozměrné pole o velikosti 48 bitů.. Vstupní bity z každého bloku (reprezentované číslem) jsou na výstupu seřazeny následovně: 32
1
2
3
4
5
4
5
6
7
8
9
8
9
10
11
12
13
12
13
14
15
16
17
16
17
18
19
20
21
20
21
22
23
24
25
24
25
26
27
28
29
28
29
30
31
32
1
Tabulka 6: Pořadí bitů datového bloku (číslo) po průchodu expanzní funkcí.
Tedy poslední bit 32bitového bloku textu se po projitím expanzní funkcí nachází na 1 a 47 bitu. Druhý bit textu zprávy nalezneme pouze na pozici č. 3.
23
3.2.5
Selektivní funkce S
V rámci standardu DES je definováno osm selektivních funkcí S1, S2, …, S8. Vstupem selektivní funkce jsou 6 bitové bloky; výstupem pak 4bitové bloky.Funkce S1 je použita pro prvních 6 bitů z 32bitového bloku. Pro bity č. 7 až 12 je použita funkce S2 atd. Pro posledních 6 bitů (č. 43 až 48) je pak použita funkce S8. #/#
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0
14
4
13
1
2
15
11
8
3
10
6
12
5
9
0
7
1
0
15
7
4
14
2
13
1
10
6
12
11
9
5
3
8
2
4
1
14
8
13
6
2
11
15
12
9
7
3
10
5
0
3
15
12
8
2
4
9
1
7
5
11
3
14
10
0
6
13
Tabulka 7: Definice selektivní funkce S1.
Ilustrujme si použití S1 funkce na bloku dat B=(011011). Index řádku získám z prvního a posledního bitu bloku B. V našem případě 01, což převedeno do dekadické soustavy označuje řádek číslo 1. Z prostředních 4 bitů pak získáme index sloupce. V našem případě je index sloupce 1101; převedeno do dekadické soustavy tedy číslo 13.Číslo ležící v řádku 1 a sloupci 13 je 5. Převedeno do dvojkové soustavy je reprezentováno jako 0101. Obdobně je naloženo se všemi B-bloky.
24
3.2.6
Permutační funkce P
P funkce je definována velmi podobně jako inicializační permutace. Jejím vstupem je 32bitový blok dat a výstup má rovněž velikost 32 bitů. Prvním bitem bloku vystupujícího z permutační funkce bude 16 bit bloku vstupujícího. Tedy opět podle následující tabulky. 16
7
20
21
29
12
28
17
1
15
23
26
5
18
31
10
2
8
24
14
32
27
3
9
19
13
30
6
22
11
4
25
Tabulka 8: Definice umístění vstupního bitu (číslo) na výstupu z permutační funkce (pořadí).
25
3.2.7
Key scheduler KS
Key Scheduler je specifická funkce, která má za úkol pro každou ze šestnácti iterací potřebných k zašifrování či odšifrování dat připraví subklíč o velikosti 48 bitů ze zadaného 64bitového klíče. K tomuto KS funkce využívá dalších dvou funkcí označovaných jako PC-1 a PC-2. PC značí permuted choice a dá se volně přeložit jako permutovaný výběr. Funkce jsou velmi podobné P funkci z kapitoly 3.2.4, nicméně má svá specifika.
Obrázek 9: Key scheduler. Zdroj: http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf
26
3.2.7.1
PC-1
Úkolem funkce PC-1 je rozdělit klíč do dvou částí (C a D) podle následující tabulky: C: 57
49
41
33
25
17
9
1
58
50
42
34
26
18
10
2
59
51
43
35
27
19
11
3
60
52
44
36
63
55
47
39
31
23
15
7
62
54
46
38
30
22
14
6
61
53
45
37
29
21
13
5
28
20
12
4
D:
Tabulka 9: Definice funkce PC-1.
Bity vstupující do funkce PC1 jsou opět označeny číslem, jejich výstup je pak určen pořadím v tabulce.Tato funkce se volá pro každý blok šifrovaných dat jenom jednou. V momentě, kdy je klíč rozdělen do bloků C a D je toto rozdělení pro všech 16 iterací definitivní.
27
3.2.7.2
PC-2
Na rozdíl od PC-1 je funkce PC-2 volána při každé z 16ti iterací sloužících k šifrování/dešifrování dat. Je definována, tak jako většina funkcí, tabulkou: 14
17
11
24
1
5
3
28
15
6
21
10
23
19
12
4
26
8
16
7
27
20
13
2
41
52
31
37
47
55
30
40
51
45
33
48
44
49
39
56
34
53
46
42
50
36
29
32
Tabulka 10: Definice funkce PC-2.
Vstupem do funkce PC-2 je konkatenace bloků klíče Cn a Dn, kde n značí pořadí iterace. Předtím jsou však bloky C a D pozměněny funkcí Left shift.
3.2.7.3
Left shift
Funkce left shift je velice jednoduchá funkce, která podle níže uvedené tabulky posouvá pointer na začátek řetězce o předem definovaný počet bitů. Číslo iterace 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
1
2
2
2
2
2
2
1
Počet bitů o které se přesouvá pointer 1
1
2
2
2
2
2
Tabulka 11: Počet posunutí bitů ve funkci left shift.
28
3.3
Blowfish
Blowfish je symetrický blokový šifrovací algoritmus vyvinutý B. Schneierem a zveřejněný v roce 1994. Původní myšlenku, že šifra bude volně šiřitelná se nakonec podařilo prosadit. Narozdíl od ostatních algoritmů je Blowfish zcela volně šiřitelná. Podobně jako DES a 3DES využívá Feistelových sítí. Bloky se kterými tento algoritmus pracuje jsou, stejně jako u DES 64 bitové. Délka klíče je variabilní a může být až 448 bitů. Vlastní šifrování probíhá, stejně jako u DES v 16 cyklech. Co se požadavků na výpočetní výkon týče, je algoritmus blowfish výpočetně mnohem méně náročný. Samotný algoritmus se skládá ze dvou částí. Jednou je key-expansion, druhou pak je vlastní šifrování dat. Všechny operace na úrovni bitů jsou prováděny bitovou operací XOR. 3.3.1
Šifrovací algoritmus
Vstupem do šifrovacího algoritmu je 64bitové slovo x, které je rozděleno následovně: xL jsou bity 32-63 slova x a xR jsou bity 0-31 ze vstupu x. Samotné šifrování probíhá v šestnácti cyklech dle následujícího schématu.
Obrázek 10: Schéma algoritmu Blowfish. Zdroj: http://moon.felk.cvut.cz/~pjv/Jak/_info/i677/html/blowfish.htm
29
3.3.2
Šifrovací algoritmus
Funkce F spojuje jednotlivé dvaatřicetibitové bloky dat s klíčem. Výstupem funkce F je opět 32 bitový blok. Na vstupu je nejříve blok rozdělen do čtyř osmibitových bloků. Blok A představuje bity 24-31, B pak bity 16-23 atd. Funkce F je definována následujícím vzorcem: F = (( S1A + S 2 B mod 2 32 ) xorS 3C ) + S 4 D mod 2 32 Grafická interpretace výše zmíněného vzorce je pak následující:
Obrázek 11: Šifrovací funkce algoritmu Blowfish. Zdroj: http://moon.felk.cvut.cz/~pjv/Jak/_info/i677/html/blowfish.htm
3.3.3
Expanze klíče
Key expansion je v podstatě generování podklíčů potřebných pro následující šifrování. Podklíče jsou pak po celou dobu šifrování uloženy v jednom P-boxu (18 řádků krát 32 bitů) a čtyřech S-boxech. Každý S-box má 256 dvaatřiceti bitových řádků. Řádky P-boxu označme jako P1, P2, … P18. 5ádky S-boxů jako Si;0, Si;1, … Si;255, Kde i je identifikační číslo S-boxu (1 až 4). •
Prvotní inicializace P-boxu a S-boxů probíhá pomocí přesně definovaného řetězce – desetinných míst čísla π v šestnáctkové soustavě. Inicializace probíhá v pořadí: P1, P2, …, P18, S1;0, S1;1, …, S1;255, S2;0, …, S2;255, …, S4;255.
•
V cyklu probíhá čtení vždy 32 bitů klíče a operace XOR s P-boxy. Když čtení dojde na konec klíče, začíná se číst znovu od začátku. Končí se až naplněním P18 .
•
Dále algoritmu probíhá v cyklech. o Za použití takto získaných P-boxů a algoritmu Blowfish se tento aplikuje na
nulový řetězec o délce 64 bitů. Výslednými 64 bity se zaplní P1 a P2.
30
o Znovu se (za pomoci již pozměněných P-boxů P1 a P2) a P-boxů P3 – P18
provádí aplikace alogitmu Blowfish na nulový řetězec. Výsledek je uložen do P3 a P4. o Takto se postupně naplní všechny P-boxy a S-boxy. Celkem se jedná o 521
iterací. •
Takto získané P-boxy a S-boxy se dále nijak nemodifikují.
Dešifrování zprávy je vlastně stejný algoritmus jenom P-boxy do algoritmu vstupují v opačném pořadí.
3.4
MD5
Algoritmus MD5 je součástí rodiny algoritmů MD. MD je akronym slov Message Digest. Pětka pak značí, že se jedná o pátou verzi z této rodiny. Bezpochyby nejslavnějšího člena. Tento algoritmus vyvinul v roce 1991 Ronaldem Rivestem – spoluautorem RSA. Jeho oficiální standard je v RFC1321. MD5 je jednosměrná bloková šifra. Jednosměrná znamená, že není cesty, jak z MD5otisku (hashe, haše) získat původní text. Toto bylo velmi výhodné pro ukládání uživatelských hesel v databázích apod. Pro zvýšení bezpečnosti je však ke každému heslu před uložením i před ověřením zadaného hesla připojena tzv. salt. Jde o krátkou sekvenci znaků specifickou pro konkrétní produkt. Takto lze při vyzrazení MD5 hashe zabránit dalšímu zneužití. Protože salt je specifický pro každý systém, tak i hash ze stejného hesla ale na jiném systému (s jinou posloupností salt) bude jiná. Dnes je již MD5 na pokraji konce. Kryptoanalytikům se však zatím podařilo pouze podle původního textu vytvořit jiný text avšak se stejným MD5 otiskem. Nicméně je stále nemožné z otisku získat původní text. Jako první s touto myšlenku v praxi předvedl čínský tým Xiaoyun Wang, Dengguo Feng , Xuejia Lai, Hongbo Yu [5]. Významně se na prolomení MD5 podílel i náš kryptolog V. Klíma [6]. 3.4.1
Rozšíření zprávy
V prvním krokem je zpráva rozšířena tak aby délka (v bitech) byla dělitelná číslem 512. Zpráva je nejprve rozšířena o jeden bit s hodnotou 1 a dále o potřebný počet bitů s hodnotou 0. Ke zprávě je vždy přidán alespoň jeden bit; nejvýše však 512 bitů.
31
3.4.1.1
Inicializace bitových registrů
Následujícím krokem je inicializace čtyř 32 bitových bufferů. Tyto buffery (A, B, C, D) jsou inicializovány podle následující tabulky: A
01 23 45 67
B
89 ab cd ef
C
fe dc ba 98
D
76 54 32 10
Tabulka 12: Inicializační nastavení bufferů A, B, C, D.
3.4.1.2
Šifrovací funkce F, G, H, I
Kryptovací funkce jsou jednoduché operace s jednotlivými bity v bufferech. Jsou definovány následujícím způsobem: F(X,Y,Z) = (X and Y) or (not X and Z), G(X,Y,Z) = (X and Z) or (Y and not Z), H(X,Y,Z) = X xor Y xor Z, I(X,Y,Z) = Y xor (X or not Z).
3.4.1.3
Shift funkce
Tato funkce během každého cyklu určuje levou rotaci bufferu. Je velmi podobná funkci Left shift z kapitoly o algoritmu DES. Je opět definována následující tabulkou: Číslo cyklu (i)
1
2
4
5
6
8
9
10 11 12 13 14 15 16
Posunutí (x)
7
12 17 22
7
12 17 22
7
12 17 22
Číslo cyklu (i) Posunutí (x) Číslo cyklu (i) Posunutí (x) Číslo cyklu (i) Posunutí (x)
3
7
7
12 17 22
17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 5
9
14 20
5
9
14 20
5
9
14 20
5
9
14 20
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 4
11 16 23
4
11 16 23
4
11 16 23
4
11 16 23
49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 6
10 15 21
6
10 15 21
6
10 15 21
Tabulka 13: Pootočení bufferu o x bitů v i-tém cyklu.
32
6
10 15 21
3.4.1.4
Hlavní cyklus
Hlavních cyklů je 64. Graficky se dá znázornit následujícím obrázkem:
Označuje Zbytek po dělení 2 součtu Zde vstupují data, pro která chceme vypočítat otisk
Obrázek 12: Schéma výpočtu MD5. Zdroj: http://upload.wikimedia.org/wikipedia/commons/thumb/d/d8/MD5.svg/546px-MD5.svg.png
Jak tedy vlastně výpočet otisku probíhá? Zpráva je nejprve rozšířena tak, aby její délka v bitech byla dělitelná 512. Dále se zpracovávají tyto 512 bitové bloky samostatně. Každý z nich je rozdělen na šestnáct dvaatřicetibitových bloků. Tyto bloky vstupují do hlavního cyklu jako Mi. Před prvním během dochází k inicializaci proměnných A, B, C, a D. Při prvním běhu do cyklu vstupuje blok dat M1, jako kryptovací funkce se použije F; při druhém běhu opět vstupuje M1, ale jako kryptovací funkce se použije G. Výstupem z algoritmu MD5 jsou za sebe poskládané buffery A, B, C a D.
33
4
Kvantová kryptografie
Na počátku kvantové kryptografie byla kvantová mechanika. Kvantová mechanika nám umožnila vznik například laseru. Bylo pouze otázkou času, než se někdo pokusil využít kvantovou mechaniku k bezpečnému ukládání či přenášení souborů. Navíc se kvantová kryptografie z kvantové mechaniky nevyčlenila přímo, ale přes vědní obor kvantová teorie informace. Kvantová mechanika vznikla ve stejné době jako teorie relativity, ale ve srovnání s ní je „podivná“. Kvantová kryptografie nabízí nepodmíněnou bezpečnost. Nepodmíněná znamená, že její absolutní bezpečnost je zaručena přírodními zákony. Tím pádem není podmíněna žádnými předpoklady na schopnosti a technické možnosti útočníka. Takovou kombinaci bezpečnosti nám zaručuje Vernamova šifra se spojení s kvantovou kryptografií. Přírodní zákon, který nám zaručuje absolutní bezpečnost kvantové kryptografie říká, že částice (konkrétně foton5) nelze klonovat. Navíc měření prováděné na částici ovlivní její stav. Tím pádem můžeme poznat, že někdo odposlouchává. Kvantová kryptografie nezabrání odposlouchávání na přenosovém médiu, ale umí jej odhalit. V praxi se pro potřeby kryptografie používají fotony. Respektive rovina jejich polarizace6. 5
Uvažujeme kvantovou teorii světla. Světlo je tvořeno nedělitelnými částicemi – fotony; nikoliv vlnami.
6
Polarizace světla je jev popisující kmitání fotonů. Pokud fotony kmitají libovolně, říkáme, že světlo není polarizované. Pokud kmitají v jedné rovině, říkáme, že světlo je polarizované a že má určitou rovinu polarizace, v rámci které se fotony pohybují.
34
4.1.1
Polarizace fotonů
Kvantová část protokolu má jediný cíl a to bezpečně přenést klíč, který bude následně použit pro Vernamovu šifru. Bity klíče jsou reprezentovány generovanými fotony v různých polarizačních bázích navzájem otočených o 45° podle následujícího schématu.
Obrázek 13: Určení hodnoty bitu v závislosti na polarizační bázi. Zdroj: http://optics.upol.cz/download/vyzkum/prezent-krypto.pdf
K rozpoznání polarizace fotonu je použito tzv. polarizačních hranolů. Polarizační hranoly jsou vyrobeny z islandského vápence a v závislosti na polarizaci procházejících fotonů buď projdou skrz (obr. a) a nebo se fotony odrazí(obr. b). Pokud však pošleme k hranoly fotony polarizované jinou bází (shodou okolností pootočenou o 45°), polovina fotonů se odrazí a polovina projde skrz polarizační hranol (obr. c).
Obrázek 14: Chování fotonu při průchodu polarizačním hranolem. Zdroj: http://optics.upol.cz/download/vyzkum/prezent-krypto.pdf
Tento jev má smysl i pro tak malé energie, jakou je jeden jediný foton. Jak jsme říkali, tak je foton nedělitelný a tudíž se s pravděpodobností 50 % buď odrazí, nebo s pravděpodobností 50 % projde skrz hranol (obr. 14d).
35
4.2
BB84
Prvním protokolem kvantové kryptografie je protokol BB84. Teoretickými tvůrci jsou Charles H. Bennett a Gilles Brassard. BB84 je název složený z prvních písmen jmen autorů - Bennet a Brassard a číslicí 84 označující rok 1984 ve kterém tato teorie vznikla. V roce 1985 se podařilo byla teorie BB84 převedena do praxe. Zasloužil se o to Ch. Bennet a jeho student John Smolin. 4.2.1
Popis algoritmu BB84
Představme si opět Alici a Boba, kteří spolu chtějí bezpečně komunikovat za pomoci kvantové kryptografie. Pro zjednodušení uvažujme, že fotony pro klíč bude generovat vždy pouze Alice. Bezpečná komunikace však může probíhat oběma směry. Kromě kvantového komunikačního kanálu bude potřeba ještě jeden kanál (Telefon, Ethernet apod.) pro pomocnou komunikaci a pro přenos šifrovaných dat.
Obrázek 15: Schéma protokolu BB84. Zdroj: http://optics.upol.cz/download/vyzkum/prezent-krypto.pdf
Samotný algoritmus má několik částí. Jednou z nich je fáze generování a bezpečné předávání klíče probíhá následovně: 1. Alice generuje náhodné bity pro klíč Vernamovy šifry. 2. Náhodně generuje roviny polarizace mezi × a +. 3. Bity klíče přemění na fotony s určitou polarizací v určité polarizační bázi. 4. Jednotlivé fotony přes kvantový kanál pošle Bobovi. 5. Bob na svém zařízení náhodně střídá polarizační báze ×a +. 6. Bob pečlivě zaznamenává naměřené hodnoty (bity). 36
Pro přehlednost jsou předchozí body shrnuty do následující tabulky7. Jednotlivé řádky odpovídají krokům popsaným v bodech 1 až 6. generované bity
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
0
polarizační báze
+
×
+
+
+
×
×
×
+
+
×
+
×
×
+
×
polarizace fotonů
―
\
―
|
―
/
\
/
|
|
\
―
\
/
―
\
volené polar. báze
+
+
×
+
×
+
×
+
+
×
+
+
×
×
+
×
naměřené hodnoty
1
1
1
0
0
0
0
1
0
1
0
1
0
1
1
0
Tabulka 14: Generování bitů klíče pro kvantovou kryptografii a jejich přenos kvantovým kanálem.
Přenos výše zmiňovaných informací je zcela bezpečný. Nicméně kvůli zabránění odposlouchávání pomocí stejného zařízení vloženého do kvantového kanálu mezi Alicí a Bobem se informace o nastavení polarizační báze předává až po skončení kvantového přenosu. Další částí toho protokolu je tedy tzv. veřejná diskuze. Ta se provádí na pomocném kanále a je nešifrovaná. 7. Bob oznamuje Alici báze, ve kterých měřil polarizaci jednotlivých fotonů. 8. Alice sděluje Bobovi, ve kterých případech se shodli. 9. Přenesená sekvence bitů je přesně ta, kterou Alice poslala. Pokud ovšem komunikaci někdo neodposlouchával. Opět si shrňme kroky z druhé části protokolu do tabulky. naměřené hodnoty
1
1
1
0
0
0
0
1
0
1
0
1
0
1
1
0
volené polar. báze
+
+
×
+
×
+
×
+
+
×
+
+
×
×
+
×
shoda?
A
A
A
A
A A A A A
Platné bity klíče
1
0
0
0
1
0
1
1
0
Tabulka 15: Ověřování shody volených polarizačních bází.
7
V Tabulce předpokládáme, že nedošlo ke ztracení fotonu cestou kvantovým kanálem. V praxi se však ztrácí pouhé 1 – 2% fotonů.
37
Třetí a poslední část tohoto protokolu je tzv. obětování bitů. To slouží k odhalení odposlechu. Jak je popsáno níže ( kapitola 4.1.3) odposlech na kvantovém médiu způsobí 25% chyb. Chybou8 je myšleno, že Bob i Alice se shodli v polarizační bázi, Bob úspěšně detekoval polarizaci fotonu v rámci konkrétní polarizační báze, avšak Alice odeslala bit s jinou hodnotou, než získal Bob. V případě, že je odposlech potvrzen, se v další komunikaci nepokračuje. Shrňme si tedy „Obětování bitů“ do přehledové tabulky: Generované bity
1
Platné bity klíče
1
Shoda obětovaných
A
1
1
Použitelné bity
0
0
0
0
0 0
1
0
1
0
0
1
0
1
1
0
1
0
1
1
0
A 0
0
0
1
A 1
0
Tabulka 16: Obětování bitů za účelem odhalit odposlech.
V České republice se na laboratorních zkouškách podílela zejména laboratoř optiky Univerzity Palackého v Olomouci. Podařilo se sestrojit a experimentálně ověřit funkční exemplář. Na rozdíl od jiných exemplářů má český jedinec až desetkrát nižší chybovost. 8
Chybovost se běžně pohybuje okolo 1%.
38
5
Vývojové trendy kryptografie
Dokud zůstaneme u konvenčních počítačů stále nás může zachránit prodlužování délky klíče. Problém nastane v momentě, kdy se začnou prosazovat počítače kvantové. Umí totiž počítat s více vstupními stavy jakoby najednou. Tím pádem například počet operací nutných pro rozklad čísla na prvočinitele přestává růst exponenciálně s délkou klíče, ale stává se z tohoto problému „pouhý“ konečný polynom n-tého stupně. V nedávné době byl zaznamenán poměrně masivní nárůst využití nesymetrických kryptografických metod. Toto je způsobeno především jednodušší správou šifrovacích klíčů. Z dnes používaných šifrovacích algoritmů se zatím jeví bezpečným algoritmus RSA. Zatím i Blowfish odolává útokům. DES by prolomen již poměrně dávno, nicméně je stále ještě poměrně často nasazován. Ne však jako hlavní algoritmus, ale jako pomocný. V poslední době se hodně píše o kolizích algoritmu MD5. Jak se zdá jeho použití se stává nebezpečným. Zatím sice stále ještě není možné z otisku získat původní zprávu ale již existují i velice rychlé programy, které jsou schopné po zadání řetězce dopočítat jiný řetězec se stejným otiskem. Jediná jistota jaká prozatím existuje je v podobě Vernamovy šifry. Jako jediná je, pokud se dobře používá, zcela určitě bezpečná. Zejména spojení Vernamovy šifry a jejího klíče předávaného kvantovým kanálem se zdá být správnou cestou do budoucnosti. Naštěstí je všude kolem nás dostatek jedinečných fotonů. Ty jsou vynikajícím zdrojem náhodné posloupnosti. Bezpečnost RSA je pro zatím a vzhledem k jeho použití dostačující. Ještě pár let nám bude například pro připojení do banky a nějakou manipulaci s penězi stačit.
39
Závěr Tato práce přehledně shrnula nejzajímavější etapy vývoje kryptografických metod. A to od starověku až po současnost. Největší podíl práce je však věnován kryptografii současné a kvantové. V kapitole součastná kryptografie jsou přehledně popsány nejdůležitější kryptografické algoritmy dnes běžně používané. Jedná se o asymetrické RSA v současnosti implementované např. jako součást PGP a používané jako hlavní kryptografická metoda pro bezpečný přístup do elektronického bankovnictví. Dále je zde popsán algoritmus DES, který je, i přes jeho známé slabiny, i dnes poměrně hodně nasazován. Jako jeho následovník je představen i algoritmus Blowfish. Vychází stejně jako DES a jeho předchůdce Lucifer z teorie Freistelových sítí. Nicméně je dnes algoritmus Blowfish považován za bezpečný. Posledním popsaným algoritmem je hashovaní algoritmus MD5. I přes jeho prolomení je dnes stále používaná a to především jako kontrolní součet přenesených dat. Poslední kapitola je věnována kvantové kryptografii a protokolu BB84. Při popisu jsem se snažil vyjít zejména z implementace provedené v laboratoři optiky na Palackého univerzitě v Olomouci, která je dnes uznávanou laboratoří v oboru kvantové kryptografie.
40
Seznam použité literatury:
1. Vývoj kryptografie, http://krypto.krokonet.com/, [12.12.2008] 2. "cryptology." Encyclopædia Britannica. 2008. Encyclopædia Britannica Online. [17.12.2008], http://www.britannica.com/EBchecked/topic/145058/cryptology 3. DATA ENCRYPTION STANDARD (DES), [11.2.2009], http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf 4. RIVEST R., SHAMIR A., ALEMAN L.: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, [15.2.2009], http://theory.lcs.mit.edu/~rivest/rsapaper.pdf 5. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD, rump session, CRYPTO 2004, second version, [17.8.2004],http://eprint.iacr.org/2004/199.pdf 6. KLÍMA Vlastimil: Nalézání kolizí MD5 - hračka pro notebook, [5.3.2005], http://cryptography.hyperlink.cz/md5/MD5_kolize.pdf 7. DUŠEK Miloslav, Kvantová kryptografie, [15.3.2009] http://optics.upol.cz/download/vyzkum/prezent-krypto.pdf
