Strona główna » Algorytmy » Szyfry » Szyfry ADFGX i ADFGVX
 

Szyfry ADFGX i ADFGVX

https://mattomatti.com/a35aj

Opis

Szyfry ADFGX i ADFGVX są to dwa bardzo podobne szyfry, który były używane podczas pierwszej wojny światowej w 1918 r. Pierwsza wersja ADFGX została opracowana przez pułkownika Fritza Nebela, który swój pomysł przedstawił wojsku niemieckiemu.

Metoda szyfrowania

Początkowo szyfrowanie, w wersji ADFGX, odbywało się przy pomocy szachownicy Polibiusza. Jednak sama tablica była wypełniania literami w sposób losowy i była znana tylko nadawcy i odbiorcy. Kolejne wiersze jak i kolumny miały literowe nagłówki zgodnie z nazwą szyfru. Zgodnie z ideą szachownicy Polibiusza litery I oraz J były szyfrowane przy pomocy tej samej kombinacji znaków. Przykładowa, poprawna tabelka może wyglądać następująco:

ADFGX
AVMLCB
DQOAGW
FNPZRH
GISKTD
XYFZEU

Kolejny etap polega na zaszyfrowaniu kolejnych znaków tekstu jawnego. Przykładowo tekst TAJNA INFORMACJA będzie zaszyfrowany następująco:

Znak jawnyTAJNAINFORMACJA
Znak zaszyfrowanyGGDFGAFADFGAFAXDDDFGADDFAGGADF

Przedostatni etap polega na zaszyfrowaniu danych przy pomocy klucza. Ma to za zadanie dokonać transpozycji szyfrowanej wiadomości. Hasło składające się z n znaków tworzy tabelkę o n kolumnach. Następnie do każdej kolumny po kolei dopisuje się kolejny znak z tekstu zaszyfrowanego. Jeśli po zapisaniu do tabelki ostatniego znaku szyfrogramu w ostatnim wierszu są wolne miejsca to można je wypełnić dowolnymi znakami lub konkretną literą. Przykładowo wypełniona tabelka na podstawie dotychczasowego przykładu i hasła KLUCZ wygląda następująco:

KLUCZ
GGDFG
AFADF
GAFAX
DDDFG
ADDFA
GGADF

Ostatni etap szyfrowania polega na posortowaniu alfabetycznie kolumn według nagłówka kolumn, następnie odczytaniu wszystkich znaków wiersz po wierszu:

CKLUZ
FGGDG
DAFAF
AGAFX
FDDDG
FADDA
DGXAF

W tym przypadku jest przesuwana tylko jedna kolumna C na początek tabelki. Szyfrogram tworzą znaki w kolejnych wierszach bez hasła czyli: FGGDGDAFAFAGAFXFDDDGFADDADGXA.

Deszyfrowanie

Podczas procesu deszyfrowania na początek należy zapisać szyfrogram w formie tabelki i dokonać transpozycji kolumn zgodnie z kluczem. Kolejny etap to jedynie odczytanie kolejnych dwóch znaków i znalezienie zaszyfrowanego znaku w tabelce.

Wersja ADFGVX

Następca szyfru ADFGX miał identyczną metodę szyfrowania. Różnica polega na dodaniu literki V do nagłówka kolumn i wiersza tabelki według, której dane są szyfrowane. Zmiana pozwoliła na szyfrowanie wszystkich 26 znaków alfabetu oraz 10 znaków cyfr. Przykładowa, poprawna tabelka 6x6 mogłaby wyglądać następująco:

ADFGVX
ABDI5MT
DNLOWFX
F890A47
GURJKQS
VCEP321
XHVGY6Z

Implementacja

Założenia

Implementacja szyfru będzie dotyczyć szyfrowania ADFGX. Użytkownik na wejściu będzie wprowadzał trzy linijki danych: tabelkę szyfrowania w postaci 25 znakowego tekstu, gdzie kolejne znaki to kolejne znaki z kolejnych wierszy od lewej do prawej. Druga linijka będzie zawierać klucz: ciąg znaków bez dwóch identycznych znaków. Trzecia linijka to tekst do zaszyfrowania. Kod przewiduje, że wszystkie znaki będą jedynie małymi znakami alfabetu łacińskiego.

Szyfrowanie

Efektywny program to taki, który jest najszybszy i zużywa mało pamięci, dlatego program nie będzie wykonywał zadania krok po kroku tak jak było przedstawione w przykładzie. Funkcja szyfrująca wygląda następująco:

  1. char* szyfrujADFGX(char* table, char* klucz, char* txt) {
  2.   int dl = strlen(txt);
  3.   int dlugosc = int ((2*dl + strlen(klucz) - 1) / strlen(klucz)) * (strlen(klucz));
  4.   char* data = "adfgx";
  5.   char* wynik = new char[dlugosc + 1];
  6.   wynik[dlugosc] = '\0';
  7.   int* klucz_przes = przygotujKlucz(klucz);
  8.   int wiersz = 0, kolumna = 0;
  9.   int i = 0;
  10.   for (; i < dl; i++) {
  11.     int t = (txt[i] == 'j') ? znajdz(table, 'i') : znajdz(table, txt[i]);
  12.     dopiszZnak(wynik, klucz, klucz_przes, wiersz, kolumna, data[t / 5]);
  13.     dopiszZnak(wynik, klucz, klucz_przes, wiersz, kolumna, data[t % 5]);
  14.   }
  15.   i *= 2;
  16.   for (; i < dlugosc; i++) {
  17.     dopiszZnak(wynik, klucz, klucz_przes, wiersz, kolumna, 'x');
  18.   }
  19.   delete[] klucz_przes;
  20.   return wynik;
  21. }

(1.) Funkcja szyfrująca wymaga trzech argumentów: table - tabeli używanych do zamiany, klucz - klucz użyty do szyfrowania oraz txt - tekst do zaszyfrowania. (2.) Pobierz długość tekstu i (3.) wylicz ile znaków będzie faktycznie zapisanych. Związku z tym, że transpozycja wymaga równej długości wierszy to może istnieć potrzeba dopisania dodatkowych znaków. (4.) Ustal litery nagłówków wierszy / kolumn. (5. - 6.) Przygotuj pamięć pod zapis szyfrogramu.

(7.) Przygotuj klucz do szyfrowania. Zwrócona lista określa jak zamienione zostały kolumny. (8.) Zmienne pomocnicze, które pomagają określić, gdzie zapisywany jest znak oraz (9.) który znak jest aktualnie szyfrowany. (10.) Dla każdego znaku: (11.) znajdź w tabelce pozycję znaku i an tej podstawie (12. - 13.) określ jakie litery należy dopisać do szyfrogramu. (15.) Zmień indeks zapisywanego znaku na ilość zapisanych znaków i (16. - 18.) uzupełnij wolne pola tabelki przy pomocy znaku x. (19.) Usuń klucz przesunięcia i (20.) zwróć wynik.

Przygotowanie klucza

Przygotowanie klucza polega na zapisaniu do której kolumny znak z i-tej kolumny ma zostać zapisany.

  1. int* przygotujKlucz(char* klucz) {
  2.   int dl = strlen(klucz);
  3.   int* klucz_przes = new int[dl];
  4.   int j = 0;
  5.   for (int i = 0; i < 26; i++) {
  6.     int t = znajdz(klucz, 'a' + i);
  7.     if(t != - 1)
  8.       klucz_przes[t] = j++;
  9.   }
  10.   return klucz_przes;
  11. }

(1.) Na podstawie klucza utwórz tablicę przesunięć kolumn: (2.) pobierz długość klucza i (3.) utwórz tablicę liczb o tej samej długości. (4.) Utwórz indeks dla listy klucz_przes. (5.) Dla każdej litery znaku alfabetu: (6.) sprawdź czy występuje w kluczu. Jeśli tak to zapisz pod tą samą pozycją co w kluczu na jaką tabelkę jest zamieniana. (10.) Na koniec zwróć utworzoną listę.

Dopisywanie znaku

Na podstawie obecnego szyfrogramu, klucza, klucza przesunięć i aktualnej pozycji zapisu zapisz znak.

  1. void dopiszZnak(char* wynik, char* klucz, int* klucz_przes, int& wiersz, int& kolumna, char znak) {
  2.   wynik[strlen(klucz) * wiersz + klucz_przes[kolumna]] = znak;
  3.   kolumna++;
  4.   if (kolumna == strlen(klucz)) {
  5.     wiersz++;
  6.     kolumna = 0;
  7.   }
  8. }

(2.) Wylicz pozycję zapisu znaku uwzględniając przesunięcie. (3. - 7.) Przejdź do następnej pozycji zapisu.

Znajdź

Powyższe funkcje wspomaga funkcja znajdz(), która dla podanego znaku c zwraca jego pozycję w łańcuchu txt. Jeśli znak nie występuje to zwracane jest -1.

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

Deszyfrowanie

Zgodnie z metodą deszyfrowania:

  1. char* deszyfrujADFGX(char* table, char* klucz, char* txtc) {
  2.   int dl = strlen(txtc);
  3.   char* data = "adfgx";
  4.   char* wynik = new char[dl / 2 + 1];
  5.   wynik[dl / 2] = '\0';
  6.   int* klucz_przes = przygotujKlucz(klucz);
  7.   int wiersz = 0, kolumna = 0;
  8.   for (int i = 0; 2 * i < dl; i ++) {
  9.     int y = znajdz(data, pobierzZnak(txtc, klucz, klucz_przes, wiersz, kolumna));
  10.     int x = znajdz(data, pobierzZnak(txtc, klucz, klucz_przes, wiersz, kolumna));
  11.     wynik[i] = table[y * 5 + x];
  12.   }
  13.   delete[] klucz_przes;
  15.   return wynik;
  16. }

(2. - 7.) Przygotuj dane do deszyfrowania. (8.) Dla każdej pary znaków: (9. - 10.) odczytaj pozycję x, y znaku w tabelce i (11.) na tej podstawie znajdź znak i dopisz do wyniku. (13.) Posprzątaj zbędne dane i (14.) zwróć tekst jawny.

Pobierz znak

Funkcja pobierająca odpowiedni znak jest niemalże identyczna do funkcji dopiszZnak():

  1. char pobierzZnak(char* txtc, char* klucz, int* klucz_przes, int& wiersz, int& kolumna) {
  2.   char znak = txtc[strlen(klucz) * wiersz + klucz_przes[kolumna]];
  3.   kolumna++;
  4.   if (kolumna == strlen(klucz)) {
  5.     wiersz++;
  6.     kolumna = 0;
  7.   }
  8.   return znak;
  9. }

Testowanie funkcji

W celu przetestowania funkcji można skorzystać z poniższej funkcji main(), która zgodnie ze specyfikacją wczytuje dane od użytkownika:

  1. int main () {
  2.   char* table = new char[32];
  3.   char* klucz = new char[32];
  4.   char* txt = new char[512];
  5.   cin.getline(table, 32);
  6.   cin.getline(klucz, 32);
  7.   cin.getline(txt, 32);
  8.   char* txt_c = szyfrujADFGX(table, klucz, txt);
  9.   cout << txt_c << endl;
  10.   char* txt_d = deszyfrujADFGX(table, klucz, txt_c);
  11.   cout << txt_d << endl;
  12.   delete[] txt_c, txt_d;
  13.   system("pause");
  14.   return 0;
  15. }

Przykładowo poprawnymi danymi wejściowymi są:

  1. vmlcbqoagwnpzrhisktdyfjeu
  2. klucz
  3. tajnainformacja

Zadania

Zadanie 1

Napisz program, który będzie szyfrował dane zgodnie z szyfrem ADFGVX. Specyfikacja pozostaje zgodna z przedstawioną implementacją szyfru ADFGVX.

Przykładowo dla danych:

  1. bdi5mtnlowfx890a47urjkqscep321hvgy6z
  2. klucz
  3. tajnainformacja

Program wypisze na ekran:

  1. gaxfgffdagaafddgvdfdgavfvfagfg