Analiza częstości wyjaśniona

Przez stulecia najlepszym sposobem na ukrycie wiadomości było zastąpienie każdej litery alfabetu inną. Liczba możliwych kluczy jest astronomiczna, więc szyfr wydawał się nie do złamania. A jednak już w IX wieku pewien uczony z Bagdadu znalazł jego słabość: język używa niektórych liter znacznie częściej niż innych i żadne przestawianie tego nie ukryje. Analiza częstości zmieniła łamanie szyfrów ze zgadywania w metodę i wciąż jest pierwszą rzeczą, jaką każdy próbuje na nowym szyfrze.

Wykres słupkowy liter szyfru od najczęstszej do najrzadszej, zestawiony z częstością liter w języku angielskim, nad szyfrogramem, w którym rozwiązano już pierwsze litery
Wykres słupkowy liter szyfru od najczęstszej do najrzadszej, zestawiony z częstością liter w języku angielskim, nad szyfrogramem, w którym rozwiązano już pierwsze litery

Szyfr podstawieniowy

Prosty szyfr podstawieniowy zastępuje każdą literę alfabetu inną według stałej tabeli: na przykład A staje się Q, B staje się W i tak dalej, a każda litera jest użyta raz. Tabela jest kluczem. W przeciwieństwie do szyfru Cezara, który tylko przesuwa alfabet i ma 25 kluczy, szyfr podstawieniowy może używać dowolnej kolejności liter: 26! kluczy, około 4 × 10²⁶. Nawet komputer sprawdzający miliard kluczy na sekundę potrzebowałby ponad dziesięciu miliardów lat, by wypróbować wszystkie.

Odkrycie al-Kindiego

Około 850 roku arabski filozof Abu Jusuf al-Kindi napisał traktat o odczytywaniu tajnych wiadomości, najstarszy znany opis analizy częstości. Radził wziąć długi tekst w tym samym języku, policzyć, jak często występuje każda litera, potem policzyć litery tajnej wiadomości i dopasować je do siebie: najczęstszą do najczęstszej, następną do następnej. Uczeni badający Koran od pokoleń liczyli litery i słowa i być może właśnie stąd wziął się ten pomysł.

Litery, pary i słowa

W angielskim około 12,7% liter to E, 9% to T, a 8% to A, podczas gdy Z pojawia się raz na ponad tysiąc liter. Same liczności wskazują jedynie właściwy kierunek, zwłaszcza w krótkich tekstach, dlatego łamacze szyfrów wykorzystują każdy wzorzec, jaki uda się znaleźć. Słowo jednoliterowe to w angielskim A lub I. Najczęstsze pary to TH, HE, IN i ER, a najczęstsze podwojone litery to LL, EE, SS i OO. Po Q prawie zawsze następuje U. Częste słowo trzyliterowe to zapewne THE, a gdy znane są już T, H i E, na swoje miejsca wskakują słowa takie jak THAT i THERE. Każdy język ma swój odcisk palca: w niemieckim i niderlandzkim E dominuje jeszcze bardziej, a w portugalskim prowadzi A.

Zgubny szyfr królowej

W 1586 roku więziona w Anglii Maria Stuart, królowa Szkotów, wymieniała zaszyfrowane listy z Anthonym Babingtonem, który spiskował, by ją uwolnić i zabić królową Elżbietę I. Listy przemycano w beczkach piwa, ale przechodziły one przez ręce szefa wywiadu Elżbiety, Francisa Walsinghama, którego łamacz szyfrów Thomas Phelippes złamał szyfr – podstawienie z kilkoma dodatkowymi symbolami dla częstych słów – za pomocą analizy częstości. Odszyfrowane listy dowiodły udziału Marii w spisku i w lutym 1587 roku została stracona.

Ukrywanie częstości

Twórcy szyfrów nie pozostali dłużni. Szyfry homofoniczne dawały częstym literom po kilka symboli, tak by każdy symbol występował mniej więcej równie często. W tekście rozsiewano też nulle, czyli symbole bez znaczenia, by zakłócić liczenie. Prawdziwą odpowiedzią okazały się szyfry polialfabetyczne, takie jak szyfr Vigenère'a z XVI wieku, które w trakcie szyfrowania przełączają się między kilkoma alfabetami, tak że jedna litera tekstu jawnego staje się wieloma różnymi literami szyfru. Szyfr ten opierał się łamaczom aż do XIX wieku, gdy Charles Babbage i Friedrich Kasiski pokazali, jak znaleźć długość klucza, a następnie zastosować analizę częstości do każdego alfabetu osobno.

Jak komputery rozwiązują kryptogramy

Program też nie jest w stanie wypróbować każdego klucza, ale potrafi się wspinać. Zaczyna od typu, ocenia wynik według tego, jak bardzo przypomina język – zwykle według tego, jak częste są jego grupy od dwóch do czterech liter – a potem zamienia pary liter w kluczu, zachowując każdą zamianę, która podnosi wynik. Gdy żadna zamiana nie pomaga, potrząsa kluczem i zaczyna wspinać się od nowa, zachowując najlepszy wynik. Ta metoda, zwana metodą wspinaczkową (ang. hill climbing), rozwiązuje szyfr podstawieniowy złożony z kilkuset liter w ułamku sekundy, a jej odmiany złamały historyczne szyfry, które przez stulecia opierały się ludziom.

Analiza częstości dziś

Współczesne szyfry, takie jak AES, są projektowane tak, by szyfrogram wyglądał na całkowicie losowy: każda wartość bajtu występuje równie często, a ta sama wiadomość za każdym razem szyfruje się inaczej. Analiza częstości nie ma się tu czego uchwycić. Mimo to idea żyje dalej: statystyka języka pomaga rozpoznać, kiedy odszyfrowanie jest poprawne, łamać szyfry w łamigłówkach i escape roomach oraz odczytywać stare zaszyfrowane listy odnalezione w archiwach. W 2023 roku z pomocą komputera odszyfrowano listy Marii Stuart, które przez stulecia uchodziły za zaginione.

Wypróbuj sam

Otwórz narzędzie do analizy częstości, aby dostać zaszyfrowany akapit po angielsku, niemiecku, francusku, hiszpańsku, włosku, portugalsku lub niderlandzku. Porównaj na wykresie liczności liter z językiem, skorzystaj ze wskazówek – par, podwojonych liter i krótkich słów – i uzupełniaj klucz litera po literze. Podpowiedź i Sprawdź pomagają, gdy utkniesz, a algorytm pokazuje, jak metoda wspinaczkowa kończy pracę.

Często zadawane pytania

Dlaczego E jest najczęstszą literą w angielskim?

Bo występuje w wielu najczęstszych słowach, takich jak THE, BE, HE, WE i ARE, oraz w częstych końcówkach, takich jak -ED i -ES. Większość języków europejskich ma tę cechę: E prowadzi także we francuskim, niemieckim, niderlandzkim i hiszpańskim.

Czy analiza częstości złamie każdy szyfr?

Nie. Łamie szyfry, w których każda litera tekstu jawnego jest zawsze zastępowana tym samym symbolem. Szyfry, które zmieniają podstawienie w trakcie, oraz współczesne szyfry działające na bitach, a nie na literach, wymagają innych metod albo nie da się ich złamać wcale.

Czym jest kryptogram?

To cytat lub zdanie zaszyfrowane prostym podstawieniem i wydrukowane, by czytelnicy rozwiązali je ręcznie. Kryptogramy ukazują się w gazetach od XIX wieku i rozwiązuje się je dokładnie tak, jak pokazuje narzędzie: zaczynając od krótkich słów i najczęstszych liter.

Jak odszyfrowano zaginione listy Marii Stuart?

W 2023 roku George Lasry, Norbert Biermann i Satoshi Tomokiyo rozpoznali w 57 zaszyfrowanych listach z francuskiej biblioteki jej korespondencję. Szyfr używał prawie 200 symboli, więc połączyli komputerową metodę wspinaczkową, która podsunęła prawdopodobne znaczenie wielu symboli, ze staranną ręczną pracą nad resztą.

Chcesz wypróbować?

Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.

Otwórz narzędzie do analizy częstości