Strona główna » Algorytmy » Szyfry » Szyfr Cezara Grupujący
 

Szyfr Cezara Grupujący

https://mattomatti.com/a35av

Metoda szyfrowania

Przed przystąpieniem do czytania tego artykułu warto przeczytać o Szyfrze Cezara.

Szyfr Cezara grupujący potrzebuje dwóch argumentów do szyfrowania. Jeden z nich k odpowiada za przesunięcie każdej grupy o n oraz p, który określa po ile znaków powinny być grupy. Przypuśćmy, że mamy alfabet składający się z 3 liter {a, b, c}. W przypadku p = 1 szyfrowanie zachowuje się jak zwykły szyfr Cezara. Szyfrowanie słowa ab z parametrami k = 1, p = 1 zwróci szyfrogram bc. W przypadku, gdy k = 1, p = 2 przesunięcie następuje po posortowanej alfabetycznie tablicy wszystkich dwuelementowych kombinacji liter użytego alfabetu. Oznacza to, że tablica wartości przesunięć to {aa, ab, ac, ba, bb, bc, ca, cb, cc}. Przykładowo szyfrowany tekst ab z parametrami (k, p) = (1, 2) zwróci ac. Z kolei dla parametrów (k, p) = (4, 2) wynikiem będzie bc.

Może się jednak zdarzyć, że danego słowa nie można podzielić na grupy po g elementów. Przykładowo INFORMACJA podczas podziału p = 3 będzie szyfrować kolejno INF, ORM, ACJ, A. W przypadku, gdy liczebność grupy jest niższa niż wskazany parametr p należy zamiast p użyć wartości liczebności grupy. Innymi słowy w tym przypadku ostatnia grupa z literą A jest szyfrowana zgodnie z Szyfrem Cezara.

W przypadku takiego szyfrowania warto zauważyć, że im większe p tym zakres z którego można wybierać przesunięcie to (0, np), gdzie n to długość alfabetu. (Wykluczone zostały przesunięcia 0 i np kiedy to szyfrogram jest identyczny z tekstem jawnym).

Przykład

Przypuśćmy, że szyfrowany tekst to SZYFROWANIE z parametrami (k, p) = (3, 2), wtedy kolejno będą szyfrowane:

GrupaPrzesunięciaSzyfrogram
SZ..., SZ, TA, TB, TC, ...TC
YF..., YF, YG, YH, YI, ...YI
RO..., RO, RP, RQ, RR, ...RR
WA..., WA, WB, WC, WD, ...WD
NI..., NI, NJ, NK, NL, ...NL
E..., E, F, G, H, ...H

Szyfrogram końcowy to TCYIRRWDNLH. W celu odszyfrowania danych należy postępować odwrotnie do kroków w metodzie szyfrowania.

Implementacja

Założenia

Napisany program będzie szyfrował tekst złożony z dużych liter alfabetu łacińskiego (A - Z) oraz znaków interpunkcyjnych.

Szyfrowanie

Funkcja szyfrująca cipher() przyjmuje trzy argumenty: data - tekst do zaszyfrowania, k - przesunięcie oraz p - po ile litery mają być grupowane. Ze względu na fakt, że funkcja ma nie modyfikować przekazanych danych to na początek należy dane przepisać.

  1. char* cipher(const char* data, int k, int p) {
  2.   int dl = strlen(data) + 1;
  3.   char* dataout = new char[dl];
  4.   for (int i = 0; i < dl; i++)
  5.     dataout[i] = data[i];

Następna część kodu ma za zadanie grupować litery w grupy po p znaków, a potem dokonać przesunięcia grupy. Do samego przesunięcia jest wykorzystywana funkcja change().

  1.   int i = 0;
  2.   int licznik = 0;
  3.   while (data[i] != '\0') {
  4.     while (licznik < p && data[i] >= 'A' && data[i] <= 'Z') {
  5.       licznik++;
  6.       i++;
  7.     }
  8.     if (licznik != 0) {
  9.       change(dataout, i - 1, k, licznik);
  10.       licznik = 0;
  11.     } else {
  12.       i++;
  13.     }
  14.   }
  15.   dataout[dl] = '\0';
  16.   return dataout;
  17. }

(6.) Zainicjalizuj indeks i oraz (7.) licznik. (8.) Dopóki istnieje szansa, aby znaleźć jakąkolwiek grupe: (9. - 12.) znajdź długość następnej grupy. (13.) Może się okazać, że występują obok siebie dwa znaki interpunkcyjne i wtedy licznik będzie wynosić 0. (17.) W takim przypadku (18.) należy przejść do następnego znaku i rozpocząć poszukiwanie grupy do przesunięcia od nowej pozycji. Jednak (14.) jeśli grupa została znaleziona czyli licznik jest większy od 0. Wtedy (15.) dokonaj przesunięcia grupy. Warto tu zauważyć, że parametr licznik odgrywa tutaj rolę parametru p. Oczywiście po zamianie (16.) należy wyzerować licznik. Na koniec (20.) dopisz znak końca danych i (21.) zwróć wskaźnik na odpowiednie miejsce w pamięci.

Przesuwanie grupy

Do przesuwania grupy służy funkcja change(), któa przyjmuje cztery argumenty: data - ciag znaków tekstu do zaszyfrowania, from - indeks ostatniej litery szyfrowanej podgrupy, k - żądane przesunięcie grupy oraz p - określa ile liter znajduje się w szyfrowanej grupie. Funkcja w sposób rekurencyjny szyfruje kolejne znaki.

  1. void change(char* data, int from, int k, int p) {
  2.   if (p > 0) {
  3.     int pos = data[from] - 'A' + k;
  4.     data[from] = (pos % ('Z' - 'A' + 1)) + 'A';
  5.     change(data, from - 1, pos / 26, p - 1);
  6.   }
  7. }

Rozwiązanie rekurencyjne polega na zmniejszaniu długości szyfrowanej grupy o jeden przy każdym kolejnym wywołaniu, więc (2.) warunkiem stopu jest wartość mniejsza lub równa 0 parametru p. Jeśli wywołanie ma do zamiany literę to (3.) wylicza jej wartość z przesunięciem i (4.) zamienia na odpowiedni znak. (5.) Na podstawie pos wyliczana jest (5.) zmiana następnego pola. Ze względu na to, że na początku była podana pozycja pierwszego znaku od prawej w grupie to: parametr from jest zmniejszany o 1, nowy parametr k to ilość pełnych cykli przejścia szyfrowanej litery czyli wyliczona wartość pos podzielona przez 26. Bardzo ważne jest, aby pamiętać o zmniejszeniu parametru p o 1, ponieważ inaczej rekurencja będzie nieskończona.

Deszyfrowanie

Dane można rozszyfrować używając odpowiednio przygotowanego klucza. Pozwala to na zaoszczędzenie wielu linijek kodu i błędu pomyłki. W przypadku szyfru Cezara wystarczyło dopełnić przesunięcie tak, aby przesunięcia k z poprzednim przesunięciem dało w sumie długość alfabetu. W przypadku tego szyfru jest podobnie, ale nie musi to być oczywiste.

W tym przypadku przesunięcie k zawiera informacje o przesunięciu dla każdego znaku w grupie. W celu utworzenia klucza przeciwnego należy odczytać każde z przesunięć dla kolejnych znaków i utworzyć wartość przeciwną tak jak w przypadku oryginalnego szyfrowania Cezara.

  1. char* decipher(const char* data, int k, int p) {
  2.   int suma = 0;
  3.   for (int i = 0; i < p; i++) {
  4.     suma += 26 - (p % 26);
  5.     p /= 26;
  6.   }
  7.   return cipher(data, suma, p);
  8. }

(2.) Przygotuj zmienną pod przeciwne przesunięcie i (3. - 6.) oblicz przeciwne przesunięcie dla każdego znaku w grupie i (8.) zwróć szyfrogram zaszyfrowany kluczem przeciwnym, aby odszyfrować.

Testowanie funkcji

W celu przetestowania napisanych funkcji szyfrujących można skorzystać z poniższej funkcji main(), która najpierw wczytuje dane od użytkownika, a potem pokazuje szyfrogram i rozszyfrowany tekst jawny.

  1. int main () {
  2.   int k, p;
  3.   cout << "Podaj przesuniecie: ";
  4.   cin >> k;
  5.   cout << "Podaj po ile liter grupowac: ";
  6.   cin >> p;
  7.   char* txt = new char[512];
  8.   cin.ignore();
  9.   cout << "Podaj tekst:\n";
  10.   cin.getline(txt, 512);
  11.   char* txtc = cipher(txt, k, p);
  12.   cout << "\nSzyfrogram:\n" << txtc << endl;
  13.   char* txtd = decipher(txt, k, p);
  14.   cout << "\nTekst Jawny:\n" << txtd << endl;
  15.   system("pause");
  16.   return 0;
  17. }

Zadania

Zadanie 1

Dotychczas wersja programu dla tekstu "TAJNA INFORMACJA" z parametrami (k, p) = (1, 3) dzieliła odpowiednia na takie podgrupy: {TAJ, NA, INF, ORM, ACJ, A}.

Napisz program, który podczas dzielenia na grupy będzie ignorował inne znaki niż duże litery alfabetu łacińskiego podczas grupowania, ale nie będzie ich usuwał z wyniku końcowego. Wtedy tekst "TAJNA INFORMACJA" dla p = 3 powinien zostać podzielony na podgrupy {TAJ, NAI, NFO, RMA, CJA}, ale tekstem wynikowym jest "INIORPACMD".