Friedmanův test — index koincidence

Dalším způsobem jak prolomit Vigenèrovu šifru je Friedmanův test, díky kterému lze relativně snadno ověřit, jestli byl šifrový text zašifrován klíčem zvolené délky. Friedmanův test je proto dobré kombinovat s Kasiského testem, který nám nabídne množinu pravděpodobných délek klíčů a pomocí Friedmanova testu zvolíme takovou délku klíče, která je nejvíce pravděpodobná.

Index koincidence

Index koincidence nám udává, jak velká je pravděpodobnost, že když náhodně vybereme z textu dvě písmena, že budou stejná. Například v textu „aaaaaa“ máme 100% pravděpodobnost, že zvolená dvojice bude stejná. V textu „aaaabbc“ bude pravděpoddbnost 1/3 a nejpravděpodobnější bude, že zvolíme dvě písmena „a“.

Jak bychom index koincidence spočítali? Mějme nějaký vstupní text t a hodnoty n_a, n_b, …, n_z, které označují počet výskytů daného písmene v textu t. Takže pro t = „aaaabbc“ máme hodnoty n_a = 4, n_b = 2, n_c = 1 a ostatní hodnoty jsou nulové.

Dále spočítáme počet stejných dvojic písmen. Kolik existuje různých dvojic písmen „a“? Můžeme vzít tuto dvojici “aaaabbc“ nebo třeba tuto “aaaabbc“ a několik dalších. Kolik jich je celkem? Protože nezáleží na pořadí, zvolíme kombinace. Máme celkem n_a možností jak vybrat písmeno „a“ a máme celkem n_a − 1 možností, jak k němu přidat další „a“. Protože nezáleží na pořadí, hodnotu ještě vylíme dvěma. Počet všech různých dvojic písmen „a“ je tak roven:

$$ \frac{n_a\cdot(n_a-1)}{2} $$

Tento vzorec můžeme použít pro všechna písmena, tzn., že počet všech možných stejných dvojic písmen je roven

$$ \frac{n_a\cdot(n_a-1)}{2} + \frac{n_b\cdot(n_b-1)}{2} + \dots + \frac{n_z\cdot(n_z-1)}{2}. $$

Pro náš text bychom získali:

$$ \frac{4\cdot3}{2}+\frac{2\cdot1}{2}+\frac{1\cdot0}{2}=7 $$

A jsou to tyto dvojice stejných písmen: “aaaabbc“, „aaaabbc“, „aaaabbc“, “aaaabbc“, “aaaabbc“, „aaaabbc“, „aaaabbc“.

Předchozí vzorec můžeme rozepsat pomocí sumy (zde už je x proměnná, ne písmeno):

$$ \sum_{x=„a“}^{„z“} \frac{n_x\cdot(n_x-1)}{2} $$

Abychom získali pravděpodobnost, vydělíme tuto hodnotu počtem všech možných dvojic písmen (stejných nebo různých), které v textu existují. Pokud označíme délku textu N, pak počet všech dvojic bude

$$ \frac{N \cdot (N - 1)}{2} $$

Důvod je opět stejný: máme celkem N možností jak vybrat nějaké písmeno a máme celkem N − 1 možností, jak k němu přidat další písmeno a utvořit tak dvojici. Protože nezáleží na pořadí, dělíme dvěma. Celková pravděpodobnost, a zároveň index koincidence, je tak roven, označíme IK:

$$ IK = \frac{\sum_{x=„a“}^{„z“} \frac{n_x\cdot(n_x-1)}{2}}{\frac{N \cdot (N - 1)}{2}} $$

Dvojky ve jmenovateli můžeme zkrátit, takže nám zůstane:

$$ IK = \frac{\sum_{x=„a“}^{„z“} n_x\cdot(n_x-1)}{N \cdot (N - 1)} $$

To už je finální vzorec. Pokud bychom dosadili hodnoty z našeho textu:

$$ IK =\frac{\sum_{x=„a“}^{„z“} n_x\cdot(n_x-1)}{N \cdot (N - 1)}=\frac{4\cdot3+2\cdot1+1\cdot0}{7\cdot6}=\frac{14}{42}=\frac13 $$

Index koincidence textu „aaaabbc“ je roven jedné třetině. Tzn., že máme třetinovou pravděpodobnost, že když náhodně zvolíme dvě písmena v textu, že tato písmena budou stejná.

Index koincidence náhodného textu

Máme-li dlouhý náhodný text s uniformním rozdělením písmen, vyskytují se v něm všechna písmena přibližně stejně často. Můžeme říci, že u nekonečně dlouhého textu s uniformním rozdělením písmen budeme mít vždy pravděpodobnost 1/26, že náhodně zvolíme dané písmeno. (Počítáme s anglickou abecedou, která má 26 písmen.) Jaký by takový text měl index koincidence?

V takovém textu bychom pro každé písmeno získali pravděpodobnost $\frac{1}{26}\cdot\frac{1}{26}$, že vybereme stejnou dvojici písmen. Protože máme celkem 26 různých písmen, tak celková pravděpodobnost, že náhodně vybereme dvě stejná písmena je

$$ \sum_{i=1}^{26} \frac{1}{26}\cdot\frac{1}{26} = \sum_{i=1}^{26} \frac{1}{676} = \frac{26}{676} = \frac{1}{26}. $$

Index koincidence jazyka

Protože text napsaný v nějakém běžném jazyku jako je češtině není náhodný text, má i jiný index koincidence než náhodný text. Jak spočítat index koincidence nějakého jazyka? Zkrátka někde posbíráme hromady českých textů a spočítáme index koincidence těchto textů.

Čím více textů seženeme, tím lepší výsledky dostaneme. Samozřejmě neexistuje nic jako „oficiální index koincidence českého jazyka“, protože takový index se de facto mění s každým nově napsaným/řečeným slovem v českém jazyce.

Pro ilustraci jsem zkusil provést tuto analýzu nad pěti tisíci česky psanými knihami, které jsem zakoupil na uložto. Výsledkem je, že index koincidence 5000 českých knih vyšel zhruba 0.0588. Můžeme tak říci, že index koincidence českého jazyka je přibližně 0.0588. Jiný zdroj uvádí velmi podobnou hodnotu, 0.06027. Stejný zdroj uvádí i indexy pro další jazyky:

Jak prolomit Vigenèrovu šifru s pomocí Friedmanova testu

Index koindcidence použijeme pro testování, zda daná délka je délkou původního šifrového klíče Vigenèrovy šifry. Přesný postup:

1. Odhadneme, že by klíč mohl být v rozmezí 2 až 15 (proč zrovna 15? Je to jedno.) Označme: K_o = {2,…,15}.

2. Pomocí kasiského metody zjistíme další množinu pravděpodobných klíčů, označme ji K_k.

3. Obě množiny sjednotíme K = K_o ∪ K_k. Získáme tím všechny pravděpodobné délky Vigenèrovy šifry. Jinými slovy — budeme zkoušet všechny délky mezi 2 a 15 plus ty délky, které vrátí Kasiského test.

4. Pro každou délku klíče, tj. pro každé k∈ K: rozdělíme šifrový text do k bloků, v prvním bloku bude vždy 1. písmeno šifrového textu, (1 + k)-té písmeno, (1 + 2k)-té písmeno, atd. Ve druhém bloku bude vždy 2. písmeno šifrového textu, (2 + k)-té písmeno, (2 + 2k)-té písmeno, atd. Bloky si označíme B_i.

5. Pro každý blok B_i spočítáme index koincidence IK_i.

6. Spočítáme průměrný index koincidence všech bloků:

   $$\mbox{IK} = \frac{\sum_{i=1}^k \mbox{IK}_i}{k}$$

7. Nalezneme délku klíče, která má odpovídající index koincidence nejnižší. Tuto délku má pravděpodobně i originální klíč.

8. Prolomíme Vigenèrovu šifru pomocí klasického algoritmu na prolomení Vigenèrovy šifry se znalostí délky klíče.

Online nástroj na prolomení Vigenèrovy šifry

Následující nástroj simuluje uvedený postup.

Šifrový text:

wtzpokioidtgxulwnzswmsgpoflgvlbusducjlsoscvgjluacwmpdcwlymineuqjocucnfzoscvgjluacwmplpzwzlvxsnswkgakwluuskmloyirygzerfuccevcwtzpokioidtgxyipsemfiwmlsezqcvclkccfenpgwymrbtbqwpvrykwteuqlkvagbzhvovirynmnoxxqfckjexqtxphcwjanoysqevioxlxcxpdmyfscwyirkymxkcqmkxakrxuqvpruovzccymtykbguwbcudcrcyqpkdxqblsoscvgjluacwmpmpscwlhuouitjlptoumpkdxtkgvqeemrvzbwkoixkxbcwdgtfecergqnsdmkzpalsyladlsxocvgcewlsnqwufkjiyamowqpujaryghfonpgwzlglcinnzxgvtame