Test Friedmana - indeks zbieżności

Innym sposobem na złamanie szyfru Vigenère'a jest test Friedmana, który pozwala stosunkowo łatwo zweryfikować, czy szyfrogram został zaszyfrowany kluczem o wybranej długości. Dlatego też dobrym pomysłem jest połączenie testu Friedmana z testem Kasiskiego, który daje nam zestaw prawdopodobnych długości klucza, i użycie testu Friedmana do wybrania długości klucza, która jest najbardziej prawdopodobna.

Indeks koincydencji

Indeks koincydencji mówi nam, jak prawdopodobne jest, że jeśli losowo wybierzemy dwie litery z tekstu, będą one takie same. Na przykład w tekście "aaaaaa" mamy 100% prawdopodobieństwo, że wybrana para będzie taka sama. W tekście "aaaabbc" prawdopodobieństwo wyniesie 1/3 i najbardziej prawdopodobne jest, że wybierzemy dwie litery "a".

Jak obliczyć indeks zbieżności? Biorąc pod uwagę tekst wejściowy t i wartości n_a, n_b, …, n_z, które wskazują liczbę wystąpień danej litery w tekście t. Tak więc dla t = "aaaabbc" mamy wartości n_a = 4, n_b = 2, n_c = 1, a pozostałe wartości wynoszą zero.

Następnie liczymy liczbę identycznych par liter. Ile jest różnych par litery "a"? Możemy wziąć tę parę "aaaabbc" lub"aaaabbc" i kilka innych. Ile jest ich w sumie? Ponieważ kolejność nie ma znaczenia, wybieramy kombinacje. Mamy w sumie n_a możliwości wyboru litery "a" i mamy w sumie n_a − 1 możliwości dodania do niej kolejnej litery "a". Ponieważ kolejność nie ma znaczenia, dodamy jeszcze dwa do wartości. W ten sposób liczba wszystkich różnych par litery "a" jest równa:

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

Możemy użyć tego wzoru dla wszystkich liter, tj. liczba wszystkich możliwych takich samych par liter jest równa

$$ \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}. $$

Dla naszego tekstu otrzymalibyśmy:

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

A to następujące pary takich samych liter:"aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc", "aaaabbc".

Poprzedni wzór można podzielić za pomocą sumy (tutaj x jest już zmienną, a nie literą):

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

Aby uzyskać prawdopodobieństwo, należy podzielić tę wartość przez liczbę wszystkich możliwych par liter (takich samych lub różnych), które istnieją w tekście. Jeśli oznaczymy długość tekstu przez N, wówczas liczba wszystkich par wyniesie

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

Powód jest ponownie ten sam: mamy w sumie N możliwości wyboru litery i mamy w sumie N − 1 możliwości dodania do niej innej litery w celu utworzenia pary. Ponieważ kolejność nie ma znaczenia, dzielimy przez dwa. Całkowite prawdopodobieństwo i indeks współwystępowania są zatem równe, oznaczając IK:

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

Możemy obciąć dwójki w mianowniku, dzięki czemu otrzymamy:

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

To jest ostateczna formuła. Jeśli podłączymy wartości z naszego tekstu:

$$ 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 $$

Indeks zbieżności tekstu "aaaabbc" jest równy jednej trzeciej. Oznacza to, że mamy jedną trzecią prawdopodobieństwa, że jeśli losowo wybierzemy dwie litery w tekście, litery te będą takie same.

Wskaźnik zbieżności losowego tekstu

Jeśli mamy długi losowy tekst z równomiernym rozkładem liter, wszystkie litery w tekście występują w przybliżeniu równie często. Możemy powiedzieć, że dla nieskończenie długiego tekstu o równomiernym rozkładzie liter, zawsze będziemy mieli prawdopodobieństwo 1/26 losowego wyboru danej litery (liczymy alfabet angielski, który ma 26 liter). Jaki byłby indeks koincydencji takiego tekstu?

W takim tekście dla każdej litery otrzymalibyśmy prawdopodobieństwo $\frac{1}{26}\cdot\frac{1}{26}$, że wybierzemy tę samą parę liter. Ponieważ mamy w sumie 26 różnych liter, całkowite prawdopodobieństwo losowego wybrania dwóch identycznych liter wynosi

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

Wskaźnik zbieżności językowej

Ponieważ tekst napisany w popularnym języku, takim jak czeski, nie jest tekstem losowym, ma on inny indeks koincydencji niż tekst losowy. Jak obliczyć indeks koincydencji języka? Krótko mówiąc, zbieramy gdzieś stosy czeskich tekstów i obliczamy indeks koincydencji tych tekstów.

Im więcej tekstów zbierzemy, tym lepsze wyniki otrzymamy. Oczywiście nie ma czegoś takiego jak "oficjalny indeks koincydencji języka czeskiego", ponieważ taki indeks de facto zmienia się z każdym nowo napisanym/wypowiedzianym słowem w języku czeskim.

Aby to zilustrować, spróbowałem przeprowadzić tę analizę na pięciu tysiącach czeskich książek, które kupiłem na saveto. W rezultacie indeks współwystępowania 5000 czeskich książek wyniósł około 0,0588. Można więc powiedzieć, że wskaźnik współwystępowania języka czeskiego wynosi około 0,0588. Inne źródło podaje bardzo podobną wartość, 0,06027. To samo źródło podaje również wskaźniki dla innych języków:

Jak złamać szyfr Vigenère'a za pomocą testu Friedmana

Używamy wskaźnika koincydencji, aby sprawdzić, czy dana długość jest długością oryginalnego klucza szyfru Vigenère'a. Dokładna procedura:

1. Szacujemy, że klucz może mieć długość od 2 do 15 (dlaczego 15? To nie ma znaczenia): K_o = {2,…,15}.

2. Korzystając z metody Cassisa, znajdźmy inny zestaw prawdopodobnych kluczy, oznaczmy go przez K_k.

3. Ujednolicamy oba zbiory K = K_o ∪ K_k. To daje nam wszystkie prawdopodobne długości szyfru Vigenère'a. Innymi słowy, wypróbujemy wszystkie długości z przedziału od 2 do 15 plus długości zwrócone przez test Kasiskiego.

4. Dla każdej długości klucza, tj. dla każdego k∈ K: podzielimy szyfrogram na bloki k, pierwszy blok będzie zawsze zawierał pierwszą literę szyfrogramu, (1 + k)- tę literę, (1 + 2k)- tę literę itd. Drugi blok będzie zawsze zawierał drugą literę szyfrogramu, (2 + k)-ta litera, (2 + 2k)-ta litera itd. Oznaczymy bloki B_i.

5. Dla każdego bloku B_i obliczamy indeks współwystępowania IK_i.

6. Obliczamy średni wskaźnik współwystępowania wszystkich bloków:

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

7. Znajdujemy długość klucza, który ma najniższy indeks koincydencji. Jest to prawdopodobnie długość oryginalnego klucza.

8. Łamiemy szyfr Vigenère'a przy użyciu klasycznego algorytmu łamania szyfru Vigenère'a ze znajomością długości klucza.

Narzędzie online do łamania szyfru Vigenère'a

Poniższe narzędzie symuluje powyższą procedurę.

Szyfrogram:

wtzpokioidtgxulwnzswmsgpoflgvlbusducjlsoscvgjluacwmpdcwlymineuqjocucnfzoscvgjluacwmplpzwzlvxsnswkgakwluuskmloyirygzerfuccevcwtzpokioidtgxyipsemfiwmlsezqcvclkccfenpgwymrbtbqwpvrykwteuqlkvagbzhvovirynmnoxxqfckjexqtxphcwjanoysqevioxlxcxpdmyfscwyirkymxkcqmkxakrxuqvpruovzccymtykbguwbcudcrcyqpkdxqblsoscvgjluacwmpmpscwlhuouitjlptoumpkdxtkgvqeemrvzbwkoixkxbcwdgtfecergqnsdmkzpalsyladlsxocvgcewlsnqwufkjiyamowqpujaryghfonpgwzlglcinnzxgvtame