Strona główna » Algorytmy » Szyfry » Szyfr Zakręcona Linia

Szyfr Zakręcona Linia

Szyfr

Szyfr Zakręcona Linia to szyfr przestawieniowy, który pozwala zaszyfrować dowolny zestaw znaków. Jest to wygodny szyfr do stosowanie bez użycia komputera i nie wymaga pamiętania wielu reguł. Szyfrowanie jest podzielone na dwa etapy pierwszy z nich polega na określeniu tabelki, która posłuży za tabelkę pośrednią. Tabelka powinna mieć conajmniej tyle miejsc ile jest liter w tekście jawnym. Teoretycznie w tabeli nie powinno być wolnych pól, ale można w nie wpisać np. znak spacji, albo inny dowolny znak z alfabetu.

Po narysowaniu tabelki należy do niej wpisać kolejne znaki tekstu jawnego. Do pierwszej literki wpisuje się od lewej do prawej, w drugim od prawej do lewej, w trzecim od lewej do prawej itd. Drugi etap polega na odczytaniu szyfrogramu z tabelki. Działanie jest analogiczne, ale tym razem odbywa się po kolumnach. Szyfrogram to znaki kolejne z pierwsze kolumny od góry do dołu, z drugiej od dołu do góry, z trzeciej od góry do dołu itd. W celu rozszyfrowania danych należy najpierw zapisać znaki w tabeli kolumnami, a następnie odczytać tekst jawny wierszami od tyłu.

Warto zauważyć, że tego szyfr nie posiada ograniczeń względem zestawu znaków użytych w tekście jawnym, więc bez zmian można go stosować w każdym języku. Należy jednak pamiętać, że samo przestawienie liter może okazać się mało skuteczne. Osoba, która przechwyci wiadomość może spróbować odczytać wiadomość na podstawie znaków, które się znajdują w szyfrogramie.

Przykład

Niech szyfrowanym tekstem jawnym będzie "TAJNAINFORMACJA". Tekst ma długość 15, więc można go zapisać do tabeli 3×5 bez dopisywania dodatkowych znaków. Pierwszy etap zgodnie z wymienioną wcześniej isntrukcją polega na zapisaniu tekstu w kolejnych wierszach. Poniżej został przedstawiony schemat zapisywania kolejnych znaków do tabeli:

Wstępna transpozycja tekstu

Tego typu sposób wpisywania znaków prowadzi do powstanie następującej tabeli:

TAJNA
ROFNI
MACJA

Dane zgromadzone w tabeli należy teraz odczytać kolumnami. Schemat odczytywania jest następujący:

Odczytywanie szyfrogramu

W ten sposób powstaje szyfrogram: "TRMAOAJFCJNNAIA".

Implementacja

Założenia

Implementacja szyfrowania będzie wczytywać od użytkownika jedynie tekst do zaszyfrowania. Na podstawie jego długości zostanie określona tabelka, który podłuży do zaszyfrowania danych. Przyjmujemy, że długość liczby wierszy jest zawsze mniejsza równa liczbie kolumn co pozwoli uniknąć problemów, że podczas szyfrowania użyto tabelki n×m, a do odszyfrowania m×n. W przypadku, gdy tekst jest krótszy od ilości znaków w tekście jawnym program doda automatycznie na koniec odpowiednią liczbę znaków spacji do tekstu jawnego.

Rozmiar tabelki

Funkcja wyliczRozmiar() służy do wyliczania rozmiarów tabelki a×b dla tekstu o długości n. Zmienne a i b są przesyłane przez referencję, więc funkcja nic nie zwraca.

  1. void wyliczRozmiar(int n, int &a, int &b) {
  2.   a = 1;
  3.   b = 1;
  4.   int dzielnik = 2;
  5.   while (n > 1) {
  6.     while (n % dzielnik == 0) {
  7.       if (a < b) {
  8.         a *= dzielnik;
  9.       } else {
  10.         b *= dzielnik;
  11.       }
  12.       n /= dzielnik;
  13.     }
  14.     dzielnik++;
  15.   }
  16.   if (a > b)
  17.     swap(a, b);
  18. }

(2. - 3.) Przypisz zmiennym wstępną wartość oraz (4.) rozpocznij szukanie dzielników n od 2. (5.) Dopóki liczba n nie została podzielona do 1 to (6.) sprawdź czy znaleziono dzielnik n i jeśli tak to (7. - 11.) to pomnóż mniejszą wartość z a i b przez dzielnik, a potem (12.) wyrzuć tem dzielnik z liczby n. (14.) Jeśli dzielnik już nie występuje w n to zwiększ dzielnik. (16.) Na koniec upewnij się, że liczba wierszy jest mniejsza lub równa liczbie kolumn i jeśli nie to (17.) zamień wartości miejscami.

Szyfrowanie

Funkcja szyfrująca szyfruj() przyjmuje tylko jeden argument txt - tekst do zaszyfrowania.

  1. char* szyfruj(const char* txt) {
  2.   int dl = strlen(txt);
  3.   int n = 1, m = 1;
  4.   wyliczRozmiar(dl, n, m);
  5.   char* txtTemp = new char[n * m];
  6.   for (int y = 0; y < n; y++) {
  7.     for (int x = 0; x < m; x++) {
  8.       int pos = y * m + x;
  9.       char c = (pos < dl) ? txt[pos] : ' ';
  10.       if (y % 2 == 0) {
  11.         txtTemp[y * m + x] = c;
  12.       } else {
  13.         txtTemp[(y + 1) * m - (x + 1)] = c;
  14.       }
  15.     }
  16.   }

Na początek (2.) określ długość tekstu i (3. - 4.) znajdź wymiary tabelki tymczasowej. (5.) Zadeklaruj zmienną tymczasową, która będzie zdegenerowaną tabelką. (6.) Dla każdego wiersza oraz (7.) kolumny: (8.) wylicz pozycję znaku w tekście jawnym i (9.) pobierz znak z tekstu o ile istnieje. Jeśli nie to przypisz domyślny znak (tu znak spacji). (10.) W zależności od parzystości wiersza: (11.) zapisz od lewej do prawej lub (13.) od prawej do lewej.

  1.   char* txtc = new char[n * m + 1];
  2.   for (int x = 0, i = 0; x < m; x++) {
  3.     for (int y = 0; y < n; y++) {
  4.       if (x % 2 == 0) {
  5.         txtc[i++] = txtTemp[y * m + x];
  6.       } else {
  7.         txtc[i++] = txtTemp[(n - y - 1) * m + x];
  8.       }
  9.     }
  10.   }
  11.   txtc[n * m] = '\0';
  12.   delete txtTemp;
  13.   return txtc;
  14. }

(17.) Alokuj miejsce pod tekst wynikowy. (18.) Dla każdej kolumny i (19.) każdego wiersza: (20.) wybierz sposób wybierania liter z tabeli: (21.) od góry do dołu czy (23.) od dołu do góry. (27.) Dopisz na koniec znak końca danych. (28.) Usuń tymczasową tablicę i (29.) zwróć tekst wynikowy.

Deszyfrowanie

Funkcja deszyfrująca deszyfruj() nie wnosi żadnych nowych mechanizmów przedstawionych w funkcji szyfruj().

  1. char* deszyfruj(const char* txtc) {
  2.   int dl = strlen(txtc);
  3.   int n = 1, m = 1;
  4.   wyliczRozmiar(dl, n, m);
  5.   char* txtTemp = new char[n * m];
  6.   for (int x = 0, i = 0; x < m; x++) {
  7.     for (int y = 0; y < n; y++) {
  8.       if (x % 2 == 0) {
  9.         txtTemp[y * m + x] = txtc[i++];
  10.       } else {
  11.         txtTemp[(n - y - 1) * m + x] = txtc[i++];
  12.       }
  13.     }
  14.   }

Na początek (2.) określ długość tekstu i (3. - 4.) znajdź wymiary tabelki tymczasowej. (5.) Zadeklaruj zmienną tymczasową. Będzie to tymczasowa tabelka. (6.) Dla każdej kolumny oraz (7.) wiersza: określ parzystość kolumny: (9.) odczyt od góry do dołu lub (11.) od dołu do góry.

  1.   char* txt = new char[n * m + 1];
  2.   for (int y = 0, i = 0; y < n; y++) {
  3.     for (int x = 0; x < m; x++) {
  4.       if (y % 2 == 0) {
  5.         txt[i++] = txtTemp[y * m + x];
  6.       } else {
  7.         txt[i++] = txtTemp[(y + 1) * m - (x + 1)];
  8.       }
  9.     }
  10.   }
  11.   txt[n * m] = '\0';
  12.   delete txtTemp;
  13.   return txt;
  14. }

(15.) Alokuj miejsce pod tekst wynikowy. (16.) Dla każdego wiersza i (17.) każdej kolumny: (18.) wybierz sposób zapisu liter z tabelki: (19.) od lewej do prawej (21.) czy na odwrót. (25.) Dopisz na koniec znak końca danych. (26.) Usuń tymczasową tablicę i (27.) zwróć tekst wynikowy.

Uwagi

Przedstawiony kod można zapisać tak, aby nie tworzył tabelki tymczasowej. Tego typu implementacja jest odpowiedzią na Zadanie 1 zamieszczonego na dole strony.

Testowanie funkcji

Do przetestowania napisanych funkcji służy poniższa funkcja main(), która wczyta od użytkownika tekst, a następnie wyświetli szyfrogram oraz rozszyfrowany szyfrogram.

  1. int main () {
  2.   char* txt = new char[512];
  3.   cout << "Podaj tekst do zaszyfrowania:\n";
  4.   cin.getline(txt, 512);
  5.   char* txtc = szyfruj(txt);
  6.   cout << "\nSzyfrogram to:\n" << txtc;
  7.   char* txtd = deszyfruj(txtc);
  8.   cout << "\nTekst jawny to:\n" << txtd;
  9.   delete txt, txtc, txtd;
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz implementację szyfru Zakręcona Linia tak, aby podczas szyfrowani i deszyfrowania program nie musiał korzystać z dodatkowej tablicy pomocniczej.