Strona główna » Algorytmy » Szyfry » Łamanie szyfru Cezara
 

Łamanie szyfru Cezara

https://mattomatti.com/a35aa
· Szyfrowanie · Łamanie szyfru ·

Wstęp

Szyfr Cezara był używany w starożytnym Rzymie. Jednak dopiero kilkaset lat temu pojawiły się pierwsze zapiski, które wskazywały na próbę złamania szyfru Cezara. Szyfrowanie polega na przesunięciu znaków w prawo lub lewo o n pozycji. Oznacza to, że określony tekst przy określonym alfabecie o n znakach można zaszyfrować maksymalnie na n - 1 sposobów. Niewielka ilość możliwych szyfrogramów powoduje, że wiadomość można odczytać po maksymalnie n - 1 próbach.

Istnieje jednak metoda, która pozwala na znacznie szybsze i łatwiejsze odczytanie ukrytej wiadomości. Jednak przed przystąpieniem należy zwrócić uwagę, że jeśli mamy k takich samych znaków w tekście jawnym to w szyfrogramie będzie ich tyle samo, ale będą jedynie reprezentować inny znak. W określonym alfabecie niektóre znaki występują częściej, a niektóre rzadziej o czym można się przekonać z poniższego wykresu:

Częstotliwość występowania polskich liter w alfabecie

Szyfrowanie Cezara nie zmienia częstotliwości występowania wybranego znaku, a jedynie jego reprezentację. Oznacza to, że tworząc wykres dla wszystkich znaków w szyfrogramie można określić o ile było wykonane przesunięcie. Oczywiście metoda ta będzie działała dla dłuższych tekstów, które będą zawierały sensowne wyrazy, a nie np. AAABBBCCC. Oczywiście częstotliwość występowania znaków różnią się pomiędzy alfabetami, więc należy przed przystąpieniem do łamania tą metodą określić w jakim języku będzie ukryta wiadomość. Zwiększy to skuteczność działania przedstawionej dalej metody.

Implementacja

Wstępne założenia

Ze względu na fakt, że przedstawiona metoda łamania szyfrogramów ma charakter poglądowy w trakcie łamania programu nie zostaną uwzględnione polskie litery co zmieni nieco wygląd wykresu:

Częstotliwość występowania polskich liter w alfabecie bez polskich znaków

Działanie programu będzie polegało na próbie utworzenia wykresu na podstawie wpisanego tekstu, a następnie wypisaniu jaki klucz został prawdopodobnie wykorzystany w trakcie szyfrowania. Z założenia tekst składa się tylko z małych liter alfabetu łacińskiego.

Analiza

Na początek program musi policzyć ile jakich liter dokładnie występuje. Następny krok polega na próbie dopasowania wyliczonych wartości do danych wprowadzonych przez użytkownika na temat wybranego alfabetu. Najprostszy sposób dopasowania polega na znalezieniu znaku z największym procentem, a następnie znalezienie przesunięcia.

  1. int findKey(char* alfabet, double* wyst, char* txt){
  2.   int dl = strlen(alfabet), t = -1, txt_dl = 1;
  3.   double* txt_znaki = new double[dl];
  4.   for(int i = 0; i < dl; i++)
  5.     txt_znaki[i] = 0;
  6.   for(int i = 0; txt[i]; i++){
  7.     t = findChar(alfabet, txt[i]);
  8.     if(t != -1){
  9.       txt_znaki[t]++;
  10.       txt_dl++;
  11.     }
  12.   }

(1.) Funkcja findkey() przyjmuje trzy argumenty: alfabet - wszystkie litery z których składa się alfabet tekstu jawnego, wyst - procentowa częstotliwość występowania każdej litery oraz txt - tekst do rozszyfrowania. Wynikiem działania będzie liczba całkowita, która będzie kluczem użytym do szyfrowania oryginalnego tekstu. (2.) Deklaracja zmiennych: dl przechowa ile liter ma alfabet, t - bufor przechowujący wynik przeszukiwania alfabetu oraz txt_dl - zmienna, która zliczy ile jest znaków od a do z w tekście. (3.) Zadeklarowanie tablicy w której będą przechowywane częstotliwości występowania poszczególnych liter w podanym tekście. (4. - 5.) Wyzerowanie wartości występowania znaków. (6.) Dla każdego znaku w tekście: (7.) wyszukujemy znak w alfabecie i (8.) jeśli występuje to (9.) zwiększa się częstotliwość występowania litery oraz (10.) długość tekstu.

  1.   for(int i = 0; i < dl; i++){
  2.     txt_znaki[i] /= txt_dl;
  3.     txt_znaki[i] *= 100;
  4.   }
  5.   int max_wyst = 0, max_znaki = 0;
  6.   for(int i = 0; i < dl; i++){
  7.     if(wyst[max_wyst] < wyst[i]){
  8.       max_wyst = i;
  9.     }
  10.     if(txt_znaki[max_znaki] < txt_znaki[i]){
  11.       max_znaki = i;
  12.     }
  13.   }
  14.   delete[] txt_znaki;
  15.   return (max_znaki + dl - max_wyst) % dl;
  16. }

(13. - 16.) Dla każdego znaku w tekście wyliczana jest jego procentowa zależność. Wskazane linijki można pominąć. (17. - 25.) Wyszukiwanie przesunięcia polega na znalezieniu maksymalnych wartości dla częstotliwości występowania litery w alfabecie jak również dla częstotliwości występowania liter dla podanego tekstu. (26.) Dealokacja tablicy z wartościami występowania poszczególnych liter oraz (27.) zwrócenie przesunięcia.

W funkcji findkey() została wykorzystana funkcja findChar(), której zadanie polega na znalezieniu litery na podanej liście. Jeśli dana litera jest na liście to zwracany jest jej indeks, a w przeciwnym wypadku wartość -1.

  1. int findChar(char* alfabet, char c){
  2.   for(int i = 0; alfabet[i]; i++)
  3.     if(alfabet[i] == c)
  4.       return i;
  5.   return -1;
  6. }

Testowanie funkcji

Funkcję można przetestować przy pomocy poniższej funkcji main(). Program na wejściu oczekuje w pierwszej linijce n liter alfabetu zapisanych bez przerw. Następnie należy wpisać n liczb określających częstotliwość występowania poszczególnych liter, a na koniec w pojedynczej linii tekst do rozszyfrowania. Na konsole zostanie wypisana liczba określająca klucz użyty do zaszyfrowania.

  1. int main () {
  2.   char* alfabet = new char[32];
  3.   cin >> alfabet;
  4.   int dl = strlen(alfabet);
  5.   double* wyst = new double[dl];
  6.   for(int i = 0; i < dl; i++)
  7.     cin >> wyst[i];
  8.   cin.ignore();
  9.   char* txt = new char[1024];
  10.   cin.getline(txt, 1024);
  11.   cout << findKey(alfabet, wyst, txt) << endl;
  12.   delete[] alfabet, wyst, txt;
  13.   system("pause");
  14.   return 0;
  15. }

Przykładowy prawidłowy sposób wprowadzenia danych to:

  1. abcdefghijklmnopqrstuvwxyz
  2. 9.90 1.47 4.36 3.25 8.77 0.30 1.42 1.08 8.21 2.28 3.51 3.92 2.80 5.72 8.60 3.13 0.14 4.69 4.98 3.98 2.50 0.04 4.65 0.02 3.76 6.53
  3. Fmlse Prmnen oly hmljnal j fgnebmlgalz Emlzvr. Wrqanx qbcvreb xvyxnfrg yng grzh cbwnjvyl fvr cvrejfmr mncvfxv, xgber jfxnmljnyl an cebor mynznavn fmlseh Prmnen. Fmlsebjnavr cbyrtn an cemrfhavrpvh manxbj j cenjb yho yrjb b a cbmlpwv. Bmanpmn gb, mr bxerfybal grxfg ceml bxerfybalz nysnorpvr b a manxnpu zbman mnfmlsebjnp znxflznyavr an a - 1 fcbfbobj. Avrjvryxn vybfp zbmyvjlpu fmlsebtenzbj cbjbqhwr, mr jvnqbzbfp zbman bqpmlgnp cb znxflznyavr a - 1 cebonpu.

Jest to zaszyfrowany pierwszy akapit artykułu. Program prawidłowo rozpoznaje, że użyto przesunięcia 18.

Zadania

Zadanie 1

Przedstawiony przykładowy program nie uwzględnia dużych liter, które mogą mieć znaczenie podczas wyznaczania przesunięcia. Przepisz program tak, aby wczytywał zarówno małe jak i duże litery alfabetu, a następnie prawidłowo obliczał ile razy które litera występuje.