Strona główna » Algorytmy » Szyfry » Szyfr Ślimak
 

Szyfr Ślimak

https://mattomatti.com/a35w

Wstęp

Szyfr Ślimak to sprytny sposób na ukrycie tajnej informacji. Jednak ze względu na fakt, że tylko przestawia litery i są fragmenty ustawione jak w tekście szyfrowanym powoduje, ze szyfr ten bardzo łatwo złamać. Inspiracją do stworzenia tego szyfru był niewątpliwie ślimak, a konkretniej linie na jego skorupie. Tekst, który szyfrujemy zapisujemy w podstawie kwadratowej tabelki. Następnie szyfrogram odczytujemy odczytując kolejne pełne wiersze z powstałej tabelki.

Algorytm

Szyfrowanie

Dane w tabelce zapisuje się w specjalny sposób. Przede wszystkim na początku należy ustalić rozmiar tabelki - tabelka musi być kwadratowa oraz długość boku musi być liczbą nieparzystą. Tylko wtedy powstanie nam skorupa ślimaka. Innymi słowy należy wybrać taką najmniejszą liczbę n postaci 2k + 1, której kwadrat jest dłuższy od długości tekstu szyfrowanego. Literki do tabeli należy zacząć wpisywać od pozycji o obu współrzędnych (n + 1)/2. W tym przypadku przyjmujemy, że komórka tabelki w lewym górnym rogu ma pozycję (1, 1). Kolejne znaki dopisujemy dookoła już napisanych. Poniżej przedstawiono przykład szyfrowania tekstu TEKST DO ZASZYFROWANIA:

Przykładowa tabelka

Bardzo ważne, aby od pierwszego znaku wyjść w lewo, a następnie "skręcać" tylko w prawo tak jak pokazano na przykładzie. Tylko w ten sposób można uzyskać coś na kształt muszli. W tym przypadku tekst szyfrowany ma długość 22 znaków, a dostępnych komórek jest 25, dlatego na koniec zostały dopisane trzy losowe znaki. W przykładowej tabelce zostały oznaczone ciemnożółtym kolorem. Następnym krokiem jest odczytanie wszystkich danych wiersz po wierszu co pozwoli odczytać ostateczny szyfrogram: ZYFROSKSTWAET AZ ODNZYXAI.

Deszyfrowanie

W przypadku deszyfrowania n można wyznaczyć obliczając pierwiastek z długości szyfrogramu. Później wystarczy podzielić zaszyfrowany tekst na n grup i zapisać je w formie tabelki. Kolejny krok polega na odczytaniu znaków w taki sam sposób w jaki zapisywało się je do tabelki.

Implementacja

Strategia

Szyfrowanie i deszyfrowanie opiera się na właściwym przechodzeniu po tabelce, dlatego potrzebna jest strategia wyliczania kolejnych pozycji. Najprostszym rozwiązaniem jest zadeklarowanie zmiennych x i y, które będą przechowywać pozycję na której zapisujemy znak oraz przesx i przesy - o ile następuje przesunięcie w danym kroku. Do tego potrzebujemy wiedzieć kiedy skręcić w lewo. Można to uzyskać ograniczając obszar przesuwania poprzez dodatkowe zmienne left, right, top i bottom. Po każdym skręcie będzie trzeba jedynie przesunąć ściankę na którą lecimy o jeden. Ze względu na fakt używania tej funkcji w obu funkcjach (szyfrujących i deszyfrujących) funkcjonalność ta zostanie wyciągnięta do funkcji move() tak jak poniżej:

  1. void move(int &x, int &y, int &przesx, int &przesy, int &left, int &right, int &top, int &bottom){
  2.   if(x == left && przesx == -1){
  3.     top--;
  4.     przesx = 0;
  5.     przesy = -1;
  6.   } else if(y == top && przesy == -1){
  7.     right++;
  8.     przesx = 1;
  9.     przesy = 0;
  10.   } else if(x == right && przesx == 1){
  11.     bottom++;
  12.     przesx = 0;
  13.     przesy = 1;
  14.   } else if(y == bottom && przesy == 1){
  15.     left--;
  16.     przesx = -1;
  17.     przesy = 0;
  18.   }
  19.   x += przesx;
  20.   y += przesy;
  21. }

(1.) Zmienne będą przekazywane podczas referencję, aby zmiany były widoczne na zewnątrz funkcji. (2. - 18.) W zależności od aktualnego przesunięcia i o ile dotknęliśmy odpowiedniej ściany obszaru zwiększamy kolejny obszar i ustawiamy nowe przesunięcie. (19. - 20.) Na koniec zmieniamy pozycję (x, y) o wektor [przesx, przesy].

Szyfrowanie

Podczas szyfrowania danych na początek należy określić rozmiar tabelki. Potem trzeba wykonać symulację chodzenia po tabelce. Ze względów wydajnościowych nie będzie tworzona tabelka pośrednia. Dane będą zapisywane do ostatecznej tabeli wynikowej. Szyfrowanie realizuje poniższy kod:

  1. char* cipher(char* data){
  2.   int n = sqrt(strlen(data));
  3.   if(n % 2 == 0){n++;}
  4.   if(n*n < strlen(data)){n+=2;}
  5.   char* wynik = new char[n*n + 1];
  6.   wynik[n*n] = '\0';
  7.   int x = (n - 1) / 2, y = x;
  8.   int left = x, right = x, top = x, bottom = x;
  9.   int przesx = 0, przesy = 1;
  10.   for(int i = 0; i < n*n; i++){
  11.     wynik[y*n + x] = (i < strlen(data)) ? data[i] : rand() % ('Z' - 'A' + 1) + 'A';
  12.     move(x, y, przesx, przesy, left, right, top , bottom);
  13.   }
  14.   return wynik;
  15. }

Na początku trzeba wyliczyć szerokość i wysokość tabelki n: (2.) wyciągamy pierwiastek z długości podanego szyfrogramu (data). (3.) Jeśli n wyszło parzyste to zwiększamy jego dugość o 1 (nie zmniejszamy, bo wtedy wyjdzie za mało komórek, aby zapisać tekst). (4.) Należy się jeszcze jednak upewnić, że zmieszczą się wszystkie litery jako, że odrzucamy część ułamkową wyliczonego pierwiastka. Jeśli będzie za mało miejsc to zwiększamy n o 2 - w ten sposób zostaje zachowana nieparzystość n. (5.) Następnie alokujemy pamięć pod tekst wynikowy i (6.) dopisujemy na końcu znak \0. (7.) Ustalamy pozycję początkową od której będziemy zapisywać dane. W celu ułatwienia obliczeń tabelka w tym przypadku zaczyna się od pozycji (0, 0), a kończy na (n - 1, n - 1). (8.) Odpowiednim zmiennym przypisujemy też obszar, który zapisujemy oraz (9.) aktualne przesunięcie. Symulujemy tutaj, że zapisujemy pierwszą literę zapisaliśmy przychodząc z góry i, że skończył się obszar. Spowoduje to, że skręcimy w prawo i następną literę zapiszemy faktycznie pole obok.

Teraz pozostaje (10.) dla każdego pola w tabelce: (11.) zapisać znak (dopóki możemy to pobieramy z data). W przeciwnym wypadku losujemy znak pomiędzy A, a Z. (12.) Symulujemy przejście do następnego znaku. Na koniec (14) zwracamy gotowy szyfrogram.

Deszyfrowanie

Proces deszyfrowanie różni się sposobem wyliczania n i zamiast zapisywać odczytuje odpowiednie pozycje w szyfrogramie.

  1. char* decipher(char* data){
  2.   int n = sqrt(strlen(data));
  3.   char* wynik = new char[n*n + 1];
  4.   wynik[n*n] = '\0';
  5.   int x = (n - 1) / 2, y = x;
  6.   int left = x, right = x, top = x, bottom = x;
  7.   int przesx = 0, przesy = 1;
  8.   for(int i = 0; i < n*n; i++){
  9.     wynik[i] = data[y*n + x];
  10.     move(x, y, przesx, przesy, left, right, top , bottom);
  11.   }
  12.   return wynik;
  13. }

W procesie szyfrowania (2.) wyliczenie n jest znacznie prostsze. Wystarczy tylko wyciągnąć pierwiastek z długości szyfrogramu. Poza tym kod bez większych zmian.

Testowanie funkcji

Ważną kwestią jest (2.) zainicjalizowanie funkcji losującej o ile chcemy, aby dodatkowe znaki podczas szyfrowania mogły być wylosowane przy użyciu funkcji rand().

  1. int main () {
  2.   srand(time(0));
  3.   char* txt = new char[128];
  4.   cin.getline(txt, 128);
  5.   char* txtc = cipher(txt);
  6.   cout << txtc << endl;
  7.   char* txtd = decipher(txtc);
  8.   cout << txtd << endl;
  9.   delete[] txt, txtc, txtd;
  10.   system("pause");
  11.   return 0;
  12. }

Zadania

Zadanie 1

Napisz funkcję generateTable(), która wypisze na ekran tabelkę z której można odczytać szyfrogram. Przykładowo dla podanego słowa TO SUPER TAJNA INFORMACJA wypisze:

  1. NA IN
  2. J SUF
  3. AOTPO
  4. T RER
  5. AJCAM

Zadanie 2

Zmień funkcję generateTable() tak, aby dodatkowa rysowała linie przejścia pomiędzy kolejnymi literami. Przykładowo dla podanego słowa TO SUPER TAJNA INFORMACJA wypisze:

  1. N-A- -I-N
  2. |       |
  3. J  -S-U F
  4. | |   | |
  5. A O-T P O
  6. |     | |
  7. T- -R-E R
  8.         |
  9. A-J-C-A-M