Szyfr Amsco

Opis

Szyfr Amsco jest szyfrem, który do szyfrowania wykorzystuje podział znaków na grupy, a następnie dokonania transpozycji tych elementów. W ten sposób powstaje szyfrogram, który bardzo trudno złamać. Oczywiście wszystko zależy od właściwego doboru klucza szyfrującego na podstawie którego dokonuje się transpozycji.

Szyfrowanie

Przyjmijmy, że szyfrowanym tekstem będzie "TAJNA INFORMACJA", a kluczem będzie 312. Ze względu na to, że znak spacji może umknąć to został zastąpiony poprzez znak zapytania ?. Pierwszą operacją do wykonania jest podział na grupy. Każda nieparzysta grupa to 2 znak, a każda parzysta to 1 znak. Stosując tę zasadę do podanego przykładu powstanie następująca lista: {"TA", "J", "NA", "?", "IN", "F", "OR", "M", "AC", "J", "A?"}. W przypadku, gdy podczas tworzenia grup zabraknie znaku w ostatniej parze to można dodać dowolny znak, ale z reguły wystarczy dopisać znak spacji.

Kolejny etap polega na uzupełnieniu tabelki utworzonymi grupami. Klucz w tym przypadku składa się z trzech cyfr, dlatego tabelka będzie miała trzy kolumny. Następnie wiersze należy wypełnić kolejnymi elementami z grupy. Każda kolejna kolumna ma taki nagłówek jaki wynika z klucza tj. i-ta kolumna ma i-tą cyfrę klucza jako nagłówek. Żaden wiersz nie powinien mieć pustego pola. Jeśli tak sytuacja ma miejsce to należy wypełnić go odpowiednią ilością znaków spacji.

Następnie należy z tabelki odczytać dane poprzez wybranie kolumny z indeksem 1, a następnie spisaniu danych z kolejnych wierszy. Operację tę powtarzamy dla każdej kolejnej kolumny wybierając dalej kolumny o nagłówkach 2, 3, 4, itd..

Po spisaniu danych w tym przypadku wychodzi szyfrogram "JINMA?NAFAC?TA?ORJ".

Deszyfrowanie

Odszyfrowanie danych jest nieco bardziej skomplikowany niż proces szyfrowania, ale nie powinno być z nim problemu. Przypuśćmy, że szyfrogram to "JINMA?NAFAC?TA?ORJ". Przede wszystkim na początku należy przygotować odpowiednią tabelkę na podstawie klucza. Jednak podczas tworzenie takiej tabelki należy tworzyć kolejny wiersz dopóki suma wolnych miejsc nie będzie równa długości tekstu zaszyfrowanego.

Po utworzeniu tabelki pozostaje uzupełniać kolejne wiersze w kolejnych kolumnach kolejnymi wartościami z szyfrogramu. Czyli przykładowo dla kolumny 1 wybieramy z szyfrogramu kolejno: J. IN. M. A?. Po zapisaniu danych w tabelce powinno się otrzymać taką samą jak w procesie szyfrowania.

Po zakończeniu rozszyfrowywania otrzymujemy początkowy tekst "TAJNA INFORMACJA".

Implementacja

Założenia

Implementacja opisywanego szyfru będzie korzystać z dodatkowej listy indeksów. Utworzenie tabeli może być wygodne, ale mało efektywne. Krok ten można pominąć poprzez utworzenie listy indeksów. W trakcie szyfrowania można na początku obliczyć ile wierszy ma tabelka oraz jaka będzie długość tekstu wynikowego. (Należy tu pamiętać, że długość szyfrogramu może być dłuższa od długości tekstu wejściowego.)

Posiadając informację ile jest wierszy wiadomo ile znaków maksymalnie zostanie przepisanych z każdej kolumny. Z tego powodu można utworzyć listę, która będzie przechowywać informację o pozycji następnego znaku przepisanego z i-tej kolumny. Po przepisaniu można uzupełnić wolne miejsca znakami przerwy poprzez sprawdzenie czy indeksy osiągnęły już wartość maksymalną.

Pozycji w wierszu

Sumowanie ciągu o dwóch różnych kolejnych wyrazach może być mało wygodne, dlatego warto dopisać dodatkową funkcję countEl(), która dla podanych argumentów n i level obliczy sumę n pierwszych wyrazów ciągu (1, 2, 1, ..) jeśli level jest parzyste, albo ciagu (2, 1, 2, ..)(2, 1, 2, ..) jeśli level jest nieparzyste.

1. int countEl(int n, int level) {
2.   bool nieparz = (n % 2 == 1);
3.   if (nieparz)
4.     n--;
5.   return 3 * n / 2 + (nieparz ? ((level + 1) % 2 + 1) : 0);
6. }

Pozycji w kolumnie

Sumowanie ile jest pozycji w kolumnie wykonuje funkcja countElCol(), która na podstawie k - indeksu kolumny (według klucza), dl_key - ilości kolumn, rows - ilości wierszy oblicza ile jest łącznie pozycji w danej kolumnie.

1. int countElCol(int k, int dl_key, int rows) {
2.   int suma = 0;
3.   for (int i = 0; i < rows; i++) {
4.     suma += ((k + 1) % 2) + 1;
5.     k += dl_key;
6.   }
7.   return suma;
8. }

Szyfrowanie

Pierwszym etapem w szyfrowaniu jest znalezienie ile wierszy miałaby tabelka pośrednia. (Sama tabelka nie zostanie nigdy utworzona).

1. char* cipher(char* txt, char* key) {
2.   int dl_txt = strlen(txt);
3.   int dl_key = strlen(key);
4.   int dl_cipher = 0;
5.   int rows = 0;
6.   for (int i = 0; dl_cipher < dl_txt; i++) {
7.     dl_cipher += countEl(dl_key, i);
8.     rows++;
9.   }

Wyznacz długości (2.) tekstu oraz (3.) klucza. (4.) Przyjmij, że szyfrogram będzie miał długość 0 i (5.) tabelka nie będzie miała żadnego wiersza. Potem (6. - 9.) w pętli dopóki długość szyfrogramu jest mniejsza od tekstu to (7.) zwiększ długość szyfrogramu o ilość pozycji w i-tym wierszu tabelki i (8.) zwiększ ilość wiersz. Po tym etapie znana jest długość szyfrogramu oraz ile wierszy miałaby tabelka.

10.   int* indeksy = new int[dl_key];
11.   int indeks = 0;
12.   for (int i = 0; i < dl_key; i++) {
13.     indeksy[i] = indeks;
14.     indeks += countElCol(key[i] - 1 - '0', dl_key, rows);
15.   }
16.   int* indeksy_maks = new int[dl_key];
17.   indeksy_maks[dl_key - 1] = indeks;
18.   for (int i = dl_key - 1; i >= 1; i--) {
19.     indeksy_maks[i - 1] = indeksy[i];
20.   }

Znając ilość wierszy można wyliczyć ile znaków zostanie przepisanych z każdej kolumny tabeli. Pozwoli to na ustalenie indeksów od której pozycji w tablicy wynikowej są zapisywane znaki z konkretnej kolumny. (10.) Zadeklaruj listę indeksów (jest ich tyle co znaków w kluczu). (11.) Do sumowania poprzednich indeksów posłuży zmienna indeks. W pętli (12. - 15.) wyznacz indeksy dla pierwszych znaków przepisywanych z każdej kolumny. Drugi etap polega na (16. - 20.) wyznaczeniu indeksów końcowych. Bez tego nie byłoby możliwości dopisania brakujących znaków.

21.   int block_size = 2;
22.   indeks = 0;
23.   char* txtc = new char[dl_cipher + 1];
24.   for (int i_row = 0; i_row < rows; i_row++) {
25.     for (int i = 0; i < dl_key; i++) {
26.       for (int j = 0; j < block_size; j++) {
27.         if (indeks < dl_txt)
28.           txtc[indeksy[key[i] - 1 - '0']++] = txt[indeks++];
29.       }
30.       block_size = (block_size % 2) + 1;
31.     }
32.   }

Trzeci etap polega na rozpoczęciu przepisywania każdej komórki tabelki od pierwszego wiersza. Jak wiadomo w pierszej komórce (21.) przepisywany blok ma długość 2, a następne 1, 2, 1, 2 itd. (22.) Zmienna indeks będzie teraz wskazywać, który znak tekstu jawnego jest przepisywany. (23.) Zadeklaruj wynikową tablicę znaków. (24.) Dla każdego wiersza (25.) i każdej kolumny: (26. - 29.) przepisz odpowiedni blok znaków i (30.) zmień długość bloku znaków (tj. ile powinno być przepisane z następnej komórki).

Kluczowa jest tutaj (28.) linijka przepisywania znaków z tekstu jawnego. Pobrany kolejny znak tekstu jawnego: kopiuje znak na odpowiedni indeks na podstawie wcześniej wyliczonych indeksów każdej kolumny w szyfrogramie. Indeks jest wybierany na podstawie nagłówka kolumny w której znajduje się algorytm.

33.   for (int i = 0; i < dl_key; i++) {
34.     while (indeksy[i] < indeksy_maks[i]) {
35.       txtc[indeksy[i]++] = ' ';
36.     }
37.   }
38.   txtc[dl_cipher] = '\0';
39.   return txtc;
40. }

Ostatni etap polega na (33. - 37.) dopisaniu brakujących znaków. Można to zrobić (34.) porównując aktualny indeks zapisu kolumny razem z jej maksymalnym indeksem. Na koniec (38.) należy dopisać znak końca danych i zwrócić (39.) teksty wynikowy.

Deszyfrowanie

Pierwsze 20 linijek kodu jest dokładnie takich samych jak podczas szyfrowania. Polegają one na wyznaczeniu ilości wierszy w tabelce oraz indeksów, gdzie są zapisywane kolejne kolumny. Różnica polega na tym, że tym razem te indeksy zostaną użyte do odczytania danych, a nie ich zapisania.

1. char* decipher(char* txt, char* key) {
2.   int dl_txt = strlen(txt);
3.   int dl_key = strlen(key);
4.   int dl_cipher = 0;
5.   int rows = 0;
6.   for (int i = 0; dl_cipher < dl_txt; i++) {
7.     dl_cipher += countEl(dl_key, i);
8.     rows++;
9.   }
10.   int* indeksy = new int[dl_key];
11.   int indeks = 0;
12.   for (int i = 0; i < dl_key; i++) {
13.     indeksy[i] = indeks;
14.     indeks += countElCol(key[i] - 1 - '0', dl_key, rows);
15.   }
16.   int* indeksy_maks = new int[dl_key];
17.   indeksy_maks[dl_key - 1] = indeks;
18.   for (int i = dl_key - 1; i >= 1; i--) {
19.     indeksy_maks[i - 1] = indeksy[i];
20.   }

Dalsza część różni się jedynie kierunkiem przepisywania. Podczas szyfrowania tekst jawny był zapisany do szyfrogramu, a tym razem (28.) to szyfrogram jest przepisywany do tekstu jawnego.

21.   char* txtd = new char[dl_txt + 1];
22.   int block_size = 2;
23.   indeks = 0;
24.   for (int i_row = 0; i_row < rows; i_row++) {
25.     for (int i = 0; i < dl_key; i++) {
26.       for (int j = 0; j < block_size; j++) {
27.         if (indeks < dl_txt)
28.           txtd[indeks++] = txt[indeksy[key[i] - 1 - '0']++];
29.       }
30.       block_size = (block_size % 2) + 1;
31.     }
32.   }
33.   txtd[dl_txt] = '\0';
34.   return txtd;
35. }

Warto zauważyć, że rozszyfrowany tekst może być dłuższy niż wejściowy tekst jawny przed zaszyfrowaniem jest to spowodowane faktem, że transpozycja wymaga tekstu jawnego konkretnej długości. Konwersja ta jest dokonywana potajemnie podczas szyfrowania (dopisywanie znaków spacji).

Testowanie funkcji

Funkcja main(), która przetestuje działanie programu wygląda następująco:

1. int main() {
2.   char* txt = new char[128];
3.   char* key = new char[16];
5.   cout << "Podaj tekst do zaszyfrowania:\n";
6.   cin.getline(txt, 128);
7.   cout << "Podaj klucz szyfrujacy: ";
8.   cin.getline(key, 16);
9.   char* txt_c = cipher(txt, key);
10.   cout << "\nSzyfrogram to:\n" << txt_c;
11.   char* txt_d = decipher(txt_c, key);
12.   cout << "\nTekst jawny to:\n" << txt_d;
13.   delete txt, key, txt_c, txt_d;
14.   system("pause");
15.   return 0;
16. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który wykorzysta metodę szyfrowania Amsco, ale pozwoli na zdefiniowanie własnego ciągu ile znaków jest przepisywanych z kolejnych kolumn. Przyjmujemy, że wczytane zostaną od użytkownika dwie dodatkowe zmienne a, b, które utworzą ciąg (a, b, a, b, ..), który z kolei będzie opisywać ile danych ma zostać przepisanych z kolejnych komórek. Program musi posiadać funkcję szyfrującą oraz deszyfrującą.

Przykładowo dla danych "INFORMACJA" klucza "21" oraz (a, b) = (1, 3) szyfrowanie odbędzie się według takiej tabelki. (Znak "?" zastępuje znak spacji.)

Oznacza to, że szyfrogramem będzie wyrażenie "NFOMACA IRJ".

• Kod źródłowy Zadanie 1