Strona główna » Algorytmy » Szyfry » Szyfr Choinkowy
 

Szyfr Choinkowy

Szyfr

Szyfr choinkowy to szyfr transpozycyjny, którego główną ideą jest wypisanie liter tekstu jawnego tak, aby wyglądem struktura przypominała choinkę. Znaki początkowo należy wpisać do kolejnych wierszy, a szyfrogram powstaje poprzez odczytanie kolejnych kolumn.

Szablon choinki do wypełniania tworzy się następująco: pierwsza linijka ma zawsze jeden element. Pierwszy segment choinki składa się z wiersza o jednym znaku, a drugi mieści 3 znaki. Każdy następny segment ma dodawany jeden wiersz, który jest o dwa dłuższy nić poprzedni. Kolejne segmenty są tak długo dodawane, dopóki nie ma odpowiednio dużo miejsc na wszystkie znaki tekstu jawnego.

W celu zaszyfrowania danych szablonu tekst wpisuje się do kolejnych wierszy. Jeśli w tekście jawnym zabraknie liter to należy wstawić znaki z początku tekstu (tj. wybieramy je cyklicznie). Następnie szfrogram odczytuje się czytając od góry do dołu kolejne kolumny. W celu odszyfrowania danych szablon uzupełnia się kolejnymi kolumnami, a tekst jawny odszyfrowuje się czytając kolejne wiersza.

Przykład

Zaszyfrujmy przykładowo tekst "TAJNAINFORMACJAZASZYFROWANA". W tym celu tworzymy odpowiedni szabloni wypełnia się go odpowiednio literami. Szablon będzie składał się z 3 segmentów, ponieważ tekst ma długość 29, a segmenty mają kolejno pojemności 4, 9 i 16 czyli łącznie 29 pozycji i dwie pozostają wolne. Brakujące litery zostały oznaczone kursywą. Oto wypełniony szablon

   T   
  AJN  
   A   
  INF  
 ORMAC 
   J   
  AZA  
 SZYFR 
OWANATA
   [_]   

Powstały szyfrogram należy odczytać czytając kolumny od góry do dołu. Wynikiem jest: "OOSWAIRAZATJANMJZYNNFAAFACRXX".

Implementacja

Strategia

Ustalmy, że kolumna, która jest osią symetrii choinki ma numer 0. Kolumne na lewo mają coraz to mniejsze wartości, a kolumny na prawo coraz większe. W celu oszczędzenia pamięci w programie zostaną utworzone dwie tablice pomocnicze. Tekst zostanie podzielny na grupy i jedna z tablic będzie przechowywać indeksy pierwszych elementów dla każdej z grup. Z kolei druga tablica będzie przechowywać ile elementów leży na prawo (lub lewo) od środkowej kolumny. Tu warto zauważyć, że każdy wiersz zawsze składa się z co najmniej jednego znaku.

Szyfrowanie

W celu zaszyfrowania danych najpierw zostaną wyliczone parametry "choinki", a dopiero na ich podstawie zostanie utworzony szyfrogram.

C++
C#
  1. string szyfruj(string tekst) {
  2.   int ile = 1, poz = 1, wierszy = 0;
  3.   while (ile < tekst.length()) {
  4.     ile = 2*ile + poz * 2 + 1;
  5.     poz++;
  6.     wierszy += poz;
  7.   }
  8.   int* wsk = new int[wierszy];
  9.   int* maxbok = new int[wierszy];
  10.   int max = 1, bok = 1;
  11.   wsk[0] = 0;
  12.   maxbok[0] = 0;
  13.   for (int i = 1; i < wierszy; i++) {
  14.     wsk[i] = wsk[i - 1] + maxbok[i - 1]*2 + 1;
  15.     maxbok[i] = bok;
  16.     bok++;
  17.     if (bok > max) {
  18.       max++;
  19.       bok = 0;
  20.     }
  21.   }
  22.   max = 1; bok = 0;
  23.   string w = "";
  24.   for (int i = -poz + 1; i <= poz - 1; i++)
  25.     for (int j = 0; j < wierszy; j++)
  26.       if (abs(i) <= maxbok[j])
  27.         w += tekst[wsk[j]++ % tekst.length()];
  28.   return w;
  29. }

Na początek (2.) należy zadeklarować zmienne: ile - ile zostało przygotowanych pozycji pod znaki tekstu jawnego, poz - ile jest segmentów w aktualnym schemacie oraz wierszy - ile wierszy ma łącznie schemat. Potem (3. - 7.) dokładane są kolejne segmenty tak długo, aż bedzie wystarczająco dużo wolnych pól. W drugiej części kodu deklarujemy tablice pomocnicze (8.) wsk - wskaźniki na pierwsze elementy grup oraz (9.) maxbok - ile elementów jest na prawo (lub lewo) w wierszu od środkowego. Kolejny etap polega na (10. - 21.) wypełnieniu tych tablic. Na koniec (22. - 26.) wystarczy wybierać kolejne elementy z odpowiedniej grupy pod warunkiem, że w danym wierszu jest coś w i-tej kolumnie. (27.) Funkcja zwraca szyfrogram zapisany w zmiennej w.

Odszyfrowanie

Funkcja odszyfruj() początkowo wykonuje te same instrukcje co funkcja szyfruj(). Różnica tkwi jednak w sposobie wyboru elementów z zadanego tekstu. Tym razem wybieramy kolejne elementy i wstawiamy tam gdzie wskazuje aktualnie indeks grupy. Oto fragment funkcji, który został zmieniony:

C++
C#
  1. string odszyfruj(string tekst) {
C++
C#
  1.   int el = 0; max = 1; bok = 0;
  2.   char* w = new char[tekst.length() + 1];
  3.   w[tekst.length()] = '\0';
  4.   for (int i = -poz + 1; i <= poz - 1; i++)
  5.     for (int j = 0; j < wierszy; j++)
  6.       if (abs(i) <= maxbok[j])
  7.         w[wsk[j]++] = tekst[el++];
  8.   return w;
  9. }

(23.) Deklaracja tablicy wynikowej w której (24.) należy pamiętać o znaku końcowym. Potem (28.) wybierany znak jest wstawiany tam gdzie wskazuje indeks j-tej grupy.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika tekst jawny, a następnie wypisuje utworzony na jego podstawie szyfrogram oraz rozszyfrowywuje z powrotem do tekstu jawnego.

C++
C#
  1. int main() {
  2.   cout << "Wpisz tekst do zaszyfrowania:\n";
  3.   string txt;
  4.   getline(cin, txt);
  5.   cout << "\nZaszyfrowany tekst:\n";
  6.   string txtk = szyfruj(txt);
  7.   cout << txtk << endl;
  8.   cout << "\nRozszyfrowany tekst:\n";
  9.   string txtr = odszyfruj(txtk);
  10.   cout << txtr << endl;
  11.   system("pause");
  12.   return 0;
  13. }

Zadania

Zadanie 1

Napisz funkcję wypisz(), która wypisze schemat używany podczas szyfrowania, które mógłby zostać użyty do szyfrowania. Zakładamy, że danymi wejściowymi jest tekst jawny. Dodatkowo schemat powinien na górze posiadać gwiazdkę "*", a na dole donicznkę "[_]". Z kolei każdy wiersz przed ciągiem znaków powinien posiadać "/", a na końcu "\". Wolne pola powinny zostać zaznaczone przy pomocy znaku kropki ".".

Przykładowo po wpisaniu "TEST FUNKCJI":

  1.     *
  2.    /T\
  3.   /EST\
  4.    / \
  5.   /FUN\
  6.  /KCJI.\
  7.    [_]