Łamanie szyfru Cezara

Popularną techniką łamania szyfrów podstawieniowych używaną w kryptoanalizie jest zliczanie częstości występowania liter w szyfrogramie. Okazuje się, że przy dłuższych tekstach można zidentyfikować z dużym prawdopodobieństwem najczęściej występujące litery. Tutaj można zobaczyć częstości występowania poszczególnych liter.

Spróbujmy wykonać następujące kroki:

  1. Policzyć częstość występowania poszczególnych liter w zadanym tekście
  2. Znaleźć najczęściej występującą literę i przyjąć, że jest to a. Przyjąć, że jest to klucz - czyli wartość o jaką należy przesunąć wszystkie litery.
  3. Rozszyfrować tekst za pomocą wyliczonego klucza.

Policzyć częstość

…występowania poszczególnych liter w zadanym tekście

Do obliczenia częstości występowania liter przydatne będzie użycie struktury danej zwanej zbiorem. Funkcja set() zamienia listę lub napis na zbiór elementów bez powtórzeń. Proszę przeanalizować poniższy kod.

Mając strukturę danych, w której każdy element występuje tylko raz, można z niej pobierać litery i zliczać ich częstość w napisie.

Została użyta metoda count(znak) zliczająca wystąpienia wartości zmiennej``znak`` w napisie t. W ostatniej linijce zastosowano bardzo wygodny i intuicyjny sposób formatowania napisów. Za każdą pustą parę nawiasów klamrowych jest wstawiana kolejna wartość z metody format.

Znaleźć najczęściej występującą literę

Rozbudujmy nasz snippet o wyszukiwanie najczęściej występującej litery. Nie musimy budować listy, w której będziemy przechowywać częstości poszczególnych znaków. Wystarczy, że będziemy zapisywać częstość i znak, który jest najczęściej występujący w danym momencie.

Rozszyfrować tekst

W tym momencie już w zasadzie znamy klucz. Najczęściej występująca litera jest zapewne literą a. Załóżmy na chwilę, że program wyświetlił, iż najczęściej występującą literą jest d. Skoro kryje się pod nią litera a, to należy przesunąć wszystkie litery o trzy pozycje w lewo, lub co na to samo wyjdzie 23 pozycje w prawo (alfabet 26 literowy). Gdy dochodzimy do skrajnej litery alfabetu, to liczenie kontynuujemy z drugiego końca. Jest to tzw. arytmetyka zegarowa - z tym, że na cyferblacie „zegara” mamy 26 liter.

Nie tylko angielski alfabet

Kolejnym problemem, nad którym się pochylimy, jest znalezienie pozycji litery w alfabecie. Jeżeli mamy do czynienia z 26 literowym alfabetem łacińskim, to sytuacja jest stosunkowo prosta, bo możemy skorzystać z kodów ASCII, które przyporządkowują kolejne litery, są kolejnymi liczbami naturalnymi.

Szyfrowanie pojedyńczej litery

Sytuacja wyglada inaczej, gdy mamy alfabet z polskimi znakami. Pierwsze 127 kodów ASCII pokrywa się z kodami znaków w UTF-8. Programy w Pythonie stosują kodowanie UTF8. Polskie dziewięć liter ąćęłóńśźż ma kody powyżej 250. Rozsądnym wydaje się stworzenie zmiennej alfabet = "aąbcćdeęfghijklłmnńoópqrsśtuvwxyzźż" i zamiast funkcji ord() użycie metody alfabet.index(znak) zwracającej pozycję, na której znajduje się znak w zmiennej alfabet.

Odpowiednikiem funkcji chr() byłoby odczytanie odpowiedniej litery ze zmiennej alfabet przy pomocy nawiasów kwadratowych. Mamy więc print(alfabet[ (alfabet.index(znak) + klucz ) % len(alfabet)]) .

W przykładowych programach powyżej warunek "a" <= znak <= "z" sprawdzający, czy mamy do czynienia z literą, należy zastąpić przez znak in alfabet - czy znak jest w zmiennej alfabet.