Kryptografie Doc. Ing. Cyril Klimeš, CSc.
1
Proč kryptografie již pro žáky základních a středních škol? • Současná informatika se bez kryptografie neobejde. • Základní znalosti jsou použitelné i v jiných oblastech. • Jsou to mnohdy hd zábavné b teorie i a jejich j ji h využití v praxi. • Správné využití umožní bezpečnější provoz počítačových systémů a jejich aplikací. aplikací 2
Kurz Zákl d kryptografie Základy k t fi pro učitele Seznámení s obsahem kurzu, zopakování matematických základů, potřebných pro objasnění algoritmů šifrování. Historické algoritmy, g y, jjednoduché ppříkladyy šifrování Moderní algoritmy šifrování Šifrování s veřejnými klíči – metoda RSA Kryptografie v bezpečnosti informačních systémů Využití kryptografie Ukázky kryptografických aplikací z běžného života a prezentace praktického využití ve výuce, výuce diskuse 3
Základní pojmy • Kryptologie = Kryptografie + Kryptoanalýza • Kryptografie - nauka o metodách šifrování yp ý - metodyy luštění šifer • Kryptoanalýza kryptologie
kryptografie zabývá se návrhem šifrovacích systémů
kryptoanalýza zabývá se odhalováním 4 slabin v šifrovacích systémech
Základní schema Klíč (způsob šifrování)
Odesilatel
zpráva Posel
Šifrovací algoritmus ( t d ) (metoda)
Komunikační kanál
Alskdôlalkjda Adkljhalkdjlkj Adlkjlakdj Kldjalkj Adôj Dadae dasf
deŠifrovací algoritmus
Alskdôlalkjda Adkljhalkdjlkj Adlkjlakdj Kldjalkj Adôj Dadae dasf
Odposlech
Příjemce zpráva 5
Cíle kryptografie • důvěrnost dů (confidentiality) ( id i li ) -
též bezpečnost - jedná se o udržení obsahu
zprávy v tajnosti.
• celistvost dat (data integrity) - též integrita - jedná se o zamezení neoprávněné modifikace dat. Tato modifikace může být smazání části dat, vložení nových ý h ddat, nebo b substituce b i čá částii stávajících á jí í h dat d jinými ji ý i daty. d Se S zamezením í neoprávněné modifikace souvisí i schopnost tuto modifikaci detekovat.
• autentizace (authentication) - též identifikace identifikace, neboli ztotožnění znamená prokazování totožnosti, tj. ověření, že ten, s kým komunikujeme, je skutečně ten, se kterým si myslíme, že komunikujeme. Autentizace může probíhat na základě znalosti (heslo), vlastnictví (klíče od bytu, kreditní karta) nebo charakteristických vlastností (biometrické informace - např. otisky prstů).
• autorizace (authorization) - je j potvrzení t í původu ů d ((původnosti) ů d ti) dat. d t Tedy T d prokázání, že data vytvořil (je jejich autorem) skutečně ten, o němž si myslíme, že je autorem.
• nepopiratelnost (non-repudiation) - souvisí s autorizací - jedná 6se o jistotu, že autor dat nemůže své autorství popřít (např. bankovní transakci).
Kerckhoffsův princip • Bezpečnost šifrovacího systému nesmí záviset na utajení algoritmu, ale pouze na j klíče. utajení
7
Příklad doručení balíčku • Odesílatel chce poslat balíček zabezpečený v kufru klíčem, ale nedůvěřuje nikomu a y klíč ((ani ppříjemci). j ) Dále nechce dát z ruky neexistuje druhý klíč a kufr je nerozbitný. • Existuje nějaké jednoduché řešení? • Pozn. Kufr lze zamknout větším počtem zámků ale ke každému je jen jeden klíč. zámků, klíč 8
Příjemce zamkne kufřík svým vlastním zámkem a vyjme klíč
Odesilatel umístí balíček do kufru, ten zamkne svým zámkem a vyjme klíč Klíč 1
Balíček vložen do kufru
Klíč 2 K příjemci
Balíček v kufru
Zpět k odesilateli
Příjemce pomocí svého klíče sejme z kufříku svůj zámek a vyndá balíček
Odesilatel pomocí svého klíče sejme z kufříku svůj zámek K příjemci
Balíček B líč k v kufru
Balíček yj vyjmut z kufru
9
Prolomení šifry • Způsob nalezení dešifrovacího klíče • Útok hrubou silou – Zkoumání všech dešifrovacích klíčů – Získat tak smysluplný text
10
Kryptoanalytické metody - typy útoků na šifru • útok se známou šifrou (Ciphertext Only Atack) e znám á plaintext p a e - nejobtížnější ejob ějš není kryptoanalytická metoda. K výsledku lze dospět na základě rozborů pravidelností v textu šifry • útok se známým původním textem (Known Plaintext Atack) - jsou známy text původní a jjeho šifra. Rozborem lze odvodit klíč a šifrovací algoritmus • útok s vybraným otevřeným textem (Chosen Plaintext Atack) - lze zvolit vstupní text a získat jeho šifru. Vhodným výběrem vstupního textu11 mohou být odhalena slabá místa šifrovače.
Kryptografické yp g systémy y y • symetrická kryprografie (SK) s tajným klíčem • asymetrická kryptografie (AK) s veřejným a soukromým klíčem • jjednocestné hash funkce (HF) ( ) - vstupní p data libovolné délkyy jsou transformována do výstupních bloků pevné délky (charakteristika/výtah/hash) – s klíčem – bez klíče • Kryptografické systémy zabezpečují autentičnost, integritu, důvěrnost, nepopiratelnost zodpovědnosti
12
Symetrická y kryptografie yp g ((SK)) s tajným j ý klíčem Princip p symetrické y kryptografie yp g
Distribuce klíče Tajný klíč X
Tajný klíč X
Šifra Původní text
Šifrování
Odesílatel dokumentu
Dešifrování
Původní Pů d í text
Příjemce dokumentu
13
Princip asymetrické kryptografie
soukromý klíč
A
Distribuce klíče
veřejný klíč
A
Šifra Původní text
Šifrování
Odesílatel dokumentu - A
veřejný ř j ý klíč
B
Dešifrován í
Původní text
Příjemce dokumentu - B
soukromý klíč
B 14
Rozdíly • Symetrická kryptografie: menší výpočetní náročnost - vyšší výpočetní rychlost, hl problematické bl i k šíření kl klíče, ddvě kopie k i tajemství (obě strany), pro komunikaci s n partnery je třeba mít n klíčů, klíčů pro komunikaci s neznámým partnerem je obtížné ověřit jeho identitu • Asymetrická kryptografie: značná výpočetní náročnost - až 1000 x nižší výpočetní rychlost než u předchozího, pouze jedna kopie tajemství (pod vlastní kontrolou), snadné šíření klíčů (možnost uložit VK na veřejně dostupném místě), při komunikaci s neznámým partnerem lze poměrně snadno ověřit ěřit jeho j h identitu. id tit
15
Princip digitálního podpisu
16
Matematické základy kryptografie yp g
Modulární aritmetika • Pro čísla x a n, je x mod n zbytek po dělení 12 x číslem n 11 1 • Příklady 10 2 • 7 mod 6 = 1 „hodinová 9 3 aritmetika“ • 33 mod 5 = 3 • 33 mod 6 = 3 8 4 • 51 mod 17 = 0 7 5 6 • 17 mod 6 = 5
Základní operace v modulární aritmetice • Sčítání 3 + 5 ≡22 mod 6 2 + 4 ≡0 mod 6 3 + 3 ≡0 0 mod d6 (7 + 12) mod 6 ≡19 mod 6 ≡1 mod 6 (7 + 12) mod 6 ≡(1 + 0) mod 6 ≡1 mod 6
• Odčítání je definováno jako sčítání pomocí aditivní inverze mod n a -b mod n = a+ (-b)mod n 8 –5 ≡8+(-5) 8 ( ) ≡33 mod d9 5 –8 ≡5+(-8) = -3 ≡6 mod 9
Základní operace v modulární aritmetice • Násobení – násobení může být nula i když žádný z činitelů není roven nule – odvozeno z opakovaného sčítání
• Příklad: 2 . 4 ≡ 2 (mod 6) 5 . 5 ≡ 1 (mod 6) 3 . 4 ≡ 0 (mod 6) (7 . 4) modd 6 ≡ 28 28mod d 6 ≡ 4 mod d6 (7 . 4) mod 6 ≡ (1 . 4) mod 6 ≡ 4 mod 6
Základní operace v modulární aritmetice • Dělení je definováno jako násobení pomocí u p a v inverzí ve mod od n multiplikativní • Příklad: 3 :5 mod 7 ≡ 3 · 5-1 mod 7 ≡ 3 · 3 mod 7 ≡ 9 mod 7 ≡ 2 modd 7
• Podíl dvou celých čísel v modulární aritmetice mod n je vždy celé číslo (v případě, že lze dělení provést)
Umocňování • lze realizovat pomocí opakovaného násobení se ( ) ((tzn. n5 = n·n·n·n·n)) složitostí O(n) • efektivnější metoda je algoritmus „square and multiply multiply“ • rekurzivní výpočet mocniny xn pro celé kladné číslo n – Mocnina (x,n) (x n) = x pro n=1 n 1 – Mocnina (x,n) = Mocnina (x2,n/2) pro n sudé – Mocnina M i (x,n) ( ) = x.Mocnina M i (x ( 2,(n-1)/2) ( 1)/2) pro n liché li hé
Malá Fermatova věta • Je-li p prvočíslo a gcd(a,p)=1, pak ap-1 ≡ 1 (mod p) • Je-li p prvočíslo pak ap ≡ a (mod p) • Je-li Je li p prvočíslo a gcd(a,p)=1, gcd(a p) 1 pak ap-2≡ a-1(mod p) gcd –(Greatest Common Divisor) –Největší společný dělitel 1) Určete multiplikativní inverzi 18 mod 31 1829 mod d 31 ≡ 19 mod d 31 18*19 mod 31 ≡ 1 mod 31 2) Spočtěte mocninu 4961mod 479: 4961 ≡ (4478)2 * 45 ≡ 256 mod d 479 , protože ž 4478 ≡ 1 (mod 479)
Výpočet ýp GCD • Výpočet GCD pomocí Euklidova algoritmu - Algoritmus spočívá v opakovaném dělení dělitele zbytkem dokud zbytek není nula. a = n*b+r. Největší společný dělitel je poslední nenulový zbytek v tomto algoritmu. V okamžiku, kdy r=0 výpočet končí. Př. Výpočet gcd(4864,3458) 4864=1 3458+1406 4864=1.3458+1406 3458=2.1406+646 1406=2.646+114 646=5.114+76 114=1.76+38 76=2 38+0 76=2.38+0 gcd(4864,3548)=38
Operace XOR ⊕ • • • • • • • •
Někdy označovaná jako sčítání mod 2 y = a XOR b y=a ⊕b a b y 0 0 0 0 1 1 1 0 1 1 1 0 Název pochází z anglického eXclusive OR, tedy výlučné nebo.
Příklad XOR • Půjdu do kina, nebo do divadla (znamená to, že s a nepůjdu, epůjdu, půjdu je jen naa jedno jed o z nich). c ). naa obě místa Rozdíl mezi klasickým OR a výlučným XOR vnímá tedy i česká (slovenská) gramatika gramatika, která rozlišuje nebo ve významu slučovacím (OR) • Jako jednoduchá šifra: C = M K. • Díky symetrii operace je pak M = C K. K M=1101101 K= 1001010 C= 0100111
Prvočísla • Prvočíslo je přirozené číslo, které je beze zbytku dělitelné právě dvěma různými čísly a to číslem jedna a sebou samým čísly, (tedy 1 není prvočíslo). Přirozená čísla různá ů á odd jedné, j d é která k á nejsou j prvočísla, čí l se nazývají složená čísla. • Každé složené číslo lze jednoznačně vyjádřit jako součin prvočísel. prvočísel Proces rozkladu čísla na jeho prvočíselné činitele ( (prvočinitele) či it l ) se nazývá ý á faktorizace. f kt i
Příklady • Začátek řady prvočísel: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 … • Číslo 13 má při dělení dvěma zbytek 1, 1 při dělení 3 zbytek 1, při dělení pěti zbytek 3 atd. d Beze zbytku b k jje dělitelné d li l pouze 1 a 13. Proto je 13 prvočíslo. • Číslo 24 je dělitelné čísly 1, 2, 3, 4, 6, 8, 12, 24 – proto není prvočíslem prvočíslem.
Historie kryptografie
Starověké šifrování Historicky nejstarší je steganografie ... skrytá komunikace Histiaeus napsal zprávu sluhovi na oholenou hlavu a poslal jej do Míletu, aby zprávou pomohl v koordinaci boje proti Peršanům Demaratus zjistil kdy Peršané vytáhnou proti Řekům, použil dřevěné psací destičky pokryté voskem
Sparťané v 5. století př. n. l. používali transpozici. Pisatel zprávy nejprve omotal proužek kůže kolem dřevěné tyče.
Starověké šifrování • Řecký spisovatel Polybius (přibližně 203–120 př. n. .) vytvořil vy vo šifru, š u, kde de abecedu napsal apsa do čtverce č ve ce l.) o pěti sloupcích a pěti řádcích. Každé písmeno pak bylo možné interpretovat jako kombinaci dvou čísel, čísel přičemž první představovalo číslo řádku, druhé číslo sloupce. l 1 2 3 4 5
1 A F L Q V
2 B G M R W
3 C H N S X
4 D IJ O T Y
5 E K P U Z
ř ký spisovatel řecký i l „42 42 15 13 25 54 43 35 24 43 34 51 11 44 15 31 31“
Transpoziční šifry • • • •
Jednoduchá transpozice Šifrovací kříže Tabulky Transpozice dle klíče
Jednoduchá transpozice • psaní pozpátku – mění pouze pořadí písmen, nikoli jejich vzhled
• zepředu/zezadu – vypisuje vždy jedno písmeno zepředu, jedno písmeno zezadu
• prolnutí p – Text se rozdělí na dvě poloviny. Do šifrového textu se nejprve na liché pozice napíší písmena první poloviny a poté na sudé pozice písmena druhé poloviny t t textu.
• podle plotu – Text se rozdělí na dvě skupiny – první bude obsahovat všechna lichá písmena a druhá všechna sudá písmena. Šifrový text se vytvoří spojením první a druhé skupiny p y za sebe.
Šifrovací kříže • Šifru je se buď pomocí jednoduchého (+) nebo d jitéh (#) kříže. dvojitého kříž Pí Písmena se rozdělí dělí do d skupin k i po čtyřech, nebo po osmi a ty se pak zapíší kolem křížů. Zpráva se poté přepíše po řádcích.
Tabulky • Text se různým způsobem zapíše do tabulky a poté se přepíše po řádcích
Transpozice dle klíče • Š Šifrovanou zprávu si napíšeme do sloupců tabulky a p klíčové slovo. Poté sloupce p nad tabulku si napíšeme seřadíme podle abecedního pořadí písmen v klíčovém slově a šifrový text se vypíše po řádcích
Substituční šifry y • Substituce, neboli záměna nahrazuje písmeno zprávy jiným písmenem nebo znakem, písmenem, znakem podle šifrové abecedy. abecedy – Monoalfabetická substituční šifra – celý text se šifruje jednou šifrovou abecedou, tedy každé písmeno se nahrazuje stále stejným znakem. – Homofonní substituční šifra – některá ppísmena ((zpravidla p tyy nejčenější) se dají šifrovat více než jedním znakem. – Polyalfabetická substituční šifra – každé písmeno se šifruje jinou šifrovou abecedou podle určitého klíče. – Bigramová (trigramová, polygramová...) substituční šifra – skupina písmen z textu (bigram – dva znaky) se nahradí jinou skupinou písmen šifrového textu o stejném počtu písmen. – Digrafická Di fi ká substituční b tit č í šifra šif – každé k ždé písmeno í se nahradí h dí dvojicí d ji í znaků.
Caesarova posunová šifra (nebo posunutá abeceda) • V prvním řádku je celá abeceda, v druhém řádku je abeceda posunutá (v našem případě podle klíče A=T). p )
Ahoj lidi - Hovq spkp
Posun s p pomocným ý slovem • V prvním řádku je normální abeceda. Do druhého napíšeme íš napřed ř d klíčové klíč é slovo, l které kt é nesmíí obsahovat žádné písmeno dvakrát (například SIFRA) a doplníme zbývající písmena abecedy. Čím Č delší jje klíčové slovo,, tím více budou ppísmena zpřeházená.
Pomocné slovo - Rqoqgpi anqvq
Převrácená abeceda • Šifrová abeceda je proti otevřené abecedě obrácená tak, že A=Z a Z=A, B=Y a Y=B atd.
Převrácená abeceda - Kiveizxvmz zyvxvwz
Numerická abeceda • Každé písmeno je nahrazeno číslem podle pořadí v abecedě
Numerická Nu e c abeceda beced - 14;21;13;5;18;9;3;11;1;1;2;5;3;5;4;1; ; ; 3;5; 8;9;3; ; ; ; ;5;3;5; ; ;
Tabulkové kříže • Velký polský kříž – Při šifrování se podle tabulky nakreslí rámeček, ve kterém se písmeno nachází a pozice se určí tečkou.
Tabulkové kříže • Malý polský kříž
Zlomky y při šifrování se zapíší souřadnice písmene jako zlomek číslo číslosloupce/číslořádku,
Jednoduché zlomky 5/2;5/1;4/1;4/3;5/3;4/1;5/4;3/1;3/2;5/1;5/5;2/3;5/3;3/3;1/3;4/5;
Šifra ADFGVX • mřížka 6x6 je náhodně vyplněna 26 písmeny a 10 čísly
Playfairova šifra • Playfairova šifra nahrazuje každou dvojici písmen v ootevřeném ev e é textu e u jinou j ou dvojicí dvoj c písmen. p s e . Odesílatel Odes a e i příjemce si nejprve musí určit klíčové slovo, například SIFRA SIFRA. Šifruje se podle tabulky 5x5, 5x5 první se zapíše klíčové slovo a potom se pokračuje podle dl abecedy, b d písmena í I a J se spojí jí v jediný j di ý prvekk
Posuvná šifra: zaměňuje každé písmeno otevřeného textu písmenem, í které kt é je j v abecedě b dě o k míst í t dále. dál Číslo k, k které může nabývat hodnot 0 0,1,2,….,25, 12 25 je klíč. klíč Substituční tabulka pro klíč k = 7: abcdefghijklmnopqrstuvwxyz hijklmnopqrstuvwxyzabcdefg
Nevýhoda: příliš málo (malý prostor) klíčů, lze je všechny vyzkoušet. y cvidw vgvio zkjmo vn dwjex whwjp alknp wo exkfy xixkq bmloq xp fylgz yjylr cnmpr yq gzmha h zkzms k donqs d zr hanib alant eport as
Řešení Ř š í hrubou h b silou il (exhaustive search)
Jednoduchá substituce Nahrazuje každé písmeno otevřeného textu nějakým jiným písmenem abecedy p y Klíčem je substituční tabulka, ve které je pod každým písmenem abecedy ve spodním řádku písmeno písmeno, které jej v šifrovém textu nahrazuje: abcdefghijklmnopqrstuvwxyz elqdxbpkyrwvamoiuszcfhntjg
Spodní řádek tabulky je vlastně nějakou permutací písmen abecedy Prostor klíčů je dostatečně velký – 26! – nelze řešit hrubou silou. Slabina: zachovává statistické vlastnosti otevřeného textu.
Vigenérova šifra Používá periodicky několik různých posunutí abecedy. Klíčem je nějaké slovo, které udávalo délku posunutí podle následující á l d jí í tabulky. b lk
Princip p • Nejvrchnější řádek čtverce reprezentuje otevřený text Každé písmeno lze zašifrovat kteroukoliv z 26 text. šifrových abeced. • Pokud například použijeme abecedu 6, pak písmeno j jako j G,, ppři abecedě 16 bude písmeno p a a šifrujeme jako M atd. • Abychom Ab h využili žili sílu íl Vigenerovy Vi šifry, šif tak t k každé k ždé písmeno zašifrujeme pomocí jiného řádku.
Příklad Zašifrujte text Zlato je ulozeno v jeskyni klíčové slovo - poklad.
P O K L A D P O K L A D P O K L A D P O K L z l
a t
o j
e u l
O Z K E O M T I
o z e n o v j
e s k y n i
V Z Z H C C F U E V Z M X T
Polyalfabetická y šifra Podobná Vigenérově g šifře,, místo různých ý p posunutí ale p používá různé obecné jednoduché substituce. Každé písmeno otevřeného textu šifruje pomocí jiné permutace. permutace Ideální je, pokud se žádná permutace nepoužívá dvakrát. abcdefghijklmnopqrstuvwxyz 1:gkqwhrjvoisnazcubdxplfytme 2:cintzuhsymjabvoelxwpkfqgrd 3:ekrwxpavqbslcfitudgjmhnyzo 4:dqcuimhvrelnwgofjkztysabpx Šifrujeme:
koza s ood
Transpoziční p šifry y Spočívají v přeházení pořadí (permutaci) písmen v otevřeném textu. textu Permutace bývala definována pomocí nějakého slova – klíče. Například pomocí klíče nezny se šifrovalo následovně: 21534 nezny tanco valab ychja azset rasu
aacza tvyar cajeu obatn lhss
Jednoduchá transpozice
Šifrovací algoritmus RSA • Vygenerujeme dvě dostatečně velká prvočísla p a q (každé má délku 1024 bitů) a spočteme n=pq. • Čí Číslo l n je j parametrem t šifrovacího šif íh systému té (šifrovací (šif í modul) d l) a zveřejňuje se spolu s veřejným klíčem. • Spočítá S čítá se Eulerova E l funkce f k
Φ(n)= (p-1)(q-1) udává počet přirozených čísel menších než n, která jsou nesoudělná s číslem n (protože n je součinem dvou prvočísel, je takových čísel právě (p-1)(q-1))
Šifrovací algoritmus RSA • Zvolíme privátní klíč e z množiny {1,..,n} {1 n} nesoudělný s číslem (p(p 1)(q-1) • K privátnímu i át í klíči e vypočteme čt Eulerovým E l ý algoritmem l it veřejný ř j ý klíč d podle vztahu d⋅e modd (p-1)(q-1)= ( 1)( 1) d⋅e modd Φ(n)= ( ) 1 • Tato rovnice má jediné řešení d • Zakódování zprávy z se provede dle vztahu ze mod n =s • Dekódování zprávy se provede dle vztahu sd mod n =zz • Korektnost šifry je dána vztahem: z=sd mod n = zde mod n = zkΦ(n)+1 mod n =1⋅z mod n=z
Příklad • • • • • •
p=7, q=13 N=91, Φ(N)=6.12=72 t=7 s.7 mod 72 = 1, s=31 Veřejný klíč s=31, N=91, y=x31mod 91 T j ý klíč t=7, Tajný t 7 p=7, 7 q=13, 13 Φ(N)=72, Φ(N) 72 x=y7 mod 91
Příklad • x=24 • y= x31mod 91= 2431mod 91 = ((2416mod 91). ) ((248mod 91). ) ((244mod 91). ) (242mod 91). (241mod 91) = 24.30.81.9.81mod 91= 42515280 mod 91 = 80 • x = 807 mod 91 91= (801 mod 91) 91). (802 mod 91). (804 mod 91) = 80.30.81 mod 91 = 24
Použití kryptografických yp g ý metod • E-commerce ((E-business)) - bezpečnost p obchodních transakcí – E-tailingg na webových ý stránkách ((nákup p zboží))
• Bankovnictví – otevřený ř ý standard d d pro obchodování b h d á í – byl vyvinut společnostmi Visa a MasterCard – pro bezpečné platby kartami přes Internet
• Bezpečnostní mechanismy informačních systémů • ……
58
59
Děkuji za pozornost
[email protected]
60
