1
Šifrování – Kryptografie
Každý z nás si určitě umí představit situaci, kdy je důležité utajit obsah posílané zprávy tak aby ho byl schopen přečíst jen ten komu je určená a nikdo nepovolaný nebyl schopen zjistit pravý obsah sdělení. V dnešní době se se šifrováním setkáváme na každém kroku, ať již jde o šifrování e-mailů, bezpečný přístup k webu, nebo veškerou bankovní komunikaci a operace s platebními kartami. Mohlo by se zdát, že šifrování úzce souvisí jen s moderní elektronickou komunikací, ale má hluboké historické kořeny. V historii potřeba šifrovat vznikala převážně u vojenské nebo vládní komunikace, ze starověkého Řecka je velmi známá Caesarova šifra (substituční šifra). Rozlišujeme dva základní typy šifrování a to symetrické a asymetrické. Symetrické šifry mají hluboké historické kořeny, patří mezi ně výše zmiňovaná Caesarova šifra. Naproti tomu nesymetrické šifrování, často nazývané šifrování s veřejným klíčem je velice nové odvětví.
Symetrické šifry Princip symetrických šifer je v podstatě velice jednoduchý. Obě komunikující strany si zvolí šifrovací / dešifrovací metodu a tajný klíč. Pomocí klíče pak jedna strana zašifruje zprávu a odešle jí straně druhé, která jí opět pomocí klíče rozšifruje. Mohli bychom to přirovnat k sejfu s dobrým zámkem, ke kterému mají klíč jen komunikující strany. Princip šifrovací metody je obecně známý, jediné společné tajemství je klíč. Uveďme několik jednoduchých šifrovacích metod: 1. substituce písmen, 2. posunutí písmen, 3. afinní šifra. Substituce písmen Metoda je založená na vytvoření substituční tabulky, tedy každému znaku (písmenu, mezeře) jednoznačně přiřadíme jiný znak. Pomocí takové tabulky pak daný text zašifrujeme i rozšifrujeme. Tedy tajným klíčem je celá substituční tabulka. U každé šifrovací metody si musíme položit důležitou otázku: Jak moc je odolná proti rozluštění třetí strnou? U substituce by se na první pohled mohlo zdát, že je odolná. Pokud bychom náhodně zkoušeli všechny možné substituce nedostaneme se k výsledku za pomoci mnoha výkonných počítačů ani za deset let. Všech možných substitucí je totiž faktoriál počtu znaků. Budeme-li tedy uvažovat 26 znaků abecedy máme 26! ≈ 288 možných substitucí. A to jsme do substituce použili jen písmenné znaky bez háčků a čárek. Takovému pokusu o prolomení šifry říkáme útok hrubou silou. Existují i chytřejší útoky, proti kterým substituce není odolná. Můžeme totiž analyzovat četnosti písmen případně bigramů nebo trigramů (dvojic, trojic písmen). Statistické vlastnosti zašifrovaného textu jsou totiž shodné s textem původním. Tedy například nejčastěji se vyskytující znak v šifrovaném textu je nejčastěji se vyskytujícím znakem v původním textu, který s velkou pravděpodobností bude odpovídat nejčastějšímu znaku v daném jazyce. Dále nám mohou pomoci krátká slova, nebo samostatně stojící písmena. Proti takovému útoku již substituční šifra odolná není. 1
Tabulka 1: Četnosti písmen v českém textu psaném bez háčků a čárek s mezerami písmeno A B C D E F G H I J K L M N
% 6,5 1,2 2,4 3,1 10,7 2,3 1,3 4,3 5,6 0,1 0,3 2,8 2,0 5,8
písmeno O P Q R S T U V W X Y Z -
% 6,7 1,6 0,1 5,2 5,0 8,7 2,1 0,8 1,6 0,1 1,6 0,1 18,2
Tabulka 2: Nejčastější bigramy, trigramy a jiné uskupení písmen
nejčastější digramy nejčastější trigramy nejčastější slova nejčastější začátky slov ¿nejčastější konce slov
st, ne, se, na, ni, po, le, ko, od, ra, pr, ov, ro, je, te pro, pri, pre, ost, sta, ter, eni, ova, kte, pra a, v, se, na, je, do, to, pro, ve, k, ze, s, o, z, i p, s, n,o, v, z e, i, a, o, y, u
Zkuste rozšifrovat následující text psaný v češtině bez háčků a čárek zašifrovaný pomocí substituce. Pro usnadnění mezera v šifrovaném textu odpovídá mezeře v původním textu. Pomoci vám mohou tabulky 1 a 2. Posunutí písmen a afinní šifra Jsou založeny na podobném principu a jedná se vlastně o velmi specifické substituce. Jejich výhodou proti substituci je rozsah tajného klíče. Zatímco u obecné substituce je to celá tabulka u posunutí písmen je tajným klíčem jediné číslo, u afinní šifry jsou to dvě čísla. Velikou nevýhodou je jejich malá odolnost proti útokům. Obě metody fungují tak, že písmena v abecedě nějakým způsobem posuneme. K tomu již potřebujeme zavést dva matematické pojmy. Říkáme že celé číslo x je kongruentní s celým číslem y modulo n (přirozené číslo) pokud je rozdíl x − y dělitelný číslem n. Matematicky to zapisujeme takto x ≡ y mod n. Což znamená, že čísla x a y mají stejný zbytek po dělení číslem n. Je-li číslo y ∈ {0, 1, . . . , n − 1}, můžeme jej chápat jako zbytek čísla x po dělení číslem n. Druhým pojmem je číselný okruh
2
Číselný okruh Zm se skládá z 1. množiny Zm = {0, 1, . . . , m − 1}, 2. dvou operací + a × o kterých platí, že pro všechna a, b ∈ Zm : (a) a + b ≡ c mod m, (c ∈ Zm ) (b) a × b ≡ d mod m, (d ∈ Zm ) Navíc jsou obě operace komutativní (a+b = b+a, a×b = b×a), platí asociativní zákony pro obě operace (a + (b + c) = (a + b) + c, a × (b × c) = (a × b) × c), číslo nula označíme jako neutrální prvek vzhledem ke sčítání, protože platí a + 0 = a a číslo 1 je neutrální prvek vzhledem k násobení (a × 1 = a). Vzhledem ke sčítání existuje inverzní prvek. Což je takový prvek b pro který platí a + b ≡ 0 mod m. Je jasné, že takovouto vlastnost má prvek m−a. Naopak inverzní prvek vzhledem k násobení nemusí existovat. Nyní si můžeme na příkladu anglické abecedy předvést jak funguje posunutí písmen a afinní šifra. Písmena očíslujeme od 0, tedy A = 0, B = 1, . . ., Z = 25. U metody posunutí písmen zvolíme tajný klíč k ∈ {0, . . . , 25} a místo písmena s číslem n budeme do šifrovaného textu psát písmeno s číslem m a písmeno očíslované číslem m rozšifrujeme jako písmeno s číslem n takto: n→m≡n+k
mod 26, m ∈ Z26 ,
m→n≡m−k
mod 26, n ∈ Z26 .
U afinní šifry zvolíme jako tajný klíč dvojici čísel k = (a, b). a, b ∈ {0, . . . , 25} a číslo a volíme nesoudělné s 26, tato podmínka je nutná pro existenci inverzního prvku vzhledem k násobení k číslu a v číselném okruhu Z26 (označme jej a−1 ), který budeme potřebovat pro dešifrování. Schéma je velice podobné jako u posunutí písmen, místo písmena s číslem n budeme do šifrovaného textu psát písmeno očíslované číslem m a písmeno s číslem m rozšifrujeme jak písmeno s číslem n takto: n → m ≡ a × n + b mod 26, m ∈ Z26 , m → n ≡ a−1 × (m − b)
mod 26, n ∈ Z26 .
Samozřejmě existují daleko rafinovanější symetrické šifry například AES (Advanced Encryption Standard) používané v dnešní době. U každé symetrické šifry musíme na počátku vyřešit problém jak si předat tajný klíč, aby nepadl do rukou třetí straně. Dlouho nikoho ani nenapadlo, že je možné, sdělit si tajný klíč veřejně. S nápadem jak to provést přišli v roce 1976 Whitfield Diffie, Martin Hellman a Ralph Merkel, kteří tím položili základy asymetrického šifrování.
Asymetrické šifrování Je často nazýváno šifrování s veřejným klíčem, což velmi dobře vystihuje podstatu věci. Na rozdíl od symetrické šifry je známá jak šifrovací metoda, tak i veřejná část klíče. Na jednoduchém schématu 1 popišme, jak takový princip může fungovat. Pojmenujme si komunikující strany Alice a Bob. Bob vybere veřejný kpub a tajný kpr klíč. Veřejnou část klíče zveřejní, takže ho znají všichni (i Alice). Alice pomocí veřejného klíče zašifruje svojí zprávu 3
Obrázek 1: Schéma šifrování s veřejným klíčem
Alice
Bob k pub
k pub , k pr
y
x = k pr o y
y = k pub o x
a pošle jí Bobovi. Ačkoliv všichni znají veřejnou část klíče je Bob jediný, kdo je schopen zašifrovanou zprávu rozšifrovat. To je možné díky jednosměrným funkcím. Jednosměrná funkce Je taková funkce, u které je spočtení y = f (x) pro zadané x lehce proveditelné a zároveň zjištění x při známém y, tedy spočtení x = f −1 (y) je neproveditelné v reálném čase. Funkce s takovými vlastnostmi jsou třeba faktorizace přirozeného čísla, nebo problém diskrétního logaritmu. ¿Faktorizace přirozeného čísla (tedy rozklad na součin prvočísel) je výpočetně velice náročná, třeba v případě kdy zadané číslo je součinem dvou velkých prvočísel. Zkuste si faktorizovat číslo 12144971 a uvidíte jak moc vám to dá práce i když na to půjdete chytře. Tedy nebudete zkoušet dělit všemi možnými čísly, ale jen prvočísly, nebo použijete Fermatovu faktorizaci. Naopak vynásobit dvě prvočísla 3571 a 3401 je velmi snadné. Tato jednosměrná funkce se používá v RSA šifře. Problém diskrétního logaritmu je založen na tomto. Je jednoduché spočítat y = αx mod n pokud známe α, x, n ∈ N, ale zároveň je velmi těžké zjistit z tohoto vztahu x když známe všechno ostatní. Pokud si odmyslíme mod n jde o rovnici y = αx , kterou umíme řešit logaritmem. V následující demonstraci si můžete vyzkoušet, že řešení tohoto problému v reálných číslech je díky monotonii exponenciely celkem snadné i když neumíme počítat logaritmus, zatímco jeho diskrétní obdoba je výpočetně velmi obtížná. U spojité varianty vezmeme nějaké x spočteme αx . Předpokládejme, že α > 1, pokud je výsledek menší než zadané y vezmeme x o něco větší. Je-li výsledek větší než zadané y vezmeme x o něco menší. V případě 0 < α < 1 postupujeme obráceně. A takto můžeme postupovat dokud se dostatečně nepřiblížíme nebo přesně netrefíme zadané y. Nic takového ovšem v diskrétní formě neplatí. Výsledky operace αx mod n jsou naprosto chaotické. Je li αx1 mod n větší než zadané y pak neplatí, že když zkusíme x2 < x1 že bychom se s výsledkem výpočtu αx2 mod n měli přiblížit k požadovanému y. Diffie Hellmanova výměna klíče Na problému diskrétního logaritmu je založená výměna tajného klíče podle Diffieho a Hellmana. Můžeme si jí snadno znázornit na schématu 2. Bob zvolí dostatečně velké prvočíslo p a nějaké α ∈ {2, 3, . . . , p − 2}, (α, p) zveřejní jako veřejnou část klíče. Alice si zvolí svůj tajný klíč a ∈ {2, 3, . . . , p−2}
4
Obrázek 2: Schéma Diffie Hellmanovy výměny klíče
Alice
Bob p, α
vybere a ∈ {2,..., p − 2}
A = α a mod p
vybere prvočíslo p vybere α ∈ {2,..., p − 2} vybere b ∈ {2,..., p − 2}
A B
k AB = B a mod p
B = α b mod p k AB = Ab mod p
a spočte A ≡ αa mod p a pošle jej Bobovi. Bob si zvolí svůj tajný klíč b ∈ {2, 3, . . . , p − 2} a spočte B ≡ αb mod p a pošle jej Bobovi. Oba potom přijatou zprávu umocní na svůj tajný klíč a tím získají stejný tajný klíč. Přesvědčme se, že opravdu oba získají stejný klíč, Alice spočte kAB ≡ B a mod p ≡ (αb )a mod p ≡ (αa )b mod p ≡ Ab mod p, což je to samé co spočítá Bob. Ačkoli celou komunikaci mohla slyšet třetí strana, není schopná v krátkém čase spočíst tajný klíč kAB , neboť by to znamenalo zjistit buď tajný klíč Alice (a), nebo tajný klíč Boba (b). Jenže tyhle klíče se nedají odposlechnout a těžko Alice nebo Bob vyzradí svůj tajný klíč, nezbývá tedy než vyřešit A ≡ αa mod p, pro neznámé a. To je ovšem problém diskrétního logaritmu, což je pro dostatečně velké prvočíslo p nezvládnutelné. RSA šifra Využívá druhou výše zmiňovanou jednosměrnou funkci, tedy faktorizaci čísla. Zkratka RSA jsou první písmena jmen jejích objevitelů pánů Ronalda Rivesta, Adi Shamira a Leonarda Adelmana. Princip šifrování si můžeme snadno znázornit na schématu 3. Než se do toho pustíme, musíme zavést Eulerovu funkci. Eulerova funkce ϕ(n) : N → N je definovaná na přirozených číslech takto ϕ(n) = počet přirozených čísel menších než n nesoudělných s n pro výpočet Eulerovy funkce platí následující tvrzení. Pro p prvočíslo a k ∈ N ϕ(p) = p − 1 , ϕ(pk ) = (p − 1)pk−1 . Pro složené číslo n = pk11 · pk22 . . . pkl l ϕ(n) = ϕ(pk22 ) · ϕ(pk22 ) . . . ϕ(pkl l ) Nyní již máme všechno, abychom mohli vysvětlit princip RSA šifry. Bob zvolí dvě dostatečně velká prvočísla p a q a spočte n = p · q a ϕ(n), pak vybere exponent e ∈ {1, . . . , ϕ(n) − 1} tak aby e a ϕ(n) byla nesoudělná čísla. Nakonec 5
Obrázek 3: Schéma RSA šifry
Alice
Bob vybere 2 prvočísla p, q spočte n p q spočte (n) ( p 1)(q 1) vybere e 1,..., (n) 1, e nesoudělné s φ(n) spočte d: d e 1 mod (n)
n, e zpráva x y x e mod n
y x y d mod n
spočte dešifrovací exponent d tak aby platilo d·e ≡ 1 mod ϕ(n). Neboli nalezne inverzní prvek vzhledem k násobení k prvku e číselného okruhu Zϕ(n) . Podmínka nesoudělnosti e a ϕ(n) je zde proto, aby d existovalo. Čísla n a e pošle Alici jako veřejnou část klíče. Alice zašifruje zprávu x pomocí veřejného klíče tak, že spočte y ≡ xe mod n a zašifrovanou zprávu pošle Bobovi. Ten jí dešifruje pomocí exponentu d tak, že spočte x ≡ y d mod n. Na první pohled není vůbec jasné, že Bob opravdu získá původní zprávu x, že je tato šifra odolá vůči útoku a ani jak Bob spočte dešifrovací exponent d. Nejprve se podívejme na odolnost šifry. Třetí strana zná veřejný klíč n, e a zašifrovanou zprávu y, zná samozřejmě i RSA schéma a je jí jasné, že k dešifrování potřebuje tajný klíč d. Ten ale nelze odposlechnout a Bob ho stěží vyzradí. Nezbývá tedy, než ho spočítat. Tedy najít inverzi k číslu e vzhledem k násobení v číselném okruhu Zϕ(n) . Samotné hledání inverze není těžké a snadno se provede pomocí rozšířeného Euklidova algoritmu, to co je nezvládnutelné v reálném čase je spočtení ϕ(n). Z výše uvedených tvrzení pro výpočet Eulerovy funkce plyne, že nutně potřebujeme znát faktorizaci čísla n. Pokud Bob zvolí dostatečně velká prvočísla, dostatečně od sebe vzdálená nedokážeme faktorizovat n ani pomocí tisíců výkonných počítačů za desítky let. Pokud by Bob zvolil sice velká prvočísla, ale blízko sebe dokážeme najít faktorizaci rychle pomocí Fermatovy faktorizační metody. Tedy RSA šifra je odolná proti útokům jen v případě, že Bob volí prvočísla p a q chytře. Zkusme na jednoduchém příkladu ověřit, že Bob opravdu jednoduchým mocněním dešifruje zprávu. Nechť je situace následující. Bob provede tyto kroky: 1. zvolí dvě prvočísla p = 3, q = 11 2. spočte n = p · q = 3 · 11 = 33 3. spočte ϕ(n) = ϕ(33) = ϕ(3) · ϕ(11) = 2 · 10 = 20 4. zvolí e ∈ {1, . . . , 19}, tak aby e a 20 byli nesoudělné, e = 3 5. najde d tak aby platilo d · 3 ≡ 1 mod 20, d = 7 (7 · 3 = 21 ≡ 1 mod 20)
6
6. pošle Alici veřejný klíč 33, 3 Alice má zprávu x = 4, kterou zašifruje y ≡ 43 mod 33, tedy y = 64 ≡ 31 mod 33 Bob obdrží zprávu y = 31, kterou dešifruje 317 ≡ 4 mod 33 Na příkladu jsme viděli, jak funguje šifra RSA. Zůstává samozřejmě několik otázek. Jak se provádí Fermatova faktorizace, jak hledat inverze pomocí Euklidova algoritmu, nebo jak rychle provádět mocnění v číselných okruzích Zm . Pokud vás téma zaujalo, můžete se těšit na předměty BI-BEZ Bezpečnost kde se setkáte s praktickou stránkou šifrování a předmět MI-MPI Matematika pro informatiku kde porozumíte matematice která je za jednotlivými algoritmy a schématy schovaná. Jako ochutnávku převeďme Fermatův faktorizační algoritmus. Fermatova faktorizace Je faktorizační metoda pro lichá přirozená čísla N a je založena na tvrzení, že každé přirozené liché číslo N může být zapsáno jako rozdíl čtverců, tedy N = a2 − b2 . Tento vztah může být přepsán do tvaru N = (a + b) · (a − b) , tedy pokud najdeme čísla a a b, pak již máme faktory čísla N , pokud (a + b), nebo (a − b) nejsou prvočísla zopakujeme Fermatovu faktorizaci, pokud jsou sudá budeme nejdříve vytýkat mocniny dvojky. Takto jsem schopni rozložit číslo N na součin prvočísel. Jak ale najít čísla a a b? Budeme postupovat podle iteračního schématu: √ 1. a = celá část z N 2. b2 = a2 − N (vyplývá z výše uvedeného tvrzení) √ 3. pokud b = a2 − N není přirozené číslo zvýšíme a o jedna a pokračujeme krokem 2, je-li b ∈ N pak hledaná faktorizace je N = (a + b)(a − b) Odtud je vidět, že pokud bude N součinem dvou skoro stejně velkých prvočísel, najdeme faktorizaci rychle. Ukažme si to na příkladu. Buď N = 19 · 17 = 323 a postupujme podle schématu √ 1. a = celá část z 323, a = 18 2. b2 = 182 − 323 = 1 3. b = 1, hledaná faktorizace je 323 = (18 + 1) · (18 − 1) = 19 · 17. Odtud vidíme, že pokud je N součinem dvou blízkých prvočísel, dokážeme najít faktorizaci rychle (třeba jen v jednom kroku). Ale pokud jsou prvočísla od sebe dost vzdálená je tato metoda velice pomalá, protože v každém kroku zvyšujeme a jen o jedna.
7
