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

Szyfr Karolinka

Szyfr

Szyfr Karolinka opiera się na utworzeniu tabeli 10x10, która posłuży nam do szyfrowania danych. Na początek rysujemy tabelkę 10x10. Pierwsze pole na pozycji 1x1 zostawimy puste. W pierwszym wierszu kolejne pola uzupełniamy kolejnymi cyframi począwszy od 1 skończywszy na 9. Podobnie robimy dla pierwszej kolumny, gdzie kolejne pola uzupełniamy kolejnym cyframi począwszy od 1. W drugiej kolumnie do każdego kolejnego wiersza, począwszy od drugiego, wpisujemy kolejne litery wyrazu KAROLINKA. Następnie w każdym wierszu uzupełniamy wolne pola. Litera w danym polu musi być następna po literze w tym samym wierszu i kolumnie wcześniej zgodnie z alfabetem łacińskim. Zakładamy, że po literze Z mamy A. Innymi słowy jeśli wiersz zaczyna się od K to uzupełniamy go kolejno: L, M, N, O, P, Q, R, S. W ten sposób dla wyrazu KAROLINKA powstaje taka tabelka:

x123456789
1KLMNOPQRS
2ABCDEFGHI
3RSTUVWXYZ
4OPQRSTUVW
5LMNOPQRST
6IJKLMNOPQ
7NOPQRSTUV
8KLMNOPQRS
9ABCDEFGHI

Jeśli chcemy zaszyfrować literę to szukamy jej wystąpienia w tabelce. Następnie patrzymy na numer kolumny, potem wiersza i zapisujemy je koło siebie (bez przerwy i w ustalonej kolejności). W ten sposób otrzymujemy liczbę, która jest naszym zaszyfrowanym znakiem. Warto zauważyć, że dana literę możemy szyfrować na kilka sposobów. Przykładowo literę A zaszyfrujemy jako 12 lub 19. Z drugiej strony literę Z zapiszemy tylko na jeden sposób: 93, a literę O na sześć różnych sposobów!

Zaszyfrowane znaki zapisujemy koło siebie i zostawiamy między nimi odstęp, ale jest to niekonieczne, ponieważ każdemu znakowi odpowiadają dokładnie dwie cyfry. W celu zoszyfrowania danych należy wybrać kolejne dwie cyfry, który będą współrzędnymi xy tabeli. Przykładowo 89 to 8 kolumna i 9 wiersz czyli litera H.

Tylko KAROLINKA ?

Nie, ale wyraz musi spełniać kilka warunków:

  1. musi być długości 9 liter - limit możemy zwiększyć do 10 liter przyjmując, że nagłówki wierszy i kolumn zaczniemy numerować od 0
  2. kolejną ważną kwestią jest, aby w tabeli znalazły się wszystkie litery alfabetu łacińskiego - inaczej nie da się zaszyfrować całej wiadomości (chyba, że wiadomość nie zawiera wszystkich znaków)
  3. możemy uwzględnić polskie znaki, ale może to oznaczać, że nadawać się będzie niewiele wyrazów

Implementacja

Założenia

Napisz program, który na wejściu otrzyma tekst złożony z dużych liter alafabetu łacińskiego i zaszyfruje go przy pomocy szyfru KAROLINKA. Zaszyfrowany tekst powinien zostać wypisany na ekran.

Przykładowo dla wyrazu INFORMACJA otrzymamy:

  1. 99 66 96 72 18 13 91 93 62 21

Szyfrowanie - metoda 1

Szyfrowanie można by przeprowadzić tak:

  1. tworzymy tabelkę 10 x 10
  2. wczytujemy tekst
  3. każdy znak w tekście wyszukujemy w tabelce, zgodnie z szyfrem przepisujemy współrzędne
  4. wypisujemy na ekran zaszyfrowany tekst

Jednak to podejście nie jest najlepsze: zużywamy dużo pamięci. Do tego rozwiązania nie podaje kodu - zostawiam jako dobre ćwiczenie do zapoznania się z tabelami 2D w C++.

Szyfrowanie - metoda 2

Każda litera to specjalnie interpretowana liczba, dlatego możemy od siebie odejmować litery. Skorzystamy z tego w rozwiązaniu. Załóżmy, że nasze szyfrowanie będzie szukać pierwszego wystąpienia litery (nie będziemy korzystać z wielu wariantów zaszyfrowania jednego znaku). Podczas zapisywania szyfrogramu będziemy zostawiać przerwy między liczbami.

  1. char* cipher(const char* cipher, const char* txt){
  2.   int dl = strlen(txt)*3;
  3.   char* wynik = new char[dl];

(1.) Przyjmujemy dwa argumenty: code - jest to nasze słowo klucz w szczególności KAROLINKA, a drugi to dowolne słowo. (2.) Ustalamy długość tekstu wynikowego: 2 miejsca na liczbę i jedno przerwy. (3.) Alokujemy pamięć pod wynik.

  1.   for(int i = 0; txt[i]; i ++){
  2.     int j = 0;
  3.     while (txt[i] < cipher[j] || txt[i] > cipher[j] + 8) j++;
  4.     wynik[3*i] = (char)(j + 1 + '0');
  5.     wynik[3*i + 1] = (char)((txt[i] - cipher[j] ) + 1 + '0');
  6.     wynik[3*i + 2] = ' ';
  7.   }

(4.) Dla każdego znaku do zaszyfrowania: (5.) ustalamy początkowy indeks kolumny na 0. Wiemy, że znak jeśli jest w wierszu j + 1 to musi być w zakresie [litera, litera + 8][litera, litera + 8]. Dzięki temu wiemy, że (6.) musimy zwiększać j, aż litera do zaszyfrowania będzie w podanym przedziale. Po znalezieniu wystarczy wyliczyć pozycje: (7.) (8.). Dodajemy do każdej pozycji jeden, ponieważ zaczynamy numerować wiersze i kolumny od 1. (9.) Dopisujemy znak przerwy.

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

(11.) Dopisujemy znak końca danych \0 i (12.) zwracamy szyfrogram.

Warto zauważyć, że funkcja korzysta z tu poprawności danych wejściowych, ponieważ inaczej kod w linijce (6.) zwróci błąd. Drugą kwestią jest możliwość wprowadzenia dowolnego klucza tworzącego tabelkę.

Deszyfrowanie - metoda 2

Deszyfrowanie jest prostsze w zapisie:

  1. char* decipher(const char* cipher, const char* txt){
  2.   int dl = strlen(txt)/3;
  3.   char* wynik = new char[dl];
  4.   for(int i = 0; i < dl; i ++)
  5.     wynik[i] = cipher[txt[3*i] - '0' - 1] + (txt[3*i + 1] - '0' - 1);
  6.   wynik[dl]='\0';
  7.   return wynik;
  8. }

(1.) Wyliczamy długość tekstu wynikowego. (2.) Alokujemy pamięć pod tekst rozszyfrowany. (3.) Dla każdego zaszyfrowanego znaku: (4.) pobieramy dwie kolejne cyfry i korzystając z cipher odczytujemy zaszyfrowaną literę. Korzystamy tu z tego, ze pierwsza cyfra wskazuje kolumnę czyli y-1 znak cipher, a druga o ile powinniśmy ją przesunąć. (5.) Dopisujemy znak \0 i (6.) kończymy program.

Testowanie funkcji - metoda 2

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

Szyfrowanie - metoda 3

Tym razem zmodyfikujemy kod, aby program uwzględniał różne warianty zaszyfrowania tego samego znaku:

  1. char* cipher(const char* cipher, const char* txt){
  2.   int dl = strlen(txt)*3;
  3.   char* wynik = new char[dl];
  4.   for(int i = 0; txt[i]; i ++){
  5.     int j = rand()%9;
  6.     while (txt[i] < cipher[j] || txt[i] > cipher[j] + 8) j=(j+1)%9;
  7.     wynik[3*i] = (char)(j + 1 + '0');
  8.     wynik[3*i + 1] = (char)((txt[i] - cipher[j] ) + 1 + '0');
  9.     wynik[3*i + 2] = ' ';
  10.   }
  11.   wynik[dl]='\0';
  12.   return wynik;
  13. }

Modyfikujemy dotychczasową funkcje cipher(), aby losowała numer wiersza z którego miałaby pobrać pozycję znaku. (5.) Dodajemy losowanie wiersza od którego zaczynamy poszukiwania znaku. Kod, aby zadziałać potrzebuje jeszcze zmiany w linijce (6.), aby nie wyjść poza zakres cipher.

Dane zaszyfrowane w ten sposób deszyfrujemy tą samą funkcję. W celu implementacji losowania należy dołączyć odpowiednie biblioteki:

  1. #include <cstdlib>
  2. #include <ctime>

oraz zainicjować losowanie w funkcji main():

  1.   srand(time(NULL));

Zadania

Zadanie 1

Zmodyfikuj kod, aby:

  1. program wstawiał losowe cyfry zamiast spacji
  2. każda cyfra w szyfrogramie była uzupełnienia do 10 czyli 1 to będzie 9, 2 to 8, ..., 9 będzie 1

Przykładowo dla danych:

  1. KAROLINKA
  2. INFORMACJA
otrzymujemy:
  1. 99666396172818513491593762921