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

Szyfr Choinkowy

https://mattomatti.com/a35bq

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.    [_]