Szyfr Cyfrowy

Algorytm

Szyfrowanie

Szyfr Cyfrowy wymaga pewnych założeń pomiędzy adresatem i odbiorcą. Mianowicie najpierw muszą ustalić jaką literę zamieniają na jaką literę zamieniają na jaką liczbę oraz liczbę kodującą.

Przykładowo korespondenci ustalili taką tabelkę:

oraz liczbę kodującą 613.

Kodowanie odbywa się w dwóch etapach. W pierwszym każdą literę zastępujemy poprzez liczbę zgodnie z tabelką. W ten sposób dla tekstu jawnego otrzymujemy tymczasowy szyfrogram. Przykładowo weźmy słowo "INFORMACJA". Zgodnie z naszą tabelka zamieniamy to na: "10-13-5-16-17-14-2-4-9-2"

W drugim etapie pod każdą liczbę z tymczasowego szyfrogramu podpisujemy kolejną cyfrą z liczby kodującej. Liczę kodującą traktujemy tutaj jako nieskończony ciąg cyfr, więc jeśli dojdziemy do ostatniej cyfry to zaczynamy dopisywać cyfry patrząc od początku liczby. Kolejne kolumny w obu wierszach sumujemy. W ten sposób uzyskując szyfrogram.

Kontynuując przykład szyfrowania dalej:

Z tabelki łatwo odczytać gotowy szyfrogram 16-14-8-22-18-17-8-5-12-8.

Deszyfrowanie

W przypadku deszyfrowania najpierw wykonujemy odejmowanie w etapie 2, a potem odczytujemy dane według klucza w etapie 1.

Implementacja

Założenia

Calem jest napisanie aplikacji, która wczyta tekst złożony z dużych znaków alfabetu łacińskiego do zaszyfrowania i zakoduje go według szyfru cyfrowego. Przykładowo dla danych:

1. INFORMACJA
2. ABCDEFGHIJKLMNOPQRSTUVWXYZ
3. 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25
4. 613

otrzymujemy:

1. 16-14-8-22-18-17-8-5-12-8

Funkcje pomocnicze

W celu optymalizacji wykorzystania pamięci oraz uzyskania bardziej eleganckiego kodu dopiszemy dwie funkcje pomocnicze. Jedna z nich char_pos() będzie wyszukiwać znaku w tablicy znaków i zwracać pozycję znaku w napisie.

1. int char_pos(char* napis, char look){
2.   int i = 0;
3.   for(; napis[i]!=look; i++);
4.   return i;
5. }

(1.) Funkcja przyjmuje tekst do przeszukania napis oraz znak do znalezienia look i zwraca pozycję znaku w napisie. (2.) Zakładamy, że znak jest na pozycji 0. (3.) Dopóki na i tym miejscu nie ma znaku zwiększamy i co oznacza, że sprawdzamy w każdej iteracji każdy następny znak. (4.) Zwracamy i kiedy następuje zgodność znaków.

Druga funkcja pomocnicza int_length() ma za zadanie zwrócić długość liczby. Wykorzystamy do tego metodę rekurencyjną:

1. int int_length(int n){
2.   return (n > 9) ? (1 + int_length(n/10)) : 1;
3. }

(1.) Jako argument przyjmuje liczbę całkowitą n, którą jest nasza liczba. Zwracamy liczbę całkowitą, która jest rozmiarem liczby n. (2.) Jeśli liczba jest większa od 9 to znaczy, że jest więcej niż jednocyfrowa, więc zwracamy 1 i "ucinamy" ostatnią cyfrę, ponieważ dzielenie liczby całkowitej przez 10 przesunie przecinek o jeden w lewo i usunie część całkowitą oraz wywoła funkcję int_length() z nową wartością. W przypadku, gdy liczba jest mniejsza równa 9 zwracamy jeden.

Szyfrowanie

Funkcja szyfrująca encodeTxt() będzie przyjmowała cztery argumenty: tekst jawny do zaszyfrowania, tabelkę szyfrującą ze znakami, tabelkę z liczbami oraz liczbę szyfrującą. Na początek policzymy jak długi będzie tekst wynikowy:

1. char* cipher(char* txt, char* codec, int* codel, char* code) {
2.   int dl = 0;
3.   for(int i = 0; txt[i]; i++)
4.     dl+=int_length(codel[char_pos(codec, txt[i])] + code[i % strlen(code)] - '0')+1;
5.   dl--;

(2.) Zmienna dl pomoże nam w odczytaniu jak długi będzie tekst wynikowy. (3.) Dla każdego znaku w tekście jawnym wyliczamy liczbę jaką zostanie zastąpiony i doliczamy jej długość powiększoną o jeden - robimy tu miejsce na każdy znak liczby oraz znak myślnika. (4.) Na koniec zmniejszamy dl o 1, ponieważ doliczyliśmy myślnik dla ostatniego znaku.

6.   char* wynik = new char[dl];
7.   for(int j = 0, i = 0; txt[i]; i++){
8.     int liczba = codel[char_pos(codec, txt[i])] + code[i % strlen(code)] - '0';
9.     int liczba_dl = int_length(liczba);
10.     for(int t = 0; t < liczba_dl; t++){
11.       wynik[j + liczba_dl - t - 1]=(char)(liczba%10) + '0';
12.       liczba/=10;
13.     }
14.     j+=liczba_dl;
15.     if(txt[i+1] != '\0')
16.       wynik[j++]='-';
17.   }

(6.) Alokujemy pamięć pod tekst wynikowy o długości dl. Zadeklarujemy dwie zmienne: zmienna j będzie nam przechowywać, który znak tekstu wynikowego piszemy, a i, który znak tekstu jawnego sprawdzamy. (7.) Dla każdego znaku w tekście (8.) wyliczamy liczbę: char_pos() zwraca nam pozycję znaku w tablicy szyfrującej, a code[i % strlen(code)] zwraca kolejne cyfry z liczby kodującej. Musimy jeszcze odjąć znak 0, ponieważ pobrany znak np. 0 ma wartość ASCII 49, a nie 0. (9.) Pobieramy długość liczby, którą przepisujemy. (10.) Dla każdego znaku liczby dopisujemy ja do wyniku. (11.) Należy pamiętać, że modulo 10 z liczby zwróci nam ostatnią cyfrę, więc nie dopisujemy liczb po kolei, a od tyłu. (12.) Dzielimy liczbę przez 10, aby w następnej iteracji uzyskać następną cyfrę. (14.) Doliczamy dopisaną długość liczby do indeksu zapisu wyniku. (15.) Jeśli istnieje następny znak liczby to (16.) dopisujemy myślnik.

18.   wynik[dl]='\0';
19.   return wynik;
20. }

(18.) Dopisujemy na końcu znak końca napisu i (19.) zwracamy wynik.

Deszyfrowanie

Przy deszyfrowaniu możemy założyć, że znaków będzie tyle ile myślników + 1. Dzięki temu łatwiej ustalić długość tekstu wynikowego:

1. char* decipher(char* txt, char* codec, int* codel, char* code) {
2.   int dl = 0;
3.   for(int i = 0; txt[i]; i++)
4.     if(txt[i]=='-') dl++;
5.   dl++;

(2.) dl będzie zliczać długość tekstu wynikowego. (3.) Sprawdzamy każdy znak i jeśli (4.) jest myślnikiem to zwiększamy długość tekstu. (5.) Zwiększamy długość o jeden, ponieważ po ostatnim znaku myślnik nie występuje.

6.   char* wynik = new char[dl];
7.   for(int j = 0, i = 0; txt[i-1]; j++, i++){
8.     int liczba = 0;
9.     while (txt[i]!='-' && txt[i]!='\0'){
10.       liczba*=10;
11.       liczba+=txt[i] - '0';
12.       i++;
13.     }
14.     liczba-=code[j % strlen(code)] - '0';
15.     int t = 0;
16.     for(; codel[t]!=liczba; t++);
17.     wynik[j] = codec[t];
18.   }

(6.) Alokujemy pamięć pod tekst wynikowy. (7.) Deklarujemy dwie zmienne i i j. Pierwsza pomoże nam pamiętać, który znak w tekście do deszyfracji sprawdzamy, a j, który znak tekstu wynikowego nadpisujemy. (8.) Rozpoczynamy wczytywanie liczby, która przechowamy w zmiennej liczba. (9.) Dopóki nie znajdziemy myślnika lub znaku końca linii: (10.) mnożymy liczbę o 10, (11.) dopisujemy wczytaną cyfrę i (12.) zwiększamy indeks i. (14.) Wczytaną liczbę zmniejszamy o odpowiednią cyfrę z liczby kodującej. Rozpoczynamy poszukiwania liczby w tablicy liczb drugiego rzędu. (15.) Deklarujemy zmienną t, która przypuszcza, że na liczba jest na pozycji 0. (16.) Dopóki liczba nie jest na indeksie t to go zwiększamy. (17.) Po znalezieniu indeksu t do tekstu wynikowego dopisujemy odpowiedni znak powiązany z liczbą.

19.   wynik[dl]='\0';
20.   return wynik;
21. }

(19.) Dopisujemy na końcu znak końca napisu i (20.) zwracamy wynik.

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.   cin.getline(txt, 128);
4.   char* codec = new char[64];
5.   cin.getline(codec, 64);
6.   cin.clear();
7.   cin.sync();
8.   int* codel = new int[strlen(codec)];
9.   for(int i = 0; codec[i]; i++) cin >> codel[i];
10.   cin.clear();
11.   cin.sync();
12.   char* code = new char[30];
13.   cin.getline(code, 30);
14.   char* txt_cout = cipher(txt, codec, codel, code);
15.   cout << txt_cout << endl;
16.   char* txt_dout = decipher(txt_cout, codec, codel, code);
17.   cout << txt_dout << endl;
18.   delete[] txt, codec, codel, code, txt_cout, txt_dout;
19.   system("pause");
20.   return 0;
21. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Zmodyfikuj funkcję, aby algorytm szyfrowania:

• każdą małą literę traktował jak dużą i zgodnie z zasadą szyfrowania odpowiednią ją zmieniał
• znakiem rozdzielającym był +

Przykładowo dla danych:

1. InFoRmAcJa
2. ABCDEFGHIJKLMNOPQRSTUVWXYZ
3. 2 1 4 3 6 5 8 7 10 9 12 11 14 13 16 15 18 17 20 19 22 21 24 23 26 25
4. 613

1. 16+14+8+22+18+17+8+5+12+8

• Kod źródłowy Zadanie 1