PRUMYSL.CZ KONSTRUKTER.CZ 3D-TISK.CZ MATEMATIKA.CZ NOVAMEDIA.CZ

Friedmanův test — index koincidence

Zobrazit kapitoly článku
  1. Vigenèrova šifra
  2. Jak prolomit Vigenèrovu šifru se znalostí délky klíče
  3. Odhadnutí délky klíče Vigenèrovy šifry
  4. Jak spočítat délku klíče Vigenèrovy šifry
  5. 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 na, nb, …, nz, které označují počet výskytů daného písmene v textu t. Takže pro t = „aaaabbc“ máme hodnoty na = 4, nb = 2, nc = 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 na možností jak vybrat písmeno „a“ a máme celkem na − 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:

čeština0.06027
angličtina0.06689
dánština0.07073
finština0.07380
francouzština0.07460
holandština0.07981
němčina0.07667
italština0.07329
ruština0.05607
španělština0.07661

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: Ko = {2, …, 15}.

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

  3. Obě množiny sjednotíme \(K=K_o \cup 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\in 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 Bi.

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

  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:
 

Tento web používá k poskytování služeb, personalizaci reklam a analýze návštěvnosti soubory cookie. Používáním tohoto webu s tím souhlasíte. Další informace