Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza 1. Caesar neboli Každý začátek je lehký! Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 13. září 2021 Q Úvod do problematiky • Opakování • Terminologie Nun-e-zuz-o-fuf-e-juj! Bub-u-dud-e-šuš o-sus-vuv-o- bub-o-zuz-e-nun! Pup-o-zuz-o-rur! Tut-o juj-e tut-e-nun vuv-rur-a-huh! Astrid Lingrenová Nun-e-zuz-o-fuf-e-juj! Bub-u-dud-e-šuš o-sus-vuv-o- bub-o-zuz-e-nun! Pup-o-zuz-o-rur! Tut-o juj-e tut-e-nun vuv-rur-a-huh! Astrid Lingrenová Fl Při každém zakódování musí být příjemce vždy o něco před útočníkem. S pomocí této informace může příjemce zprávu rozšifrovat; tato informace nesmí být žádnému útočníkovi k dispozici, neboť by útočník byl schopen rozluštit zprávu zrovna tak lehce jako příjemce. O této exkluzivní informaci mluvíme jako o klíči. Nun-e-zuz-o-fuf-e-juj! Bub-u-dud-e-šuš o-sus-vuv-o- bub-o-zuz-e-nun! Pup-o-zuz-o-rur! Tut-o juj-e tut-e-nun vuv-rur-a-huh! Astrid Lingrenová Fl Při každém zakódování musí být příjemce vždy o něco před útočníkem. S pomocí této informace může příjemce zprávu rozšifrovat; tato informace nesmí být žádnému útočníkovi k dispozici, neboť by útočník byl schopen rozluštit zprávu zrovna tak lehce jako příjemce. O této exkluzivní informaci mluvíme jako o klíči. Klasické šifrovací metody jsou založeny na tom základě, že odesilatel a příjemce mají společný šifrovací klíč, se kterým odesilatel zprávu zašifruje a příjemce ji rozšifruje; takováto metoda se nazývá symetrická. <*> <*> V dalším uvidíme, že existují také asymetrické šifrovací algoritmy: v těchto systémech potřebuje pouze příjemce tajný klíč. V dalším uvidíme, že existují také asymetrické šifrovací algoritmy: v těchto systémech potřebuje pouze příjemce tajný klíč. V této kapitole se budeme zabývat v jistém slova smyslu pouze těmi nejednoduššími šifrovacími algoritmy a to takovými, že v nich je jedno a totéž písmeno nahrazeno jedním a tímtéž symbolem. Například písmeno e obsažené v textu by se zašifrovalo pomocí písmena K. Nejdříve několik slov k terminologii. Pojmy kryptologie a kryptografie pochází z řeckých slov Kpv^roa (tajný) a \o^oa (slovo, smysl) a ^paLpeiv (psát).Obě slova označují umění a vědu, která se zabývá rozvojem metod k utajení zpráv. (Mnozí autoři rozlišují mezi kryptografií, tj. vědou o vývoji kryptosystémů a kryptoanalýzou, uměním tyto kryptosystémy prolomit a označují slovem kryptologie, spojení těchto věd.) Nejdříve několik slov k terminologii. Pojmy kryptologie a kryptografie pochází z řeckých slov Kpv^roa (tajný) a \o^oa (slovo, smysl) a ^paLpeiv (psát).Obě slova označují umění a vědu, která se zabývá rozvojem metod k utajení zpráv. (Mnozí autoři rozlišují mezi kryptografií, tj. vědou o vývoji kryptosystémů a kryptoanalýzou, uměním tyto kryptosystémy prolomit a označují slovem kryptologie, spojení těchto věd.) Text, řetězec znaků nebo písmen, který chceme zprostředkovat se nazývá zpráva; obvykle budeme zprávu reprezentovat pomocí malých písmen a, b5 c5____Zašifrovanou zprávu budeme nazývat kryptogram; tento pak budeme psát pomocí velkých písmen A, B, C,____Šifrovací postup nazýváme šifrování, odšifrovací postup dešifrování. Odesilatel tedy šifruje, zatímco příjemce musí dešifrovat, aby si mohl přečíst zprávu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Texty, které budeme šifrovat, se skládají z písmen; tato písmena jsou prvky nějaké abecedy. V prvních dvou kapitolách bude obvykle naše abeceda přirozená abeceda {a, b5 c5...}. Texty, které budeme šifrovat, se skládají z písmen; tato písmena jsou prvky nějaké abecedy. V prvních dvou kapitolách bude obvykle naše abeceda přirozená abeceda {a, b5 c5...}. Budeme také vybírat za abecedu např. množinu {1,..., 26}, množinu {0,1} nebo také množinu {(a-i,..., a64) : a, e {0,1}} všech binárních posloupností délky 64 v případě, že to bude pro naše úvahy vhodné. Texty, které budeme šifrovat, se skládají z písmen; tato písmena jsou prvky nějaké abecedy. V prvních dvou kapitolách bude obvykle naše abeceda přirozená abeceda {a, b5 c5...}. Budeme také vybírat za abecedu např. množinu {1,..., 26}, množinu {0,1} nebo také množinu {(a-i,..., a64) : a, e {0,1}} všech binárních posloupností délky 64 v případě, že to bude pro naše úvahy vhodné. V rozporu s nadpisem kapitoly začínají dějiny kryptografie před Caesarem. O Spartská skytala • Skytala • Skytala jinak Historie začíná asi před 2500 lety. Jak dobře víme z díla řeckého dějepisce Plutarcha, používala vláda ve Spartě následující lstivou metodu pro přenos tajné zprávy pro své generály. Historie začíná asi před 2500 lety. Jak dobře víme z díla řeckého dějepisce Plutarcha, používala vláda ve Spartě následující lstivou metodu pro přenos tajné zprávy pro své generály. Odesilatel a příjemce museli mít oba tzv. skytálu: byly to dva válce o přesně stejném průměru. Odesilatel navinul úzkou pergamenovou pásku spirálovitě okolo své skytaly a napsal pak podle délky svou zprávu na pásku. Historie začíná asi před 2500 lety. Jak dobře víme z díla řeckého dějepisce Plutarcha, používala vláda ve Spartě následující lstivou metodu pro přenos tajné zprávy pro své generály. Odesilatel a příjemce museli mít oba tzv. skytálu: byly to dva válce o přesně stejném průměru. Odesilatel navinul úzkou pergamenovou pásku spirálovitě okolo své skytaly a napsal pak podle délky svou zprávu na pásku. Po odmotání pásky mohla zprávu číst jen ta osoba, která měla skytálu stejného rozměru - doufejme, že to byl pouze příjemce. Historie začíná asi před 2500 lety. Jak dobře víme z díla řeckého dějepisce Plutarcha, používala vláda ve Spartě následující lstivou metodu pro přenos tajné zprávy pro své generály. Odesilatel a příjemce museli mít oba tzv. skytálu: byly to dva válce o přesně stejném průměru. Odesilatel navinul úzkou pergamenovou pásku spirálovitě okolo své skytaly a napsal pak podle délky svou zprávu na pásku. Po odmotání pásky mohla zprávu číst jen ta osoba, která měla skytálu stejného rozměru - doufejme, že to byl pouze příjemce. Uvažujme nyní příklad převedený do moderního jazyka. Úvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Jinak Představme si, že jsme zachytili list papíru, na kterém čteme následující řetězec písmen: UNDTLATEDZEEIOVEMEJKSSMYNZ.EOI IELAENLTCTENLOIEKRZOAMKKIUENN Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Skytala jinak I Jinak Představme si, že jsme zachytili list papíru, na kterém čteme následující řetězec písmen: UNDTLATEDZEEIOVEMEJKSSMYNZ.EOI IELAENLTCTENLOIEKRZOAMKKIUENN Skytala odesílatele má průměr, který můžeme vyjádřit pomocí počtu písmen. Můžeme tedy jednoduše vyzkoušet různé rozsahy u. Zvolíme-li u = 7, dostaneme následující nesmysl: u E V S 0 N L 0 E N D E M 1 L 0 A V D Z M Y 1 T 1 M N T E E N E C E K L E J Z L T K K A 1 K ■ A E R 1 T 0 S E E N Z 3 s *0 O* Zvolíme-li ale uspořádání textu pro u = 9, dostaneme u Z J E N 0 M N E K 0 L 1 K D E S 1 T E K T 1 S 1 C K 1 L 0 M E T R U A V Y L E Z E T E N A N 0 V E M Z E L A N D E ■ □ S1 Úvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Jinak Zvolíme-li ale uspořádání textu pro u = 9, dostaneme: u Z J E N 0 M N E K 0 L 1 K D E S 1 T E K T 1 S 1 C K 1 L 0 M E T R U A V Y L E Z E T E N A N 0 V E M Z E L A N D E Skytála je prototyp transpozičního algoritmu; pňtom písmena zůstávají, co jsou, nezůstanou však, kde jsou. Nejedná se o nic jiného, než o permutaci míst písmen. Transpoziční algoritmy jsou důležitým stavebním kamenem pro moderní algoritmy. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Skytala jinak III Jinak Transpozičníalgoritmy jsou důležitým stavebním kamenem pro moderní algoritmy. Jinou složkou jsou substituční algoritmy] u nich se zpráva stane nečitelnou tím, že každé písmeno se nahradí jiným, ale jeho pozice zůstane zachována. Transpozičníalgoritmy jsou důležitým stavebním kamenem pro moderní algoritmy. Jinou složkou jsou substituční algoritmy] u nich se zpráva stane nečitelnou tím, že každé písmeno se nahradí jiným, ale jeho pozice zůstane zachována. A nyní nastává doba pro vstup Caesara na scénu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalýza Pojmy Statistika • Kryptoanalýza • Statistická analýza O Posouvací šifry • Caesar • Pojmy ■ ■ ■ ■ ■ ■ ť ■ ■ ■ v ■ 1 Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Jeden z prvních, kdo používal kryptologické techniky, byl římský vojevůdce a státník Gaius Julius Caesar (100-44 př. n. I.). Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Jeden z prvních, kdo používal kryptologické techniky, byl římský vojevůdce a státník Gaius Julius Caesar (100-44 př. n. I.). U Suetona (Caes. LVI) můžeme číst Exstant et [epistolae] ad Ciceronem, item ad familiares de rebus, in quibus, si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset; quae si qui investigare et persequi velit, quar-tam elementorum litteram, id est D pro A et perinde reliquas commutet. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Jeden z prvních, kdo používal kryptologické techniky, byl římský vojevůdce a státník Gaius Julius Caesar (100-44 př. n. I.). U Suetona (Caes. LVI) můžeme číst Exstant et [epistolae] ad Ciceronem, item ad familiares de rébus, in quibus, si qua occultius perferenda erant, per notas scripsit, id est sic structo litterarum ordine, ut nullum verbum effici posset; quae si qui investigare et persequi velit, quar-tam elementorum litteram, id est D pro A et perinde reliquas commutet. Překlad zní přibližně následovně Existují také [Caesarovy dopisy] Cicerovi a známým o věcech, v kterých psal tajným písmem, pokud něco muselo být důvěrně sděleno. Tzn. změnil pořadí písmen tak, že nešlo zjistit jediné slovo. Pokud někdo chtěl toto rozluštit a poznat obsah, musel dosadit čtvrté písmeno abecedy, tedy D, za A, )odobně toto provést se zbývajícími písmeny, j ► < = ► < = ► s *0 O* Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Šifru použitou Caesarem obdržíme tím způsobem, že místo abecedy zprávy budeme psát abecedu kryptogramu, ale o 23 míst doprava, což znamená totéž, jako posunutí doleva o 3 místa: Zpráva: abcdefgh ijklmnopqrst uvwxyz Kryptogram: DEFGHIJKLMNOPQRSTUVWXYZABC Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Šifru použitou Caesarem obdržíme tím způsobem, že místo abecedy zprávy budeme psát abecedu kryptogramu, ale o 23 míst doprava, což znamená totéž, jako posunutí doleva o 3 místa: Zpráva: abcdefgh ijklmnopqrst uvwxyz Kryptogram: DEFGHIJKLMNOPQRSTUVWXYZABC Šifruje se tím způsobem, že nahradíme písmeno zprávy pod ním stojícím písmenem kryptogramu. Například ze slova "zprava" se stane zdánlivě nesmyslné slovo "CSUDYD". Dešifrování je zrovna tak jednoduché: Každé písmeno kryptogramu se nahradí nad ním stojícím písmenem zprávy. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Člověk se ovšem může ptát, proč Caesar zvolil právě posunutí o 3 místa. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Člověk se ovšem může ptát, proč Caesar zvolil právě posunutí o 3 místa. Odpověď je jednoduchá: nebyl na to vůbec žádný důvod! Samozřejmě můžeme posunout abecedu o libovolný počet míst. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Člověk se ovšem může ptát, proč Caesar zvolil právě posunutí o 3 místa. Odpověď je jednoduchá: nebyl na to vůbec žádný důvod! Samozřejmě můžeme posunout abecedu o libovolný počet míst. Protože se naše abeceda sestává z 26 písmen, existuje právě 26 takových šifrování; mluvíme o posouvacích neboli aditivních šifrách a mezi nimi je samozřejmě triviální šifrování a -> A, b -> B5... 5 z -> Z, které samozřejmě nikdo nebude používat k šifrování tajných zpráv. Vyjasněme si na této nejjednodušší třídě šifer pojmy "šifrovací algoritmus" a "klíč". Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Vyjasněme si na této nejjednodušší třídě šifer pojmy "šifrovací algoritmus" a "klíč". Šifrovací algoritmus je bezprostředně vidět na šifrování slova zprava. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Vyjasněme si na této nejjednodušší třídě šifer pojmy "šifrovací algoritmus" a "klíč". Šifrovací algoritmus je bezprostředně vidět na šifrování slova zprava. Naproti tomu klíč je např. počet míst, o která je nutno posunout abecedu. Klíč nám přesně popisuje, jak se algoritmus použije ve speciální situaci. Partneři, kteří spolu komunikují, se musí dohodnout o šifrovacím algoritmu a o způsobu přenosu klíče. □ t3 Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Partneři, kteří spolu komunikují, se musí dohodnout o šifrovacím algoritmu a o způsobu přenosu klíče. Šifrovací algoritmus a klíč mají dvě zcela rozličné funkce a musí být proto zcela jasně rozlišitelné. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Partneři, kteří spolu komunikují, se musí dohodnout o šifrovacím algoritmu a o způsobu přenosu klíče. Šifrovací algoritmus a klíč mají dvě zcela rozličné funkce a musí být proto zcela jasně rozlišitelné. Algoritmus jako takový je zpravidla velmi "velký". Přitom mnoho algoritmů se realizuje pomocí mechanického zařízení nebo spočívá na více či méně veřejně přístupném postupu. Partneři, kteří spolu komunikují, se musí dohodnout o šifrovacím algoritmu a o způsobu přenosu klíče. Šifrovací algoritmus a klíč mají dvě zcela rozličné funkce a musí být proto zcela jasně rozlišitelné. Algoritmus jako takový je zpravidla velmi "velký". Přitom mnoho algoritmů se realizuje pomocí mechanického zařízení nebo spočívá na více či méně veřejně přístupném postupu. Z toho plyne, že algoritmus nelze v podstatě udržet v tajnosti. To pak znamená, že celková bezpečnost kryptosystému leží na utajení klíče. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Tento požadavek se zdá být přehnaný, je ale nanejvýš realistický: pro někoho, kdo chce neoprávněně číst naši zprávu, je srovnatelně lehké získat algoritmus (např. odcizit či zkopírovat přístroj). A pak tento zlosyn ví vše o algoritmu; nezná ale (doufejme) současný klíč. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Tento požadavek se zdá být přehnaný, je ale nanejvýš realistický: pro někoho, kdo chce neoprávněně číst naši zprávu, je srovnatelně lehké získat algoritmus (např. odcizit či zkopírovat přístroj). A pak tento zlosyn ví vše o algoritmu; nezná ale (doufejme) současný klíč. Z toho nutně plyne, že klíč je nutno předat bezpečnou cestou. K čemu pak vůbec šifrování zprávy? V tom případě jsme mohli hned přenést celou zprávu touto bezpečnou cestou! - Tato námitka je plně oprávněná, lze ji však následujícími argumenty podstatně zmírnit. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika O Zpráva bývá zpravidla velmi dlouhá, klíč se obvykle volí co nejkratší. Dodatečná námaha pro spolehlivý přenos klíče je pak silně redukovatelná. Proto je pravděpodobnost, že klíč bude odposloucháván, relativně malá. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika O Zpráva bývá zpravidla velmi dlouhá, klíč se obvykle volí co nejkratší. Dodatečná námaha pro spolehlivý přenos klíče je pak silně redukovatelná. Proto je pravděpodobnost, že klíč bude odposloucháván, relativně malá. O Odesilatel a příjemce si mohou libovolně vybrat dobu předání klíče. Klíč lze například dohodnout dny před přenosem zprávy. Naproti tomu se zpráva musí odeslat v okamžiku, který není ovlivnitelný komunikujícími partnery (uvažme politické události, vývoj na burze, atd.) Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika O Zpráva bývá zpravidla velmi dlouhá, klíč se obvykle volí co nejkratší. Dodatečná námaha pro spolehlivý přenos klíče je pak silně redukovatelná. Proto je pravděpodobnost, že klíč bude odposloucháván, relativně malá. O Odesilatel a příjemce si mohou libovolně vybrat dobu předání klíče. Klíč lze například dohodnout dny před přenosem zprávy. Naproti tomu se zpráva musí odeslat v okamžiku, který není ovlivnitelný komunikujícími partnery (uvažme politické události, vývoj na burze, atd.) O S pomocí tzv. Public-Key systémů lze klíče bez nebezpečí vyměnit, abychom pak provedli zakódování s pomocí konvenčních postupů. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Upozorněme ještě na další nebezpečí. Je-li klíč vyměněn, musí být spolehlivě uložen; nesmí nastat případ, že jej bude možno z přístroje zjistit. Experti souhlasí s tím, že klíč je pouze tehdy bezpečně uložen, pokud přístroj nelze najít fyzikálními prostředky. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Upozorněme ještě na další nebezpečí. Je-li klíč vyměněn, musí být spolehlivě uložen; nesmí nastat případ, že jej bude možno z přístroje zjistit. Experti souhlasí s tím, že klíč je pouze tehdy bezpečně uložen, pokud přístroj nelze najít fyzikálními prostředky. Nyní ale nastala doba na změnu stran. Kryptologie se nezabývá pouze tím, že navrhuje bezpečnostní systémy pro přenos zpráv; jedna z jejich ústředních úloh je takové systémy "rozluštit" (nebo se o to alespoň pokusit!). Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Začněme tedy na okamžik hrát roli zlosyna - to lze vyjádřit trochu slušněji následovně: pracujeme jako kryptoanalytik a provádíme kryptoanalýzu kryptogramu (případně zkoumaného kryptosystému). Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Začněme tedy na okamžik hrát roli zlosyna - to lze vyjádřit trochu slušněji následovně: pracujeme jako kryptoanalytik a provádíme kryptoanalýzu kryptogramu (případně zkoumaného kryptosystému). Tvůrce kryptosystému musí vždy počítat s možností, že algoritmus je protivníkovi znám (alespoň po delší dobu). Kromě toho se doporučuje protivníka nepodceňovat a přisoudit mu co nejvyšší inteligenci; nazvěme je Mr. X. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Začněme tedy na okamžik hrát roli zlosyna - to lze vyjádřit trochu slušněji následovně: pracujeme jako kryptoanalytik a provádíme kryptoanalýzu kryptogramu (případně zkoumaného kryptosystému). Tvůrce kryptosystému musí vždy počítat s možností, že algoritmus je protivníkovi znám (alespoň po delší dobu). Kromě toho se doporučuje protivníka nepodceňovat a přisoudit mu co nejvyšší inteligenci; nazvěme je Mr. X. Představme si, že Mr. X zachytil následující kryptogram: BIBV HXZIDI CH VMVQ BIRVI Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Začněme tedy na okamžik hrát roli zlosyna - to lze vyjádřit trochu slušněji následovně: pracujeme jako kryptoanalytik a provádíme kryptoanalýzu kryptogramu (případně zkoumaného kryptosystému). Tvůrce kryptosystému musí vždy počítat s možností, že algoritmus je protivníkovi znám (alespoň po delší dobu). Kromě toho se doporučuje protivníka nepodceňovat a přisoudit mu co nejvyšší inteligenci; nazvěme je Mr. X. Představme si, že Mr. X zachytil následující kryptogram: BIBV HXZIDI CH VMVQ BIRVI Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Na základě jistých indicií došel k domněnce, že tento text byl zašifrován pomocí posouvací šifry (např. by mohl "najít" jeden z výše popsaných šifrovacích strojů). Takovýto text pak lze principiálně analyzovat dvěma způsoby. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Na základě jistých indicií došel k domněnce, že tento text byl zašifrován pomocí posouvací šifry (např. by mohl "najít" jeden z výše popsaných šifrovacích strojů). Takovýto text pak lze principiálně analyzovat dvěma způsoby. 1. "Systematické"prozkoušení všech možností Protože se jedná pouze o 26 posunutí, není naše námaha příliš velká. Mr. X ale může tuto námahu podstatně zredukovat, omezí-li se pouze na malou část zachyceného textu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Na základě jistých indicií došel k domněnce, že tento text byl zašifrován pomocí posouvací šifry (např. by mohl "najít" jeden z výše popsaných šifrovacích strojů). Takovýto text pak lze principiálně analyzovat dvěma způsoby. 1. "Systematické"prozkoušení všech možností Protože se jedná pouze o 26 posunutí, není naše námaha příliš velká. Mr. X ale může tuto námahu podstatně zredukovat, omezí-li se pouze na malou část zachyceného textu. Uvažme např. "slovo" VMVQ. Vyzkoušíme-li všechna "posunutí" této posloupnosti písmen, zjistíme snadno, že ze všech možných ekvivalentů pouze slovo neni dává smysl. Je tedy více než pravděpodobné, že kryptogram byl získán posunutím o 8 míst. Mr. X pak prověří svou domněnku tím, že dešifruje celkový text. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza laesar Kryptoanalýza 'ojmy Statistika Obdrží pak: tato zprava uz neni tajná. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Obdrží pak: tato zprava uz neni tajná. Tato metoda pro prolomení posunovací šifry je proto tak dobrá, protože většina kombinací písmen je v češtině zcela bez významu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Obdrží pak: tato zprava uz neni tajná. Tato metoda pro prolomení posunovací šifry je proto tak dobrá, protože většina kombinací písmen je v češtině zcela bez významu. Ačkoliv je toto pozorování důležitý základ pro mnoho kryptoanalytických metod, má výše uvedená metoda velkou nevýhodu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Obdrží pak: tato zprava uz neni tajná. Tato metoda pro prolomení posunovací šifry je proto tak dobrá, protože většina kombinací písmen je v češtině zcela bez významu. Ačkoliv je toto pozorování důležitý základ pro mnoho kryptoanalytických metod, má výše uvedená metoda velkou nevýhodu. Nelze ji totiž (nebo jen s neúměrně velkou námahou) automatizovat. Pokud by tato metoda měla být provedena počítačem samostatně, pak by bylo nutno uložit všechna (nebo v každém případě velmi mnoho) česká slova. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Obdrží pak: tato zprava uz neni tajná. Tato metoda pro prolomení posunovací šifry je proto tak dobrá, protože většina kombinací písmen je v češtině zcela bez významu. Ačkoliv je toto pozorování důležitý základ pro mnoho kryptoanalytických metod, má výše uvedená metoda velkou nevýhodu. Nelze ji totiž (nebo jen s neúměrně velkou námahou) automatizovat. Pokud by tato metoda měla být provedena počítačem samostatně, pak by bylo nutno uložit všechna (nebo v každém případě velmi mnoho) česká slova. I když je to v principu možné, používali bychom zbytečně silný Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika V češtine, nemčine a angličtine (stejné jako v každém přirozeném jazyku) se nevyskytují všechna písmena se stejnou četností; spíše má každé písmeno svou charakteristickou četnost. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika V češtine, nemčine a angličtine (stejné jako v každém přirozeném jazyku) se nevyskytují všechna písmena se stejnou četností; spíše má každé písmeno svou charakteristickou četnost. Tyto četnosti jsou uvedeny v následující tabulce: Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza íaesar Kryptoanalýza 'ojmy Statistika Písmeno Četnost v % němčina Četnost v % angličtina a 6.51 6.40 b 1.89 1.40 c 3.06 2.70 d 5.08 3.50 e 17.40 10.00 f 1.66 2.00 g 3.01 1.40 h 4.76 4.20 i 7.55 6.30 j 0.27 0.30 k 1.21 0.60 1 3.44 3.50 m 2.53 2.00 Písmeno Četnost v % Četnost v % němčina angličtina n 9.78 5.60 0 2.51 5.60 P 0.79 1.70 q 0.02 0.40 r 7.00 4.90 s 7.27 5.60 t 6.15 7.10 u 4.35 3.10 v 0.67 1.00 w 1.89 1.80 X 0.03 0.03 y 0.04 1.80 z 1.13 0.02 Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Můžeme pak písmena rozdělit v závislosti na četnosti jejich výskytu do čtyř skupin (např. v němčině). V první skupině budou nejpočetněji se vyskytující e a n, v druhé skupině budou písmena s ještě relativně velkou četností (cca.7%); ve třetí skupině jdou uvedena písmena s malou, ale dosti podstatnou četností zatímco v poslední skupině jsou uvedena zanedbatelná písmena. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Můžeme pak písmena rozdělit v závislosti na četnosti jejich výskytu do čtyř skupin (např. v němčině). V první skupině budou nejpočetněji se vyskytující e a n, v druhé skupině budou písmena s ještě relativně velkou četností (cca.7%); ve třetí skupině jdou uvedena písmena s malou, ale dosti podstatnou četností zatímco v poslední skupině jsou uvedena zanedbatelná písmena. Skupina Počet písmen skupiny v textu e, n 27.18% i, s, r, a, t 34.48% d, h, u, 1, c, g, m, o, b, w, f, k z 36.52% p, v, j, y, x, q 1.82% Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Co se stane, dešifrujeme-li nějakou (německou) zprávu? Pak samozřejmě zůstane četnost písmen zachována; avšak jednotlivé četnosti písmen nemusí být již přiřazeny svým odpovídajícím písmenům. Např. zašifrujeme-li ve zprávě písmeno e za X, pak bude písmeno X nejčetnějším písmenem kryptogramu, zašifrujeme-li y za S, nebude se S v kryptogramu téměř vyskytovat. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Co se stane, dešifrujeme-li nějakou (německou) zprávu? Pak samozřejmě zůstane četnost písmen zachována; avšak jednotlivé četnosti písmen nemusí být již přiřazeny svým odpovídajícím písmenům. Např. zašifrujeme-li ve zprávě písmeno e za X, pak bude písmeno X nejčetnějším písmenem kryptogramu, zašifrujeme-li y za S, nebude se S v kryptogramu téměř vyskytovat. Konkrétně Mr. X ve své analýze zprávy MRNBNA CNGC RBC WRLQC VNQA PNQNRV vytvoří seznam jednotlivých četností Písmeno: ABCDEFGHIJKLMNOPQRSTUVWXYZ Četnost: 2240001 00001 3601 340002 1 000. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Pozor: Protože celá metoda je založená na statistice, není nic 100% jisté! Mr. X se musí zabývat dalším potvrzením své domněnky. Je-li jeho domněnka správná, jedná se o posunutí o 9 písmen. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Pozor: Protože celá metoda je založená na statistice, není nic 100% jisté! Mr. X se musí zabývat dalším potvrzením své domněnky. Je-li jeho domněnka správná, jedná se o posunutí o 9 písmen. Pak by muselo R odpovídat písmenu i (to potvrzuje jeho hypotézu, že se R vyskytuje relativně často) a W by muselo odpovídat písmenu n - to je však v rozporu s tím, že W se vyskytlo pouze jednou. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Pozor: Protože celá metoda je založená na statistice, není nic 100% jisté! Mr. X se musí zabývat dalším potvrzením své domněnky. Je-li jeho domněnka správná, jedná se o posunutí o 9 písmen. Pak by muselo R odpovídat písmenu i (to potvrzuje jeho hypotézu, že se R vyskytuje relativně často) a W by muselo odpovídat písmenu n - to je však v rozporu s tím, že W se vyskytlo pouze jednou. Z druhé strany se vyskytují A, B, C relativně často (měly by odpovídat r, s, t, a ekvivalenty x, y5 z (totiž G, H, I se prakticky nevyskytují). Pozor: Protože celá metoda je založená na statistice, není nic 100% jisté! Mr. X se musí zabývat dalším potvrzením své domněnky. Je-li jeho domněnka správná, jedná se o posunutí o 9 písmen. Pak by muselo R odpovídat písmenu i (to potvrzuje jeho hypotézu, že se R vyskytuje relativně často) a W by muselo odpovídat písmenu n - to je však v rozporu s tím, že W se vyskytlo pouze jednou. Z druhé strany se vyskytují A, B, C relativně často (měly by odpovídat r, s, t, a ekvivalenty x, y5 z (totiž G, H, I se prakticky nevyskytují). Mr. X se tedy pokusí provést posunutí zpět o 9 písmen a obdrží dieser text ist nicht mehr geheim Výše uvedený text je smysluplný a tedy jeho domněnka je s konečným závěrem potvrzena. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Výše uvedený text je smysluplný a tedy jeho domněnka je s konečným závěrem potvrzena. Závěrem několik poznámek. Druhá metoda má bezespornou přednost, že ji počítač může sám lehce provést. Protože zde ale rozhodující roli hrají statistické úvahy, musí být zachována jistá obezřetnost. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Caesar Kryptoanalyza Pojmy Statistika Výše uvedený text je smysluplný a tedy jeho domněnka je s konečným závěrem potvrzena. Závěrem několik poznámek. Druhá metoda má bezespornou přednost, že ji počítač může sám lehce provést. Protože zde ale rozhodující roli hrají statistické úvahy, musí být zachována jistá obezřetnost. Obzvláště při krátkých textech může vést naivní hledání po nejčastěji se vyskytujícím písmenu do slepé uličky. Pokud ale uvážíme ještě četnosti několika jiných písmen, lze použít algoritmy, které jsou i při velmi krátkých textech velmi úspěšné. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Decedy Klíčová slova áměnné šifry Q Monoabecední šifrování • Abecedy • Záměnné šifry • Klíčová slova B l/ľ\;r»+Aonnl\'i-70 Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Šifrování se nazývá monoabecední, jestliže každý symbol otevřeného textu nahrazuje odpovídajícím symbolem zašifrovaného textu. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Šifrování se nazývá monoabecední, jestliže každý symbol otevřeného textu nahrazuje odpovídajícím symbolem zašifrovaného textu. Monoabecední šifrování si můžeme představit tím, že pod abecedu zprávy napíšeme abecedu kryptogramu. Např. následující metody šifrování jsou monoabecední. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Šifrování se nazývá monoabecední, jestliže každý symbol otevřeného textu nahrazuje odpovídajícím symbolem zašifrovaného textu. Monoabecední šifrování si můžeme představit tím, že pod abecedu zprávy napíšeme abecedu kryptogramu. Např. následující metody šifrování jsou monoabecední. Zpráva: a bcdef g h i j k I mnopq r st uvwxy z Kryptogram: QWERTZUIOPASDFGHJKLYXCVBNM. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Šifrování se nazývá monoabecední, jestliže každý symbol otevřeného textu nahrazuje odpovídajícím symbolem zašifrovaného textu. Monoabecední šifrování si můžeme představit tím, že pod abecedu zprávy napíšeme abecedu kryptogramu. Např. následující metody šifrování jsou monoabecední. Zpráva: a bcdef g h i j k I mnopq r st uvwxy z Kryptogram: QWERTZUIOPASDFGHJKLYXCVBNM. Ale Zpráva: a b cdef g h i j k I mnopq r st uvwxy z Kryptogram: Q^Ec^/3U±OP3Y79V245. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Šifrování se nazývá monoabecední, jestliže každý symbol otevřeného textu nahrazuje odpovídajícím symbolem zašifrovaného textu. Monoabecední šifrování si můžeme představit tím, že pod abecedu zprávy napíšeme abecedu kryptogramu. Např. následující metody šifrování jsou monoabecední. Zpráva: a bcdef g h i j k I mnopq r st uvwxy z Kryptogram: QWERTZUIOPASDFGHJKLYXCVBNM. Ale Zpráva: a b cdef g h i j k I mnopq r st uvwxy z Kryptogram: Q^Ec^/3U±OP3Y79V245. Jednoduché substituční šifry se lehce napadají, protože šifra netají frekvenci používání různých symbolů \^otevřeném textut Poslední príklad by nám měl připomenout, že zpráva a kryptogram nemusí být definovány nad stejnou abecedou. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Poslední příklad by nám měl připomenout, že zpráva a kryptogram nemusí být definovány nad stejnou abecedou. Je-li tomu ale tak, pak každému monoabecední šifrování odpovídá permutace písmen abecedy; obráceně lze každé permutaci přiřadit monoabecední šifrování. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Poslední příklad by nám měl připomenout, že zpráva a kryptogram nemusí být definovány nad stejnou abecedou. Je-li tomu ale tak, pak každému monoabecední šifrování odpovídá permutace písmen abecedy; obráceně lze každé permutaci přiřadit monoabecední šifrování. Z toho zejména plyne, že máme přesně 26! =26-25.....2-1 «4 - 1026 monoabecedních šifrování nad přirozenou abecedou {a, b5 c5 ■ ■ ■ 5 Z}. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Chceme-li použít k zakódování písmen počítač, pak identifikujeme obvykle a (resp. A) s 1, b (resp. B) s 2, atd.; x (resp. X) s 24, y (resp. Y) s 25 a z (resp. Z) s 0. Pomocí této reprezentace lze posouvací šifry popsat obzvlášť dobře: posunutí o s míst odpovídá přičtení čísla s modulo 26. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Chceme-li použít k zakódování písmen počítač, pak identifikujeme obvykle a (resp. A) s 1, b (resp. B) s 2, atd.; x (resp. X) s 24, y (resp. Y) s 25 a z (resp. Z) s 0. Pomocí této reprezentace lze posouvací šifry popsat obzvlášť dobře: posunutí o s míst odpovídá přičtení čísla s modulo 26. Konkrétně postupujeme následovně: • Nejdříve převedeme písmena zprávy do odpovídajících číslic; o pak připočteme k tomuto číslu číslo s; • z výsledku uvažujeme pouze zbytek, který obdržíme po dělení 26; tento zbytek přeložíme zpátky na odpovídající písmeno. Tímto způsobem získáme příslušný text kryptogramu. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Příklad 4.1 Nyní chceme zašifrovat písmeno a pomocí posunovací šifry, která posouvá o 3 místa. • a se reprezentuje pomocí číslice 1; o 1 +3 = 4; • 4 je reprezentace písmena D kryptogramu. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Příklad 4.1 Nyní chceme zašifrovat písmeno a pomocí posunovací šifry, která posouvá o 3 místa. • a se reprezentuje pomocí číslice 1; o 1 +3 = 4; • 4 je reprezentace písmena D kryptogramu. Při dešifrování písmene B postupujeme následovně: • B se reprezentuje pomocí číslice 2; o 2 - 3 = -1; • Zbytek -1 po dělení26 je 25 a to odpovídá písmenu y zprávy. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy Zamenne šifry Klíčová slova Příklad 4.1 Nyní chceme zašifrovat písmeno a pomocí posunovací šifry, která posouvá o 3 místa. • a se reprezentuje pomocí číslice 1; o 1+3 = 4; • 4 je reprezentace písmena D kryptogramu. Při dešifrování písmene B postupujeme následovně: • B se reprezentuje pomocí číslice 2; 9 2 - 3 = -1; • Zbytek -1 po dělení26 je 25 a to odpovídá písmenu y zprávy. S pomocí této metody lze tzv. čísla sčítat 5 c\(y Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Celá věc se stává podstatně zajímavější, pokud budeme písmena násobit. To lze provést následovně: Abychom mohli násobit písmena číslem ř, budeme počítat opět modulo 26. Tzn., že vynásobíme číslo odpovídající zadanému písmenu číslem t a uvažujeme zbytek po dělení 26. Pak je tomuto zbytku odpovídající písmeno výsledek tohoto "násobení". Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Celá věc se stává podstatně zajímavější, pokud budeme písmena násobit. To lze provést následovně: Abychom mohli násobit písmena číslem ř, budeme počítat opět modulo 26. Tzn., že vynásobíme číslo odpovídající zadanému písmenu číslem t a uvažujeme zbytek po dělení 26. Pak je tomuto zbytku odpovídající písmeno výsledek tohoto "násobení". Vynásobíme-li hodnotu každého písmena zprávy číslem 2, obdržíme Zpráva: abcdefgh i j k I mnopq rs t uvwxy z Kryptogram: BDFHJLNPRTVXZ BDFHJLNPRTVXZ. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Celá věc se stává podstatně zajímavější, pokud budeme písmena násobit. To lze provést následovně: Abychom mohli násobit písmena číslem ř, budeme počítat opět modulo 26. Tzn., že vynásobíme číslo odpovídající zadanému písmenu číslem t a uvažujeme zbytek po dělení 26. Pak je tomuto zbytku odpovídající písmeno výsledek tohoto "násobení". Vynásobíme-li hodnotu každého písmena zprávy číslem 2, obdržíme Zpráva: abcdefgh i j k I mnopq rs t uvwxy z Kryptogram: BDFHJLNPRTVXZ BDFHJLNPRTVXZ. Vidíme, že vždy dvě písmena (např. h a u ) nám dávají tentýž "součin" (v našem případě P ). Proto nemůžeme tuto substituci použít jako šifru. <*> <*> = Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Pro každé šifrování musí totiž platit doposud nevyslovené ale zcela samozřejmé pravidlo, že text zprávy musí být s pomocí klíče jednoznačně rekonstruovatelný z kryptogramu. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Pro každé šifrování musí totiž platit doposud nevyslovené ale zcela samozřejmé pravidlo, že text zprávy musí být s pomocí klíče jednoznačně rekonstruovatelný z kryptogramu. Mnozí považují toto pravidlo za příliš omezující; lze ho však zeslabit a zároveň odůvodnit: Každý kryptogram musí být s pomocí klíče dešifrovatelný nějakým počítačem. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Pro každé šifrování musí totiž platit doposud nevyslovené ale zcela samozřejmé pravidlo, že text zprávy musí být s pomocí klíče jednoznačně rekonstruovatelný z kryptogramu. Mnozí považují toto pravidlo za příliš omezující; lze ho však zeslabit a zároveň odůvodnit: Každý kryptogram musí být s pomocí klíče dešifrovatelný nějakým počítačem. Pokusme naše štěstí ještě jednou a vynásobme všechna písmena číslem 3; Zpráva: abcdef gh i j k Imnopq r s t uvwxy z Kryptogram: CFILORUXADGJMPSVYBEHKNQTWZ. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Pro každé šifrování musí totiž platit doposud nevyslovené ale zcela samozřejmé pravidlo, že text zprávy musí být s pomocí klíče jednoznačně rekonstruovatelný z kryptogramu. Mnozí považují toto pravidlo za příliš omezující; lze ho však zeslabit a zároveň odůvodnit: Každý kryptogram musí být s pomocí klíče dešifrovatelný nějakým počítačem. Pokusme naše štěstí ještě jednou a vynásobme všechna písmena číslem 3; Zpráva: abcdef gh i j k Imnopq r s t uvwxy z Kryptogram: CFILORUXADGJMPSVYBEHKNQTWZ. V tomto případě získáme skutečně monoabecední šifrování Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Lehkým prozkoušením vidíme, že obdržíme monoabecední šifrování právě tehdy, když násobíme jedním z čísel 1, 3, 5, 7, 9,11,15,17,19, 21, 23 nebo 25; takovéto šifrování nazýváme multiplikativní šifry. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Lehkým prozkoušením vidíme, že obdržíme monoabecední šifrování právě tehdy, když násobíme jedním z čísel 1, 3, 5, 7, 9,11,15,17,19, 21, 23 nebo 25; takovéto šifrování nazýváme multiplikativní šifry. Máme tedy (včetně triviální šifry) právě 12 multiplikativních šifrování; jejich počet je tedy ještě menší než počet posouvacích šifer. Proto můžeme od těchto šifer očekávat velmi nepatrnou kryptografickou bezpečnost. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Lehkým prozkoušením vidíme, že obdržíme monoabecední šifrování právě tehdy, když násobíme jedním z čísel 1, 3, 5, 7, 9,11,15,17,19, 21, 23 nebo 25; takovéto šifrování nazýváme multiplikativní šifry. Máme tedy (včetně triviální šifry) právě 12 multiplikativních šifrování; jejich počet je tedy ještě menší než počet posouvacích šifer. Proto můžeme od těchto šifer očekávat velmi nepatrnou kryptografickou bezpečnost. Můžeme ale navzájem kombinovat posouvací a multiplikativní šifry. Za tímto účelem přičteme nejprve k písmenu zprávy číslo s a výsledek vynásobíme dalším číslem t. Podle tohoto předpisu získáme opět šifru, tzv. záměnnou (afinní)šifru, kterou budeme označovat [s, ŕ]. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Klíč záměnné šifry [s, ř] sestává z dvojice čísel (s, ř) (přirozeně musí být pro každou záměnnou šifru číslo ř zvoleno tak, že násobení číslem ř je multiplikativní šifra; ř tedy musí být jedno z výše uvedených čísel 1, 3, 5, 7, 9,11,15,17,19, 21, 23 nebo 25). Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Klíč záměnné šifry [s, ř] sestává z dvojice čísel (s, ř) (přirozeně musí být pro každou záměnnou šifru číslo ř zvoleno tak, že násobení číslem ř je multiplikativní šifra; ř tedy musí být jedno z výše uvedených čísel 1, 3, 5, 7, 9,11,15,17,19, 21, 23 nebo 25). Počet všech záměnných šifer vypočteme jako počet všech posúvacích šifer vynásobený počtem všech multiplikativních šifer; tedy počet všech záměnných šifer je 26 • 12 = 312. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Klíč záměnné šifry [s, ř] sestává z dvojice čísel (s, ř) (přirozeně musí být pro každou záměnnou šifru číslo ř zvoleno tak, že násobení číslem ř je multiplikativní šifra; ř tedy musí být jedno z výše uvedených čísel 1, 3, 5, 7, 9,11,15,17,19, 21, 23 nebo 25). Počet všech záměnných šifer vypočteme jako počet všech posúvacích šifer vynásobený počtem všech multiplikativních šifer; tedy počet všech záměnných šifer je 26 • 12 = 312. Toto číslo je už tak velké, že při ruční kryptoanalýze nám systematické prověření všech možností dá pěkně zabrat. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Velké množství monoabecedních šifer získáme následujícím způsobem: klíč sestává ze dvou komponent - klíčového slova a klíčového písmene. Nejdříve vytvoříme z klíčového slova posloupnost písmen, ve které se každé písmeno vyskytne pouze jednou. To získáme následujícím způsobem, že každé písmeno se při svém druhém, třetím, ... výskytu vyškrtne. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Velké množství monoabecedních šifer získáme následujícím způsobem: klíč sestává ze dvou komponent - klíčového slova a klíčového písmene. Nejdříve vytvoříme z klíčového slova posloupnost písmen, ve které se každé písmeno vyskytne pouze jednou. To získáme následujícím způsobem, že každé písmeno se při svém druhém, třetím, ... výskytu vyškrtne. Máme-li zvoleno například klíčové slovo MATEMATIKA, získáme posloupnost MATEIK. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Napišme nyní tuto posloupnost pod abecedu zprávy, a to tím způsobem, že bude začínat právě pod klíčovým písmenem. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Napišme nyní tuto posloupnost pod abecedu zprávy, a to tím způsobem, že bude začínat právě pod klíčovým písmenem. Např., zvolili jsme jako klíčové písmeno obdržíme Zpráva: abcdefghi j k I mnopqrstuvwxyz Kryptogram: MAT E I K Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Napišme nyní tuto posloupnost pod abecedu zprávy, a to tím způsobem, že bude začínat právě pod klíčovým písmenem. Např., zvolili jsme jako klíčové písmeno obdržíme Zpráva: abcdefghi j k I mnopqrstuvwxyz Kryptogram: MAT E I K Na závěr napíšeme zbývající písmena kryptogramu v abecedním pořádku, přičemž začneme po posledním písmenu klíčového slova. Uvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Abecedy ^ Zamenne šifry Klíčová slova Napišme nyní tuto posloupnost pod abecedu zprávy, a to tím způsobem, že bude začínat právě pod klíčovým písmenem. Např., zvolili jsme jako klíčové písmeno obdržíme Zpráva: abcdefghi j k I mnopqrstuvwxyz Kryptogram: MAT E I K Na závěr napíšeme zbývající písmena kryptogramu v abecedním pořádku, přičemž začneme po posledním písmenu klíčového slova. V našem případě pak získáme Zpráva: abcde f gh i j k Imnopq rs t uvwxy z Kryptogram: QRSUVWXYZMATE IKBCDFGHJLNOP. Zřejmě lze každé monoabecední šifrování získat pomocí vhodného klíčového slova. s> ►<=►<= ► = Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza • Hillova šifra Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Hillova šifra lineárně transformuje d znaků otevřeného textu na d znaků šifrového textu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Hillova šifra lineárně transformuje d znaků otevřeného textu na d znaků šifrového textu. Bude-li d = 2, pak C = c0 M m0 K k0 k2 k} k3 Hillova šifra lineárně transformuje d znaků otevřeného textu na d znaků šifrového textu. Bude-li d = 2, pak «-(;)•"-(£)■■<-(£ s)- Šifrování zahrnuje násobení regulární matice K blokem otevřeného textu M, t.j C = KM. Hillova šifra lineárně transformuje d znaků otevřeného textu na d znaků šifrového textu. Bude-li d = 2, pak c-U>-(E>K-(íí £)• Šifrování zahrnuje násobení regulární matice K blokem otevřeného textu M, t.j C = KM. Dešifrování zahrnuje násobení matice K~1 blokem šifrového textu C, tj M = K"1 C. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Příklad 5.1 d = 2 a budeme pracovat nad abecedou s 27 znaky (26 písmen a mezera), tj. nadZ2j. Zvolme K pak K"1 = 4 12 11 10 Příklad 5.1 d = 2 a budeme pracovat nad abecedou s 27 znaky (26 písmen a mezera), tj. nad Z27. Zvolme V tomto případě je determinant K nesoudělný s 27, tedy inverzní matice K~1 opravdu existuje. J P y Q Kryptoanalýza • Kerckhoff osouvaci šifry 9 Útoky na šifru □ S1 "Filozofii" moderní kryptoanalýzy lze popsat Kerckhoffovým principem; tento princip byl poprvé formulován v knize La cryptographie militaire (1883) holandským jazykovědcem Jeanem Guillaumem Hubertem Victorem Francoisem Alexandrem Augustem Kerckhoffem von Nieuwenhofem (1835-1903). Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Kerckhoff 1 "Filozofii" moderní kryptoanalýzy lze popsat Kerckhoffovým principem; tento princip byl poprvé formulován v knize La cryptographie militaire (1883) holandským jazykovědcem Jeanem Guillaumem Hubertem Victorem Francoisem Alexandrem Augustem Kerckhoffem von Nieuwenhofem (1835-1903). Kerckhoffův princip. Spolehlivost kryptosystému nesmí záviset na utajení algoritmu. Spolehlivost je založena pouze na utajení klíče. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Kerckhoff 1 "Filozofii" moderní kryptoanalýzy lze popsat Kerckhoffovým principem; tento princip byl poprvé formulován v knize La cryptographie militaire (1883) holandským jazykovědcem Jeanem Guillaumem Hubertem Victorem Francoisem Alexandrem Augustem Kerckhoffem von Nieuwenhofem (1835-1903). Kerckhoffův princip. Spolehlivost kryptosystému nesmí záviset na utajení algoritmu. Spolehlivost je založena pouze na utajení klíče. To je zásadní varování pro tvůrce kryptosystému. Nesmíme být tak naivní a přepokládat, že Mr. X nemá možnost získat znalost algoritmu. Dějiny kryptografie jsou plné příkladů, kdy objevitel kryptosystému založil důvěru na něm tím, že jeho algoritmus nikdy nemohl být znám. Úvod Spartská skytala Posouvací šifry Monoabecední šifry Další šifry Kryptoanalýza Útoky na šifru Naopak: Cílem moderní kryptografie musí být vývoj systémů, které zůstanou bezpečné i v tom případě, že o algoritmu bylo dlouhou dobu veřejně diskutováno. "Příkladem" je AES-algoritmus. Útoky na šifru Kryptoanalytik rozlišuje následující prípady útoku na šifru: 1. Known ciphertext attack: Kryptoanalytik zná relativně velkou část kryptogramu. To je opravdu reálný předpoklad, protože je zpravidla celkem jednoduché zajistit si (libovolně dlouhé) části kryptogramu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Útoky na šifru 1 Kryptoanalytik rozlišuje následující případy útoku na šifru: 1. Known ciphertext attack: Kryptoanalytik zná relativně velkou část kryptogramu. To je opravdu reálný předpoklad, protože je zpravidla celkem jednoduché zajistit si (libovolně dlouhé) části kryptogramu. 2. Known plaintext attack: Kryptoanalytik zná relativně malou část související zprávy/kryptogramu. Tato hypotéza je reálnější, než se na první pohled zdá. Totož často "ví" Mr. X, o co se jedná, a může proto uhádnout několik hlavních slov. Mimoto lze nalézt zpravidla standardní úvodní a závěrečné fráze atd. Útoky na šifru 3. Chosen plaintext attack: Má-li kryptoanalytik přístup k šifrovacímu algoritmu (s aktuálním klíčem), může pak za účelem zjištění klíče kódovat vybrané části zprávy a pokusit se udělat z obdrženého kryptogramu závěry o struktuře klíče. Útoky na šifru 3. Chosen plaintext attack: Má-li kryptoanalytik přístup k šifrovacímu algoritmu (s aktuálním klíčem), může pak za účelem zjištění klíče kódovat vybrané části zprávy a pokusit se udělat z obdrženého kryptogramu závěry o struktuře klíče. Mohl by například do stroje vkládat pravidelná zdrojová slova, např. posloupnosti stejných písmen (aaa ...) za účelem jejich zakódování. Nebezpečí takovéhoto útoku spočívá v tom, že by se mohlo Mr. X podařit přimět šifrovací stroj k tomu, aby zakódoval zdánlivě neškodné zprávy, s jejichž pomocí pak Mr. X může zašifrovat zprávu, kterou by odesilatel nikdy nezašifroval. Útoky na šifru 3. Chosen plaintext attack: Má-li kryptoanalytik přístup k šifrovacímu algoritmu (s aktuálním klíčem), může pak za účelem zjištění klíče kódovat vybrané části zprávy a pokusit se udělat z obdrženého kryptogramu závěry o struktuře klíče. Mohl by například do stroje vkládat pravidelná zdrojová slova, např. posloupnosti stejných písmen (aaa ...) za účelem jejich zakódování. Nebezpečí takovéhoto útoku spočívá v tom, že by se mohlo Mr. X podařit přimět šifrovací stroj k tomu, aby zakódoval zdánlivě neškodné zprávy, s jejichž pomocí pak Mr. X může zašifrovat zprávu, kterou by odesilatel nikdy nezašifroval. Jak nebezpečný může být takovýto útok, se obzvláště ukáže, když pomyslíme na to, že mnohé šifrovací přístroje pouze nešifrují, ale také "podpisují". 1 Pokud je algoritmus tak slabý, že dovolí tento útok, pak by mohl Mr. X vytvořit z nevinně vyhlížejících podepsaných zpráv brizantní, platně podepsaný dokument. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Útoky na šifru III Pokud je algoritmus tak slabý, že dovolí tento útok, pak by mohl Mr. X vytvořit z nevinně vyhlížejících podepsaných zpráv brizantní, platně podepsaný dokument. Každé monoabecední šifrování přirozeného jazyka může být dosti lehce prolomeno. Musíme si pouze ujasnit, že každé monoabecední šifrování (přirozeného jazyka) lze prolomit již za vysoce slabého (přičemž opravdu realistického) předpokladu 1. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Útoky na šifru III Pokud je algoritmus tak slabý, že dovolí tento útok, pak by mohl Mr. X vytvořit z nevinně vyhlížejících podepsaných zpráv brizantní, platně podepsaný dokument. Každé monoabecední šifrování přirozeného jazyka může být dosti lehce prolomeno. Musíme si pouze ujasnit, že každé monoabecední šifrování (přirozeného jazyka) lze prolomit již za vysoce slabého (přičemž opravdu realistického) předpokladu 1. Předvedeme pouze "princip" algoritmu. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Útoky na šifru III Pokud je algoritmus tak slabý, že dovolí tento útok, pak by mohl Mr. X vytvořit z nevinně vyhlížejících podepsaných zpráv brizantní, platně podepsaný dokument. Každé monoabecední šifrování přirozeného jazyka může být dosti lehce prolomeno. Musíme si pouze ujasnit, že každé monoabecední šifrování (přirozeného jazyka) lze prolomit již za vysoce slabého (přičemž opravdu realistického) předpokladu 1. Předvedeme pouze "princip" algoritmu. Představme si, že Mr. X zachytil kryptogram o délce asi 500 písmen a že ví, že kryptogram byl zašifrován pomocí monoabecedního šifrování. Útoky na šifru Krok 1. Nejdříve Mr. X zjistí četnosti písmen kryptogramu. Tím získá ekvivalent e, n spolu s množinou písmen {i, s, r, a, t}. Jednotlivá písmena z této množiny přitom zpravidla ještě nemůže identifikovat. Útoky na šifru Krok 1. Nejdříve Mr. X zjistí četnosti písmen kryptogramu. Tím získá ekvivalent e, n spolu s množinou písmen {i, s, r, a, t}. Jednotlivá písmena z této množiny přitom zpravidla ještě nemůže identifikovat. Krok 2. Nyní Mr. X spočte bigramy, tzn. páry po sobě sledujících písmen. Nejčastější bigramy německého jazyka jsou uvedeny v následující tabulce: Bigram Četnost Bigram Četnost en 3.88% nd 1.99% er 3.75% ei 1.88% ch 2.75% ie 1.79% te 2.26% in 1.67% de 2.00% es 1.52% Takto může Mr. X izolovat písmena o největším výskytu. Útoky na šifru Např. dvojice er má velmi velkou četnost, zatímco všechny jiné kritické kombinace s e se vyskytují dosti zřídka (ea a et jsou opravdu velmi řídké - pod 0.5%) a také es se vyskytuje se signifikantně malou četností. Útoky na šifru Např. dvojice er má velmi velkou četnost, zatímco všechny jiné kritické kombinace s e se vyskytují dosti zřídka (ea a et jsou opravdu velmi řídké - pod 0.5%) a také es se vyskytuje se signifikantně malou četností. Konkurentem by mohla být dvojice ei; tu však lze vyřadit tím způsobem, že testujeme inverzní dvojice: jen u těchto dvojic je tomu tak, že jak v původní posloupnosti, tak i v obráceném pořadí se vyskytují s prakticky stejnou četností. Útoky na šifru Např. dvojice er má velmi velkou četnost, zatímco všechny jiné kritické kombinace s e se vyskytují dosti zřídka (ea a et jsou opravdu velmi řídké - pod 0.5%) a také es se vyskytuje se signifikantně malou četností. Konkurentem by mohla být dvojice ei; tu však lze vyřadit tím způsobem, že testujeme inverzní dvojice: jen u těchto dvojic je tomu tak, že jak v původní posloupnosti, tak i v obráceném pořadí se vyskytují s prakticky stejnou četností. Tímto způsobem může Mr. X nejprve izolovat rozlišitelná písmena skupiny {i, s, r, a, t} s druhou největší četností. Dále může rozpoznat písmena c a h podle toho, že se jako dvojice vyskytují relativně často ale samostatně velmi zřídka. Úvod Posouvací šifry Další šifry Spartská skytala Monoabecední šifry Kryptoanalýza Útoky na šifru Útoky na šifru V Např. dvojice er má velmi velkou četnost, zatímco všechny jiné kritické kombinace s e se vyskytují dosti zřídka (ea a et jsou opravdu velmi řídké - pod 0.5%) a také es se vyskytuje se signifikantně malou četností. Konkurentem by mohla být dvojice ei; tu však lze vyřadit tím způsobem, že testujeme inverzní dvojice: jen u těchto dvojic je tomu tak, že jak v původní posloupnosti, tak i v obráceném pořadí se vyskytují s prakticky stejnou četností. Tímto způsobem může Mr. X nejprve izolovat rozlišitelná písmena skupiny {i, s, r, a, t} s druhou největší četností. Dále může rozpoznat písmena c a h podle toho, že se jako dvojice vyskytují relativně často ale samostatně velmi zřídka. Tímto způsobem může prakticky bezchybně identifikovat nejčastěji se vyskytující písmena; tj. písmena e5 n5 i, s5 r5 a, t5 h5 c, která tvoří více než dvě třetiny textu. Krok 3 Pak nechá Mr. X dosadit rozpoznaná písmena do celého textu. Jinak řečeno: počítač rozšifruje známé díly textu. Ten se objeví na obrazovce, přičemž nerozluštěná písmena se nahradí účelně prázdnými znaky. Útoky na šifru Krok 3 Pak nechá Mr. X dosadit rozpoznaná písmena do celého textu. Jinak řečeno: počítač rozšifruje známé díly textu. Ten se objeví na obrazovce, přičemž nerozluštěná písmena se nahradí účelně prázdnými znaky. Zpravidla tento text není rozšifrován, nebo se jeho šifrování provádí ještě stále náročně. Další písmena však může inteligentní Mr. X na základě kontextu lehce hádat\ To provede a nechá si vždy po každém kroku ukázat změněný text. Po dvou nebo třech krocích dospěje k velmi dobře čitelnému textu. Útoky na šifru Krok 3 Pak nechá Mr. X dosadit rozpoznaná písmena do celého textu. Jinak řečeno: počítač rozšifruje známé díly textu. Ten se objeví na obrazovce, přičemž nerozluštěná písmena se nahradí účelně prázdnými znaky. Zpravidla tento text není rozšifrován, nebo se jeho šifrování provádí ještě stále náročně. Další písmena však může inteligentní Mr. X na základě kontextu lehce hádat\ To provede a nechá si vždy po každém kroku ukázat změněný text. Po dvou nebo třech krocích dospěje k velmi dobře čitelnému textu. Shrnutí: Monoabecední šifrování nad přirozeným jazykem jsou pozoruhodně nejistá (přirozený jazyk má málo písmen, jež jsou dost nerovnoměrně rozdělena). V současné době proto používáme buď monoabecední šifrování nad umělým jazykem nebo po/yabecední šifrování.