Strona główna » Algorytmy » Szyfry » Quagmire II
 

Quagmire II

· Quagmire I · Quagmire II ·

Wstęp

Quagmire I to szyfr podstawieniowy, który jest jedną z czterech wariacji szyfru Quagmire. Do szyfrowania używane jest hasło oraz słowo kluczowe. Takie połączenie zwiększa skuteczność szyfrowania.

Opis Szyfrowania

Część procesu jedt identyczna jak w Quagmire I. W celu zaszyfrowania informacji przy pomocy szyfru Quagmire II należy wpierw określić hasło oraz słowo klucz. Hasło służy do utworzenia zaszyfrowanego alfabetu. W celu jego utworzenia należy ustalić hasło, a następnie zostawić tylko pierwsze wystąpienia każdej litery i uzupełnić nie wystepującymi znakami z alfabetu. Ostatecznie zaszyfrowany alfabet powinien mieć taką samą długość co przyjęty alfabet oraz powinien mieć wszystkie znaki różne.

Następnie na podstawie słowa klucz tworzy się tabelką podstawień. W celu utworzenia takiej tabelki w pierwszym wierszu należy zapisać zwykły alfabet (po jednej literze w każdej kolumnie). Pod literą 'A' w pierszym wierszu należy zapisać pionowo słowo kluczowe. Każdy wiersz uzupełnia się literami alfabetu zaszyfrowanego poprzez zapisanie po lewej i po prawej znanej litery w wierszu odpowiedniego poprzednie i kolejne znaki, które są wybierane cyklicznie z zaszyfrowanego alfabetu.

W celu zaszyfrowania danych należy pogrupować litery po tyle znaków jaką długość ma słowo kluczowe. Następnie każdy kolejny znak jest zamieniany na podstawie tabeli podstawień. Litera c jest szukana w pierwszym wierszu tabeli, a następnie pobierany jest znak w tej samej kolumnie co został znaleziony znak, ale k pozycji dalej, gdzie k to numer znaku w grupie (indeksujemy od 0). Po zamianie wszystkich znaków otrzymujemy szyfrogram.

Przykład

Poniżej zostanie przedstawiony proces szyfrowania tekstu "TAJNAINFORMACJA" przy pomocy hasła "TAJNEHASLO" i słowem kluczowym "KLUCZ". Pierwszy etap polega na utworzeniu zaszyfrowanego alfabetu. W tym celu wpierw usuwamy powtarzające się litery (prócz pierwszego ich wystąpienia) i otrzymujemy "TAJNEHSLO", a następnie uzupełniamy przy pomocy liter alfabetu jawnego: "TAJNEHSLOBCDFIKMNPQRUVWXYZ".

Teraz można przejść do tworzenia tabeli. W pierwszy wiersz wpisany zostaje zwykły alfabet, a klucz zostanie zapisany w kolumnie pod literą 'A'. Następnie każdy wiersz zostaje uzupełniony zaszyfrowanym alfabetem tak, że na prawo są kolejne znaki, a na lewo poprzednie znaki, które są wybierane cyklicznie.

ABCDEFGHIJKLMNOPQRSTUVWXYZ
KMPQRUVWXYZTAJNEHSLOBCDFGI
LOBCDFGIKMPQRUVWXYZTAJNEHS
UVWXYZTAJNEHSLOBCDFGIKMPQR
CDFGIKMPQRUVWXYZTAJNEHSLOB
ZTAJNEHSLOBCDFGIKMPQRUVWXY

Tabela podstawień została utworzona. Przed rozpoczęciem szyfrowania warto pogrupować litery. W tym przypadku słowo klucz ma dokładnie 5 liter, więc po tyle samo znaków będzie mieć każda z grup.

TAJNAINFORMACJA

Litera 'T' znajuje się w pierwszej kolmnie i jest zastępowana przez literę 'O' z kolejnego wiersza. Kolejna litera 'A' jest druga w grupie, więc pobieramy wiersz z drugiej kolumny i trzeciego wiersza. Jest to litera 'L'. Z kolei litera 'F' znajduje się w 13 kolumnie i jest trzecia w grupie, więc jej odpowiednik jest w czwartym wierszu i jest to 'Z'. Poniżej została przedstawiona pełna lista zamian:

ZnakTAJNAINFORMACJA
W grupie123451234512345
SzyfrogramOLNXZXUZYMALWRZ

Otrzymany szyfrogram to "OLNXZXUZYMALWRZ".

Implementacja

Uzupełnianie alfabetu

Funkcja uzupelnijAlfabet() przyjmuje jeden argument a - hasło użyte do szyfrowania. Wynikiem działania funkcji jest zaszyfrowany alfabet.

C++
C#
  1. string uzupelnijAlfabet(string a) {
  2.   string w = "";
  3.   for (int i = 0; i < a.length(); i++)
  4.     if (w.find(a[i]) == string::npos)
  5.       w += a[i];
  6.   for (int i = 'A'; i <= 'Z'; i++)
  7.     if (w.find(i) == string::npos)
  8.       w += i;
  9.   return w;
  10. }

Proces uzupełniania alfabet został podzielony na dwa etapy. (2. - 4.) W pierwszym przepisywane są kolejne znaki hasła pod warunkiem, że do tej pory taka litera nie została przepisana, a drugi etap polega na (5. - 7.) sprawdzeniu, których liter alfabetu brakuje.

Tworzenie tabeli

Utworzona tabela podstawień będzie tablicą wartości typu string. W tabeli nie będzie przetrzymywany zaszyfrowany alfabet (zostanie on przekazany oddzielnie). Funkcja utworzTabele() potrzebuje podania dwóch argumentów: alfabet - zaszyfrowany alfabet oraz klucz - słowo klucz.

C++
C#
  1. string* utworzTabele(string alfabet, string klucz) {
  2.   string* tabela = new string[klucz.length()];
  3.   for (int i = 0; i < klucz.length(); i++) {
  4.     char znak = alfabet.find(klucz[i]);
  5.     tabela[i] = "";
  6.     for (int j = 0; j < 26; j++) {
  7.       tabela[i] += alfabet[znak];
  8.       znak = (znak + 1) % 26;
  9.     }
  10.   }
  11.   return tabela;
  12. }

(2.) Utwórz tablicę wynikową. Nie ma potrzeby szukania kolumny w której zaszyfrowany alfabet ma literę 'A', ponieważ zakłada się, że wskazana jest litera 'A', która w zwykłym alfabecie jest zawsze pierwsza. (3.) Dla każdego wiersza: (4.) określ pierwszy znak w wierszu i (6. - 9.) uzupełnij wiersz. Na koniec (11.) zwróć utworzoną tabele.

Szyfrowanie danych

Do zaszyfrowania danych program potrzebuje podania następujących argumentów: tekst - tekst jawny do zaszyfrowania, alfabet - zaszyfrowany alfabet utworzony z hasła, tabela - tabela podstawień oraz n - długość słowa klucza.

C++
C#
  1. string szyfruj(string tekst, string alfabet, string* tabela, int n) {
  2.   string w = "";
  3.   for (int i = 0; i < tekst.length(); i++) {
  4.     int pozycja = tekst[i] - 'A';
  5.     w += tabela[i % n][pozycja];
  6.   }
  7.   return w;
  8. }

(2.) Przygotuj zmienną do zapisu wyniku i (3.) dla każdego znaku: (4.) określ kolumnę, a następnie (5.) przepisz do wyniku. Na koniec (7.) zwróć zmienną w, która przechowuje szyfrogram.

Rozszyfrowanie danych

Funkcja rozszyfruj() działa analogicznie do funkcji szyfruj(). W tym przypadku została zamieniona kolejność wybierania z tabeli.

C++
C#
  1. string rozszyfruj(string tekst, string alfabet, string* tabela, int n) {
  2.   string w = "";
  3.   for (int i = 0; i < tekst.length(); i++) {
  4.     int pozycja = tabela[i % n].find(tekst[i]);
  5.     w += pozycja + 'A';
  6.   }
  7.   return w;
  8. }

Testowanie funkcji

Poprawność działania napisanych funkcji można przetestować przy pomocy poniżeszego fragmentu kodu, który pozwala na wczytanie danych od użytkownika.

C++
C#
  1. int main() {
  2.   string haslo = "", klucz = "", tekst = "";
  3.   cout << "Podaj slowo szyfrujace: ";
  4.   getline(cin, haslo);
  5.   string alfabet = uzupelnijAlfabet(haslo);
  6.   cout << "Podaj slowo klucz: ";
  7.   getline(cin, klucz);
  8.   string* tabela = utworzTabele(alfabet, klucz);
  9.   cout << "Podaj tekst do zaszyfrowania: ";
  10.   getline(cin, tekst);
  11.   string szyfrogram = szyfruj(tekst, alfabet, tabela, klucz.length());
  12.   string tekstJawny = rozszyfruj(szyfrogram, alfabet, tabela, klucz.length());
  13.   cout << "\nSzyfrogram to:\n" << szyfrogram << "\n";
  14.   cout << "\nPo rozszyfrowaniu:\n" << tekstJawny << "\n";
  15.   system("pause");
  16.   return 0;
  17. }