Szyfr Drgający

Algorytm Szyfrowania

W celu zaszyfrowania danych przy pomocy Szyfru Drgającego najlepiej posłużyc się kartką papieru w kratkę. Zapisujemy pierwszy znak z szyfrowanego tekstu, a następnie kratkę do góry i prawo. Jest to nowy szczyt, więc "odbijamy" zwrot zapisu i teraz będziemy zapisywać tak długo, aż zostanie osiągnięty najniższy poziom. Po osiągnięciu doliny ponownie "odbijamy" i tak długo zapisujemy po skosie do góry w prawo, aż osiagniemy nowy poziom maksymalny. Drugi etap polega na odczytaniu każdego wiersza po kolei i zapisaniu znaków koło siebie.

Najprostszym sposobem na odszyfrowanie danych jest zaznaczanie pustych miejsc w której możnaby wpisać szyfrowane litery z tekstu jawnego. Następnie należy wpisać kolejne litery z szyfrogramu do kolejnych wierszy od lewej do prawej. Następnie należy wszystkie litery przenieść na wysokość pierwszej litery - szyfrogram został rozwiązany.

Przykład

Przypuśćmy, że szyfrujemy tekst jawny "TO JEST TAJNY TEKST". Poniżej został przedstawiony schemat zapisanego etapu I. Przyjmijmy, że na poziomie 0 znajduje się pierwsza litera T, a każdy poziom wyżej to kolejno 1, 2, 3, a niższe poziomy od 0 to -1 i -2. Jak można zauważyć szyfrowane są wszystkie znaki - nawet interpunkcyjne.

Teraz w celu odczytania szyfrogramu należy odczytać poziomy od najwyższego do najniższego. Innymi słowy poprawnym szyfrogram jest "ETTKOS ST ETYTJANJ". W przypadku deszyfrowania danych należałoby rozpisać podobny schemat z samym pustymi polami i uzupełniać pola na kolejnych poziomach. Następnie należałoby odczytać w ten sam sposób co zapisuje się podczas szyfrowania.

Implementacja

Ile poziomów?

Najprostszym, choć nie najbardziej optymalnym sposobem, będzie przepisanie każdego kolejnego poziomu przy pomocy pętli. Jednak, aby tego dokonać należy wiedzieć ile jest poziomów i po ile do góry i ile w dół. Jedna z metod polega na tym, aby zasymulować rysowanie i na bieżąco sprawdzać czy osiągnęliśmy szczyt lub doline.

Parę min. poziom × maks. poziom realizuje funkcja podajZakres(), która przyjmuje jedynie długość szyfrowanego tekstu. To w zupełności wystarcza, aby podać zakres poziomów.

1. pair<int, int> podajZakres(int dl) {
2.   pair<int, int> p = make_pair(0, 0);
3.   int y = 0;
4.   bool wgore = true;
5.   for (int i = 0; i < dl; i++) {
6.     y += wgore ? 1 : -1;
7.     if (y == p.second + 1) {
8.       p.second++;
9.       wgore = false;
10.     } else if (y == p.first - 1) {
11.       p.first--;
12.       wgore = true;
13.     }
14.   }
15.   return p;
16. }

Na początku (2.) zakres to [0, 0] co oznacza, że jest tylko poziom 0. Następnie deklarujemy zmienne pomocnicze: y - będzie przchowywać aktualny poziom oraz wgore - będzie przechowywać w którym kierunku przeprowadzamy teraz zapis. (5.) W pętli dla każdego znaku: (6.) obliczamy nową pozycję i (7. - 13.) jeśli zostanie osiągnięty szczyt lub dolina to zmieniany jest odpowiednio zakres i odbijany jest zwrot zapisu.

Szyfrowanie

Podczas szyfrowania danych do określenia pozycji elementów można skorzystać z tego samego schematu co jest w funkcji podajZakres(). Jednak w tym przypadku należy pamiętać, aby po znalezieniu znaku z przepisywanego poziomu to należy go dopisać do wyniku.

1. string szyfruj(string tekst) {
2.   pair<int, int> p = podajZakres(tekst.length());
3.   string wynik = "";
4.   bool wgore = true;
5.   for (int j = p.second; j >= p.first; j--) {
6.     int y = 0, ymin = 0, ymax = 0;
7.     for (int i = 0; i < tekst.length(); i++) {
8.       if(y == j)
9.         wynik += tekst[i];
10.       y += wgore ? 1 : -1;
11.       if (y == ymax + 1) {
12.         ymax++;
13.         wgore = false;
14.       } else if (y == ymin - 1) {
15.         ymin--;
16.         wgore = true;
17.       }
18.     }
19.   }
20.   return wynik;
21. }

(2.) Najpierw oblicz zakres poziomów oraz (3.) przygotuj zmienną do zapisu wyniku oraz (4.) określ początkowy kierunek zapisu. (5.) W pętli dla każdego poziomu: (7.) wykonaj przechodzenie po kolejnych poziomach uprzednio (6.) restując zmienne. Nie można tu pominąć deklarowania ymin oraz ymax, ponieważ trzeba na bieżąco wyszukiwać kolejnych szczytów i dolin. Podczas sprawdzania kolejnyc znaków: (8.) należy sprawdzić czy aktualny poziom jest taki sam jak ten co przepisywany i jeśli tak to (9.) wystarczy dopisać odpowiedni znak do wyniku. (20.) Ostatecznie zwracany jest wynik.

Odszyfrowanie danych

Podczas deszyfrowania danych można przeprowadzić na podstawie schematu algorytmu użytego podczas szyfrowania. Jednak tym razem zamiast dopisywać dane na koniec wyniku to należy je umieszczać na pozycji, którą aktualnie wskazuje pozycja.

1. string odszyfruj(string tekst) {
2.   pair<int, int> p = podajZakres(tekst.length());
3.   string wynik(tekst.length(), ' ');
4.   bool wgore = true;
5.   int odczyt = 0;
6.   for (int j = p.second; j >= p.first; j--) {
7.     int y = 0, ymin = 0, ymax = 0;
8.     for (int i = 0; i < tekst.length(); i++) {
9.       if (y == j)
10.         wynik[i] = tekst[odczyt++];
11.       y += wgore ? 1 : -1;
12.       if (y == ymax + 1) {
13.         ymax++;
14.         wgore = false;
15.       } else if (y == ymin - 1) {
16.         ymin--;
17.         wgore = true;
18.       }
19.     }
20.   }
21.   return wynik;
22. }

Testowanie funkcji

W celu przetestowania funkcji szyfrującej można skorzystać z poniższego fragmentu kodu. Program zapyta użytkownika o wprowadzenie tekstu, a następnie zostanie wyświetlony szyfrogram oraz odszyfrowany tekst jawny z szyfrogramu.

1. int main () {
2.   string tekst;
3.   cout << "Podaj tekst do zaszyfrowania:\n";
4.   getline(cin, tekst);
5.   string szyfrogram = szyfruj(tekst);
6.   string tekstjawny = odszyfruj(szyfrogram);
7.   cout << "Szyfrogram to:\n" << szyfrogram << endl;
8.   cout << "Tekst jawny to:\n" << tekstjawny << endl;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja