Index koincidence: Porovnání verzí
(vzorec) |
|||
| (Není zobrazeno 5 mezilehlých verzí od stejného uživatele.) | |||
| Řádek 1: | Řádek 1: | ||
{{Pracuje se}} | {{Pracuje se}} | ||
| − | '''Index koincidence''' je jednou z metod [[Kryptoanalýza|kryptoanalýzy]], která udává pravděpodobnost, že dva náhodné znaky šifry budou dva stejné znaky otevřeného textu.<ref name="Šustal">ŠŮSTAL, Ondřej. ''Aplikace pro kryptoanalýzu substitučních šifer'' [online]. Zlín: Univerzita Tomáše Bati ve Zlíně, 2015, 55 s. [cit. 2018-05-20]. Dostupné také z: http://hdl.handle.net/10563/34256. Bakalářská práce. Univerzita Tomáše Bati ve Zlíně. Fakulta aplikované informatiky, Ústav automatizace a řídicí techniky. Vedoucí práce Roman Šenkeřík.</ref> | + | '''Index koincidence''' je jednou z metod [[Kryptoanalýza|kryptoanalýzy]], která udává pravděpodobnost, že dva náhodné znaky šifry budou dva stejné znaky otevřeného textu.<ref name="Šustal">ŠŮSTAL, Ondřej. ''Aplikace pro kryptoanalýzu substitučních šifer'' [online]. Zlín: Univerzita Tomáše Bati ve Zlíně, 2015, 55 s. [cit. 2018-05-20]. Dostupné také z: http://hdl.handle.net/10563/34256. Bakalářská práce. Univerzita Tomáše Bati ve Zlíně. Fakulta aplikované informatiky, Ústav automatizace a řídicí techniky. Vedoucí práce Roman Šenkeřík.</ref> Někdy se též uvadí pod názvem '''Friedmanův test''' podle kryptologa Williama Fredericka Friedmana.<ref name="Friedman">Friedmanův test — index koincidence. ''Matematika.cz'' [online]. Brno: Vydavatelství Nová média, ©2016-2014 [cit. 2018-05-21]. Dostupné z: https://matematika.cz/friedmanuv-test</ref> |
<br /> | <br /> | ||
Principem '''indexu koincidence''' je výpočet pravděpodobnosti s jakou náhodně zvolená dvojice znaků bude shodná. Výpočet lze vyjádřit: | Principem '''indexu koincidence''' je výpočet pravděpodobnosti s jakou náhodně zvolená dvojice znaků bude shodná. Výpočet lze vyjádřit: | ||
<br /> | <br /> | ||
<br /> | <br /> | ||
| − | <math>IC = \frac{\sum_{i=1}^c n_i \left( n_i - 1 \right)}{N \left( N - 1 \right) | + | <math>IC = \frac{\sum_{i=1}^c n_i \left( n_i - 1 \right)}{N \left( N - 1 \right) }</math> |
<br /> | <br /> | ||
<br /> | <br /> | ||
| − | kde ''IC'' je index koincidence, ''N'' je celkový počet znaků zprávy, ''c'' označuje počet znaků abecedy a ''n<sub>i</sub>'' je počet znaků s indexem i kde <math>i \in \{ | + | kde ''IC'' je index koincidence, ''N'' je celkový počet znaků zprávy, ''c'' označuje počet znaků abecedy a ''n<sub>i</sub>'' je počet znaků s indexem i kde <math>i \in \{ a,b...z \}</math>.<ref name="Šustal" /> Tedy ''i'' je označení jednoho konkrétního znaku (v tomto případě v rámci anglické abecedy) a postupně nabývá všech hodnot (tedy obsáhne všechny znaky v textu). V zásadě za pomoci sumy v čitateli lze získat počet všech kombinací stejných znaků a naopak výpočet ve jmenovateli udává počet kombinací všech dvojic znaků nezávisle na tom, které znaky to jsou (protože v tomto výpočtu nezávisí na pořadí znaků, měli by být jak čitatel, tak jmenovatel vyděleny dvojkou, nicméně obě dvojky se zkrátí a jsou ze vzorečku vynechány). Výsledným výpočtem se získá finální pravděpodobnost - Index koincidence.<ref name="Friedman" /> |
| − | + | <br /> | |
| − | + | <br /> | |
| − | + | === Index koincidence náhodného textu === | |
| − | + | V případě náhodného textu s pravidelným výskytem každého znaku, u kterého by délka textu byla nekonečně dlouhá (za použití anglické abecedy) by index koincidence byl 1/26, to je přibližně 3,85% pravděpodobnost výskytu dvou stejných znaků za sebou.<ref name="Šustal" /><ref name="Friedman" /> | |
| + | <br /> | ||
| + | == Využití indexu koincidence == | ||
| + | Index koincidence v bězných jazycích je podstatně vyšší než v případě zcela náhodného textu (Kupříkladu index koincidence v češtině je přibližně 6% a v angličtině přibližně 6,7%). Při použití monoalfabetické substituční šifry zůstává index koincidence zachován a odpovídá danému jazyku. Při použití například polyalfabetické šifry se naopak index koincidence významně přiblíží hodnotě náhodného textu. Lze tak určit, zda se jedná o monoalfabetickou substituční šifru.<ref name="Šustal" /> | ||
| + | === Prolomení Vigenèrovy šifry=== | ||
| + | Za pomoci indexu koincidence a [[Kasiského test|Kasiského testu]] lze nalézt periodu [[Vigenèrova šifra|Vigenèrovy šifry]]. Následně každý znak v konkrétní pozici každé periody odpovídá jednomu posunu [[Caesarova šifra|Caesarovy šifry]]. Jednotlivé posuny již lze prolomit hrubou silou či za použití [[Frekvenční analýza|Frekvenční analýzy]].<ref name="Friedman" /> | ||
Aktuální verze z 21. 5. 2018, 19:54
|
Na této stránce se právě pracuje. Prosím needitujte tuto stránku, dokud na ní zůstává tato šablona. Předejdete tak editačnímu konfliktu. Jestliže uběhla od poslední editace doba alespoň dvou dnů, neváhejte tuto šablonu odstranit. |
|
Index koincidence je jednou z metod kryptoanalýzy, která udává pravděpodobnost, že dva náhodné znaky šifry budou dva stejné znaky otevřeného textu.[1] Někdy se též uvadí pod názvem Friedmanův test podle kryptologa Williama Fredericka Friedmana.[2]
Principem indexu koincidence je výpočet pravděpodobnosti s jakou náhodně zvolená dvojice znaků bude shodná. Výpočet lze vyjádřit:
kde IC je index koincidence, N je celkový počet znaků zprávy, c označuje počet znaků abecedy a ni je počet znaků s indexem i kde .[1] Tedy i je označení jednoho konkrétního znaku (v tomto případě v rámci anglické abecedy) a postupně nabývá všech hodnot (tedy obsáhne všechny znaky v textu). V zásadě za pomoci sumy v čitateli lze získat počet všech kombinací stejných znaků a naopak výpočet ve jmenovateli udává počet kombinací všech dvojic znaků nezávisle na tom, které znaky to jsou (protože v tomto výpočtu nezávisí na pořadí znaků, měli by být jak čitatel, tak jmenovatel vyděleny dvojkou, nicméně obě dvojky se zkrátí a jsou ze vzorečku vynechány). Výsledným výpočtem se získá finální pravděpodobnost - Index koincidence.[2]
Obsah
Index koincidence náhodného textu
V případě náhodného textu s pravidelným výskytem každého znaku, u kterého by délka textu byla nekonečně dlouhá (za použití anglické abecedy) by index koincidence byl 1/26, to je přibližně 3,85% pravděpodobnost výskytu dvou stejných znaků za sebou.[1][2]
Využití indexu koincidence
Index koincidence v bězných jazycích je podstatně vyšší než v případě zcela náhodného textu (Kupříkladu index koincidence v češtině je přibližně 6% a v angličtině přibližně 6,7%). Při použití monoalfabetické substituční šifry zůstává index koincidence zachován a odpovídá danému jazyku. Při použití například polyalfabetické šifry se naopak index koincidence významně přiblíží hodnotě náhodného textu. Lze tak určit, zda se jedná o monoalfabetickou substituční šifru.[1]
Prolomení Vigenèrovy šifry
Za pomoci indexu koincidence a Kasiského testu lze nalézt periodu Vigenèrovy šifry. Následně každý znak v konkrétní pozici každé periody odpovídá jednomu posunu Caesarovy šifry. Jednotlivé posuny již lze prolomit hrubou silou či za použití Frekvenční analýzy.[2]
Odkazy
Reference
- ↑ 1,0 1,1 1,2 1,3 ŠŮSTAL, Ondřej. Aplikace pro kryptoanalýzu substitučních šifer [online]. Zlín: Univerzita Tomáše Bati ve Zlíně, 2015, 55 s. [cit. 2018-05-20]. Dostupné také z: http://hdl.handle.net/10563/34256. Bakalářská práce. Univerzita Tomáše Bati ve Zlíně. Fakulta aplikované informatiky, Ústav automatizace a řídicí techniky. Vedoucí práce Roman Šenkeřík.
- ↑ 2,0 2,1 2,2 2,3 Friedmanův test — index koincidence. Matematika.cz [online]. Brno: Vydavatelství Nová média, ©2016-2014 [cit. 2018-05-21]. Dostupné z: https://matematika.cz/friedmanuv-test
Související články
Asymetrická_kryptografie
Historický vývoj kryptografie v období světových válek
Informační bezpečnost - její klíčové aspekty, hrozby a minimalizace rizika
Moderní použití kryptologie
Symetrická_kryptografie
Šifrování s veřejným klíčem (metoda RSA)
Šifry
Vigenèrova šifra
Základní pojmy v kryptologii
Základní rozdělení kryptologie
Klíčová slova
Kryptoanalýza, Šifra, Dešifrování, Šifrovací klíč, Klasické šifry
Text je dostupný pod licencí Creative Commons Uveďte autora 3.0 Česko při dodržení případných autorských práv a dalších podmínek
© 2013 ISSN: 2336-5897
