Drobný úvod do matematiky bezpečnosti

Drobný u´vod do matematiky bezpeˇcnosti Martin Beránek Stˇredn´ı Sm´ıchovsk´ a pr˚ umyslov´ a ˇskola

17. ledna 2015

ˇ Martin Ber´ anek (SSPS)

Drobn´ yu ´vod do matematiky bezpeˇ cnosti

17. ledna 2015

1 / 105

Co nás ˇceká 1 2

3

4 5 6

7 8 9

´ Uvod Informace! Obsaˇznost jazyka Typy ˇsifer Proudová ˇsifra Bloková ˇsifra Caesarova ˇsifra Vernamova ˇsifra Spousta teorie Konf´ uze vs dif´ uze P=NP? Exponenciáln´ı ˇsifra Axiomy Kvadratické residuum ˇ Martin Ber´ anek (SSPS)

10 11

12

13 14 15

Generátory grupy Prvoˇc´ısla Maska a co s n´ı Inverze Hledán´ı prvoˇc´ısel Eratosthenovo s´ıto Rabin-Miller Malá Fermatova vˇeta Eulerova funkce ˇ C´ınská vˇeta RSA RSA-CRT Feistel˚ uv kryptosystém


16 17 18 19

20 21 22

23

AES Operaˇcn´ı módy RC4 Hash Kolize HMAC Veˇrejné kl´ıˇce DSA Model OIS Sluˇzby bezpeˇcnosti Mechanismy bezpeˇcnosti ´ Utoky na bezpeˇcnost Závˇer 17. ledna 2015

2 / 105

Worf!



17. ledna 2015

3 / 105

Entropie M´ıra neurˇcitosti zprávy Entropie vyjadˇruje pr˚ umˇernou informaˇcn´ı hodnotu jedné zprávy z daného zdroje Co je ale informaˇcn´ı hodnota? Zde pravdˇepodobnost jedné zprávy zdroje P H(X ) = − ni=1 pi log2 pi Pˇr.: Mˇejme ˇctyˇri zprávy ˇcervená, ˇzlutá, zelená a b´ılá (barvy odjezdového návˇestidla na nádraˇz´ı), ty maj´ı pravdˇepodobnost: 1 1 1 1 4 , 2 , 8 , 4 , potom entropie je rovna: H(X ) = −( 14 log2 14 + 21 log2 12 + 18 log2 18 + 14 log2 14 ) = −( 41 · (−2) + 12 · (−1) + 81 · (−3) + 41 · (−2)) = 1, 75



17. ledna 2015

4 / 105

Entropie Maximáln´ı entropie nastává, pokud maj´ı vˇsechny zprávy stejnou pravdˇepodobnost: H(X ) = log2 (n) Minimáln´ı nastává, pokud pˇrijde pouze jedna zpráva a má pravdˇepodobnost 1, potom H(x) = 0 A k ˇcemu nám to je? K ˇcemu to potˇreboval pan Shannon? K tomu potˇrebujeme nadefinovat hned nˇekolik veliˇcin: ) – Obsaˇznost jazyka pro zprávy délky N, X je zdroj zprávy, RN RN = H(X N potom vrát´ı pr˚ umˇernou entropii znaku zprávy r = limN→∞ RN – Obsaˇznost jazyka vzhledem k 1 p´ısmenu, pr˚ umˇerná entropie znaku ve zprávˇe, pro angliˇctinu r = 1,3 aˇz 1,5 N R = logN2 L = log2 L – Absolutn´ı obsaˇznost jazyka – pr˚ umˇerná entropie znaku pokud by byly vˇsechny zprávy a znaky stejnˇe pravdˇepodobné L – poˇcet znak˚ u v abecedˇe LN – poˇcet zpráv délky N vˇsechny stejnˇe pravdˇepodobné: p = L1N Entropie takového zdroje H(X 0 ) = log2 LN = N log2 L D = R - r – Redundance jazyka, nadbyteˇcnost ˇ Martin Ber´ H(K )anek (SSPS)


17. ledna 2015

5 / 105

Pˇr´ıklad

Mˇejmˇe AES-256 s délkou kl´ıˇce 256 bit˚ u. Touto ˇsifrou zachytáváme text, o kterém v´ıme, ˇze je v angliˇctinˇe v k´ odován´ı ASCII 8-bit. Kolik znak˚ u mus´ıme odchytit, aby mu odpov´ıdala jediná smysluplná zpráva. H(K ) = 256 – entropie kl´ıˇce D = R − r – redundance R = 8 (abeceda je ASCII 8-bit) r = 1, 5 (angliˇctina) D = 8 − 1, 5 = 6, 5 ) 256 δU = H(K D = 6,5 = 39, 38 Staˇc´ı nám tedy 40 znak˚ u ˇsifrového textu, abychom vˇedˇeli, ˇze text obsahuje jediný smyslnuplný otevˇrený text.



17. ledna 2015

6 / 105

Otázka!

Kolik znak˚ u ˇsifrového textu by bylo potˇreba s DES?



17. ledna 2015

7 / 105

SRSLY?



17. ledna 2015

8 / 105

Proudová ˇsifra Vigener˚ uv autokláv ˇ Sifra reaguje na minulý stav ˇsifrovaných dat ˇ Sifrovac´ ı funkce má dva vstupy, minulý kousek dat a kl´ıˇc



17. ledna 2015

9 / 105

Proudová ˇsifra



17. ledna 2015

10 / 105

Bloková ˇsifra



17. ledna 2015

11 / 105

Caesarova ˇsifra

Kl´ıˇcem je celé ˇc´ıslo Kl´ıˇc se pˇriˇc´ıtá k ˇc´ıselné hodnotˇe p´ısmena abecedy Funkce vypadá pro jedno p´ısmeno: f (a) = |a + k|24 , kde k je kl´ıˇc, a je vstupn´ı znak a 24 je modulo poˇctu symbol˚ u abecedy Deˇsifrován´ı obstará inverzn´ı funkce: f (b) = |b − k|24 , kde k je kl´ıˇc, b je vstupn´ı znak pro deˇsifrován´ı a 24 je modulo poˇctu symbol˚ u abecedy Problémem je frekveˇcn´ı analýza, která se dá vygenerovat pro kaˇzdý jazyk



17. ledna 2015

12 / 105

Caesarova ˇsifra



17. ledna 2015

13 / 105

Caesarova ˇsifra

K prolomen´ı staˇc´ı vhodnˇe porozumˇet frekvenˇcn´ı analýze Vypracujete si ˇcetnost p´ısmen abecedy r˚ uzných jazyk˚ u Podle ˇcetnosti v kódovaném textu potom m˚ uˇzete zkusit aplikovat posun



17. ledna 2015

14 / 105

Frekvenˇcn´ı analýza C# public class FrqAnalys { public Dictionary < char , int > chars ; public string fileName ; public FrqAnalys ( string name ) { chars = new Dictionary < char , int >() ; fileName = name ; } public void countFreq () { Stream s = new FileStream ( fileName , FileMode . OpenOrCreate ) ; StreamReader sr = new StreamReader ( s ) ; string text = sr . ReadToEnd () ; sr . Close () ; for ( int i = 0; i < text . Length ; i ++) { char c = text [ i ]; if ( chars . ContainsKey ( c ) ) chars [ c ]++; else chars . Add (c , 1) ; } } }



17. ledna 2015

15 / 105

Vernamova ˇsifra Nejbezpeˇcnˇejˇs´ı ˇsifra Neprolomitelná Do dnes pouˇz´ıvaná (ˇr´ıká se, ˇze Ruskými agenty) Kl´ıˇc je stejnˇe dlouhý jako otevˇrený text Pouˇz´ıvá se operace XOR˚ u



17. ledna 2015

16 / 105

Vernamova ˇsifra



17. ledna 2015

17 / 105

Vernamova ˇsifra C++ # include < iostream > # include < string > using namespace std ; char * EnDecrypt ( const string & input , const string & key ) { if ( key . length () != input . length () ) throw string ( " Key or input not same size ! " ) ; char * output = new char [ input . length () ]; for ( unsigned int i =0; i < input . length () ; i ++) { output [ i ]=( input [ i ]^ key [ i ]) ; } return output ; } int main () { string text ( " Hello world ! " ) ; string key ( " abcdefghkijk " ) ; string cipher = string ( EnDecrypt ( text , key ) ) ; cout << EnDecrypt ( cipher , key ) << endl ; return 0; }



17. ledna 2015

18 / 105

Konfúze vs difúze

Konf´ uze má za u ´kol zmˇenit ˇsifrový text tak, ˇze zmˇen´ıme znaky v OT ˇ na jiné a vytvoˇr´ıme ST I

Pˇr´ıkladem je substituce - té se pouˇz´ıvá v Caesarovˇe ˇsifˇre, ...

ˇ tak, ˇze nen´ı Dif´ uze má za u ´kol zmˇenit poˇrad´ı znak˚ u OT do ST um´ıstˇen´ı znak˚ u nen´ı stejné (jako, kdybychom podle nˇejakého kl´ıˇce zam´ıchali OT) I

Pˇr´ıkladem jsou tˇreba ˇsifry maticového charakteru, tedy Hillova ˇsifra, Transpoziˇcn´ı ˇsifra, ...

A proˇc tyto term´ıny znát? Uˇz jen tˇreba kv˚ uli tomu, ˇze modern´ı ˇsifry kombinuj´ı oboje.



17. ledna 2015

19 / 105

P=NP

P jsou polynomiáln´ı problémy - tedy u ´lohy, které lze ˇreˇsit v polynomiáln´ım ˇcase I I

I

Hledán´ı GCD je tˇreba takový problém V podstatˇe vˇsechny problémy, které m˚ uˇzete ˇreˇsit na deterministickém Turingovˇe stroji Tedy vˇsechny problémy, na které lze vymyslet nˇejaké ˇcasovˇe sh˚ udné ˇreˇsen´ı

NP jsou nedeterministické polynomiáln´ı problémy - tedy u ´lohy, které dokáˇze vyˇreˇsit jen nedeterministický Turing˚ uv stroj I I I

Tˇreba deˇsifrován´ı dobré ˇsifry, pokud neznáte postup ˇreˇsen´ı Pro NP u ´plné problémy dokonce nen´ı moˇzné hledat polynomiáln´ı ˇreˇsen´ı Velká otázka matematiky a stringologie je, zdali P=NP?



17. ledna 2015

20 / 105

P=NP

Co kdyby P=NP? Co to znamená pro kryptografii Nˇekdo by naˇsel algoritmus, který by kaˇzdý NP problém pˇrevedl na P problém ˇ Sifrov´ an´ı v RSA je P problém a stejnˇe tak deˇsifrován´ı, pokud máme správný kl´ıˇc Prolamován´ı je ale uˇz NP problém a pokud by NP=P, pak by i prolamován´ı byl P problém To by byl konec kryptografie, jak j´ı známe



17. ledna 2015

21 / 105

Vernamova ˇsifra



17. ledna 2015

22 / 105

Exponenciáln´ı ˇsifra

Kryptovac´ı funkce c = |p e |m , kde 0 < e < m − 1; gcd(e, m − 1) = 1 Dekryptovac´ı funkce p = |c d |m , kde d = |e −1 |m−1 Podm´ınky jsou omezuj´ıc´ı, protoˇze mus´ı existovat inverzn´ı ˇ c´ıslo v modulárn´ı soustavˇe. Za m si nem˚ uˇzeme zvolit ledajaké ˇc´ıslo Celý problém vycház´ı z diskrétn´ıho logaritmu. Pokud Y ≡ q k (mod m), pak inverzn´ı funkci je skoro nemoˇzné nalézt Takových vlastnost´ı se vyuˇz´ıvá pro Diffie-Helman algoritmus



17. ledna 2015

23 / 105

Alice a Bob



17. ledna 2015

24 / 105

Diffie Helmann pro dva uˇzivatele

g - je grupa - grupa je matematické tˇeleso, které obsahuje vlastnosti uzavˇrenosti na operaci ⊕; je asociativn´ı, má inverzn´ı prvek a obsahuje neutráln´ı prvek ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

25 / 105

Axiomy

Uzavˇrenost - nen´ı pˇr´ımo axiom - mˇejme a a b, které jsou ze stejné mnoˇziny (N, W, R, ...), potom operace ⊕ mezi a ⊕ b z˚ ustává stále na stejné mnoˇzinˇe 1

a ⊕ b = b ⊕ a - komutativita (takovou vlastnost grupa nemá, pokud ano, pak se nazývá Abbelova grupa)

2

(a ⊕ b) ⊕ c = a ⊕ (b ⊕ c) - asociativita

3

a ⊕ i = 1, kde i je inverzn´ı prvek

4

a ⊕ n = a, kde n je neutráln´ı prvek



17. ledna 2015

26 / 105

Kvadratické residuum

Pokud m je kladné celé ˇc´ıslo ⇒ celé ˇc´ıslo a je kvadratické residuum modulo m, kdyˇz gcd(a, m) = 1 a kongruence x 2 ≡ amod(m) má nˇejaké ˇreˇsen´ı. Kdyˇz tato kongruence nemá ˇzádné ˇreˇsen´ı ⇒ a je kvadratické nonresiduum modulo m. Vlastnˇe zjiˇst’ujeme, jaká ˇc´ısla nám dává vztah |x 2 |m . Takto m˚ uˇzete stanovit mnoˇziny residu´ı a nonresidui´ı (ˇc´ısel, které se nevyskytuj´ı mezi residui).



17. ledna 2015

27 / 105

Symboly Legendre˚ uv symbol – Je 1 kdyˇz a je kvadratickým residuem, -1 pokud a je kvadratickým nonresiduem. Jacobiho symbol – a mus´ı být nesoudˇelné s n (jinak je a stejnˇe nonresiduum). Udˇeláme kanonický rozklad modula (ˇc´ısla n) – tj rozklad na souˇcin prvoˇc´ısel. Rychle urˇc´ıme, zdali je a residuem, nebo nonresiduem n. Jaké je x nezjist´ıme. Pˇr´ıklad: 2 2 2 2 · 5 = (−1)2 · (−1) = −1 = = 2 45 3 3 ·5 2 je tedy kvadratické nonresiduum.

2



17. ledna 2015

28 / 105

Generátory grup

Co kdybychom pro pˇredpis grupy potˇrebovali jen jedno ˇc´ıslo v grupˇe a to by nám vygenerovalo ostatn´ı ˇc´ısla grupy? A jak s t´ım souvis´ı grupy o prvoˇc´ıselné velikosti? Je 7 generátorem grupy Z11 ? To znamená skládat |7|11 ,|7 ∗ 7|11 , ... Pokud mi vypadne z mocnin ˇc´ıslo 1, pak se zastav´ım Pokud byly vˇsechny ˇc´ısla, které jsem vygeneroval, souˇcást´ı grupy Z11 , pak je 7 generátorem grupy Z11



17. ledna 2015

29 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC Jak velká ˇc´ısla m˚ uˇzeme dát do známých datových typ˚ u? Char má bajt (8 bit˚ u, max ˇc´ıslo 28 ) Int má 4 bajty (32 bit˚ u, max ˇc´ıslo 232 ) Long int má 4 bajty (32 bit˚ u, max ˇc´ıslo 232 ) Long long int má 8 bajt˚ u (64 bit˚ u, max ˇc´ıslo 264 ) Double má 8 bajt˚ u (64 bit˚ u, max ˇc´ıslo 264 ) Float má 4 bajt˚ u (32 bit˚ u, max ˇc´ıslo 232 ) Co se stane, kdyˇz ˇc´ıslo pˇreteˇce? A co dˇelá poˇc´ıtaˇc, kdyˇz potˇrebuje poˇc´ıtat s vˇetˇs´ımi ˇc´ısli?



17. ledna 2015

30 / 105

Vˇsechno je o datových typech!



17. ledna 2015

31 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC Ukázka pˇreplut´ı C++ # include < iostream > using namespace std ; int main () { unsigned int i =10; long long unsigned int j =0; // pocitadlo while ( i !=9) { i ++; j ++; } cout << " pocet konecnych iteraci cyklu je : " << j << endl ; // napoveda : 2^32 -1 , proc tomu tak je ? return 0; }



17. ledna 2015

32 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC Datové typy jsou takové velké modluárn´ı soustavy Pokud chcete skladovat vˇetˇs´ı ˇc´ısla, rozdˇelte je do menˇs´ıch pomoc´ı masek Pˇr´ıklad: Ukládáme druhý byte (8 bit˚ u) z unsigned integeru (32 bit˚ u) do charu (8 bit˚ u): (10101110 10101111 10111110 10101010)2 & (00000000 00000000 11111111 00000000)2 = (00000000 00000000 10111110 00000000)2

Protoˇze ale budeme ukládat do bytu, mus´ıme jeˇstˇe posunout int doprava o 8 m´ıst a potom ORovat do char: 8 >> (00000000 00000000 10111110 00000000)2 | = (00000000 00000000 00000000 10111110)2

A to uˇz se do charu vejde. ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

33 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC C++ # include < iostream > using namespace std ; int main () { unsigned int input =2930753194; // 10101110 10101111 10111110 10101010 unsigned int mask =65280; // 00000000 00000000 11111111 00000000 unsigned int output =0; unsigned char outputc =0; output = mask & input ; cout << output << endl ; // 48640 output > >=8; cout << output << endl ; // 190 outputc |= output ; cout << ( unsigned int ) outputc << endl ; // 190 return 0; }



17. ledna 2015

34 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC

Pˇresnˇe takhle m˚ uˇzete vymaskovat ˇc´ısla z velkých ˇc´ısel a malá ˇc´ısla dávat zase do velkých ˇc´ısel Binárn´ı operace vˇetˇsinou pˇrekladaˇc vyhodnot´ı do rychlejˇs´ıch instrukc´ı neˇz jiné operace Maska nen´ı jen spojité ˇc´ıslo dlouhé maximálnˇe 32 bit˚ u, ale moˇznost, jak z ˇc´ısla z´ıskat ˇc´ıslo



17. ledna 2015

35 / 105


Pro ˇsifrován´ı, jak jsme vidˇeli u exponenciáln´ıch ˇsifer, je nutné m´ıt vˇsechny operace ., :, +, − To ale nemus´ı vˇzdy platit, proto se pouˇz´ıvaj´ı soustavy z modulem prvoˇc´ısel Pro operace dˇelen´ı je potˇreba inverzn´ı ˇc´ıslo a.X ≡ b (mod m) X ≡ b. 1a (mod m) Pokud je ale gcd(a, m) = 1. Pokud tomu tak nen´ı, výsledk˚ u m˚ uˇze být v´ıc. Pokud má ˇc´ıslo jednoznaˇcnou inverzi, plat´ı jednoduˇse: |a.b| ≡ 1 (mod m) kde a je ˇc´ıslo a b je inverzn´ı ˇc´ıslo. GCD = greatest common divisor



17. ledna 2015

36 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC Pˇr´ıklad pokud gcd=1 neplat´ı: 8x ≡ 4 (mod 12) Urˇc´ıme gcd pomoc´ı rozˇs´ıˇreného Euklidova algoritmu: zbytek 12 8 1 0 12 8 0 1 1 4 1 -1 2 0 Z toho vytvoˇr´ıme Diofantickou rovnici 8u + 12v = 4, coˇz podle naˇseho výpoˇctu dává u = −1; v = 1, gcd je rovno 4. Postup funguje tak, ˇze si nejdˇr´ıve vytvoˇr´ım dva sloupce. Prvn´ı sloupec je pro pod´ıly dˇelen´ı a druhý pro zbytky. Zbytek pˇred ˇrádkem, kde je 0, je naˇse gcd. pod´ıl



17. ledna 2015

37 / 105


Dva dalˇs´ı sloupce jsou rozˇs´ıˇren´ı Euklidova algoritmu, kde vˇzdy sloˇzen´ı 1*12+0*8=12, tedy sloupeˇcku zbytk˚ u. Jak sloˇzit dalˇs´ı ˇrádek je trochu sloˇzitˇejˇs´ı. se sloˇz´ı pomoc´ı vztahu <prvn´ı ˇrádek, tˇret´ı sloupec>-1*, tedy 1 se sloˇz´ı pomoc´ı vztahu <prvn´ı ˇrádek, ˇctvrtý sloupec>-1*, tedy -1 To se dá ovˇeˇrit pomoc´ı posledn´ıho vztahu 4 = 12 + (−1) ∗ 8, coˇz plat´ı



17. ledna 2015

38 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC −1.4 u.4 = gcd(12,8) = −1 a protoˇze jsme v modulu, pro Ted’ urˇc´ıme x0 = gcd(12,8) -1 plat´ı, ˇze je rovno 11 12 Ted’ stanov´ıme x = x0 ∗ (mod gcd(12,4) ) = 11 (mod 3) = 2 (mod 3) Ted’ uˇz v´ıme, ˇze poˇcet ˇreˇsen´ı bude 4, protoˇze gcd je rovno 4. Bude v mod 12, jako p˚ uvodn´ı zadán´ı a mus´ı se ”odkrokovat”od 1 do 4, coˇz je poˇrád naˇse gcd. Dalˇs´ım poznatkem je, ˇze kaˇzdý ˇclen bude seˇcten s x0 a násobkem modula u x, tedy pro tento pˇr´ıklad: 12 12 12 12 , x0 − 2 ∗ gcd(12,4) , x0 − 3 ∗ gcd(12,4) , x0 − 4 ∗ gcd(12,4) }| |{x0 − 1 ∗ gcd(12,4) (mod 12) = = |{−1 + 1.3, −1 + 2.3, −1 + 3.3, −1 + 4.3}| (mod 12) = = |{2, 5, 8, 11}| (mod 12)



17. ledna 2015

39 / 105


Jenomˇze nˇeco takového se rozhodnˇe nedá pouˇz´ıt v exponenciáln´ı ˇsifˇre, kde hledáme vˇse jednoznaˇcné Jak by jinak bylo moˇzné text znovu rozluˇstit Proto se pouˇz´ıvá takové soustavy, kdy gcd je rovno 1 a inverzn´ı ˇc´ıslo je vˇzdy jednoznaˇcnˇe dohledatelné a je jen jedno



17. ledna 2015

40 / 105

Prvoˇc´ıselná modulárn´ı soustava a ˇcastá modula v PC Pˇr´ıklad pokud gcd=1 plat´ı: 3x ≡ 4 (mod 5) x ≡ 4 ∗ 13 (mod 5) Urˇc´ıme gcd pomoc´ı rozˇs´ıˇreného Euklidova algoritmu: pod´ıl

zbytek 5 3 5 1 0 3 0 1 1 2 1 -1 1 1 -1 2 2 0 Potom m˚ uˇzeme napsat x ≡ 4 ∗ 2 (mod 5) tedy x ≡ 8 (mod 5) a po uplatnˇen´ı modula x ≡ 3 (mod 5)



17. ledna 2015

41 / 105

Prvoˇc´ıslo Prvoˇc´ıslo je pˇrirozené ˇc´ıslo dˇelitelné jedniˇckou a sebou samým Jenˇze jak na to pˇrij´ıt pokud je ˇc´ıslo vetˇs´ı neˇz 10n , kde n je jakékoliv pˇrirozené ˇc´ıslo A jak nˇejaké vysoké ˇc´ıslo vygenerovat? Hloupý test v Pythonu: # !/ usr / bin / python from math import sqrt def isPrimeDul ( input =0) : for i in range (2 , int ( sqrt ( input ) +1) ) : if ( input % i ) == 0: return False return True print isPrimeDul (3571) # True print isPrimeDul (3570) # False



17. ledna 2015

42 / 105

Prvoˇc´ıslo

Jenˇze, co kdyˇz prvoˇc´ıslo bude tak ohromné, ˇze poˇcet iterac´ı, které se budou muset proj´ıt, bude rovno samotnémé odmocninˇe ˇc´ısla? √ M˚ uˇzeme tedy odvodit sloˇzitost O( n) pro nejtˇeˇzˇs´ı pˇr´ıpad, kdy ˇc´ıslo je doopravdy prvoˇc´ıslo Ω(1) pro nejlehˇc´ı pˇr´ıpad, kdy je ˇc´ıslo hned dˇelitelné dvˇema √ Θ( n) pro jakékoliv ˇc´ıslo, coˇz je pomˇernˇe dost Dalˇs´ı algoritmus, který se dá pouˇz´ıt pro hledán´ı prvoˇc´ısel na podobném základˇe, ale je nepouˇzitelný, je Eratosthenovo s´ıto



17. ledna 2015

43 / 105

Eratosthenovo s´ıto C++ Jak by asi vypadala tabulka pro ˇc´ıslo 257885161 − 1? Jak velkou pamˇet’ bychom museli pouˇz´ıt? # include < iostream > using namespace std ; unsigned int * giveMe ErPrime s ( const unsigned int & sizeIn ) { unsigned int * retField = new unsigned int [ sizeIn ]; for ( unsigned int i =0; i < sizeIn ; i ++) retField [ i ]=1; // o vsech cislech predpokladam , ze jsou prvocisla for ( unsigned int i =2; i < sizeIn ; i ++) { if ( retField [ i ]) { // cislo je prvocislo , tak jeho nasobky uz ale prvocislo rozhodne nebudou for ( unsigned int j =2; j *i < sizeIn ; j ++) { // vsechny nasobky oznacime , ze jsou neprvocisla retField [ j * i ]=0; } } } return retField ; } ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

44 / 105

Rabin-Miller˚ uv test

Co kdyˇz budeme m´ıt funkci, která nám s nˇejakou pravdˇepodobnost´ı dá prvoˇc´ıslo? A co kdyˇz budeme m´ıt funkci, která nám s jistou pravdˇepodobnost´ı vrát´ı, zdali je ˇc´ıslo prvoˇc´ıslo? Takovým testem je Rabin-Miller˚ uv test, který vrát´ı se sloˇzitost´ı pár krok˚ u, zdali je naˇse ˇc´ıslo prvoˇc´ıslo Test v˚ ubec nemluv´ı o tom, jac´ı dˇelitelé dˇel´ı ˇc´ıslo, pokud nen´ı prvoˇc´ıslo, ale ˇr´ıká, ˇze existuj´ı, coˇz staˇc´ı



17. ledna 2015

45 / 105

Rabin-Miller˚ uv test Pˇr´ıklad: uˇze být svˇedkem, lháˇrem ˇci silným lháˇrem, Otestujte ˇc´ıslo 13 s báz´ı 5 - 5 m˚ ˇze ˇc´ıslo 13 je, ˇci nen´ı prvoˇc´ıslo. Volba báze je velice d˚ uleˇzitá. Pokud test udˇeláte pro ˇc´ısla 18 báz´ı 25, test vrát´ı, ˇze 18 je prvoˇc´ıslo a 25 je potom lháˇrem. Uprav´ıme p − 1 = 12 = 22 .3 ⇒ m = 3, b = 2 (512 − 1) ≡ 0 (mod 13) (56 − 1)(56 + 1) ≡ 0 (mod 13) (53 − 1)(53 + 1)(56 + 1) ≡ 0 (mod 13) ˇ ısla uˇz dál nem˚ C´ uˇzem dˇelit na dalˇs´ı koˇreny (v R), proto rozdˇel´ıme výpoˇcet na tˇri ˇcásti. Jakákoliv z nich m˚ uˇze být rovna nule, pokud ano, test vyˇsel: (53 − 1) tedy |53 |13 = 8 6≡ 1 (mod 13) (53 + 1) tedy 8 6≡ −1 (mod 13) (56 + 1) tedy |56 |13 = |82 |13 = 12 ≡ −1 (mod 13) Test vyˇsel, 13 je prvoˇc´ıslo a 5 je jeho svˇedkem. Pokud chcete vyzkouˇset, jak se to programuje, pod´ıvejte se na http://rosettacode.org/wiki/Miller-Rabin_primality_test ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

46 / 105

Homer a Velká Fermatova vˇeta



17. ledna 2015

47 / 105

Malá Fermatova vˇeta Vˇeta tvrd´ı, ˇze pro prvoˇc´ıslo p a pˇrirozené ˇc´ıslo a, kde gcd(a,p)=1 plat´ı: ap−1 ≡ 1 (mod p) K ˇcemu nám ale vˇeta je? |x| Mˇejme |ax |p (p-prvoˇc´ıslo, gcd(p,a)=1), potom plat´ı ||a|p p−1 |p . Ukáˇzeme si na pˇr´ıkladu: |100012345 |19 hned vid´ıme, ˇze se vˇeta dá pouˇz´ıt |12345|18 ||1000|19 |19 ≡ |1215 |19 dokonce si m˚ uˇzeme dovolit ˇc´ısla otoˇcit ve své 15 modulárn´ı soustavˇe | − 7 |19 ≡ |(11.11.11.11.11.11.11.(−7))|19 ≡ |7.7.7.11.(−7)|19 ≡ |11.7.11.(−7)|19 ≡ |7.7.(−7)|19 ≡ | − 1|19 ≡ |18|19

Fermat byl velký matematik a jeho nejvˇetˇs´ı pˇr´ınos budoucnosti byla Velká Fermatova vˇeta, která se stala symbolem snahy celé generace matematik˚ u. Rád bych ji zde napsal, ale uˇz nemám m´ısto na slidu.



17. ledna 2015

48 / 105

Eulerova funkce Jenˇze to plat´ı pro p prvoˇc´ıslo, coˇz je velice málo pˇr´ıpad˚ u M˚ uˇzeme ale pouˇz´ıt Eulerovu funkci Eulerovu funkce: Znaˇc´ı se jako Φ(n) Vrac´ı poˇcet nesoudˇelných ˇc´ısel s n Pˇr´ıklad: √ √ 12 23 1 √ 2 13 24 √ √ 3 14 25 √ 4 15 26 √ √ 5 16 27 √ 17 28 = 16 Φ(32) = 6 √ √ 18 29 7 √ 8 19 30 √ √ 9 20 31 √ 10 21 32 √ 11 22 ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

49 / 105

Eulerova funkce

Funkce má zajimavé vlastnosti popsané správnˇe na Wikipedii Jedna z nich je, ˇze pro Φ(p) = p − 1, kdy p je prvoˇc´ıslo |b|Φ(c)

Ukázka aplikace z pˇr´ıkladu: Mˇejme |ab |c , potom plat´ı ||a|c |122| ||47|32 Φ(32) |32

|c .

|122| ||47|32 16 |32

|47122 |32 = = = ||15|10 |32 = |225.225.255.255.255|32 = |1.1.1.1.1|32 = 1



17. ledna 2015

50 / 105

ˇ ınská vˇeta o zbytc´ıch Velká C´

ˇ ıká se, ˇze na n´ı pˇriˇsel Sun Tzu pˇri poˇc´ıtán´ı voják˚ R´ u Nechal je seˇradit podle nˇekolika kritéri´ı a spoˇc´ıtal zbytky Pak ˇrekl kolik jich je V IT se vˇeta pouˇz´ıvá k výpoˇctu velkých ˇc´ısel, kv˚ uli postupu se celý výpoˇcet rozloˇz´ı na menˇs´ı ˇcásti a t´ım se dá znaˇcnˇe urychlit



17. ledna 2015

51 / 105

Terakotova armáda

Výpoˇcet byl testován na hlinˇených vojác´ıch - testy na lidech jsou zakázané!



17. ledna 2015

52 / 105

ˇ ınská vˇeta o zbytc´ıch C´ Pˇr´ıklad: Mˇejme |x|3 = 1, |x|5 = 2, |x|7 = 3 soustava modul je nesoudˇelná, vypoˇcteme si M: M = 3.5.7 = 105, potom malá M: M3 = 7.5 = 35, M5 = 3.7 = 21, M7 = 3.5 = 15 potom se dá sestavit celý vztah následovnˇe: x = ||x|3 M3 y3 + |x|5 M5 y5 + |x|7 M7 y7 |M yn jsou inverz´ı ˇc´ısla k malým M, tedy: 35y3 ≡ 1 (mod 3), 21y5 ≡ 1 (mod 5), 15y7 ≡ 1 (mod 7) Modula jsou prvoˇc´ısla, proto m˚ uˇzeme uplatnit postup pomoc´ı rozˇs´ıˇreného Euklidova algoritmu a dostaneme: y3 ≡ 2 (mod 3), y5 ≡ 1 (mod 5), y7 ≡ 1 (mod 7) Ted’ m˚ uˇzeme uˇz dopsat celý vztah: = |1.35.2 + 2.21.1 + 3.15.1|105 = |157|105 = 52



17. ledna 2015

53 / 105

ˇ ınská vˇeta o zbytc´ıch C´ Vˇeta má i svou obecnou verzi, pˇri které opakovanˇe dosazujeme. Ukáˇzeme si to na pˇr´ıkladu: Vojáci nastoup´ı pˇred kasárna a je jim pˇrikázáno, aby se ˇradili na povel. Prvn´ı povel byl seˇradit se po dvou, v posledn´ı ˇradˇe zbyl jeden voják. Pˇri seˇrazen´ı po tˇrech zbyly dva, pˇri ˇctyˇrech tˇri, pˇri pˇeti ˇctyˇri, pˇri ˇsesti pˇet a pˇri sedmi nezbyl ˇzádný. Ted’ uˇz m˚ uˇzem sestavit podle zadán´ı systém kongurencn´ı: x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 4), x ≡ 4 (mod 5), x ≡ 5 (mod 6), x ≡ 0 (mod 7) Oproti minulému pˇr´ıkladu vid´ıme, ˇze modula kongurencn´ı jsou soudˇelná, proto nem˚ uˇzeme pouˇz´ıt pˇr´ımo prvn´ı metodu. Jenomˇze, co je výsledek kongurence neˇz zbytek po dˇelen´ı. M˚ uˇzeme tedy s klidem napsat, ˇze x ≡ 1 (mod 2) se rovná x = 1 + 2.t. V´ıme totiˇz, ˇze dˇelen´ım dvˇema vyˇsel zbytek jedna, ale nev´ıme kolik t jsme museli m´ıt pro takový výsledek. Ted’ uˇz jen zbývá postup opakovat a dosazovat. ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

54 / 105

ˇ ınská vˇeta o zbytc´ıch C´ Dosad´ıme náˇs poznatek do dalˇs´ı kongurence, protoˇze hledáme jedno x. 1 + 2t = 2 (mod 3) zde se odeˇcten´ım dostaneme k t = 12 (mod 3) a ˇreˇsen´ı prvn´ıho dosazen´ı je t = 2 (mod 3), to zase m˚ uˇzeme pˇrepsat na t = 2 + 3s a zase dosadit. 2 + 3s = 3 (mod 4) vypoˇcteme na s = 3 (mod 4) a znovu sestavit s = 3 + 4u. To dosad´ıme do 3 + 4u = 4 (mod 5) vypoˇcteme u = 4 (mod 5) a sestav´ıme u = 4 + 5z. Znovu dosad´ıme 4 + 5z = 5 (mod 6) vypoˇcteme z = 5 (mod 6) a sestav´ıme z = 5 + 6y . To dosad´ıme do posledn´ı kongurence: 5 + 6y = 0 (mod 7) kde z´ıskáme y = 5 (mod 7) a proto y = 5 + 7p. Ted’ vˇse dosad´ıme zpátky do sebe, abychom mohli vyjádˇrit x. x = 1 + 2(2 + 3(3 + 4(4 + 5(5 + 6(5 + 7p))))) jenomˇze ted’ nám stále zbývá vyjádˇrit p, coˇz ale p˚ ujde aˇz uvid´ıme, co vznikne po roznásoben´ı a posˇc´ıtán´ı. x = 4319 + 2.3.4.5.6.7p ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

55 / 105

ˇ ınská vˇeta o zbytc´ıch C´

Ted’ ze vztahu x = 4319 + 2.3.4.5.6.7p vyjádˇr´ıme lcm(2, 3, 4, 5, 6, 7), kde a.b vztah pro lcm(a.b) = gcd(a.b) , pokud bychom si to rozepsali, pˇrijdeme na výsledek 420. No a ted’ tento výsledek pouˇzijem jako naˇse modulo: x = 4319 (mod 420) z toho plyne, ˇze naˇsich voják˚ u bylo x = 119 (mod 420). Pˇr´ıklad je ilustraˇcn´ı, pˇredstavte si zástup voják˚ u, kdyˇz se ˇradili po dvou.



17. ledna 2015

56 / 105

RSA Nejsd´ılenˇejˇs´ı software planety Iniciály autor˚ u Rivest, Shamir, Adleman 1

Zvol´ı se dvˇe r˚ uzná velká prvoˇc´ısla p a q

2

Spoˇc´ıtá se jejich souˇcin n = p · q

3

Spoˇcitá se Eulerova funkce Φ(n) = (p − 1) · (q − 1)

4

Zvol´ıme celé ˇc´ıslo 1 < e < Φ(n) , které je s Φ(n) nesoudˇelné

5

Nalezneme ˇc´ıslo d tak, aby platilo d · e = 1 mod Φ(n) Dvojice VK = (n, e) budeme ˇr´ıkat veˇrejné kl´ıˇce, dvojice SK = (n, d) budeme ˇr´ıkat soukromé kl´ıˇce.



17. ledna 2015

57 / 105

RSA



17. ledna 2015

58 / 105

RSA

ˇ Sifrov´ an´ı provád´ıme takto: c = EVK (m) = |me |n , kde m je zpráva a e s n jsou naˇse veˇrejné kl´ıˇce. Takto ˇsifruje pouze ten, který má veˇrejné kl´ıˇce, tedy nˇekdo venku. Deˇsifrován´ı provád´ıme takto: m = DSK (c) = |c d |n , kde c je ˇsifrový text a d s n jsou naˇse privátn´ı kl´ıˇce. Takto deˇsifruje pouze ten, který má soukromé kl´ıˇce, tedy my. Exponenciáln´ı rovnice jsou ale velice sloˇzité, nedalo by se udˇelat rychleji? Zkusme na to pouˇz´ıt mocnou ˇc´ınskou s´ılu!



17. ledna 2015

59 / 105

RSA-CRT

Urychlen´ı aˇz 4x oproti p˚ uvodn´ımu deˇsifrován´ı 1

Zvol´ı se dvˇe r˚ uzná velká prvoˇc´ıla p a q

2

Spoˇc´ıtá se jejich souˇcin n = p · q a Φ(n) = (p − 1) · (q − 1)

3

Zvol´ıme celé ˇc´ıslo 1 < e < Φ(n) , které je s Φ(n) nesoudˇelné

4

Dopoˇcteme d · e = 1 mod Φ(n)

A od této chv´ıle pˇridáme dalˇs´ı krok: 6

Vypoˇcteme dp = |d|p−1 , dq = |d|q−1 , qinv = |q −1 |p



17. ledna 2015

60 / 105

RSA-CRT ˇ Sifrov´ an´ı provád´ıme takto: c = EVK (m) = |me |n , kde m je zpráva a e s n jsou naˇse veˇrejné kl´ıˇce. Takto ˇsifruje pouze ten, který má veˇrejné kl´ıˇce, tedy nˇekdo venku. ˇ Sifrov´ an´ı nelze zrychlit! Deˇsifrován´ı u toho, kdo má privátn´ı kl´ıˇce, prob´ıhá podle tˇechto vzorc˚ u: Vypoˇcteme: m1 = |c dp |p m2 = |c dq |q h = |(m1 − m2 ) · qinv |p m = m2 + hq ˇ ınské vˇety o zbytc´ıch. Vˇeˇrte tomu nebo ne, toto vycház´ı z C´



17. ledna 2015

61 / 105

RSA-CRT pˇr´ıklad Pˇr.: Mˇejme: p = 7, q = 11, n = 77, Φ(n) = 6 · 10 = 60 e = 13 veˇrejný kl´ıˇc je tedy VK = (77, 13) d = |e −1 |Φ(n) = |13−1 |60 = 37 Dopoˇcteme: dp = |d|p−1 = |37|6 = 1 dq = |d|q−1 = |37|10 = 7 qi nv = |q −1 |p = |11−1 |7 = 2 Náˇs soukromý kl´ıˇc je tedy SK = (p, q, dp , dq , qinv ) = (7, 11, 1, 7, 2) Nˇekdo z venku nám zaˇsifruje zprávu: m = 15 do této podoby: c = EVK (15) = |1513 )|77 = 64. My j´ı pˇrijmeme a vypoˇctem: m1 = |641 |7 = 1 m2 = |647 |11 = 4 h = |(1 − 4) · 2|7 = 1 m = 4 + 1 · 11 = 15 Pokud bychom pouˇzili normáln´ı deˇsifrován´ı, problém by byl daleko vˇetˇs´ı: m = DSK (64) = |6437 |77 = 15 - u tohoto výpoˇctu nám nepom˚ uˇze ani Malá fermatova vˇeta ani Eulerova funkce ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

62 / 105

Feistel˚ uv kryptosystém



17. ledna 2015

63 / 105

Feistel˚ uv kryptosystém a DES

Základ blokových ˇsifer DES z tohoto systému vycház´ı - 3DES jej provede tˇrikrát U DES jsou 4 iterace pro ˇsifrován´ı + poˇcáteˇcn´ı permutace a koneˇcná inverzn´ı permutace Triple DES provád´ı pro ˇsifrován´ı (d˚ uvodem je rozˇs´ıˇren´ı kl´ıˇce) I

ˇsifrován´ı ⇒ deˇsifrován´ı ⇒ ˇsifrován´ı

Triple DES provád´ı pro deˇsifrován´ı I

deˇsifrován´ı ⇒ ˇsifrován´ı ⇒ deˇsifrován´ı

D˚ uvodem je rozˇs´ıˇren´ı kl´ıˇce z 56 na 168 bit˚ u



17. ledna 2015

64 / 105

AES Podporuje nˇekolik délek kl´ıˇce, podle toho mˇen´ı poˇcet rund 128, 192 a 256 bit˚ u (s poˇcty rund 10, 12 a 14) Nemá slabé kl´ıˇce, je odolný diferencovatelným a lineárn´ım metodám kryptoanalýzy Je vhodný i pro paraleln´ı zpracován´ı 1

SubBytes – substituce bajt˚ u matice dle pevnˇe dané tabulky.

2

ShiftRows – ˇrádky matice se posunou postupnˇe o 0-3 bajty doleva (1. ˇrádek o 0, 2. o 1 atd.).

3

MixColumns – lineárn´ı substituce 32 bit˚ u za 32 bit˚ u.

4

AddRoundKey – na sloupce matice se zleva doprava naxoruj´ı 4 odpov´ıdaj´ıc´ı rundovn´ı kl´ıˇce.



17. ledna 2015

65 / 105

AES diagram



17. ledna 2015

66 / 105

Operaˇcn´ı módy blokových ˇsifer

Operaˇcn´ı módy jsou zp˚ usoby nasazen´ı blokových ˇsifer v daném kryptosystému OT nen´ı jen jeden blok ale symbol abecedy, coˇz jsou v podstatˇe jednotlivé byty OT Maj´ı r˚ uzné vyuˇzit´ı a vhodné zp˚ usoby, kdy je dobré je pouˇz´ıt



17. ledna 2015

67 / 105

ECB Electronic Codebook



17. ledna 2015

68 / 105

ECB výhoda i nevýhoda Pojd’me vz´ıt AES a ECB a zakryptujme si tˇreba Homera



17. ledna 2015

69 / 105

ECB výhoda i nevýhoda



17. ledna 2015

70 / 105

CBC Cipher Block Chaining

No a ted’ po ne´ uspˇechu s ECB, zkusme Homera zakryptovat pomoc´ı CBC. ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

71 / 105

CBC Homer



17. ledna 2015

72 / 105

CFB Cipher Feedback - samosynchronn´ı, bloková ˇsifra na proudovou



17. ledna 2015

73 / 105

OFB Output Feedback - synchronn´ı prudová ˇsifra



17. ledna 2015

74 / 105

RC4

Proudová ˇsifra Jednoduchá, malá, rychlá Prolomená a snadno deˇsifrovatelná Uˇz´ıvá se tam, kde je potˇreba rychlost a malý výkon Stejnˇe tak tam, kde nevad´ı, ˇze budou data rozluˇstˇena I I I

Pˇrenos jednorázové informace Pˇrenos multimédi´ı Torrent (pouze datový stream)



17. ledna 2015

75 / 105

RC4

Nejdˇr´ıve se vytvoˇr´ı pole kl´ıˇce pomoc´ı algoritmu KSA (Key-scheduling algoritm) Potom se vezme pole kl´ıˇce a projde se pˇres Pseudonáhodný generátor Výsledek se zaˇs´ıfruje pˇres XOR (inverzn´ı operace ke XOR je zase XOR)



17. ledna 2015

76 / 105

RC4



17. ledna 2015

77 / 105

Hash Jednocestná funkce, která vrac´ı pro stejný vstup stále stejný hash Je velice rychlá, výstupn´ı hash má konstantn´ı velikost Kv˚ uli jednocestnosti se z n´ı nedá nic zpátky dostat Jeden z problém˚ u je, ˇze do malé mnoˇziny (B) se snaˇz´ıme rozbrazit ohromné mnoˇzstv´ı dat (A).

Co kdyˇz pro dva r˚ uzné vstupy najdeme jeden stejný hash? ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

78 / 105

Hash Velikost mnoˇziny B: MD5 má 128bit˚ u SHA-224, SHA-256, SHA-384 a SHA-512 - ˇc´ıslo verze oznaˇcuje poˇcet bit˚ u ... To je doopravdy málo. Pˇredstavte si to tak, jako kdyby jste se snaˇzili udˇelat seznam lid´ı a jejich id by bylo jejich hashem. Do funkce by se vkládal celý ˇclovˇek, takˇze by data byla dost náhodná. Na svˇetˇe je zhruba 7 277 686 259 lid´ı (ˇcerpáno z http://www.worldometers.info/), MD5 má 340282366920938463463374607431768211456 moˇznost´ı. Uf, to by se mohlo vej´ıt, ale co kdyˇz funkce pro dva lidi vytvoˇr´ı stejný hash? Co kdyˇz bychom chtˇeli udˇelat seznam vˇsech zrnek p´ısku?



17. ledna 2015

79 / 105

Narozeninový paradox Jaká je pravdˇepodobnost, ˇze ve fotbalovém druˇzstvu, které má 11 ˇclen˚ u, maj´ı dva lidi narozeniny ve stejný den? 10%? 0.1%? 50%? Na to se snaˇz´ı odpovˇedˇet narozeninový paradox Jde o to, ˇze se ptáme, zdali nˇekdo jiný má narozeniny ve stejný den jako nˇekdo konkrétn´ı a netuˇs´ıme, kdo jiný to vlastnˇe je 11 coˇz jsou asi 3%. To je ale velká chyba, Naivnˇe by ˇclovˇek ˇrekl, ˇze p = 365 protoˇze uvaˇzujeme vˇzdy jednoho urˇcitého ˇclovˇeka. Jak je to doopravdy? Vztah se poˇc´ıtá opaˇcnˇe, nejdˇr´ıve se ptáme, jaká je pravdˇepodobnost, ˇze je nˇekdo, kdo nemá narozeniny ve stejný den, co jeden konkrétn´ı ˇclovˇek (z Wiki): 365·364···(365−n+1) 1 2 p¯(n) = 1 · 1 − 365 · 1 − 365 · · · 1 − n−1 = 365 = 365n 365! 365n (365−n)!

p(n) = 1 − p¯(n) ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

80 / 105

Narozeninový paradox



17. ledna 2015

81 / 105

Narozeninový paradox

Dosad´ıme do vztahu: 365! = 0.85885862...(85%) ted’ vztah otoˇc´ıme 36511 (365−11)! 1 − 0.85885862... = 0.14114137...(14%) Pravdˇepodobnost je tedy nˇekde okolo 14%, coˇz je pomˇernˇe vysoko. Pokud uvaˇzujem tˇreba 50 lid´ı, pravdˇepodobnost uˇz je na 97%. Pokud budem takhle uvaˇzovat poˇcet lid´ı vˇetˇs´ı, neˇz 365, pravdˇepodobnost je uˇz 100%. Nezapom´ınejme na to, ˇze pravdˇepodobnost nen´ı exaktn´ı, nic nedokazuje. Pokud vám nˇekdo ˇrekne, ˇze 100% lid´ı by volilo Vaniˇz, skrvn a ˇsp´ıny se zbav´ıˇs, neznamená to, ˇze jej zvol´ıte i vy, ale je tu 100% pravdˇepodobnost, ˇze jej asi zvol´ıte. (Pˇr´ıklad byl ilustraˇcn´ı, no harm na lidi preferuj´ıc´ı Asurit).



17. ledna 2015

82 / 105

Kolize

Kolize ˇr´ıká, ˇze jsme schopni nalézt dvˇe zprávy, pro které plat´ı h(A1 ) = h(A2 ) Pokud tedy vezmeme dva vzory, je moˇzné pro nˇe nalézt jeden hash Modern´ı hashovac´ı algoritmy s t´ımto poˇc´ıtaj´ı a v zásadˇe nejsou proti kolizi odolné, ale jen je vysoce pravdˇepodobné, ˇze k n´ı nedojde Proto jsme poˇc´ıtali Narozeninový paradox, abychom si ukázali, jak je problematika oˇsemetná



17. ledna 2015

83 / 105

Kolize

Kolize prvn´ıho ˇrádu Nalezen´ı dvou r˚ uzných zpráv se stejnou hash´ı (a zde pˇricház´ı na ˇradu Narozeninový paradox). To znamená, ˇze tˇreba pro SHA-1 staˇc´ı zhruba 50% velikosti mnoˇziny hashu, tedy 280 z p˚ uvodn´ıch 2160 . Kolize druhého ˇrádu Nalezen´ı stejného hashe k pˇredem dané prvn´ı zprávˇe. V tomto pˇr´ıpadˇe je problém daleko vˇetˇs´ı a ˇcasto se mus´ı prohledat celý prostor hashe.



17. ledna 2015

84 / 105

HMAC

Keyed-hash Message Authentication Code Moˇznost autentifikace zprávy pomoc´ı HASH funkce ˇ Casto jediná moˇznost ovˇeˇrit si podpis dat Pˇresný popis naleznete na Wiki Pokud mu nerozum´ıte, m˚ uˇzeme se jej pokusit rozebrat My si vyzkouˇs´ıme zjednoduˇsený princip funkce



17. ledna 2015

85 / 105

MAC



17. ledna 2015

86 / 105

MAC



17. ledna 2015

87 / 105

HMAC Kdybychom pouˇzili nˇeco takového, vystavujeme se hned nˇekolika nebezpeˇc´ım Jak je to tedy na Wikipedii?



17. ledna 2015

88 / 105

Veˇrejné kl´ıˇce Jak pˇredat veˇrejný kl´ıˇc bez toho, aby jej nˇekdo zachytil? Samozˇrejmˇe m˚ uˇzeme pouˇz´ıt DH nebo El Gammala. To ale nˇekdy nejde. ´ cn´ık odchytne kl´ıˇc, zaˇsifruje vˇse svým kl´ıˇcem a dál poˇsle veˇrejný. Utoˇ Smˇerem zpátky poˇsle podstrˇcený kl´ıˇc. Techniky zvˇeˇrejnˇen´ı: 1

Zvˇeˇrejnit – vˇsem a vˇsemi kanály, to ale moc neˇreˇs´ı podvrˇzen´ı

2

Veˇrejný adresáˇr – správce v´ı, jaké kl´ıˇce se do adresáˇre pˇridávaj´ı, je pouˇzit bezpeˇcný kanál. Co kdyˇz ale nˇekdo ukradne SK kl´ıˇc správce?

3

Autorita pro VK – kaˇzdý kl´ıˇc je podepsán SK autoritou, kaˇzdý zná VK autority a kaˇzdý jej mus´ı z´ıskat bezpeˇcnou cestou.

4

Certifikace veˇrejných kl´ıˇc˚ u – distribuce VK bez tˇret´ıch stran

. . . v´ıte, kde máte vaˇse VK autority? ˇ Martin Ber´ anek (SSPS)


17. ledna 2015

89 / 105

A co tak v certifikátu najdem?

VK drˇzitele Datum vydán´ı a datum ukonˇcen´ı platnosti ID ...



17. ledna 2015

90 / 105

Strom

Kaˇzdý (dobrý) certifikát je podepsaný vyˇsˇs´ı autoritou Ta tvoˇr´ı strom Koˇreny se podep´ıˇs´ı kˇr´ıˇzovˇe Vˇse je pod PKI (public key infrastructure)



17. ledna 2015

91 / 105

Digitáln´ı podpis

RSA se dá pouˇz´ıt jinak SK bude slouˇzit k podpisu, VK pro ovˇeˇren´ı 1

Nezfalˇsovatelnost, autenticita – jeden podpis, nikdo jiný jej nemá

2

Ovˇeˇren´ı – pˇr´ıjemce m˚ uˇze ovˇeˇrit, zdali je autor autorem

3

Integrita – pokud zprávu zmˇen´ıme, podpis uˇz nesed´ı

4

Nepopiratelnost – podepisuj´ıc´ı nem˚ uˇze popˇr´ıt, ˇze zprávu nepodepsal



17. ledna 2015

92 / 105

DSA

Standard americké vlády pro digitáln´ı podpis (1991) - Digital Signature Algorithm Podpis 1

Vstupem jsou veˇrejné parametry (p, q, g ), privátn´ı kl´ıˇc x, zpráva m

2

Vygenerujeme tajné náhodné ˇc´ıslo k (0 < k < q)

3

r = (g k mod p) mod q

4

s = k −1 (h(m) + xr ) mod q, kde k · k −1 = 1( mod q)

5

r i s nesm´ı být rovno nule, jinak se výpoˇcet opakuje

6

Podpis je nakonec (r , s)



17. ledna 2015

93 / 105

DSA

Ovˇeˇren´ı podpisu 1

Vstupem jsou veˇrejné parametry (p, q, g ), veˇrejný kl´ıˇc y, ovˇeˇrovac´ı podpis (r , s)

2

Ovˇeˇr´ıme, ˇze (0 < r < q) a (0 < s < q)

3

w = s −1 mod q

4

u1 = wh(m) mod q a u2 = wr mod q

5

v = (q u1 y u2 mod p) mod q

6

Podpis je platný, pokud v = r



17. ledna 2015

94 / 105

Informaˇcn´ı bezpeˇcnost

Zamˇeˇruje se na IS. Aneb, jak to nikdo nemá ˇcas dˇelat . . . 1

D˚ uvˇernost, integritu a dostupnost informac´ı

2 3

Autentizaci uˇzivatel˚ u a zdroj˚ u ´ ctovatelnost operac´ı Uˇ

4

Ochranu proti neautorizované manipulaci, modifikaci nebo zniˇcen´ı D˚ uvˇernost – informace nepadne do rukou neautorizované osoby Integrita – informace je pˇrenesená bez u ´prav a poˇskozen´ı Dostupnost – informace patˇr´ı jen autorizovaným



17. ledna 2015

95 / 105

Assets

Hmotné – fyzické prostˇredky Nehmotné – SW, informace, data, . . . Zdroje – perzonál IS Poˇskozen´ı je u ´myslné i ne´ umyslné (IS je trouba a má bugy) ...



17. ledna 2015

96 / 105

Model OSI

Doporuˇcen´ı X.800 vázané na model OSI 1

Sluˇzby bezpeˇcnosti – zabezpeˇcen´ı pomoc´ı sluˇzeb, které chrán´ı IS

2

Mechanismy bezpeˇcnosti – postupy na detekci a prevenci u ´tok˚ ua odstranˇen´ı následk˚ u ´ Utoky na bezpeˇcnost – pˇr´ımé u ´toky na IS

3



17. ledna 2015

97 / 105

Sluˇzby bezpeˇcnosti



17. ledna 2015

98 / 105

Sluˇzby bezpeˇcnosti

Bezpeˇcnost podle OSI vrstev 1

2

Autentizace – ovˇeˇruje, zdaji je zdroj informace zdrojem, neˇreˇs´ı modifikaci ani duplicitu ˇ ızen´ı pˇr´ıstupu – podle autentifikace je moˇzné ˇr´ıdit pˇr´ıstup uˇzivatele R´ do IS

3

Zabezpeˇcen´ı d˚ uvˇernosti dat – k dat˚ um se nesm´ı nikdo ciz´ı dostat

4

Zabezpeˇcen´ı integrity dat – poˇskozená data nejsou pouˇzitelná data, stejnˇe tak duplikovaná a uˇz v˚ ubec ne modifikovaná

5

Ochrana proti odm´ıtnut´ı p˚ uvodu zprávy – zabezpeˇcuje d˚ ukaz o p˚ uvodu vyslaných dat, zabraˇ nuje popˇren´ı odpovˇednosti za data



17. ledna 2015

99 / 105

Mechanismy bezpeˇcnosti Definice specifické ˇcinnosti pro ochranu IS ˇ 1 Sifrov´ an´ı – pˇrenos je ˇsifrovaný 3

Digitáln´ı podpisy – data jsou autentifikány a integrita je zabezpeˇcena ˇ ızen´ı pˇr´ıstupu – k pˇr´ıstupu jsou potˇreba pˇr´ıstupová práva R´

4

Integrita dat – kontrola integrity pˇrenosu dat

5

Výmˇena autentizaˇcn´ıch informac´ı – mezi uˇzivatelem a IS

6

Vyplˇ nován´ı mezer – pˇridávat data do mezer k znesnadnˇen´ı analýzy toku dat ˇ ızen´ı smˇerován´ı – smˇer pˇrenosu dat mus´ı být zabezpeˇcený R´

2

7 8

Osvˇedˇcen´ı tˇret´ım subjektem – pˇridejte tˇret´ı stranu, která pˇridá dalˇs´ı bezpeˇcnost, co si tˇreba nem˚ uˇzete dovolit



17. ledna 2015

100 / 105

´ Utoky na bezpeˇcnost

Pasivn´ı – zamˇeˇrené na z´ıskáván´ı dat a jejich následné vyuˇzit´ı: Odkrýván´ı obsahu zpráv – sledován´ı a monitorován´ı Analýza toku dat – zachycen´ı toku a následné analýza Aktivn´ı – na základˇe zásahu do IS: Pˇredst´ırán´ı identity – výmˇena autentizace je zachycena a zneuˇzita ´ Utok opakován´ım – zachycená data jsou pos´ılána zpátky a vyvolávaj´ı neˇzádouc´ı efekt Modifikace zprávy – ˇcást zprávy je zmˇenˇena nebo odeslána opoˇzdˇenˇe Odm´ıtnut´ı sluˇzby – aktivn´ı u ´toky zabraˇ nuj´ıc´ı uˇzivateli pˇristupovat k IS



17. ledna 2015

101 / 105

Jean-Luc vás vid´ı!



17. ledna 2015

102 / 105

Pouˇcen´ı

MD5 je slab´ e? No tak pouˇziji tˇreba md5(md5(”heslo”)+md5(”heslo”)). NEEEEE!!! RC4 je tak jednoduch´ e, ˇze si ho nap´ıˇsi s´ am. NEEEEE!!! SHA/DES/AES je nuda, nap´ıˇsu si nˇ eco sv´ eho. NEEEEE!!! Udˇ el´ am si datab´ azi hesel, s˚ ul nepotˇrebuji, stejnˇ e nevim, co to doopravdy dˇ el´ a. I A co kdyˇz budou dva uˇzivatel´ e m´ıt stjen´ e heslo? Bez soli budou m´ıt i stejn´ y hash. I Ukr´ ast DB a odhalit p´ ar hesel znamen´ a odhalit velk´ y kus DB. ”Tak to zak´ oduj pˇres DES a je to.”No to asi tˇ eˇzko, zak´ odovat m˚ uˇzu nˇ eco pomoc´ı BASE64, DESem vˇ eci zaˇsifruji. PC nadˇr´ızen´ yho um´ı jen DES, tak jsem to tam nastavil na WiFi a ˇsel jsem pryˇ c. NEEEEEEEEEEEEEE! Na ten disk stejnˇ e nikdo z netu nevid´ı, tak ty data ˇsifrovat nebudem. NE Ne Ne Ne nE NEEE nE NEEE! gmail.google.com certifik´ at nen´ı podeps´ at, nevad´ı, klikni, ˇze je ti to jedno a neˇreˇs to. NEEEEE! Nikdy nikdy nikdy! Poˇsli mi heslo mailem. Joomla to tak dˇ el´ a a je to v pohodˇ e. Nope! Nen´ı to v pohodˇ e. Bezpeˇ cn´ e heslo je $$@@tt@@5nskeHeslo666. Aha... NEEEEEEE!



17. ledna 2015

103 / 105

Jean-Luc facepalm



17. ledna 2015

104 / 105

Zbytek

Snaˇzil jsem se vybrat ukázkové pasáˇze Vˇse je dohledatelné na Wiki a Doodle Pokud nˇeˇcemu nerozum´ıte, zeptejte se a napiˇste Zdrojové soubory jsou pˇriloˇzeny k prezentaci Dˇekuji vˇsem, kteˇr´ı se doˇcetli do konce a neusnuli Pouˇzil jsem Wikipedii, materiály z edux.fit.cvut.cz, ...



17. ledna 2015

105 / 105

Drobný úvod do matematiky bezpečnosti

Recommend Documents