Strona główna » Algorytmy » Szyfry » Szyfr Koła Zębate
 

Szyfr Koła Zębate

https://mattomatti.com/a35ae

Wstęp

Szyfr Koła Zębate opiera się na zasadzie działania kół zębatych. W ten sam klucz według, którego są szyfrowane daje jest ruchomy w trakcie zabezpieczania danych. W większości przypadków utrudnia to szanse na rozszyfrowanie danych, ponieważ ta sama litera może zostać zaszyfrowana na wiele różnych sposobów.

Algorytm

Klucz

Klucz w przypadku tego szyfru to n kół zębatych, połączonych ze sobą i mające na końcach zębów zapisane litery. Innymi słowy podczas budowania klucza należy ustalić liczbę n kół zębatych. Następny krok polega na określeniu ile zębów ma każde z kół. Bardzo ważne jest, aby łączna liczba zębów na wszystkich kołach była nie mniejsza niż długość alfabetu użytego do szyfrowania danych. Po rozrysowaniu lub zapisaniu w inny sposób tych danych trzeba określić na którym zębie znajduje się każda litera alfabetu. Należy pamiętać, że na jednym zębie może znaleźć się tylko jedna litera i nie wolno zapisać w kluczu tej samej litery dwa razy. Wszystkie litery muszą zostać wykorzystane, ale istnieje możliwość, aby pozostały wolne pola w kluczu w przypadku, gdy alfabet jest krótszy od ilości zębów. Pozostawienie nieopisanych zębów pozwala w łatwy sposób zwiększyć moc szyfrowania klucza. Z tak przygotowanym kluczem można przejść do (de)szyfrowania danych.

Przypuśćmy przykładowo, że klucz składa się z n = 4 kół zębatych. Użytym alfabetem będzie alfabet łaciński składający się z 26 liter. Pierwsze koło będzie miało 6 zębów i zawierało litery {D, Y, Q, X, R, M}, które w tej kolejności zgodnie z ruchem wskazówek zegara i począwszy od godziny 12 zostaną wpisaną. Dla kolejnych kół ilość zębów i listy liter to: [2] 7 zębów, {J, S, A, K, N, E, W}, [3] 7 zębów, {L, B, I, G, O, V, C} oraz ostatnie [4] 6 zębów, {F, P, H, T, U, Z}. W sumie wszystkie koła zębate mają 26 wolnych pozycji. Wtedy przykładowy klucz wygląda tak:

Rysunek pomocniczy

Szyfrowanie

Szyfrowanie polega na zamianie litery na parę liczb. Każda para liczb składa się z numeru koła na której znajduje się litera oraz jego odległości (licząc zęby) od zęba znajdującego się najbliżej godziny 12. Liczenie odbywa się zgodnie z ruchem wskazówek zegara. Po pobraniu pozycji liter koło zębate jest obracane w prawo tak, aby na godzinie 12 znalazło się nowe koło zębate. Dla uproszczenia przyjmuje się, że obrócenie i tego koła o 1 w prawo powoduje obrót o 1 w prawo wszystkie koła o tej samej parzystości indeksu, a o przeciwnej parzystości obraca się w lewo o 1. Takie uproszczenie jest zgodne z zasadą działania kół zębatych. Jeśli napotka się znak, który nie znajduje się w użytym alfabecie to można go przepisać, albo pominąć.

Przypuśćmy, że szyfrujemy tekst TAJNA INFORMACJA zgodnie z kluczem przedstawionym w poprzednim paragrafie. Pierwsza litera to T. Znajduje się ona na czwartym kole i znajduje się w odległości 3 od zęba na godzinie 12, dlatego literze T odpowiada para liczb 4 3, którą dlatego przykładu można zapisać jako 43, ponieważ wszystkie liczby w parach będą cyframi. Spowoduje to przesunięcie drugiego i czwartego koła o 1 żab w prawo oraz pierwszego i trzeciego o 1 w lewo. Teraz kolejność liter począwszy od godziny 12 dla każdego koła to:

KołoLitery
1{Y, Q, X, R, M, D}
2{W, J, S, A, K, N, E}
3{B, I, G, O, V, C, L}
4{Z, F, P, H, T, U}

Tabelka ma na celu uproszczenie danych, aby nie trzeba było rozrysowywać schematu jeszcze raz. Następną literą jest A. Literze tej odpowiada para liczb 2 i 3 tj. 23. Można zauważyć, że jeśli zamiast litery A była litera T to tym razem byłaby zaszyfrowana jako 44. Kontynuując szyfrowanie otrzyma się szyfrogram 432322.

Rozszyfrowanie

Podczas rozszyfrowania należy pobierać każdą parę liczb i pobierać znak z odpowiedniego koła zębatego i zęba. Należy pamiętać, aby po każdym pobraniu jak podczas szyfrowania, przekręcić koło z którego pobrało się literę.

Implementacja

Ze względu na fakt, że przyjmujemy uproszczenie działania kół zębatych program będzie przechowywał litery kolejnych kół na n listach. Po każdym przekręceniu tworzenie nowej listy jest zbyteczne, ponieważ wystarczy pamiętać indeks litery, która aktualnie jest na godzinie 12. Przyjmujemy, że na początku wprowadzania danych będzie liczba n określające ile kół zębatych będzie zawierał klucz. Potem w n kolejnych linijkach będą zapisane kolejne litery alfabetu bez przerw.

Wczytywanie klucza

Jedna z pierwszych funkcji, która okaże się pomocna w implementacji to czytajKlucz(). Pozwoli ona na wczytanie klucza od użytkownika. W celu pełnej manipulacji kluczem potrzebna będzie funkcja kopiujKlucz(), która skopiuje klucz oraz usunKlucz(), która prawidłowo zdealokuje pamięć do której zapisany był wcześniej klucz.

  1. char** czytajKlucz(int n) {
  2.   char** klucz = new char*[n];
  3.   char* buffer = new char[256];
  4.   cin.ignore();
  5.   for(int i = 0; i < n; i++){
  6.     cin.getline(buffer, 256);
  7.     klucz[i] = new char[strlen(buffer) + 1];
  8.     for(int j = 0; buffer[j - 1]; j++)
  9.       klucz[i][j] = buffer[j];
  10.   }
  11.   delete[] buffer;
  12.   return klucz;
  13. }

(1.) Klucz będzie przechowywany w typie char**. W celu prawidłowego utworzenia klucza potrzebna jest jego długość n. (2.) Alokacja pamięci pod główną listę list. (3.) ALokacja bufora danych i (4.) zignorowanie innych danych. (5.) Dla każdej kolejnej listy danych: (6.) wczytaj i-tą listę, (7.) utwórz klucz i (8. - 9.) przepisz wczytaną listę do klucza. (11.) Usuń bufor danych i (12.) zwróć klucz.

Kolejna funkcja kopiujKlucz() ma bardzo podobną strukturę do funkcji wczytajKlucz(), ale różni się źródłem pobieranych danych:

  1. char** kopiujKlucz(char** klucz, int n) {
  2.   char** klucz_kopia = new char*[n];
  3.   for(int i = 0; i < n; i++){
  4.     klucz_kopia[i] = new char[strlen(klucz[i]) + 1];
  5.     for(int j = 0; klucz[i][j - 1]; j++)
  6.       klucz_kopia[i][j] = klucz[i][j];
  7.   }
  8.   return klucz_kopia;
  9. }

Z kolei do usunięcia danych potrzebna jest dodatkowa funkcja usunKlucz(), która prawidłowo zwolni pamięć zaalokowaną pod klucz:

  1. void usunKlucz(char** klucz, int n) {
  2.   for(int i = 0; i < n; i++)
  3.     delete[] klucz[i];
  4.   delete[] klucz;
  5. }

Szyfrowanie danych

Szyfrowanie danych można podzielić na kilka etapów: przygotowanie klucza oraz indeksów do klucza, zamiana kolejnych liter na pary liczb oraz wykonywanie obrotów kółek, a następnie zwrócenie wyniku.

  1. char* szyfruj(char* txt, char** klucz, int n) {
  2.   char** klucz_kopia = kopiujKlucz(klucz, n);
  3.   int* indeksy = new int[n];
  4.   for(int i = 0; i < n; i++)
  5.     indeksy[i] = 0;
  6.   char* wynik = new char[2*strlen(txt) + 1];
  7.   wynik[2*strlen(txt)] ='\0';
  8.   int* pozycja = new int[2];
  9.   for(int i = 0; txt[i]; i++){
  10.     if(znajdzWKluczu(pozycja, txt[i], indeksy, klucz_kopia, n)) {
  11.       wynik[2*i] = pozycja[0] + '0';
  12.       wynik[2*i + 1] = pozycja[1] + '0';
  13.       obrocKolko(indeksy, pozycja[0], klucz_kopia, n);
  14.     } else {
  15.       wynik[2*i] = '0';
  16.       wynik[2*i + 1] = ' ';
  17.     }
  18.   }
  19.   usunKlucz(klucz_kopia, n);
  20.   delete[] indeksy;
  21.   return wynik;
  22. }

(1.) Funkcja szyfruj przyjmuje: txt - ciąg znaków do zaszyfrowania, klucz - klucz według, którego będą szyfrowane dane oraz n - ile kół zębatych ma klucz. (2.) Klucz będzie się zmieniał, dlatego wykonana zostaje kopia klucza. (3.) Przygotowanie indeksów, która litera z każdego koła jest aktualnie na godzinie 12 i (4. - 5.) wyzerowanie indeksów. (6.) Alokacja pamięci pod tekst wynikowy, (7.) Dopisanie znaku końca danych. (8.) Ze względu na fakt, że nie można zwrócić natywnie pary liczb to funkcja zwracająca wynik będzie go zapisywać w zmiennej pozycja. (9.) Dla każdego znaku w tekście do zaszyfrowania: (10.) jeśli znak istnieje to na podstawie wyliczonej pozycji (11. - 12.) dopisz kolejne znaki tekstu wynikowego i (13.) obróć koła. (14.) Jednak jeśli znaku nie ma w alfabecie to (15. - 16.) zapisz go w postaci 0x, gdzie x to znak nie występujący w alfabecie. Na koniec (19.) usuń kopię klucza, (20.) indeksy i (21.) zwróć wynik.

Deszyfrowanie danych

Deszyfrowanie jest mniej skomplikowane, ponieważ nie trzeba niczego szukać w kluczu, a wystarczy pobierać odpowiednie wartości z klucza co znacznie upraszcza kod:

  1. char* deszyfruj(char* txt, char** klucz, int n) {
  2.   char** klucz_kopia = kopiujKlucz(klucz, n);
  3.   int* indeksy = new int[n];
  4.   for(int i = 0; i < n; i++)
  5.     indeksy[i] = 0;
  6.   char* wynik = new char[strlen(txt)/2 + 1];
  7.   wynik[strlen(txt)/2] ='\0';
  8.   for(int i = 0; txt[i]; i+=2){
  9.     if(txt[i] - '0' == 0){
  10.       wynik[i/2] = txt[i + 1];
  11.     } else {
  12.       wynik[i/2] = klucz[txt[i] - '1'][(indeksy[txt[i] - '1'] + int(txt[i + 1] - '0') + strlen(klucz[txt[i] - '1'])) % strlen(klucz[txt[i] - '1'])];
  13.       obrocKolko(indeksy, txt[i] - '0', klucz_kopia, n);
  14.     }
  15.   }
  16.   usunKlucz(klucz_kopia, n);
  17.   delete[] indeksy;
  18.   return wynik;
  19. }

(1.) Funkcja rozszyfrowująca przyjmuje takie same argumenty jak funkcja szyfrująca. (2.) Wykonanie kopii klucza i (3. - 5.) utworzenie klucza. (6.) Alokacja pamięci pod szyfrogram i (7.) dodanie na końcu znak końca danych. (8.) Dla każdej pary znaków: (9.) jeśli znak nie występuje w alfabecie to (10.) dopisz do wyniku drugi znak z pary. (11.) Jednak jeśli para znaków to para liczb oznaczająca literę a klucza to (12.) pobierz odpowiednią wartość i (13.) wykonaj obrót.

Obrót kółek i szukanie znaku w kluczu

Obrót kółka polega na odpowiednim (3.) ustawieniu nowego indeksu litery na godzinie 12. W przypadku obrotu w prawo indeks zmniejsza się o -1, a jeśli w lewo to o 1.

  1. void obrocKolko (int* indeksy, int i, char** klucz, int n) {
  2.   for(int j = 0; j < n; j++)
  3.     indeksy[j] = ((indeksy[j] + (j % 2 == i % 2) ? -1 : 1) + strlen(klucz[j])) % strlen(klucz[j]);
  4. }

Niewyjaśniona pozostała jeszcze funkcja znajdzWKLuczu(), której zadanie polega na znalezienie znaku w kluczu:

  1. bool znajdzWKluczu(int* pozycja, char znajdz, int* indeksy, char** klucz, int n) {
  2.   for(int i = 0; i < n; i++){
  3.     for(int j = 0; j < strlen(klucz[i]); j++){
  4.       if(klucz[i][(j + indeksy[i]) % strlen(klucz[i])] == znajdz){
  5.         pozycja[0] = i + 1;
  6.         pozycja[1] = j;
  7.         return true;
  8.       }
  9.     }
  10.   }
  11.   pozycja[0] = pozycja[1] = -1;
  12.   return false;
  13. }

(1.) Do znalezienia znaku w kluczu potrzebne są argumenty: pozycja - gdzie znaleziona pozycja ma zostać zapisana, znajdz - czego funkcja ma szukać w kluczu, indeksy - aktualne obroty każdego z kółek, klucz - klucz szyfrowania oraz n - ile ma klucz kół zębatych. (2.) Dla każdego koła i (3.) każdej kolejnej litery od godziny 12: (4.) jeśli zostanie znaleziona żądana wartość to (5. - 6.) przepisz pozycje i (7.) zwróć prawdę. Jeśli znak nie występuje w alfabecie to (11. - 12.) usuń aktualne pozycje i (13.) zwróć fałsz.

Testowanie funkcji

Poniższy program wczytuje dane zgodnie z podaną wcześniej specyfikacją i wypisuje na ekran zaszyfrowany, a potem rozszyfrowany tekst:

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   char** klucz = czytajKlucz(n);
  5.   char* txt = new char[256];
  6.   cin.getline(txt, 256);
  7.   char* txtc = szyfruj(txt, klucz, n);
  8.   cout << txtc << endl;
  9.   char* txtd = deszyfruj(txtc, klucz, n);
  10.   cout << txtd << endl;
  11.   usunKlucz(klucz, n);
  12.   delete[] txt, txtc, txtd;
  13.   system("pause");
  14.   return 0;
  15. }

Przykładowe prawidłowe dane to:

  1. 4
  2. DYQXRM
  3. JSAKNEW
  4. LBIGOVC
  5. FPHTUZ
  6. TEST