Úvod do kryptologie. Ing. Jan Přichystal, Ph.D. 12. listopadu PEF MZLU v Brně

Úvod do kryptologie Ing. Jan Přichystal, Ph.D. PEF MZLU v Brně

12. listopadu 2008

Ing. Jan Přichystal, Ph.D.

Úvod do kryptologie

Úvod Od nepaměti lidé řeší problém:

Jak předat zprávu tak, aby nikdo nežádoucí nezjistil její obsah? Dvě možnosti: ukrytí existence zprávy ukrytí smyslu zprávy S tím také souvisí otázka:

Jak zajistit, aby zpráva nebyla cestou změněna? Odhalení nebo neodhalení zprávy často rozhodovalo o životě a smrti. Ing. Jan Přichystal, Ph.D.


Kryptologie Věda, která se zabývá studiem šifer se nazývá kryptologie. Kryptologie zkoumá jak zprávy ukrývat tak, aby je nebylo možné nalézt nebo přečíst. Kryptografie – šifrování, způsob znemožnění přečtení zprávy, neutajujeme existenci zprávy, ale její smysl. kryptos = skrytý, graphein = psát Steganografie – ukrývání samotné existence zprávy steganos = schovaný, graphein = psát Ing. Jan Přichystal, Ph.D.


Steganografie Bitva u Salamíny (480 př.n.l.) – Řek Damaratus ukryl zprávu pod voskem na prázdných psacích destičkách. Hérodotos – Oholit posla, napsat zprávu a počkat, až mu vlasy opět narostou. Staří Číňané – zpráva na kusu hedvábí, zmačkané, zalité voskem – posel kuličku polknul. Giovanni Porta (16. stol.) – speciální inkoust, napíše zprávu na vejce, uvaří jej na tvrdo, zpráva pronikne skořápkou na bílek. Mikrotečky Ing. Jan Přichystal, Ph.D.


Transpozice

Uspořádání písmen zprávy jiným způsobem. Byl pozdni vecer prvni Maj, vecerni Maj byl lasky cas. Řešení B L O D I E E P V I A V C R I A B L A K C S Y P Z N V C R R N M J E E N M J Y L S Y A BLODIEEPVIAVCRIABLAKCSYPZNVCRRNMJEENMJYLSYA Historicky první vojenské šifrování – Skytale (Sparta). Pruh kůže navinutý na tyč dané tloušťky.



Substituce

Princip spočívá v nahrazení každého znaku otevřené abecedy jedním znakem šifrové abecedy. Možných variant je 4 × 1026 . A B C D E F G H I J K L M N O P Q R S T U V W X Y Z C G F T K M Q I J A U Y O H P R W S L N V X D B Z E

Příklad: mundus vult decipi OVHTVL XVYN TKFJRJ



Obecný šifrovací postup

1

2

3

4

Odesilatel aplikuje na otevřený text šifrovací algoritmus s využitím klíče. Získá šifrový text, pošle jej příjemci. Příjemce aplikuje na šifrový text dešifrovací algoritmus s využitím klíče. Získá zpět otevřený text.



Kerckhoffův princip

Základní princip kryptografie Nizozemský lingvista Auguste Kerckhoffs von Nieuwenhoff (1883)

Bezpečnost šifrovacího systému nesmí záviset na utajení algoritmu, ale pouze na utajení klíče.



Caesarova šifra Přibližně 2000 let starý a pravděpodobně nejznámější šifrovací systém. Autorství je připisováno Juliu Caesarovi, který ji používal jako jednu z mnoha šifer. Princip spočívá v posunutí šifrovaného písmene o tři místa dále v abecedě. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z D E F G H I J K L M N O P Q R S T U V W X Y Z A B C Příklad: veni vidi vici YHQL YLGL YLFL



Vylepšení substitučních šifer použití speciálních symbolů pro nahrazení některých slov – nomenklátory znaky s klamajícím významem – nulový znak, smaž předchozí znak . . . zkomolení zprávy na základě zvukomalebnosti – „frikvence slofÿ



Vigen` erova šifra

Blaise de Vigen`ere, 1586. Polyalfabetická substituční šifra. Šifrování pomocí opakujícího se klíče délky > 1. Šifrování: Otevřený text: diverttroopstoeastridge Klíčové slovo: WHITEWHITEWHITEWHITEWHI Šifrový text: ZPDXVPAZHSLZBHIWZBKMZNM Složité na použití, náchylné k chybám. Nerozlomena po 300 let.



Homofonní šifra Používala se jako vhodný kompromis mezi rychlostí šifrování a dešifrování a poskytovaným bezpečím. Odstraňuje hlavní problém monoalfabetických šifer – frekvenční charakter. Každé písmeno se zde nahrazuje řadou reprezentací, přičemž jejich počet je úměrný frekvenci písmene. A 09 B 48 C 13 D 01 E 14 ... Y 21 Z 02

12 81 41 03 16

33 47 53 67 78 92 62 45 79 24 44 46 55 57 64 74 82 87 98

52

Příklad: a b e c e d a 09 48 14 13 19 01 12 Ing. Jan Přichystal, Ph.D.


Šifrovací stroj ENIGMA Autorem byl německý vynálezce Arthur Scherbius, Vývoj od r. 1918. Používala se v době před a během 2. sv. války německou armádou. Považována za zcela bezpečnou. Dešifrování zahájili Poláci, později své znalosti předali Spojencům, kteří ji dokázali částečně dešifrovat.



Metody kryptoanalýzy Při luštění šifer se používají nejrůznější techniky z různých oborů lidského vědění (lingvistika, statistika, matematika, informatika . . . ) Velmi důležitá je znalost jazyka otevřeného textu a jeho charakteristik. Základní představu o monoalfabetických šifrách získáme pomocí frekvenční analýzy, neaplikujeme ji však slepě. Pokoušíme se odhalit samohlásky (40 % textu) – obvykle ve slově alespoň jedna, rozvrstveny relativně pravidelně, zřídka vedle sebe. Hledáme častá slova, typické digramy, trigramy. Zkoušíme delfskou metodu – hádat celá slova, odhadnout obsah zprávy. Velmi zajímavý popis kryptoanalýzy podává v povídce Zlatý skarabeus E. A. Poe. La Disparition (Georges Perec) – povídka o 20 stranách, ve které se nevyskytuje ani jedno písmeno e. Ing. Jan Přichystal, Ph.D.


Frekvence písmen Pro každý jazyk je specifická frekvence jednotlivých písmen. S touto znalostí jazyka lze rozpoznávat konkrétní znaky na základě jejich četnosti i po zašifrování.



Další charakteristiky

Nejčastější digramy Nejčastější Nejčastější Nejčastější Nejčastější

st, ne, se, na, ni, po, pr, ov, ro, je, te, le, ko, od, ra trigramy pro, ost, sta, pri, pre, ter, eni, ova, kte, pra slova a, v, se, na, je, ze, s, o, z, i, do, to, pro, ve, k zač. slov p, s, v, z, n, o kon. slov e, i, a, o, u, y



Další charakteristiky

e a o i u y

Začátek Konec slova slova × • ◦ ◦ × • ×

• • • • ◦

Samostatné slovo × • ◦ ◦ ◦ ×


Vazby na Vazby na souhlásky samohlásky el, em, en, ne, se, × ta, je, le ak, al, na, ra, ta, la au ov, po, to ou li, ni, ic, il × ku ou, au by, vy ×


Nepřímé útoky I. Pro kryptoanalýzu jsou důležité nejen exaktní metody, ale i intuice, štěstí a rafinovanost. Uhodnutí obsahu vojenská korespondence – typická oslovení, tituly, místa, pevná struktura zprávy . . . obchodní korespondence – odhadnutí předmětu dopisování (zboží, města, jména obchodních partnerů) osobní korespondence – forma oslovení, jméno odesílatele a příjemce



Nepřímé útoky II. Chyby šifrantů Slabým místem šifrovacích systémů je lidský faktor. Typickým příkladem je zaslání stejného obsahu zašifrovaného pomocí různých klíčů. Intriky „Omylemÿ vyzrazené komunikační klíče; Předstírání, že neumím číst cizí šifru, ale přitom ji už dávno čtu; Použití šifry v šifře; Uloupení klíčů;



Problémy dneška

Satelitní telefonní hovory – kdokoliv je může odposlouchávat Placená televize – ochrana proti neautorizovaným uživatelům Placení přes internet – zajištění autentičnosti příkazce operace Víceuživatelské OS . . .



Moderní šifrovací metody

V dnešní době se pro šifrování využívá symetrických a asymetrických algoritmů. Symetrické metody: DES, 3DES, AES . . . Asymetrické metody: RSA, ElGamal . . .



Moderní steganografie

Digitální steganografie – Ukrývání zprávy do zdánlivého šumu. Obrázky, zvuk, video . . . Nešifrovanou zprávu lze snadno odhalit. Zásadní nevýhoda steganografie – při odhalení zpráva padne útočníkovi ihned celá do rukou.



Kvantová kryptografie

Využívá poznatků kvantové teorie, přenášenou informaci kóduje jako stavy částic. Umožňuje nejen přenést tajnou informaci, ale i odhalit potencionální odposlech. V dnešní době stále ještě velmi mladá a prakticky nepoužitelná technologie. Oproti jiným šifrám je její bezpečnost fundamentální a není založena na složitosti dešifrování.



Doporučená literatura Garfinkel, S., Spafford, G.: Bezpečnost v Unixu a internetu v praxi. Computer press, 1998 Garfinkel, S.: PGP — Pretty Good Privacy. Computer press, 1998 Menezes, A. J., Oorschot, P. V., Scott A. Handbook of applied cryptography. Boca Raton: CRC Press, 1997 Schneier, B. Applied cryptography: protocols, algorithms, and source code in C. New York: John Wiley & Sons, 1996 Singh, S.: Kniha kódů a šifer. Praha: Dokořán, Argo, 2003. Orig. The Code Book, 1999.



Závěr

Děkuji za pozornost Dotazy?



Úvod do kryptologie. Ing. Jan Přichystal, Ph.D. 12. listopadu PEF MZLU v Brně

Recommend Documents