Strona główna » Algorytmy » Szyfry » Szyfrowanie Przez Wybieranie
 

Szyfrowanie Przez Wybieranie

Idea szyfrowania

Szyfrowanie Przez Wybieranie to szyfr transpozycyjny, który do szyfrowania wymaga podania listy liczb. Ideą szyfru jest zabezpieczenie danych przy użyciu jedynie kartki papieru oraz ołówka. Jego zasada jest bardzo prosta i łatwo ją zapamiętać. Należy jednak pamiętać, że szyfrowane litery nie zostają zastąpione przez inne. Jego zaletą jest fakt, że pozwala szyfrować dowolny zestaw znaków.

Zasada szyfrowania

Na początek należy ustalić tekst jawny oraz listę liczb potrzebną do szyfrowania danych. Następnie należy sprawdzić jaka jest długość tekstu jawnego i przygotować tyle samo pozycji do zapisania. Początkowo rozpoczynamy zapisywanie na indeksie 0. Wybierając kolejny znak do wstawienia wybieramy cyklicznie kolejną wartość z listy szyfrującej. Następnie zwiększamy indeks o 1 i zliczamy, która jest to wolna pozycja z kolei. Wykonujemy to tak długo, aż natrafimy na pozycję, która wynosi tyle co wybrana cyklicznie wartość z kodu. Proces ten jest powtarzany dla każdej kolejnej liczby.

Przykład

Weźmy przykładowo tekst jawny "TAJNE DANE", a następnie zaszyfrujmy go kluczem {1, 2, 3, 4}. Wypełniany będzie tekst o długości n = 10:

IndeksZnakKluczNowy
Indeks
TablicaKomentarz
0T10{T, _, _, _, _, _, _, _, _, _}Pierwsza pozycja jest wolna, zastępujemy ją
0A22{T, _, A, _, _, _, _, _, _, _} 
2J35{T, _, A, _, _, J, _, _, _, _} 
5N49{T, _, A, _, _, J, _, _, _, N} 
9E11{T, E, A, _, _, J, _, _, _, N}Po wyjściu z szyfrogramu, wracamy na początek
1" "24{T, E, A, _, " ", J, _, _, _, N}Litera 'A' nie jest liczona, więc dopiero pozycja 4 jest 2-gą wolną pozycją z kolei
4D38{T, E, A, _, " ", J, _, _, D, N} 
8A43{T, E, A, A, " ", J, _, _, D, N}Poszukiwania 4 wolnej zpoycji wymusiły obejście szyfrogramu
3N16{T, E, A, A, " ", J, N, _, D, N} 
6E27{T, E, A, A, " ", J, N, E, D, N}Ostatni znak można wpisać bez szukania

Uzyskany szyfrogram to "TEAA JNEDN". W przypadku użycia klucza o większych wartościach istnieje szansa, aby litery z tego samego wyrazu były równomiernie rozłożone po całym szyfrogramie.

Proces wybierania pozycji można przyśpieszyć znając liczbę wolnych pozycji do zapełnienia. Przykłado wstawiając literą 'A' należało przejść przez szyfrogram dwa razy, ale można było tego uniknąć. Szukana była 4-ta wolna pozycja wśród 3 możliwych, więc wystarczyło szukać pozycji 4 mod 3 = 1-ej pozycji.

Implementacja

Szyfrowanie

Funkcja szyfruj() wymaga podanie dwóch argumentów: tekst - tekst jawny do zaszyfrowania oraz klucz - lista liczb użyta do szyfrowania.

C++
C#
  1. string szyfruj(string tekst, int* klucz, int n) {
  2.   char* szyfrogram = new char[tekst.length() + 1];
  3.   for (int i = 0; i < tekst.length(); i++)
  4.     szyfrogram[i] = '#';
  5.   szyfrogram[tekst.length()] = '\0';
  6.   for (int i = 0, j = 0; i < tekst.length(); i++) {
  7.     int k = klucz[i % n];
  8.     while (true) {
  9.       if (szyfrogram[j] == '#') {
  10.         k--;
  11.         if (k == 0) break;
  12.       }
  13.       j = (j + 1) % tekst.length();
  14.     }
  15.     szyfrogram[j] = tekst[i];
  16.   }
  17.   return string(szyfrogram);
  18. }

(2. - 5.) Przygotuj bufor pod wynik, a następnie (6.) dla każdego znaku z tekstu: (7.) pobierz wartość przesunięcia. (8. - 14.) W pętli wyszukaj k-tą wolną pozycję i (15.) zapisz tam wybrany znak. Na koniec (17.) zwróć bufor szyfrogram.

Deszyfrowanie

Funkcja odszyfruj() działa analogicznie do funkcji szyfrującej. Oto jej kod:

C++
C#
  1. string odszyfruj(string szyfrogram, int* klucz, int n) {
  2.   string wynik = "";
  3.   for (int i = 0, j = 0; i < szyfrogram.length(); i++) {
  4.     int k = klucz[i % n];
  5.     while (true) {
  6.       if (szyfrogram[j] != '#') {
  7.         k--;
  8.         if (k == 0) break;
  9.       }
  10.       j = (j + 1) % szyfrogram.length();
  11.     }
  12.     wynik += szyfrogram[j];
  13.     szyfrogram[j] = '#';
  14.   }
  15.   return wynik;
  16. }

(2.) Przygotuj bufor pod wynik, a następnie (3.) dla każdego znaku z tekstu: (4.) pobierz wartość przesunięcia. (5. - 11.) W pętli wyszukaj k-tą wolną pozycję i (12.) pobierz wybrany znak i (13.) oznacz, że został już pobrany. Na koniec (15.) zwróć bufor wynik.

Testowanie funkcji

Poniższy fragment kodu wczytuje od użytkownika teskt do zaszyfrowania oraz listę liczb, które zostaną użyte jako klucz. Wypisany zostanie szyfrogram oraz rozszyfrowany tekst jawny.

C++
C#
  1. int main() {
  2.   string txt; int n;
  3.   cout << "Wpisz tekst do zaszyfrowania:\n";
  4.   getline(cin, txt);
  5.   cout << "Ile szyfr w kluczu?\n n = ";
  6.   cin >> n;
  7.   int* klucz = new int[n];
  8.   for (int i = 0; i < n; i++)
  9.     cin >> klucz[i];
  10.   cout << "\nZaszyfrowany tekst:\n";
  11.   string txtk = szyfruj(txt, klucz, n);
  12.   cout << txtk << endl;
  13.   cout << "\nRozszyfrowany tekst:\n";
  14.   string txtr = odszyfruj(txtk, klucz, n);
  15.   cout << txtr << endl;
  16.   system("pause");
  17.   return 0;
  18. }
Zadania
Zadanie 1
Przedstawiony algorytm wybierania kolejnych pozycji pod zapis kolejnych liter tekst jawnego można zoptymalizować kosztem wykorzystania pamięci. Napisz funkcję szyfruj() oraz deszyfruj(), które będą deklarowały listę liczb, które będą oznaczały wolną pozycję. Po zajęciu danej pozycji odpowiednia pozycja powinna zostać usunięta z listy. Przetestuj napisaną funkcję.
Kod źródłowy Zadanie 1Kod źródłowy Zadanie 1