Strona główna » Algorytmy » Szyfry » Szyfr Cyfrowy
 

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ę:

Tekst jawnyABCDEFGHIJKLMNOPQRSTUVWXYZ
Szyfrogram2143658710912111413161518172019222124232625

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:

Tymczasowy szyfrogram101351617142492
Ciąg cyfr6136136136
Szyfrogram1614822181785128

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.

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

(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.

  1.   wynik[dl]='\0';
  2.   return wynik;
  3. }

(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.

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

(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ą.

  1.   wynik[dl]='\0';
  2.   return wynik;
  3. }

(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. }

Zadania

Zadanie 1

Zmodyfikuj funkcję, aby algorytm szyfrowania:

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