Strona główna » Algorytmy » Szyfry » Szyfr Vigenère

Szyfr Vigenère

O szyfrze

Szyfr Vigenère jest szyfrem przestawieniowym polialfabetycznym, którego tekst jawny jest szyfrowany na podstawie klucza oraz tabelki. Tabelka jest stała i reprezentuje ją 26 alfabetów (w przypadku alfabetu łacińskiego).

ABCDEFGHIJKLMNOPQRSTUVWXYZ
AABCDEFGHIJKLMNOPQRSTUVWXYZ
BBCDEFGHIJKLMNOPQRSTUVWXYZA
CCDEFGHIJKLMNOPQRSTUVWXYZAB
DDEFGHIJKLMNOPQRSTUVWXYZABC
EEFGHIJKLMNOPQRSTUVWXYZABCD
FFGHIJKLMNOPQRSTUVWXYZABCDE
GGHIJKLMNOPQRSTUVWXYZABCDEF
HHIJKLMNOPQRSTUVWXYZABCDEFG
IIJKLMNOPQRSTUVWXYZABCDEFGH
JJKLMNOPQRSTUVWXYZABCDEFGHI
KKLMNOPQRSTUVWXYZABCDEFGHIJ
LLMNOPQRSTUVWXYZABCDEFGHIJK
MMNOPQRSTUVWXYZABCDEFGHIJKL
NNOPQRSTUVWXYZABCDEFGHIJKLM
OOPQRSTUVWXYZABCDEFGHIJKLMN
PPQRSTUVWXYZABCDEFGHIJKLMNO
QQRSTUVWXYZABCDEFGHIJKLMNOP
RRSTUVWXYZABCDEFGHIJKLMNOPQ
SSTUVWXYZABCDEFGHIJKLMNOPQR
TTUVWXYZABCDEFGHIJKLMNOPQRS
UUVWXYZABCDEFGHIJKLMNOPQRST
VVWXYZABCDEFGHIJKLMNOPQRSTU
WWXYZABCDEFGHIJKLMNOPQRSTUV
XXYZABCDEFGHIJKLMNOPQRSTUVW
YYZABCDEFGHIJKLMNOPQRSTUVWX
ZZABCDEFGHIJKLMNOPQRSTUVWXY

Tabelka jest bardzo duża, ale bardzo łatwo ją zapamiętać, ponieważ alfabet znajdujący się w i-tym wierszu jest alfabetem przesuniętym w lewo o i - 1 pozycji. Bardzo łatwo jest tutaj odnaleźć powiązanie z szyfrem Cezara.

Szyfrowanie

Szyfrowanie tekstu polega na ustaleniu klucza. Klucz musi składać się z liter alfabetu użytego do zapisu tekstu jawnego. Jeśli ustalony klucz jest krótszy od szyfrowanego tekstu to wystarczy dopisywać do klucza jego oryginalną wartość, aby uzyskać klucz tej samej lub dłuższej długości niż tekst jawny. W celu zaszyfrowania i-tej litery należy znaleźć kolumnę o nagłówku równej jej wielkości, a następnie odczytać literę z wiersza, którego nagłówek jest i-tą literę klucza.

Szyfrowanie

Podczas deszyfrowania i-tej należy znaleźć kolumnę o nagłówku równym i-tej wartości klucza (lub odpowiednika). W danej kolumnie następnie należy odnaleźć i-tą literę z szyfrogramu. Nagłówek wiersza w której znajduje się dana litera odpowiada rozszyfrowanej wartości podanej litery.

Przykład

Szyfrując wyraz INFORMACJA kluczem HASLO należy kolejno: dla litery I odczytać wartość z kolumny I i wiersza H. W tym przypadku jest to litera P. Dla kolejnej litery będzie to kolumna N i wiersz A. W przypadku litery A żadna litera nie zostaje zaszyfrowana, ponieważ alfabet dla litery A klucza alfabet ma przesunięcie 0. Ostatecznie zaszyfrowany tekst to: PNXZFTAUUO.

Podczas deszyfrowania szyfrogramu PNXZFTAUUO przy pomocy klucza HASLO należy pamiętać, że: pierwsza litera szyfrogramu to P. W kolumnie H należy znaleźć wartość P i odczytać nagłówek wiersza. P zostaje rozszyfrowane jako I. Kontynuując w ten sposób uzyska się tekst jawny INFORMACJA.

Implementacja

Informacje wstępne

Zaimplementowany kod będzie prawidłowo szyfrował tekst jawny przy pomocy klucza jeśli obie wartości są zapisane tylko przy pomocy małych liter alfabetu łacińskiego. Użycie liter spoza alfabetu spowoduje, że wartości będą wyświetlały się niepoprawnie. Nie istnieje potrzeba przechowywania całej tabelki w celu szyfrowania / deszyfrowania. Wszelkie wartości można odczytać na bieżąco przy pomocy dodawania u funkcji modulo.

Szyfrowanie

  1. char* cipher (char* txt, char* key) {
  2.   char* wynik = new char[strlen(txt) + 1];
  3.   wynik[strlen(txt)] = '\0';
  4.   for(int i = 0; txt[i]; i++)
  5.     wynik[i] = ((txt[i] - 'a') + (key[i % strlen(key)] - 'a')) % 26 + 'a';
  6.   return wynik;
  7. }

(1.) Funkcja szyfrująca przyjmuje dwa argumenty: txt - tekst do zaszyfrowania oraz key - klucz według którego tekst będzie szyfrowany. (2., 3.) Alokacja pamięci pod tekst wynikowy i zapisanie znaku końca danych. (4.) Dla każdej litery tekstu txt: (5.) znajdź jego odpowiednik w tabelce i dopisz do wynik. Po zakończeniu pętli (6.) zwróć wynik.

Deszyfrowanie

  1. char* decipher (char* txt, char* key) {
  2.   char* wynik = new char[strlen(txt) + 1];
  3.   wynik[strlen(txt)] = '\0';
  4.   for(int i = 0; txt[i]; i++)
  5.     wynik[i] = ((txt[i] - 'a') - (key[i % strlen(key)] - 'a') + 26) % 26 + 'a';
  6.   return wynik;
  7. }

Podobnie jak w szyfrowaniu. Różnica jest w (5.) gdzie wartość tekstu pobiera się na innych zasadach.

Testowanie funkcji

Funkcję szyfrującą i deszyfrującą można przetestować przy pomocy poniższej funkcji main(). Po uruchomieniu program zapyta się o podanie tekstu jawnego oraz klucza, a następnie wypisze tekst zaszyfrowany i deszyfrowany.

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

Zadania

Auto klucz

Według pierwszych zapisków szyfru Vigenère podczas szyfrowania należy ustalić tylko pierwszą literę klucza, a i-ta klucza odpowiada i - 1-szej literze tekstu jawnego.

Zadanie 1

Napisz program, który będzie szyfrował zgodnie z autokluczem według powyższego opisu. Możesz założyć, że klucz będzie podawany jako jedna litera. Tekst będzie złożony jedynie z małych liter alfabetu łacińskiego.

Przykładowo dla danych:

  1. tajnytekst
  2. d

prawidłowy wynik to:

  1. wtjwlrxocl