Szyfr Nieregularna transpozycja

Szyfr

Szyfrowanie

Szyfr Nieregularna transpozycja to szyfr, który wymaga do zaszyfrowania unikalnego klucza złożonego z samych cyfr. Na podstawie klucza tworzona jest tabelka. W i-tej kolumnie znajduje się 2n + 1 wolnych, ustawionych pionowo pól, gdzie n to wartość i-tej cyfry. Wszystkie kolumny są wyśrodkowane w pionie tak, że środkowe pola każdej kolumny są w jednej linii. Kolejne znaki szyfrowanego tekstu należy wpisywać do kolejnych kolumn od góry do dołu. Następnie w celu odczytania zaszyfrowanego tekstu należy przepisać znaki poziomo z kolejnych wierszy tabelki.

Po utworzeniu tabelki na podstawie klucza może okazać, że jest za mało wolnych pól, aby zmieścić wszystkie znaki szyfrowanego tekstu. Wtedy jedną z opcji jest zmiana klucza, ale z reguły wystarczy dorysować taką samą tabelkę ile tylko trzeba, dlatego należy pamiętać, że klucz 01 jest taki sam jak klucz 0101. Należy też pamiętać, że szyfrowanie kluczem 0 jest całkowicie bezcelowe, ponieważ wtedy szyfrogram jest tekstem jawnym. Należy też pamiętać, że klucz oraz transpozycja wpływają tylko na ukrycie informacja i może zostać do zwiększenia skuteczności szyfrowanie, ale nie powinna być używana samodzielnie.

Deszyfrowanie

Deszyfrowanie polega na ponownym utworzeniu tabelki na podstawie klucza, a następnie wypełnieniu tabelki kolejnymi znakami szyfrogramu wiersz po wierszu od lewej do prawej. Tekst jawny można odczytać przepisując litery z kolejnych kolumn od góry do dołu.

Przykład szyfrowania

Do zaszyfrowania jest tekst TAJNA INFORMACJA przy pomocy klucza 011. Wtedy tabelka utworzona na podstawie klucza do wypełnienia wygląda następująco:

Łatwo jednak zauważyć, że tabelka mieści maksymalnie 7 znaków, dlatego zostanie użyty klucz 01101101, aby pomieścić wszystkie znaki. Kolejne znaki tekstu są wpisywane do kolejnych kolumn od góry do dołu:

Ze względu na fakt, że zostały wolne pola to powinny zostać wypełnione dowolnym znakiem. Przykładowo znakiem przerwy. Inaczej deszyfrowanie zostanie zaburzone, ponieważ każdy znak straci swoje określone miejsce w tabelce. W tym przypadku szyfrogram to AAFMATJ NOAJ_NIRC_. Dla wyszczególnienia puste pola zostały wypełnione znakiem _. Jak widać użycie w tym przypadku znaku przerwy mogłoby sugerować, że zostały zaszyfrowane trzy, a nie dwa słowa.

Odszyfrowywanie nie powinno stanowić problemu. Najważniejsze, aby pamiętać, żeby odpowiednio rozrysować tabelkę i ją uzupełnić.

Implementacja

Przygotowanie klucza

Klucz najłatwiej będzie wczytać jako tabelkę znaków - nie jako liczbę, ponieważ zostaną utracone zera na początku. Jednak tabelka w takim przypadku będzie wymagała zamiany znaku cyfry na odpowiednią wartość, więc warto napisać funkcję createCode(), która na podstawie wczytanego kodu utworzy listę, która będzie miała wyliczony ile dokładnie i-ta kolumna ma pól.

1. char* createCode(char* code) {
2.   int dl = strlen(code);
3.   char* values = new char [dl + 1];
4.   for(int i = 0; i < dl; i++)
5.     values[i] = 2 * (code[i] - '0') + 1;
6.   values[dl] = '\0';
7.   return values;
8. }

Szyfrowanie

Szyfrowanie można podzielić na kilka etapów. Ze względu na jak najwyższą efektywność kodu funkcja nie będzie tworzyła tabelki jak w przykładzie. Program będzie potrzebował tylko tyle pamięci ile jest potrzebne na przechowanie tekstu wynikowego. Funkcja cipher() przyjmie tylko dwa argumenty txt - tekst do zaszyfrowania oraz vcode - skonwertowana wersję wczytanego klucza tudzież wygenerowanego przez createCode().

1. char* cipher(char* txt, char* vcode) {
2.   int txt_dl = strlen(txt);
3.   int dl = 0;
4.   int k = 0;
5.   while (dl < txt_dl) {
6.     dl += vcode[k % strlen(vcode)];
7.     k++;
8.   }

Pierwszy etap szyfrowania tekstu polega na (2.) pobraniu długości szyfrowanego tekstu, a następnie wprowadzeniu dwóch liczników: (3.) ile tekstu aktualnie mieści tabelka oraz (4.) ile łącznie kolumna tabelka posiada. (5. - 8.) Następnie algorytm dodaje kolumny do tabelki na podstawie klucza tak, aby wszystkie znaki się zmieściły. W tym przypadku należy pamiętać, że tabelka na razie nie jest tworzone. Wyliczenia mają na celu optymalizację wykorzystania pamięci.

9.   int* table = new int[k];
10.   table[0] = 0;
11.   for(int i = 1; i < k; i++){
12.     table[i] = table[i - 1] + vcode[(i - 1) % strlen(vcode)];
13.   }

Kolejny etap polega na utworzeniu tabelki, która będzie przechowywała informacja indeksy pierwszych znaków w każdej kolumnie. (9.) Utworzenie tabelki o k wartościach. (10.) Znaki w pierwszym wierszu zaczynają się od początku tekstu szyfrowanego, a potem (11. - 13.) i-ta kolumna reprezentuje indeks pierwszego znaku w tekście w i-tej kolumnie.

14.   char* wynik = new char[txt_dl + 1];
15.   int max = vcode[0];
16.   for(int i = 1; vcode[i]; i++)
17.     if(vcode[i] > max)
18.       max = vcode[i];
19.   max = (max - 1) / 2;

Mają już informacje na temat podziału tekstu można przejść do szyfrowania i (14.) zadeklarować pamięć pod tekst wynikowy. Następnie (15. - 18.) należy znaleźć maksymalny rozmiar kolumny w tabelce i (19.) wyliczyć ile ma wierszy powyżej wiersza środkowego.

20.   int zapis = 0;
21.   for(int j = max; j >= -max; j--){
22.     for(int i = 0; i < k; i++){
23.       if((vcode[i % strlen(vcode)] - 1) / 2 >= abs(j)){
24.         wynik[zapis++] = (zapis >= txt_dl) ? ' ' : txt[table[i]];
25.         table[i]++;
26.       }
27.     }
28.   }
29.   wynik[zapis] = '\0';
30.   return wynik;
31. }

Podczas przepisywania znaków należy pamiętać, że (20.) potrzebny jest indeks ile znaków zostało już zapisanych w wyniku. (21.) Dla każdego wiersz tabelki i (22.) każdej kolumny tabelki: (23.) o ile w danym wierszu dana kolumna ma pole do wypełniania. (24.) Przepisz znak wskazywany przez indeks i kolumny. (25.) Następnie zwiększ ten indeks. W ten sposób następnym razem zostanie zapisany kolejny znak w kolumnie. Na koniec (29.) należy dopisać znak końca danych i (30.) zwrócić wynik.

Deszyfrowanie

Podczas szyfrowanie danych należało pamiętać od którego indeksu przepisywać znaki i-tej kolumny. W przypadku deszyfrowania bardziej przydatna jest informacja ile znaków znajduje się w j-tym wierszu. Tylko w ten sposób będzie można określić jak podzielić szyfrogram na wiersze. Dalej każdy taki kawałek będzie można odpowiednio dopasować do tabelki na podstawie klucza. Funkcja deszyfrująca również przyjmuje dwa argumenty txt - tekst do rozszyfrowania i vcode - klucz użyty do szyfrowania.

1. char* decipher(char* txt, char* vcode) {
2.   int txt_dl = strlen(txt);
3.   int dl = 0;
4.   int k = 0;
5.   while (dl < txt_dl) {
6.     dl += vcode[k % strlen(vcode)];
7.     k++;
8.   }
9.   int max = vcode[0];
10.   for(int i = 1; vcode[i]; i++)
11.     if(vcode[i] > max)
12.       max = vcode[i];
13.   int* table = new int[max];
14.   table[0] = 0;
15.   max = (max - 1) / 2;

Proces deszyfrowani jest podobny do szyfrowania i jego kolejne części to (3. - 8.) wyliczenie ile kolumn ma tabelka oraz (9. - 15.) sprawdzenie jaka jest największa ilość pól w pojedynczej tabelce. (13.) Na tej postawie tworzona jest tabelka o max wierszach. (14.) Pierwsza wartość to 0 i reprezentuje pierwszy wiersz.

15.   for(int j = max - 1; j >= -max; j--){
16.     table[- j + max] = table[- j + max - 1];
17.     for(int i = 0; i < k; i++){
18.       if((vcode[i % strlen(vcode)] - 1) / 2 >= abs(j + 1)){
19.         table[- j + max]++;
20.       }
21.     }
22.   }

(15.) Dalsze indeksy pierwszych znaków w j-tym wierszu są wyliczane w następujący sposób. (16.) Przepisz poprzedni indeks i (17.) sprawdź ile kolumn ma (18.) pole a j-tym wierszu i tylko wtedy (19.) zwiększ indeks.

23.   char* wynik = new char[txt_dl + 1];
24.   int zapis = 0;
25.   for(int i = 0; i < k; i++){
26.     for(int j = -(vcode[i % strlen(vcode)] - 1) / 2; j < (vcode[i % strlen(vcode)] - 1) / 2 + 1; j++){
27.       wynik[zapis++] = txt[table[j + max]];
28.       table[j + max]++;
29.     }
30.   }
31.   wynik[zapis] = '\0';
32.   delete[] table;
33.   return wynik;
34. }

Dalsza część kodu (23.) deklaruje pamięć pod wynik i (24.) indeks zapisu. (25.) Dla każdej kolumny (26. - 29.) Przepisywane są kolejne znaki z każdych wierszy. W i-tym kroku przepisywane jest 2n + 1 znaków, gdzie n to pierwotna cyfra reprezentująca daną kolumnę. (28.) Tak samo jak podczas szyfrowania indeksy rozpoczęcia każdego wiersza są zwiększane. To pozwala na łatwiejsze uzyskiwanie odpowiedniego znaku. Na koniec (31.) dodany jest znak końca danych, (32.) usunięta tabelka pomocnicza i (33.) zwrócenie wyniku.

Testowanie funkcji

Powyższy kod można przetestować przy pomocy poniższej funkcji main(). Program w pierwszym wierszu oczekuje klucza złożonego z cyfr, a w drugim wiersz tekstu do zaszyfrowania:

1. int main () {
2.   char* code = new char[33];
3.   cin >> code;
4.   cin.ignore();
5.   char* txt = new char[257];
6.   cin.getline(txt, 257);
7.   char* vcode = createCode(code);
8.   char* txtc = cipher(txt, vcode);
9.   cout << txtc << endl;
10.   char* txtd = decipher(txtc, vcode);
11.   cout << txtd << endl;
12.   delete[] code, txt, txtc, txtd, vcode;
13.   system("pause");
14.   return 0;
15. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Dodaj wsparcie w programie tak, aby n mogło być nie tylko cyfrą z systemu dziesiętnego, ale również szesnastkowego. Przykładowo wtedy litera A w kodzie oznacza, że i-ta kolumna powinna mieścić 21 znaków.

• Kod źródłowy Zadanie 1