Jak obliczyć długość klucza szyfru Vigenère'a
Kapitoly: Szyfr Vigenère'a, Jak złamać szyfr Vigenère'a znając długość klucza, Szacowanie długości klucza szyfru Vigenère'a, Jak obliczyć długość klucza szyfru Vigenère'a, Test Friedmana - indeks zbieżności
Test Kasiskiego
Istnieje procedura, która rzeczywiście może być użyta do oszacowania przynajmniej w przybliżeniu długości użytego klucza lub do zredukowania liczby możliwych kluczy do jakiegoś rozsądnie małego zbioru. Słabość ta została odkryta niezależnie przez dwie osoby, Charlesa Babbage'a i Friedricha Kasiskiego. Babbage był pierwszy, ale Kasiski był pierwszym, który to opublikował, więc metoda została nazwana na jego cześć - metoda Kasiskiego lub test Kasiskiego.
Główną zaletą szyfru Vigenère' a jest to, że jeśli w tekście otwartym występują dwa takie same słowa, są one szyfrowane różnymi kluczami. Zazwyczaj. Czasami jednak tak się nie dzieje i to właśnie wykorzystuje ten algorytm.
Wyobraźmy sobie, że chcemy zaszyfrować tekst "Dzisiaj idę do kina lub teatru. Pojadę samochodem lub taksówką". Używamy klucza "cipher". Wynikowy szyfrogram będzie miał postać "vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom". Spacje zostały pozostawione w szyfrogramie celowo.
Interesującą rzeczą, którą możemy zauważyć, jest to, że słowo "lub" pojawia się dwukrotnie w zwykłym tekście. Idealnie byłoby, gdyby oba wystąpienia w szyfrogramie zostały zaszyfrowane do innego szyfrogramu. Ale przez przypadek oba wystąpienia słowa "lub" zostały zaszyfrowane słowem "fmgf". Jak to się stało? Zobaczmy, jak klucz został zastosowany:
| Idę dziś wieczorem do kina lub teatru. Pojadę samochodem lub taksówką. |
| sifr asifr as ifra sifr as ifrasif rasifr asi fra sifra sifr asifras |
Widzimy, że podczas powtarzania klucza pierwsze "lub" zostało zaszyfrowane częścią klucza "sifr", a drugie "lub" dokładnie tą samą częścią klucza. Przypadek jest głupi, zdarza się.
Procedura znajdowania długości klucza
Możemy jednak wykorzystać ten błąd do oszacowania długości klucza. Załóżmy teraz, że mamy tylko szyfrogram "vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom" jako dane wejściowe. Okazuje się, że dwa słowa "fmgf" są takie same. Domyślamy się, że pierwotnie były to te same słowa, które przypadkowo zostały zaszyfrowane tym samym słowem szyfrującym.
Teraz obliczamy odległość między tymi słowami. Liczymy liczbę liter od początku pierwszego słowa "fmgf" do początku drugiego słowa "fmgf", tj. odległość: "vvjj pmril dg snea fmgf dg lnmavtf gobmil tsu gld scyvm fmgf sstneom" (nie licząc spacji). W sumie jest 30 liter. Jeśli mieliśmy rację i dwa słowa "fmgf" są w rzeczywistości tym samym słowem, to klucz będzie miał długość równą jednemu z czynników 30. Dlaczego? Na przykład, jednym z czynników jest liczba 6. Jeśli klucz miałby długość 6, powiedzmy klucz "abcdef", to szyfrowanie tekstu jawnego wyglądałoby następująco:
| Idę dziś wieczorem do kina lub teatru. Pojadę tam samochodem lub taksówką. |
| abcd efabc de fabc defa bc defabcd efabcd efa bcd efabc defa bcdefab |
Widzimy, że ponownie słowa zostaną zaszyfrowane tą samą częścią klucza. Prawdą jest, że jeśli słowa są oddalone od siebie o wielokrotność długości klucza, to słowa będą szyfrowane tą samą częścią klucza.
W tym momencie wiemy więc, że klucz jest prawdopodobnie jednej z długości 2, 3, 5, 6, 10, 15, 30. To wciąż sporo możliwości - możemy zastosować procedurę dalej i spróbować znaleźć inną parę tak samo zaszyfrowanych słów. Jeśli okaże się, że ich odległość wynosi 15, spadniemy do 3 i 5, a stamtąd będzie już bułka z masłem.
Narzędzie online do łamania szyfru Vigenère'a
Narzędzie demonstruje poprzedni algorytm. Próbuje znaleźć identyczne bloki tekstu w szyfrogramie. Jeśli znajdzie takie bloki, oblicza na ich podstawie prawdopodobne długości klucza i próbuje znaleźć klucz dla wszystkich długości. Następnie wybiera najlepszy klucz. Jeśli nie zostanie znaleziony żaden pasujący blok, algorytm kończy działanie.
Oczywiście narzędzie można ulepszyć, próbując skrócić wszystkie klucze do pewnego limitu w przypadku niepowodzenia. Algorytm próbuje tylko kluczy, których długość jest mniejsza lub równa st.
Algorytm ten często radzi sobie z długim kluczem w stosunkowo krótkim czasie, jeśli tekst jest wystarczająco długi. Możesz spróbować wstawić ten tekst do narzędzia i złamać go. Narzędzie znajdzie klucz o długości 58.