Strona główna » Algorytmy » Szyfry » Szyfr Cztery kwadraty
 

Szyfr Cztery kwadraty

Cztery kwadraty

Szyfr Cztery kwadraty opiera się na zasadzie szyfrowania Playfair. Jednak podobieństwo kończy się na samej metodzie pobierania kolejnych liter. Do szyfrowanie potrzebne są dwa klucze. Dla standardowego alfabetu łacińskiego, w którym pomija się literę J, tworzy się dwie tabelki o rozmiarach 5 x 5. Każdą z tabelek wypełnia się alfabetem. Każda litera alfabetu może wystąpić tylko raz w obrębie jednej tabelki. Do zaszyfrowania danych potrzebna jest dodatkowa tabelka 2 x 2. W jej lewy górny oraz prawy dolny róg wpisuje sie alfabet w formie tabelki. Prawy górny zastępuje pierwszy klucz, a pozostałe wolne pole wpisuje się drugi klucz.

Podczas szyfrowania danych należy pobrać dwie kolejne litery z szyfrowanego tekstu, a następnie znalezienia pozycji (x1, y1) pierwszej litery w lewej, górnej części. W ten sam sposób należy zapisać pozycję (x2, y2) drugiej litery w prawej dolnej części. Pierwszą literę z pary należy zastąpić poprzez znak na pozycji (x2, y1), a drugi na znak na pozycji (x1, y2). W przypadku, gdy zostaje pojedyncza litera do zaszyfrowania można zostawić ją niezaszyfrowaną.

Przykład

Szyfrowanie

Załóżmy, że szyfrujemy tekst złożony z dużych liter alfabetu łacińskiego bez litery J. Kluczami szyfrującymi będą: LVGTZAKBRFIEYHOPWQDUMCNXS oraz IUTBOVACZKDWNEYLFSXHRPGQM. Wtedy zapisując wszystko w tabelce otrzymujemy:

12345678910
1ABCDELVGTZ
2FGHIKAKBRF
3LMNOPIEYHO
4QRSTUPWQDU
5VWXYZMCNXS
6IUTBOABCDE
7VACZKFGHIK
8DWNEYLMNOP
9LFSXHQRSTU
10RPGQMVWXYZ

Szyfrując słowo TEST, na początek należy wziąć dwie pierwsze litery TE. Litery T należy szukać w lewym górnym rogu, a litery E w prawym dolnym. Pozycja litery T to (4, 4), a litery E to (6,10). Wystarczy teraz odczytać literę na pozycji (4, 10): U oraz na pozycji (6, 4): B. Dla kolejnej pary należy wykonać te same czynności. Ostatecznie uzyskuje się w ten sposób szyfrogram UBDS.

Deszyfrowanie

Do deszyfrowania można stworzyć nową tabelkę, albo posłużyć się starą. Użycie tej samej tabelki oszczędza czas, dlatego zaprezentuje tą metodę jako pierwszą. Podczas deszyfrowanie ponownie litery bierze się parami. Tym razem jednak pierwszą literę szuka się w prawej górnej części, a drugą w lewej dolnej. Pozycja pierwszej to (x2, y1), a drugiej to (x1, y2). Na tej podstawie łatwo znaleźć litery tekstu jawnego - są kolejno na pozycjach (x1, y1) i (x2, y2).

Druga metoda deszyfrowania polega na zaszyfrowaniu szyfrogramu tabelą odwrotną. Tabelę odwrotną uzyskuje się poprzez zamianę lewej górnej części z prawą górną i analogicznie z dolnymi częściami. Szyfrując przy pomocy w tej tabelki wykonuje się czynności identyczne z poprzednią metodą. Ta metoda ma jednak zaletę, że nie trzeba robić czynności od tyłu, a wystarczy wykonać te same co przy szyfrowaniu.

Implementacja

Wstęp

Program będzie przyjmował cztery linijki tekstu na wejściu: pierwszy określi alfabet, dwa kolejne to klucze szyfrujące, a ostatnia czwarta linijka to tekst do zaszyfrowania. Dane nie będą przechowywane w tabelce. Przed rozpoczęciem potrzebne będą dwie dodatkowe funkcje. Pierwsza z nich posłuży do wyszukiwania znaku w tabelce:

  1. int getCharFromTable(char lookfor, char* tablica){
  2.   for(int i = 0; tablica[i]; i++)
  3.     if(tablica[i] == lookfor)
  4.       return i;
  5.   return 0;
  6. }

Druga funkcja cross() posłuży do wyliczania pozycji nowej litery. Ze względu na fakt, że dysponować będziemy indeksami litery w alfabecie, bądź którymś kluczu to funkcja przyjmie dwa argumenty i0 i i1, które będą indeksami litery w określonej części. Na tej podstawie zostanie wyliczony indeks litery z innej części.

  1. int cross(int i0, int i1){
  2.   return (i0 / 5) * 5 + i1 % 5;
  3. }

Przykładowo jeśli wywołamy cross(i0,i1), gdzie i0 to indeks litery w lewej, górnej części, a i1 indeks litery z prawej, dolnej to uzyskamy indeks litery z prawej górnej części, aby uzyskać z lewej dolnej wystarczy zamienić i0 i i1 miejscami.

Szyfrowanie i deszyfrowanie

Szyfrowanie i deszyfrowanie różni się tylko sposobem zapisu danych w tabelce, dlatego można napisać wspólną funkcją dla obu operacji. Będą się natomiast różnić sposobem jej wywoływania.

  1. char* change(char* txt, char* ul, char* ur, char* bl, char* br){
  2.   char* wynik = new char[strlen(txt) + 1];
  3.   strcpy(wynik, txt);
  4.   int i = 0, i0, i1;
  5.   for(; txt[i] && txt[i + 1]; i += 2){
  6.     i0 = getCharFromTable(wynik[ i ], ul);
  7.     i1 = getCharFromTable(wynik[i+1], br);
  8.     wynik[ i ] = ur[cross(i0, i1)];
  9.     wynik[i+1] = bl[cross(i1, i0)];
  10.   }
  11.   return wynik;
  12. }

(1.) Funkcja przyjmuje: txt - tekst do zaszyfrowania. (2.) Alokacja pamięci pod wynik i (3.) skopiowanie całej zawartości tekstu jawnego. (4.) Dla każdej kolejnej pary liter: wyliczane są indeksy (5.) pierwsze i (6.) drugiej litery z pary. Następnie (7. - 8.) pobierane są nowe znaki i zastępują odpowiednie znaki w wynik. (11.) Na koniec funkcja zwraca wynik.

Teraz wystarczy, aby zaszyfrować przy pomocy pierwszej wersji tabelki:

  1. char* cipher(char* txt, char* alphabet, char* key1, char* key2){
  2.   return change(txt, alphabet, key1, key2, alphabet);
  3. }

Z kolei szyfrogram zaszyfrować tabelą odwrotną w celu rozszyfrowania:

  1. char* decipher(char* txt, char* alphabet, char* key1, char* key2){
  2.   return change(txt, key1, alphabet, alphabet, key2);
  3. }

Testowanie funkcji

Program można przetestować przy pomocy poniższej funkcji main():

  1. int main () {
  2.   char* alphabet = new char[26];
  3.   char* key1 = new char[26];
  4.   char* key2 = new char[26];
  5.   char* txt = new char[128];
  6.   cin >> alphabet >> key1 >> key2;
  7.   cin.sync();
  8.   cin.getline(txt, 128);
  9.   char* txtc = cipher(txt, alphabet, key1, key2);
  10.   cout << txtc << endl;
  11.   char* txtd = decipher(txtc, alphabet, key1, key2);
  12.   cout << txtd << endl;
  13.   delete[] alphabet, key1, key2, txt, txtc, txtd;
  14.   system("pause");
  15.   return 0;
  16. }

Zadania

Zadanie 1

Napisz program tak, aby sprawdzał poprawność danych wejściowych tj. czy klucze są permutacjami alfabetu oraz czy alfabet też jest poprawny (nie zawiera zduplikowanych liter). Jeśli tak nie jest program powinien wypisać na ekran, że wprowadzone dane są niepoprawne z wyszczególnieniem co jest nieprawidłowe.

Przykładowo dla danych, gdzie pierwszy klucz zawiera dwie litery L:

  1. ABCDEFGHIKLMNOPQRSTUVWXYZ
  2. LLGTZAKBRFIEYHOPWQDUMCNXS
  3. IUTBOVACZKDWNEYLFSXHRPGQM
  4. TEST

Program ma stwierdzić, że:

  1. Klucz 1 jest niepoprawny