Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza 2. Proč jednoduše, když to jde i složitě? Jan Paseka Ústav matematiky a statistiky Masarykova univerzita 27. září 2021 Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Více abeced Víc O čem to bude O Úvod do problematiky • Polyabecední šifrování □ t3 Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Více abeced Polyabecední šifrování I Slovo, věta a z šifer se zvedá poznaný život, náhlý smysl. Gottfried Benn □ t3 Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Více abeced Polyabecední šifrování 1 Slovo, věta a z šifer se zvedá poznaný život, náhlý smysl. Gottfried Benn Fl V této kapitole se budeme zabývat převážně polyabecedními šifrováními. U těchto šifrování se písmena zprávy nešifrují pomocí téže abecedy. Zejména tedy nelze polyabecední šifrování popsat jednoduše pomocí abecedy zprávy a pod ní napsané abecedy kryptogramu. Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Polyabecední šifrování I íce abeced Slovo, věta a z šifer se zvedá poznaný život, náhlý smysl. Gottfried Benn Fl V této kapitole se budeme zabývat převážně polyabecedními šifrováními. U těchto šifrování se písmena zprávy nešifrují pomocí téže abecedy. Zejména tedy nelze polyabecední šifrování popsat jednoduše pomocí abecedy zprávy a pod ní napsané abecedy kryptogramu. Přiřazení písmene zprávy k nějakému písmenu kryptogramu nesmí být prováděno svévolným způsobem. Šifrování musí splňovat silný požadavek jednoznačnosti; v opačném případě by nebylo možné žádné dešifrování. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza íce abeced Polyabecední šifrování II Jinak řečeno: kdyby nebylo šifrování jednoznačné, nenacházel by se příjemce principiálně v žádné lepší situaci než Mr. X! Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Polyabecední šifrování II íce abeced Jinak řečeno: kdyby nebylo šifrování jednoznačné, nenacházel by se příjemce principiálně v žádné lepší situaci než Mr. X! Typickým příkladem algoritmu, u kterého není šifra jednoznačná, je homofonní šifra. Takovéto algoritmy budou předvedeny v následujícím odstavci. Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Polyabecední šifrování II íce abeced Jinak řečeno: kdyby nebylo šifrování jednoznačné, nenacházel by se příjemce principiálně v žádné lepší situaci než Mr. X! Typickým příkladem algoritmu, u kterého není šifra jednoznačná, je homofonní šifra. Takovéto algoritmy budou předvedeny v následujícím odstavci. Největší část kapitoly bude však věnována zkoumání takovýchto polyabecedních šifer, které vzniknou z kombinací monoabecedních algoritmů; takovýmto charakteristickým příkladem je Vigenerevo šifrování. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza O čem to bude • Zneprůhlednění Q Zneprůhlednění četností Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění I eprůhlednění Jak můžeme dosáhnout toho, že všechna písmena kryptogramu se v něm vyskytují se stejnou četností? Zcela jednoduše: Šifrovací předpis přiřadí každému písmeno nikoliv znak, nýbrž množinu znaků (v našem příkladu to budou dvojice čísel), a to tak, že jsou splněny následující podmínky: Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění I eprůhlednění Jak můžeme dosáhnout toho, že všechna písmena kryptogramu se v něm vyskytují se stejnou četností? Zcela jednoduše: Šifrovací předpis přiřadí každému písmeno nikoliv znak, nýbrž množinu znaků (v našem příkladu to budou dvojice čísel), a to tak, že jsou splněny následující podmínky: - Aby bylo dešifrování jednoznačné, musí být množiny příslušející různým písmenu zprávy disjunktní. Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění I eprůhlednění Jak můžeme dosáhnout toho, že všechna písmena kryptogramu se v něm vyskytují se stejnou četností? Zcela jednoduše: Šifrovací předpis přiřadí každému písmeno nikoliv znak, nýbrž množinu znaků (v našem příkladu to budou dvojice čísel), a to tak, že jsou splněny následující podmínky: - Aby bylo dešifrování jednoznačné, musí být množiny příslušející různým písmenu zprávy disjunktní. - Počet písmen kryptogramu, které patří k nějakému písmenu zprávy, odpovídá četnosti tohoto písmene. Úvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění I eprůhlednění Jak můžeme dosáhnout toho, že všechna písmena kryptogramu se v něm vyskytují se stejnou četností? Zcela jednoduše: Šifrovací předpis přiřadí každému písmeno nikoliv znak, nýbrž množinu znaků (v našem příkladu to budou dvojice čísel), a to tak, že jsou splněny následující podmínky: - Aby bylo dešifrování jednoznačné, musí být množiny příslušející různým písmenu zprávy disjunktní. - Počet písmen kryptogramu, které patří k nějakému písmenu zprávy, odpovídá četnosti tohoto písmene. V následujícím příkladu homofonní šifry jsou znaky kryptogramu tvořeny 100 dvojicemi číslic 00, 01, ..., 99: Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění II Zneprůhlednění Příklad 2.1 Homofonní šifra Písmeno Zašifrovaní (němčina) a 10 21 52 59 71 b 20 34 c 28 06 80 d 04 19 70 81 87 e 09 18 33 38 40 42 53 54 55 60 66 75 85 86 92 93 99 f 00 41 9 08 12 97 h 07 24 47 89 i 14 39 46 50 65 76 88 94 j 57 k 23 1 16 03 84 m 27 11 49 n 30 35 43 62 63 67 68 72 77 79 0 02 05 82 P 31 q 25 r 17 36 51 69 74 78 83 s 15 26 45 56 61 73 96 t 13 32 90 91 95 98 u 29 01 58 v 37 w 22 x 44 y 48 z 64 Pri zašifrování se priradí písmenu zprávy náhodně jeden z příslušných znaků kryptogramu. ^ *0 °\ O' Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění II Zneprůhlednění Příklad 2.1 Homofonní šifra Písmeno Zašifrovaní (němčina) a 10 21 52 59 71 b 20 34 c 28 06 80 d 04 19 70 81 87 e 09 18 33 38 40 42 53 54 55 60 66 75 85 86 92 93 99 f 00 41 9 08 12 97 h 07 24 47 89 i 14 39 46 50 65 76 88 94 j 57 k 23 1 16 03 84 m 27 11 49 n 30 35 43 62 63 67 68 72 77 79 0 02 05 82 P 31 q 25 r 17 36 51 69 74 78 83 s 15 26 45 56 61 73 96 t 13 32 90 91 95 98 u 29 01 58 v 37 w 22 x 44 y 48 z 64 Pri zašifrování se priradí písmenu zprávy náhodně jeden z příslušných znaků kryptogramu. Příjemce pak může pomocí výše uvedené tabulky jednoduše dešifrovat následující text: ^ *0 O* Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění II Zneprůhlednění Příklad 2.1 Homofonní šifra Písmeno Zašifrovaní (němčina) a 10 21 52 59 71 b 20 34 c 28 06 80 d 04 19 70 81 87 e 09 18 33 38 40 42 53 54 55 60 66 75 85 86 92 93 99 f 00 41 9 08 12 97 h 07 24 47 89 i 14 39 46 50 65 76 88 94 j 57 k 23 1 16 03 84 m 27 11 49 n 30 35 43 62 63 67 68 72 77 79 0 02 05 82 P 31 q 25 r 17 36 51 69 74 78 83 s 15 26 45 56 61 73 96 t 13 32 90 91 95 98 u 29 01 58 v 37 w 22 x 44 y 48 z 64 Pri zašifrování se priradí písmenu zprávy náhodně jeden z příslušných znaků kryptogramu. Příjemce pak může pomocí výše uvedené tabulky jednoduše dešifrovat následující text: 000974495995053710 8948310213996471 3748836696427752. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Zneprůhlednění II Zneprůhlednění Příklad 2.1 Homofonní šifra Písmeno Zašifrovaní (němčina) a 10 21 52 59 71 b 20 34 c 28 06 80 d 04 19 70 81 87 e 09 18 33 38 40 42 53 54 55 60 66 75 85 86 92 93 99 f 00 41 9 08 12 97 h 07 24 47 89 i 14 39 46 50 65 76 88 94 j 57 k 23 1 16 03 84 m 27 11 49 n 30 35 43 62 63 67 68 72 77 79 0 02 05 82 P 31 q 25 r 17 36 51 69 74 78 83 s 15 26 45 56 61 73 96 t 13 32 90 91 95 98 u 29 01 58 v 37 w 22 x 44 y 48 z 64 Pri zašifrování se priradí písmenu zprávy náhodně jeden z příslušných znaků kryptogramu. Příjemce pak může pomocí výše uvedené tabulky jednoduše dešifrovat následující text: 000974495995053710 8948310213996471 3748836696427752. Protože znaky byly vybrány náhodně, vyskytuje se každý znak (v našem případě dvojice číslic) stejně často (odtud jméno "homofonní"). Případný kryptoanalytik je tak postaven před podstatně těžší úlohu než při zkoumání monoabecedního šifrování. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Zneprůhlednění III Avšak neměli bychom příliš jásat, neboť kryptoanalýza je také zde možná. Analýza je založena na pozorování, že četnosti písmen kryptogramu jsou sice stejné, ale že z uvažování nad dvojicemi znaků kryptogramu můžeme stejně dobře získat novou informaci. Budeme diskutovat dva příklady • Uvažuje-li Mr. X ekvivalent písmena c, tedy dvojici 28, zjistí, že v úvahu jako přirozený následník přichází pouze určitá písmena kryptogramu. Toto jsou dvojice 07, 24, 23, 47, 89, tedy ekvivalenty písmene h a písmene k. • Zkoumáme-li ekvivalent písmene e, tedy např. 99, zjistíme, že jisté znaky kryptogramu se vyskytují jako předchůdci a následníci 99 - a to prakticky stejně početně. Musí se pak jednat o ekvivalenty písmene i. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra O čem to bude O Vigenerova šifra • Střídavá šifra ■ Lil V jf □ t3 Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra I Vigenerovo zašifrování bylo veřejnosti zpřístupněno v roce 1586 francouzským diplomatem Blaisem de Vigenere (1523-1596). Základní idea je používat střídavě různá monoabecední šifrování. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra 1 Vigenerovo zašifrování bylo veřejnosti zpřístupněno v roce 1586 francouzským diplomatem Blaisem de Vigenere (1523-1596). Základní idea je používat střídavě různá monoabecední šifrování. Tato idea je tak přirozená, že variace Vigenerova zašifrování byly vícenásobně znovuobjeveny. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra 1 Vigenerovo zašifrování bylo veřejnosti zpřístupněno v roce 1586 francouzským diplomatem Blaisem de Vigenere (1523-1596). Základní idea je používat střídavě různá monoabecední šifrování. Tato idea je tak přirozená, že variace Vigenerova zašifrování byly vícenásobně znovuobjeveny. Dva z nejdůležitějších předchůdců byli Johannes Trithemius (1462 - 1516), jehož knihy Poligraphia (1518) a Steganographia (1531) byly uveřejněny posmrtně, a Giovanni Battista Deila Porta (1538-1615), vynálezce přístroje Camera obscura, který v roce 1558 ve své knize Magia naturalis zveřejnil polyabecední algoritmus, který vykazuje velkou podobu s Vigenerovou šifrou. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra II V této kapitole se budeme hlavně zabývat Vigenerovou šifrou, která je nejznámější mezi všemi periodickými polyabecedními algoritmy, a to ze dvou důvodů: Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra II V této kapitole se budeme hlavně zabývat Vigenerovou šifrou, která je nejznámější mezi všemi periodickými polyabecedními algoritmy, a to ze dvou důvodů: • Vigenerova šifra je prototyp mnoha algoritmů, které byly profesionálně používány až do našeho století (Caesarova šifra je zvláštním případem Vigenerovy šifry pro klíčové slovo délky 1). Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra II V této kapitole se budeme hlavně zabývat Vigenerovou šifrou, která je nejznámější mezi všemi periodickými polyabecedními algoritmy, a to ze dvou důvodů: • Vigenerova šifra je prototyp mnoha algoritmů, které byly profesionálně používány až do našeho století (Caesarova šifra je zvláštním případem Vigenerovy šifry pro klíčové slovo délky 1). • Při kryptoanalýze se seznámíme se dvěmi extrémně důležitými metodami, a to Kasiského testem a Friedmanovým testem. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra II V této kapitole se budeme hlavně zabývat Vigenerovou šifrou, která je nejznámější mezi všemi periodickými polyabecedními algoritmy, a to ze dvou důvodů: • Vigenerova šifra je prototyp mnoha algoritmů, které byly profesionálně používány až do našeho století (Caesarova šifra je zvláštním případem Vigenerovy šifry pro klíčové slovo délky 1). • Při kryptoanalýze se seznámíme se dvěmi extrémně důležitými metodami, a to Kasiského testem a Friedmanovým testem. Abychom mohli použít Vigenerův algoritmus, potřebujeme dvě věci: klíčové slovo a Vigenerův čtverec. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra 111 Vigenerův čtverec Zpráva: a b c d e f g h i j k I mnopq r s t u vwxy z Kryptogram: ABCDEFGH I JKLMNOPQRSTUVWXYZ B C D E F G H I J KLMNOPQRSTUVWXYZA C D E F G H I J KLMNOPQRSTUVWXYZAB DE FGH I J KLMNOPQRSTUVWXYZABC E FGH I J KLMNOPQRSTUVWXYZABCD FGH I J KLMNOPQRSTUVWXYZABCDE GH I JKLMNOPQRSTUVWXYZABCDE F H I J KLMNOPQRSTUVWXYZABCDEFG I J KLMNOPQRSTUVWXYZABCDEFGH J KLMNOPQRSTUVWXYZABCDEFGH I KLMNOPQRSTUVWXYZABCDEFGH I J LMNOPQRSTUVWXYZABCDEFGH I J K MNOPQRSTUVWXYZABCDEFGH I J KL NOPQRSTUVWXYZABCDE FGH I J K L M OPQRSTUVWXYZABCDE FGH I J KLMN PQRSTUVWXYZABCDE FGH I J KLMNO QRSTUVWXYZABCDE FGH I J KLMNOP RSTUVWXYZABCDE FGH I J KLMNOPQ STUVWXYZABCDE FGH I J KLMNOPQR TUVWXYZABCDE FGH I J KLMNOPQRS UVWXYZABCDE FGH I J KLMNOPQRST VWXYZABCDE FGH I JKLMNOPQRSTU WXYZABCDE FGH I J KLMNOPQRSTUV XYZABCDEFGH I JKLMNOPQRSTUVW YZABCDEFGH I J K LMNOPQRST UVWX ZABCDEFGH I J K LMNOPQRST UVWXY Tento čtverec se skládá z 26 abeced, které jsou napsány pod sebou takovým způsobem, že první abeceda je obyčejná abeceda, druhá abeceda je o jedno písmeno posunutá, třetí o dvě atd. Jinak řečeno: Vigenerův čtverec sestává z 26 posouvacích šifer v přirozeném pořadí. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra 111 Vigenerův čtverec Zpráva: a b c d e f g h i j k I mnopq r s t u vwxy z Kryptogram: ABCDEFGH I JKLMNOPQRSTUVWXYZ B C D E F G H I J KLMNOPQRSTUVWXYZA C D E F G H I J KLMNOPQRSTUVWXYZAB DE FGH I J KLMNOPQRSTUVWXYZABC E FGH I J KLMNOPQRSTUVWXYZABCD FGH I J KLMNOPQRSTUVWXYZABCDE GH I JKLMNOPQRSTUVWXYZABCDE F H I J KLMNOPQRSTUVWXYZABCDEFG I J KLMNOPQRSTUVWXYZABCDEFGH J KLMNOPQRSTUVWXYZABCDEFGH I KLMNOPQRSTUVWXYZABCDEFGH I J LMNOPQRSTUVWXYZABCDEFGH I J K MNOPQRSTUVWXYZABCDEFGH I J KL NOPQRSTUVWXYZABCDE FGH I J K L M OPQRSTUVWXYZABCDE FGH I J KLMN PQRSTUVWXYZABCDE FGH I J KLMNO QRSTUVWXYZABCDE FGH I J KLMNOP RSTUVWXYZABCDE FGH I J KLMNOPQ STUVWXYZABCDE FGH I J KLMNOPQR TUVWXYZABCDE FGH I J KLMNOPQRS UVWXYZABCDE FGH I J KLMNOPQRST VWXYZABCDE FGH I JKLMNOPQRSTU WXYZABCDE FGH I J KLMNOPQRSTUV XYZABCDEFGH I JKLMNOPQRSTUVW YZABCDEFGH I J K LMNOPQRST UVWX ZABCDEFGH I J K LMNOPQRST UVWXY Tento čtverec se skládá z 26 abeced, které jsou napsány pod sebou takovým způsobem, že první abeceda je obyčejná abeceda, druhá abeceda je o jedno písmeno posunutá, třetí o dvě atd. Jinak řečeno: Vigenerův čtverec sestává z 26 posouvacích šifer v přirozeném pořadí. Klíčovým slovem může být libovolná posloupnost písmen; pro náš de-monstranční případ vybereme slovo "VENUŠE". Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra IV Klíčové slovo: VENUSEVENUSE Zpráva: po 1 yabecedni. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra IV Klíčové slovo: VENUSEVENUSE Zpráva: po I yabecedni. Při šifrování určí písmeno klíčového slova, které stojí nad určitým písmenem zprávy příslušnou abecedu tj. řádku ve Vigenerově čtverci a pomocí této abecedy bude písmeno zprávy šifrováno. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Střídavá šifra IV Klíčové slovo: VENUSEVENUSE Zpráva: po I yabecedni. Při šifrování určí písmeno klíčového slova, které stojí nad určitým písmenem zprávy příslušnou abecedu tj. řádku ve Vigenerově čtverci a pomocí této abecedy bude písmeno zprávy šifrováno. Celkem tedy máme Klíčové slovo: V E Zpráva: p o Kryptogram: K S N U S I y a Y S S E V E N U S E b e c e d n i F Z G R Y F M. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Střídavá šifra V Je jasné, že takováto šifrovací metoda staví Mr. X před podstatně větší problémy, než je tomu při monoabecedním šifrování. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Střídavá šifra V Je jasné, že takováto šifrovací metoda staví Mr. X před podstatně větší problémy, než je tomu při monoabecedním šifrování. Četnost písmen je daleko rovnoměrnější, což lze poznat i na našem krátkém příkladu. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Střídavá šifra V Je jasné, že takováto šifrovací metoda staví Mr. X před podstatně větší problémy, než je tomu při monoabecedním šifrování. Četnost písmen je daleko rovnoměrnější, což lze poznat i na našem krátkém příkladu. Např. písmeno zprávy e bylo zašifrováno do Z a R, písmeno kryptogramu S vzniklo ze tří různých písmen zprávy (o, y5 a). Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza O čem to bude Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr O Kryptoanalýza • Dvě metody • Kasiského test • Friedmanův test • Určení klíčového slova • Závěrečné poznámky Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Dvě metody I Přirozeně lze i pomocí dnešních metod prolomit text zašifrovaný pomocí Vigenerovy šifry. Totiž dostatečně dlouhý text vykazuje mnoho statisticky zachytitelných pravidelností, které umožňují zjištění klíčového slova. Uvod Homofonní šifra Dvě metody I Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Přirozeně lze i pomocí dnešních metod prolomit text zašifrovaný pomocí Vigenerovy šifry. Totiž dostatečně dlouhý text vykazuje mnoho statisticky zachytitelných pravidelností, které umožňují zjištění klíčového slova. První uveřejněný útok byl publikován v roce 1863 pruským majorem delostrelectva Friedrichem Wilhelmem Kasiským (1805-1881). Uvod Homofonní šifra Dvě metody I Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Přirozeně lze i pomocí dnešních metod prolomit text zašifrovaný pomocí Vigenerovy šifry. Totiž dostatečně dlouhý text vykazuje mnoho statisticky zachytitelných pravidelností, které umožňují zjištění klíčového slova. První uveřejněný útok byl publikován v roce 1863 pruským majorem delostrelectva Friedrichem Wilhelmem Kasiským (1805-1881). Druhá metoda se připisuje plukovníkovi Williamu Fredericku Friedmanovi (1891-1969). Obě metody slouží k určení délky klíčového slova. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Dvě metody Klíčové slovo Kasiského test Závěr Friedmanův test Dvě metody 1 Přirozeně lze i pomocí dnešních metod prolomit text zašifrovaný pomocí Vigenerovy šifry. Totiž dostatečně dlouhý text vykazuje mnoho statisticky zachytitelných pravidelností, které umožňují zjištění klíčového slova. První uveřejněný útok byl publikován v roce 1863 pruským majorem delostrelectva Friedrichem Wilhelmem Kasiským (1805-1881). Druhá metoda se připisuje plukovníkovi Williamu Fredericku Friedmanovi (1891-1969). Obě metody slouží k určení délky klíčového slova. Protože oba testy mají i mimo speciální analýzu Vigenerovy šifry svůj dalekosáhlý a zásadní význam, představíme podrobně obě metody. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Dvě metody II Předpokládejme, že Mr. X zachytil následující text, o kterém ví (nebo se domnívá), že je zašifrován pomocí Vigenerovy šifry: Kryptogram UEQPCVCKAHVNRZURNLAO KlRVGJTDVRVRI CVIDLMY IYSBCCOJQSZNY MBVDLOK FSLMWEFRZAVIQMFJTD I H Cl FPSEBXMFFTD MHZGNMW LKDBSEI PUCEAW J S BA P MB VSZCFUEGITLEU OSJOUOH UAVAGZEZISYRHVRZHUMF RRE MWKULKVKGH AHFEUBK LRGMBJIHLI IFWMBZHUMP KAXAUVUH JHNUU LSVSJ I P JCKT I VSVMZ JEN ZSKAHZS UIHQVIBXMFFIP LCXEQXO CAVBVRTWMBLNG N IVRLPF VTDMHZGNMWKRX VRQEKVR LEUWGRBHZOLCK CWTHWDS I L D AG VNEM J FRV QSVI QMU VSWMZCTHI IWGD JSXEOWS JTKIHKEQ Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test I Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Ačkoliv tato působivá metoda analýzy polyabecedních algoritmů byla poprvé publikována Kasiským, musíme se zmínit, že anglický matematik Charles Babbage (1792-1871), který je mimo jiné znám svou koncepcí předchůdce moderního počítače, provedl neuverejnená zkoumání i v kryptografii. Mj. vyvinul Kasiského test už v roce 1854, tj. devět let před Kasiským. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test I Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Ačkoliv tato působivá metoda analýzy polyabecedních algoritmů byla poprvé publikována Kasiským, musíme se zmínit, že anglický matematik Charles Babbage (1792-1871), který je mimo jiné znám svou koncepcí předchůdce moderního počítače, provedl neuverejnená zkoumání i v kryptografii. Mj. vyvinul Kasiského test už v roce 1854, tj. devět let před Kasiským. Test je založen na následující myšlence: vyskytují-li si ve zprávě dvě posloupnosti stejných písmen (např. v němčině slovo ein), mohou obecně odpovídající posloupnosti v kryptogramu dopadnout různě. Ačkoliv tato působivá metoda analýzy polyabecedních algoritmů byla poprvé publikována Kasiským, musíme se zmínit, že anglický matematik Charles Babbage (1792-1871), který je mimo jiné znám svou koncepcí předchůdce moderního počítače, provedl neuverejnená zkoumání i v kryptografii. Mj. vyvinul Kasiského test už v roce 1854, tj. devět let před Kasiským. Test je založen na následující myšlence: vyskytují-li si ve zprávě dvě posloupnosti stejných písmen (např. v němčině slovo ein), mohou obecně odpovídající posloupnosti v kryptogramu dopadnout různě. Jsou-li ale obě počáteční písmena posloupností zašifrována pomocí téhož písmene klíčového slova, jsou i obě písmena kryptogramu stejná. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test II Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr V tomto případě bude také druhé písmeno posloupnosti v zprávě zašifrováno pomocí téhož písmene klíčového slova; tedy obdržíme i v kryptogramu stejné písmeno. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test II Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr V tomto případě bude také druhé písmeno posloupnosti v zprávě zašifrováno pomocí téhož písmene klíčového slova; tedy obdržíme i v kryptogramu stejné písmeno. To tedy znamená: Budou-li obě počáteční písmena posloupností zprávy zašifrována pomocí téhož písmene klíčového slova, pak sestávají obě posloupnosti v kryptogramu ze stejných písmen. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test II Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr V tomto případě bude také druhé písmeno posloupnosti v zprávě zašifrováno pomocí téhož písmene klíčového slova; tedy obdržíme i v kryptogramu stejné písmeno. To tedy znamená: Budou-li obě počáteční písmena posloupností zprávy zašifrována pomocí téhož písmene klíčového slova, pak sestávají obě posloupnosti v kryptogramu ze stejných písmen. Kdy může nastat případ, že dvě písmena jsou zašifrována pomocí téhož písmene klíčového slova? Právě tehdy, když se klíčové slovo mezi tato písmena n-krát vejde pro vhodné přirozené n. V tomto případě bude také druhé písmeno posloupnosti v zprávě zašifrováno pomocí téhož písmene klíčového slova; tedy obdržíme i v kryptogramu stejné písmeno. To tedy znamená: Budou-li obě počáteční písmena posloupností zprávy zašifrována pomocí téhož písmene klíčového slova, pak sestávají obě posloupnosti v kryptogramu ze stejných písmen. Kdy může nastat případ, že dvě písmena jsou zašifrována pomocí téhož písmene klíčového slova? Právě tehdy, když se klíčové slovo mezi tato písmena n-krát vejde pro vhodné přirozené n. Když nyní Mr. X najde v kryptogramu dvě posloupnosti skládající se se stejných písmen, pak se může domnívat, že jejich vzdálenost je několikanásobek délky klíče. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test III Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Tato pravděpodobnost se řídí pravidlem "čím delší, tím milejší", stejná písmena nevypovídají, že víme něco o délce klíče, a také dvojice složené ze stejných písmen by mohly vzniknout náhodně. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test III Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Tato pravděpodobnost se řídí pravidlem "čím delší, tím milejší", stejná písmena nevypovídají, že víme něco o délce klíče, a také dvojice složené ze stejných písmen by mohly vzniknout náhodně. Z posloupností třech nebo více písmen již může Mr. X dostatečně spolehlivě usuzovat na délku klíčového slova. V našem případě pak zjistí: Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test III Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Tato pravděpodobnost se řídí pravidlem "čím delší, tím milejší", stejná písmena nevypovídají, že víme něco o délce klíče, a také dvojice složené ze stejných písmen by mohly vzniknout náhodně. Z posloupností třech nebo více písmen již může Mr. X dostatečně spolehlivě usuzovat na délku klíčového slova. V našem případě pak zjistí: Posloupnost Odstup Rozklad na součin prvočinitelů odstupu JTD 50 2-5-5 VIQM 265 5-53 TDMHZGNMWK 90 2-3-3-5 MWK 75 3-5-5 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test IV Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Největší společný faktor je 5. Optimistický kryptoanalytik by mohl říci, že "že délka klíčového slova je 5" (ve skutečnosti funguje Kasiského test v praxi velmi dobře). Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test IV Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Největší společný faktor je 5. Optimistický kryptoanalytik by mohl říci, že "že délka klíčového slova je 5" (ve skutečnosti funguje Kasiského test v praxi velmi dobře). Pokud je ale kryptoanalytik opatrný, mluví pouze o silné indicii pro délku klíčového slova 5. Jsou dva důvody pro jeho opatrnost: Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test IV Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Největší společný faktor je 5. Optimistický kryptoanalytik by mohl říci, že "že délka klíčového slova je 5" (ve skutečnosti funguje Kasiského test v praxi velmi dobře). Pokud je ale kryptoanalytik opatrný, mluví pouze o silné indicii pro délku klíčového slova 5. Jsou dva důvody pro jeho opatrnost: O Mohl by nastat případ, že se vyskytují dvě posloupnosti kryptogramu ze tří nebo více stejných písmen, které mají vzdálenost nedělitelnou pěti. Pak bychom získali jako největší společný dělitel jedničku! Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test IV Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Největší společný faktor je 5. Optimistický kryptoanalytik by mohl říci, že "že délka klíčového slova je 5" (ve skutečnosti funguje Kasiského test v praxi velmi dobře). Pokud je ale kryptoanalytik opatrný, mluví pouze o silné indicii pro délku klíčového slova 5. Jsou dva důvody pro jeho opatrnost: O Mohl by nastat případ, že se vyskytují dvě posloupnosti kryptogramu ze tří nebo více stejných písmen, které mají vzdálenost nedělitelnou pěti. Pak bychom získali jako největší společný dělitel jedničku! (V našem případě tento případ skutečně nastane: posloupnost KAH se vyskytne dvakrát a sice s odstupem 128 = 2-2-2-2-2-2.) Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test V Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr To znamená, že nesmíme počítat největší společný dělitel "slepě" pomocí počítače, ale musíme jej určit "citem". Musíme tedy zřejmé chyby vypustit. o Právě proto bychom mohli přijít na myšlenku, že délka klíče by nemusela být pouze 5, nýbrž 10, 15 nebo 30 (neboť faktory 2 a 3 se vyskytují také dostatečně často). Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test V Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr To znamená, že nesmíme počítat největší společný dělitel "slepě" pomocí počítače, ale musíme jej určit "citem". Musíme tedy zřejmé chyby vypustit. o Právě proto bychom mohli přijít na myšlenku, že délka klíče by nemusela být pouze 5, nýbrž 10, 15 nebo 30 (neboť faktory 2 a 3 se vyskytují také dostatečně často). Jinak řečeno: Kasiského test nám poskytuje délku klíčového slova až na násobek. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test V Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr To znamená, že nesmíme počítat největší společný dělitel "slepě" pomocí počítače, ale musíme jej určit "citem". Musíme tedy zřejmé chyby vypustit. o Právě proto bychom mohli přijít na myšlenku, že délka klíče by nemusela být pouze 5, nýbrž 10, 15 nebo 30 (neboť faktory 2 a 3 se vyskytují také dostatečně často). Jinak řečeno: Kasiského test nám poskytuje délku klíčového slova až na násobek. Z výše uvedeného důvodu budeme prezentovat druhou metodu; tato určuje řádový odhad délky klíčového slova. Kombinace těchto obou metod je prakticky úplně spolehlivá. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Kasiského test VI Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Kryptogram UEQPCVCKAHVNRZURNLAO KIRVGJTDVRVRI CVIDLMY I YSBCCOJQSZNY MBVDLOK FSLMWEFRZAVIQMFJTD I H ClFPSEBXMFFTD MHZGNMW LKDBSEI PUCEAW JSBAPMB VSZCFUEGIT LEU OSJOUOH UAVAGZEZISYRHVRZHUMF RRE MWKULKVKGH AHFEUBK LRGMBJIHLI I FW MBZHUMP KAXAUVUH J HNUU LSVSJ I P JCKT IVSVMZJEN ZSKAHZS UIHQVIBXMFFIP LCXEQXO CAVB VRTWMB LNGN IVRLPF VTDMHZGNMWKRX VRQEKVR LEUWGRBHZOLCK CWTHWDS I LDAGVNEMJ FRV QSVIQMU VSWMZCTHI IWGD JSXEOWS JTKIHKEQ Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test I Tento postup byl vyvinut Williamem Friedmanem v roce 1925. V tomto testu se ptáme na to, s jakou šancí se náhodně vybraný pár písmen ze zprávy sestává ze stejných písmen. Odpověď je pak dána indexem koincidence. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test I Tento postup byl vyvinut Williamem Friedmanem v roce 1925. V tomto testu se ptáme na to, s jakou šancí se náhodně vybraný pár písmen ze zprávy sestává ze stejných písmen. Odpověď je pak dána indexem koincidence. Představme si nejprve libovolnou posloupnost písmen délky n. Buď n-i počet písmen a, n2 počet písmen b, ..., n26 počet písmen z. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test I Tento postup byl vyvinut Williamem Friedmanem v roce 1925. V tomto testu se ptáme na to, s jakou šancí se náhodně vybraný pár písmen ze zprávy sestává ze stejných písmen. Odpověď je pak dána indexem koincidence. Představme si nejprve libovolnou posloupnost písmen délky n. Buď n-i počet písmen a, n2 počet písmen b, ..., n26 počet písmen z. Zajímáme se o počet dvojic, kdy jsou obě písmena rovna aa. (Nepožadujeme, aby se uvažované dvojice skládaly za sebou následujích písmen.) Pro počet prvního a máme práve n-i možností, pro výběr druhého a zbývá n-i - 1 možností. Protože nezáleží na pořadí písmen, je počet hledaných dvojic roven 2 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test II Je tedy počet dvojic, kdy jsou obě písmena stejná, roven ^ • - 1) n2 • (n2 - 1) n26 ■ {n26 - 1) = n, • (n, - 1) 2 2 2 ^2 ;'=1 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test II Je tedy počet dvojic, kdy jsou obě písmena stejná, roven "1 • ("1 - 1) n2 ■ (n2 - 1) n26 ■ (n26 - 1) ^ n, ■ (n, - 1) 2 2 2 ^2 v Šance obdržení dvojice složené ze stejných písmen je určena následujícím výrazem: Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test II Je tedy počet dvojic, kdy jsou obě písmena stejná, roven 11 -1) n2 -(/72-1) A726 • (A726 - 1 ) =y> 77/-(/7/-1) 2 2 2 ^2 /=1 Šance obdržení dvojice složené ze stejných písmen je určena následujícím výrazem: ■ E£i n/-(n/-1) n-(n-1) a nazývá se Friedmanův index koincidence. Friedman sám značil toto číslo jako k, proto se občas pro metodu, kterou v dalším předvedeme, používá název kappa-test. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test III Přibližme se nyní tomuto indexu koincidence z jiné strany. Předpokládejme, že bychom věděli, že se v našem textu vyskytuje písmeno a s pravděpodobností , písmeno b s pravděpodobností p2, ..., písmeno z s pravděpodobností p26- Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test III Přibližme se nyní tomuto indexu koincidence z jiné strany. Předpokládejme, že bychom věděli, že se v našem textu vyskytuje písmeno a s pravděpodobností , písmeno b s pravděpodobností p2, ..., písmeno z s pravděpodobností p26- (Konkrétní hodnoty pro pravděpodobnosti p, můžeme určit, jestliže víme, ze kterého jazyka text pochází.) Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test III Přibližme se nyní tomuto indexu koincidence z jiné strany. Předpokládejme, že bychom věděli, že se v našem textu vyskytuje písmeno a s pravděpodobností , písmeno b s pravděpodobností p2, ..., písmeno z s pravděpodobností p26. (Konkrétní hodnoty pro pravděpodobnosti p, můžeme určit, jestliže víme, ze kterého jazyka text pochází.) Představme si nyní dvě libovolně vybraná písmena našeho textu. Pravděpodobnost, že první písmeno je rovno a je p-i; tedy přibližná pravděpodobnost, že obě písmena jsou rovna a je p-i2 (pokud n je dostatečně velké, lze takto vzniklou chybu zanedbat). Odpovídající vztahy platí i pro ostatní písmena. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test III Přibližme se nyní tomuto indexu koincidence z jiné strany Předpokládejme, že bychom věděli, že se v našem textu vyskytuje písmeno a s pravděpodobností , písmeno b s pravděpodobností p2, ..., písmeno z s pravděpodobností p26- (Konkrétní hodnoty pro pravděpodobnosti p, můžeme určit, jestliže víme, ze kterého jazyka text pochází.) Představme si nyní dvě libovolně vybraná písmena našeho textu. Pravděpodobnost, že první písmeno je rovno a je p-i; tedy přibližná pravděpodobnost, že obě písmena jsou rovna a je p-i2 (pokud n je dostatečně velké, lze takto vzniklou chybu zanedbat). Odpovídající vztahy platí i pro ostatní písmena. Tedy pravděpodobnost toho, že obě písmena jsou si rovna je 26 Pl2+P22 + -"+P262 = j^Pi2' /=1 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test IV Toto číslo závisí přirozeným způsobem na pravděpodobnostech Pí j P2, • • •, P26- Uvažme dva případy. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Dvě metody Klíčové slovo Kasiského test Závěr Friedmanův test Friedmanův test IV Toto číslo závisí přirozeným způsobem na pravděpodobnostech Pí j P2, • • •, P26- Uvažme dva případy. • Pro text v německém jazyce máme 26 Pi2 = 0.0762. /=1 To znamená, že náhodně zvolená dvojice písmen se skládá ze dvou stejných písmen s šancí 7,62%. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test IV Toto číslo závisí přirozeným způsobem na pravděpodobnostech Pí j P2, • • •, P26- Uvažme dva případy. • Pro text v německém jazyce máme 26 Pi2 = 0.0762. /=1 To znamená, že náhodně zvolená dvojice písmen se skládá ze dvou stejných písmen s šancí 7,62%. Jinak řečeno, každá třináctá dvojice písmen sestává ze stejných písmen. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test V Představme si obráceně zcela náhodný text, tj. text, ve kterém jsou písmena divoce promíchána. Pak každé písmeno se zde vyskytne se stejnou pravděpodobností 1 Pi = 26 V tomto případě pak 26 26 262 ~ 26 26 26 1 1 /=1 /=1 Šance, že v takovémto textu najdeme dvě stejná písmena: se nám zmenšila na polovinu, a tedy každá šestadvacátá dvojice písmen sestává ze stejných písmen. O Pokud známe pravděpodobnosti p-i, P2, • • •, P26 (jako je tomu např. s němčinou či angličtinou), pak víme, že součet čtverců pravděpodobností je přibližně roven indexu koincidence: Obecně lze pak dokázat, že index koincidence (nebo stejně platně i y%t-\ Pí2) Je tím větší, čím je text nepravidelnější, a menší, čím je text pravidelnější Hodnota 0.0385 je absolutní minimum pro index koincidence. Totiž 26 /=1 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test VII O Vraťme se na okamžik k monoabecedním šifrováním. Protože monoabecední šifrování je pouze permutace písmen, zůstává rozdělení četností zachováno. (Četnosti jednotlivých písmen jsou permutovány zároveň s písmeny). Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test VII O Vraťme se na okamžik k monoabecedním šifrováním. Protože monoabecední šifrování je pouze permutace písmen, zůstává rozdělení četností zachováno. (Četnosti jednotlivých písmen jsou permutovány zároveň s písmeny). Např. četnost 0.17 už nepatří písmenu e, nýbrž jeho ekvivalentu v kryptogramu. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test VII O Vraťme se na okamžik k monoabecedním šifrováním. Protože monoabecední šifrování je pouze permutace písmen, zůstává rozdělení četností zachováno. (Četnosti jednotlivých písmen jsou permutovány zároveň s písmeny). Např. četnost 0.17 už nepatří písmenu e, nýbrž jeho ekvivalentu v kryptogramu. Máme tedy, že při monoabecedním šifrování index koincidence zůstává zachován, zatímco při polyabecedním šifrování klesá, vzhledem k tomu, že polyabecední šifrování bylo vytvořeno za tím účelem, aby se navzájem vyrovnaly četnosti jednotlivých písmen. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Dvě metody Klíčové slovo Kasiského test Závěr Friedmanův test Friedmanův test VIII Z toho lze odvodit test, který nám ukáže, zda byl kryptogram vytvořen monoabecedním šifrováním nebo ne: Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test VIII Z toho lze odvodit test, který nám ukáže, zda byl kryptogram vytvořen monoabecedním šifrováním nebo ne: Nejprve vypočteme index koincidence kryptogramu. Je-li tento index přiblížené 0.0762, je šifrování pravděpodobně monoabecední. Je-li index koincidence zřetelně menší, můžeme vycházet z toho, že text byl šifrován polyabecedním šifrováním. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Dvě metody Klíčové slovo Kasiského test Závěr Friedmanův test Friedmanův test VIII Z toho lze odvodit test, který nám ukáže, zda byl kryptogram vytvořen monoabecedním šifrováním nebo ne: Nejprve vypočteme index koincidence kryptogramu. Je-li tento index přiblížené 0.0762, je šifrování pravděpodobně monoabecední. Je-li index koincidence zřetelně menší, můžeme vycházet z toho, že text byl šifrován polyabecedním šifrováním. Nyní použijeme index koincidence k výpočtu délky klíčového slova pro text zašifrovaný Vigenerovou šifrou. Cílem je určit index koincidence textu bez jeho znalosti. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test VIII Z toho lze odvodit test, který nám ukáže, zda byl kryptogram vytvořen monoabecedním šifrováním nebo ne: Nejprve vypočteme index koincidence kryptogramu. Je-li tento index přiblížené 0.0762, je šifrování pravděpodobně monoabecední. Je-li index koincidence zřetelně menší, můžeme vycházet z toho, že text byl šifrován polyabecedním šifrováním. Nyní použijeme index koincidence k výpočtu délky klíčového slova pro text zašifrovaný Vigenerovou šifrou. Cílem je určit index koincidence textu bez jeho znalosti. Protože bylo použito polyabecedního algoritmu, je index koincidence menší než 0.0762. Ale o kolik menší? Odpověď je, že to závisí na délce klíčového slova. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test IX Předpokládejme, že klíčové slovo má délku / a skládá se z navzájem různých písmen. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test IX Předpokládejme, že klíčové slovo má délku / a skládá se z navzájem různých písmen. Rozepišme náš kryptogram do / sloupců. Pak se v prvním sloupci nacházejí písmena číslo 1, / + 1,2/ + 1,..., tedy všechna ta písmena, která byla zašifrována pomocí prvního písmene klíčového slova. Podobně se v druhém, ..., Mém sloupci nacházejí všechna ta písmena, která byla zašifrována pomocí druhého, ..., Mého písmene klíčového slova. Písmeno S, klíč. slova Si S2 S3 S/ 12 3 / /+1 1 + 2 1 + 3 21 2/+1 2/+ 2 ... 3/ 3/+1 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test X Podrobnějším studiem výše uvedeného schématu lze vypočítat index koincidence. První pozorování: Každý sloupec byl získán pomocí monoabecedního šifrování (dokonce pomocí posouvací šifry). Šance, že zde vybereme dvojici stejných písmen, je tedy rovna 0,0762. Uvažme nyní dvojice písmen, která stojí v různých sloupcích. Protože příslušné šifrovací abecedy byly vybrány "náhodně", může se takováto dvojice skládat ze stejných písmen pouze náhodným způsobem. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test X Podrobnějším studiem výše uvedeného schématu lze vypočítat index koincidence. První pozorování: Každý sloupec byl získán pomocí monoabecedního šifrování (dokonce pomocí posouvací šifry). Šance, že zde vybereme dvojici stejných písmen, je tedy rovna 0,0762. Uvažme nyní dvojice písmen, která stojí v různých sloupcích. Protože příslušné šifrovací abecedy byly vybrány "náhodně", může se takováto dvojice skládat ze stejných písmen pouze náhodným způsobem. Pravděpodobnost pro tento jev je podstatně nižší než 0,0762, tj. přibližně 0,0385. (Je to přesně ^, jestliže je klíčové slovo náhodná posloupnost písmen. Pokud ne, je tato pravděpodobnost o něco vyšší.) Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XI Druhé pozorování: Vypočtěme nyní počet dvojic písmen ze stejných sloupců a z různách sloupců. Má-li náš kryptogram celkem n písmen, pak v každém sloupci je právě n/l písmen. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XI Druhé pozorování: Vypočtěme nyní počet dvojic písmen ze stejných sloupců a z různách sloupců. Má-li náš kryptogram celkem n písmen, pak v každém sloupci je právě n/l písmen. (Vzdáme se uvažování zaokrouhlovacích chyb; budeme předpokládat, že text je tak dostatečně dlouhý, že zaokrouhlovací chyby se neprojeví.) Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XI Druhé pozorování: Vypočtěme nyní počet dvojic písmen ze stejných sloupců a z různách sloupců. Má-li náš kryptogram celkem n písmen, pak v každém sloupci je právě n/l písmen. (Vzdáme se uvažování zaokrouhlovacích chyb; budeme předpokládat, že text je tak dostatečně dlouhý, že zaokrouhlovací chyby se neprojeví.) Pro výběr jednoho písmene máme přesně n možností. Je-li toto písmeno zvoleno, pak je pevně určen i sloupec, ve kterém leží. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XI Druhé pozorování: Vypočtěme nyní počet dvojic písmen ze stejných sloupců a z různách sloupců. Má-li náš kryptogram celkem n písmen, pak v každém sloupci je právě n/l písmen. (Vzdáme se uvažování zaokrouhlovacích chyb; budeme předpokládat, že text je tak dostatečně dlouhý, že zaokrouhlovací chyby se neprojeví.) Pro výběr jednoho písmene máme přesně n možností. Je-li toto písmeno zvoleno, pak je pevně určen i sloupec, ve kterém leží. V tomto sloupci máme k dispozici ještě zbývajících n/l - 1 písmen, tedy právě tolik možností pro výběr druhého písmene. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XII Je tedy počet dvojic písmen, která se nacházejí v tom samém sloupci roven ,n -w^ n-(n-l) n'(7"1)/2= 2/ ' Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XII Je tedy počet dvojic písmen, která se nacházejí v tom samém sloupci roven ,n n-(n-l) n-(y-1)/2= y2l J. Protože máme k dispozici právě n - n/l písmen mimo určený sloupec, je počet dvojic písmen z různých sloupců roven nwo n2.(/-1) Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XII Je tedy počet dvojic písmen, která se nacházejí v tom samém sloupci roven ,n -w^ n-(n-l) n'(7"1)/2= 2/ ' Protože máme k dispozici právě n - n/l písmen mimo určený sloupec, je počet dvojic písmen z různých sloupců roven A7Wo A72-(/-1) Na základě výše zmíněného pak máme, že očekávaný počet A dvojic stejných písmen je roven A = " ■ {n2~ " • 0,0762 + ^ ■ \ ~ 1 > • 0,0385. Úvod Vigenerova šifra Homofonní šifra Kryptoanalýza Dvě metody Klíčové slovo Kasiského test Závěr Friedmanův test Friedmanův test XIII Pravděpodobnost, že získáme dvojici složenou ze stejných písmen, je rovna A n-(n-1)/2 / - (/7 — 1) (A7"/} -0,0762+ n-V-]l 0,0385 /•(AI-1) Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Friedmanův test XIII Pravděpodobnost, že získáme dvojici složenou ze stejných písmen, je rovna A n-(n-1)/2 / - (/7 — 1) (A7"/} -0,0762+ n-v-]l 0,0385 /•(AI-1) tj. po úpravě A 1 n-(n-J\)/2 l-(n-l) [0,0377 • n+/• (0,0385 • n-0,0762)] Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XIV Zároveň víme, že index koincidence I je aproximací tohoto čísla; proto platí _ 0,0377-n 0,0385 -n- 0,0762 □ - = Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XIV Zároveň víme, že index koincidence I je aproximací tohoto čísla; proto platí „ 0,0377- n 0,0385 -n- 0,0762 = —--1—---- /■(n-1) n-1 Vyjádříme-li si z výše uvedeného vztahu /, získáme důležitou Friedmanovu formuli pro délku klíčového slova: Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XV Použijme nyní tuto formuli na náš příklad. Najdeme-li všechna n/, obdržíme 26 /7 = 368,^/7/2 = 5924. /=1 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XV Použijme nyní tuto formuli na náš příklad. Najdeme-li všechna n/, obdržíme 26 /7 = 368,^/7/2 = 5924. /=1 Máme tedy 5924 I = twft^ = 0,0439. 135056 Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XV Použijme nyní tuto formuli na náš příklad. Najdeme-li všechna n,-, obdržíme 26 /7 = 368,^/7/2 = 5924. /=1 Máme tedy 5924 I = twft^ = 0,0439. 135056 Jedná se tedy s velkou pravděpodobností o polyabecední šifrování. Spočtěme nyní délku klíčového slova /: /« 6,5. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Friedmanův test XV Použijme nyní tuto formuli na náš příklad. Najdeme-li všechna n,-, obdržíme 26 /7 = 368,^/7/2 = 5924. /=1 Máme tedy 5924 I = twft^ = 0,0439. 135056 Jedná se tedy s velkou pravděpodobností o polyabecední šifrování. Spočtěme nyní délku klíčového slova /: /« 6,5. To ukazuje současně s výsledkem testu Kasiského na to, že délka klíčového slova je skutečně 5 (a ne 10, 15 nebo 20). Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova I Jakmile je zjištěna délka klíčového slova, jde o to poznat klíčové slovo samotné. Ale to už není tak těžké. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova I Jakmile je zjištěna délka klíčového slova, jde o to poznat klíčové slovo samotné. Ale to už není tak těžké. Pokud kryptoanalytik Mr. X zná délku klíčového slova, ví, že písmena č. 1, / + 1,2/ + 1,... příp. č. 2, / + 2,2/ + 2,... atd. byla získána pomocí monoabecedního šifrování (dokonce pomocí posouvací šifry). Zpravidla tedy stačí nalézt ekvivalenty písmene e. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova I Jakmile je zjištěna délka klíčového slova, jde o to poznat klíčové slovo samotné. Ale to už není tak těžké. Pokud kryptoanalytik Mr. X zná délku klíčového slova, ví, že písmena č. 1, / + 1,2/ + 1,... příp. č. 2, / + 2,2/ + 2,... atd. byla získána pomocí monoabecedního šifrování (dokonce pomocí posouvací šifry). Zpravidla tedy stačí nalézt ekvivalenty písmene e. V našem příkladu je / = 5. Ze 74 písmen první "monoabecední" části je 14 rovno V. Proto odpovídá e písmenu V. Z Vigenerova čtverce pak obdržíme, že první písmeno klíčového slova je ii nii Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova II Analogicky, ze 74 písmen druhé, třetí, čtvté a páté "monoabecední" částí je 11 rovno E, 8 rovno H, 21 rovno M a 13 rovno S. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova II Analogicky, ze 74 písmen druhé, třetí, čtvté a páté "monoabecední" částí je 11 rovno E, 8 rovno H, 21 rovno M a 13 rovno S. Proto odpovídá e písmenu E, H, M a S. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova II Analogicky, ze 74 písmen druhé, třetí, čtvté a páté "monoabecední" částí je 11 rovno E, 8 rovno H, 21 rovno M a 13 rovno S. Proto odpovídá e písmenu E, H, M a S. Opětovným nahlédnutím do Vigenerova čtverce pak obdržíme, že další písmena klíčového slova jsou po řadě "A", "D", T a "O". Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova II Analogicky, ze 74 písmen druhé, třetí, čtvté a páté "monoabecední" částí je 11 rovno E, 8 rovno H, 21 rovno M a 13 rovno S. Proto odpovídá e písmenu E, H, M a S. Opětovným nahlédnutím do Vigenerova čtverce pak obdržíme, že další písmena klíčového slova jsou po řadě "A", "D", T a "O". Rozšifrování textu použitím klíčového slova "RÁDIO" je již standardní záležitostí. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Určení klíčového slova III Snadným porovnáním získáme Zpráva denhoechst eno rganisa tionsstand e r f uhrdiek ryptolog i e i n v ened igw osieinformein erstaat I ichenbue rota et igke i uka ten i mmonat bekamen eswu r de d a f ue r geso r g t dasssiewaehre ndih r er arbe i tn i chtge stoe r tw urdensi edurft enihreb tausgeuebt wu r deesgab schluesse I sek retaere dieihrbue r o im dogenpa lasthat ten und fuerihr etaet igke i t r u ndzehnd uerosabe rauch nich t ve r Iassenbevors ieeineg es tel Iteaufga bege I oe st hat ten Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Závěrečné poznámky I Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Viděli jsme, že každé Vigenerovo šifrování s dostatečně krátkým klíčem (aby se mohla ke slovu dostat pravděpodobnost ve sloupcích) lze jednoduchým způsobem rozšifrovat. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Závěrečné poznámky I Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Viděli jsme, že každé Vigenerovo šifrování s dostatečně krátkým klíčem (aby se mohla ke slovu dostat pravděpodobnost ve sloupcích) lze jednoduchým způsobem rozšifrovat. Uvažujme nyní Vigenerovo šifrování s dlouhým klíčovým slovem. Budeme předpokládat, že klíčové slovo je dlouhé právě tak, jak je délka zprávy. Ukážeme dva triky, které Mr. X znemožní účinně využít výše uvedených testů. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Závěrečné poznámky I Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Viděli jsme, že každé Vigenerovo šifrování s dostatečně krátkým klíčem (aby se mohla ke slovu dostat pravděpodobnost ve sloupcích) lze jednoduchým způsobem rozšifrovat. Uvažujme nyní Vigenerovo šifrování s dlouhým klíčovým slovem. Budeme předpokládat, že klíčové slovo je dlouhé právě tak, jak je délka zprávy. Ukážeme dva triky, které Mr. X znemožní účinně využít výše uvedených testů. Trik č.1 Mohli bychom se pokusit použít jako klíč text knihy. Takový klíč má zcela určitě tu výhodu, že ho lze přenést bez velkých problémů. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky II Např. stačí podat příjemci informaci Eugen Eichhorn: Felix Hausdorff - Paul Mongré, aby mohl začít dešifrovat kryptogram pomocí následujícího slova: As you have already heard, Hausdorff was born in the Silesian metropolis Breslau, today called Wroclaw. In the last days of the Second World War, the German Wehrmacht declared Breslau a fortress; the result was its complete destruction. That happened... Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky II Např. stačí podat příjemci informaci Eugen Eichhorn: Felix Hausdorff - Paul Mongré, aby mohl začít dešifrovat kryptogram pomocí následujícího slova: As you have already heard, Hausdorff was born in the Silesian metropolis Breslau, today called Wroclaw. In the last days of the Second World War, the German Wehrmacht declared Breslau a fortress; the result was its complete destruction. That happened... V případě použití takovéhoto klíče se všechny metody na určení délky klíče minou účinkem. Protože však klíč tvoří souvislý text nějaké řeči (angličtina, němčina, apod.), působí na kryptogram statisticky signifikantní data, takže nemůžeme takovouto šifru označit za zcela bezpečnou. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky III První, kdo odhalil tuto slabinu, byl opět Friedman. Proto půjdeme ještě o kus dál. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky III První, kdo odhalil tuto slabinu, byl opět Friedman. Proto půjdeme ještě o kus dál. Trik č.2 V případě triku č.1 mohl Mr. X ještě použít nějakou statistiku v důsledku tvaru klíčového slova. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky III První, kdo odhalil tuto slabinu, byl opět Friedman. Proto půjdeme ještě o kus dál. Trik č.2 V případě triku č.1 mohl Mr. X ještě použít nějakou statistiku v důsledku tvaru klíčového slova. Proto nyní zvolíme za klíčové slovo prakticky nekonečnou, náhodnou posloupnost písmen, na kterou si se statistickými testy nepřijdeme. Např. lze za ni zvolit výsledky opakování vrhu ideální 26-hranou kostkou. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky III První, kdo odhalil tuto slabinu, byl opět Friedman. Proto půjdeme ještě o kus dál. Trik č.2 V případě triku č.1 mohl Mr. X ještě použít nějakou statistiku v důsledku tvaru klíčového slova. Proto nyní zvolíme za klíčové slovo prakticky nekonečnou, náhodnou posloupnost písmen, na kterou si se statistickými testy nepřijdeme. Např. lze za ni zvolit výsledky opakování vrhu ideální 26-hranou kostkou. Lze pak ukázat, že takovýto způsob šifrování je dokonce teoreticky bezpečný! Jinak řečeno: nabízí nám perfektní bezpečnost. Uvod Homofonní šifra Vigenerova šifra Kryptoanalýza Dvě metody Kasiského test Friedmanův test Klíčové slovo Závěr Závěrečné poznámky III První, kdo odhalil tuto slabinu, byl opět Friedman. Proto půjdeme ještě o kus dál. Trik č.2 V případě triku č.1 mohl Mr. X ještě použít nějakou statistiku v důsledku tvaru klíčového slova. Proto nyní zvolíme za klíčové slovo prakticky nekonečnou, náhodnou posloupnost písmen, na kterou si se statistickými testy nepřijdeme. Např. lze za ni zvolit výsledky opakování vrhu ideální 26-hranou kostkou. Lze pak ukázat, že takovýto způsob šifrování je dokonce teoreticky bezpečný! Jinak řečeno: nabízí nám perfektní bezpečnost. Takovýmito perfektními systémy se budeme zabývat v následující kapitole.