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

Szyfr Wieloosobowy

Szyfr Wieloosobowy

Szyfr Wieloosobowy jest rodzajem szyfru, który zaleca wykorzystanie komputera zarówno do szyfrowania jak i odszyfrowania. Polega ona na rozszczepieniu podanego tekstu na n różnych tekstów. W celu odszyfrowania danych należy podać wszystkie utworzone wcześniej kody. Teksty są tworzone tak, że i-ty znak to reszta z dzielenia sumy wartości znaków na i-tych pozycjach w każdym utworzonym tekście. W takim przypadku mogłoby się wydawać, że istnieje klucz, który pozwoli na odzyskanie wiadomości, a tekstem rozszyfrowywanym może być dowolny z utworzonych tekstów. Warto jednak zauważyć, że klucz jest wtedy długości tekstu co oznacza, że jest on odporny na ataki typu brute force. Ponadto w n - 1 wiadomościach i-ta litera jest losowa i tylko jedna wiadomość zawiera znak korygujący tj, aby po rozszyfrowaniu na i-tej pozycji był prawidłowy znak. Budowa szyfru jednak pozwala wylosować do której wiadomości taki znak trafi co znacznie utrudnia złamanie szyfru.

Tego typu metodę można wykorzystać na wiele różnych sposobów. Przykładowo logowanie do aplikacji można rozbić na dwa etapy podczas których należy wpisać dwa teksty: jeden otrzymany drogą mailową, a drugi SMSem. Wtedy oba przekazane teksty szyfrowałaby hasło i tylko znając obydwa teksty można by zalogować się do aplikacji. Innym pomysłem na wykorzystanie jest zapisanie dwóch kodów na dwóch różnych nośnikach i rozdaniu ich n osobom. Dopóki te n nośników nie zostanie odnalezionych to wiadomość nigdy nie zostanie odszyfrowana. Należy jednak pamiętać, że całe bezpieczeństwo danych polega na przechowywaniu każdego tekstu oddzielnie.

Algorytm

Przed przystąpieniem do szyfrowania należy pamiętać, aby ustalić alfabet, ponieważ pozycja każdego znaku w alfabecie będzie miała znaczenie na szyfrowanie. Wartość znaku to numer pozycji znaku w alfabecie (indeksowanie zaczyna się od 0). Każdy znak szyfruje się oddzielnie. Szyfrując i-ty należy wylosować indeks j z zakresu [1, n]. We wszystkich wiadomościach na pozycjach różnych od j wystarczy dopisać losowy znak. Natomiast na j-tej pozycji musi się znaleźć znak korygujący. Znak korygujący można obliczyć poprzez sumowanie wszystkich wylosowanych znaków w i-tej iteracji, a następnie obliczeniu przesunięcia i-tego znaku szyfrowanego do reszty sumy wartości znaków podzielonych przez długość alfabetu.

Rozszyfrowywanie znaków odbywa się w nieco prostszy sposób. W celu odszyfrowanie i-tego znaku należy zsumować wartości wszystkich i-tych znaków. Następnie zaszyfrowany znak leży na pozycji o wartości reszty dzielenie sumy przez długość alfabetu użytego do szyfrowania. Należy pamiętać, że do szyfrowania i deszyfrowania należy użyć jednego i tego samego alfabetu. Inaczej dane nie zostaną poprawnie odszyfrowane.

Przykład

W celu dokładniejszego działania szyfru warto prześledzić przykład. Pierwszy przykład będzie szyfrował dane zapisane jedynie przy pomocy cyfr. Oznacza to, że użyty alfabet to 0123456789. Szyfrowana będzie tajna liczba 1803 czyli np. kod PIN do karty. Dane zostaną rozszczepione na 3 tajne wiadomości:

Szyfrowany znak1803
Tekst 16329
Tekst 23619
Takst 32975

Szyfrowana wiadomość 1803 została rozbita na następujące wiadomości: 6329, 3619 oraz 2975. Znaki korygujące nie zostały wyszczególnione, ponieważ znak korygujący mógłby być wylosowanym znakiem i wtedy znak korygujący zamieniłby się z innym znakiem wylosowanym na miejsca. Ponadto nietrudno zauważyć, że zaszyfrowaną wiadomością może być dowolny z utworzonych tekstów i można do niego utworzyć klucz tak, aby odszyfrował wiadomość do pierwotnej. Pokazuje to tylko elastyczność takiego szyfru, ale wcale nie wskazuje na jego lukę w zabezpieczeniu. W celu rozszyfrowani danych należy obliczyć wszystkich znaków o indeksach i, a następnie obliczyć resztę z dzielenia sumy przez długość alfabetu:

Tekst 16329
Tekst 23619
Takst 32975
Suma11181023
Rozszyfrowany znak1803

Implementacja

Wstęp

Ze względu na fakt, że szyfr jest elastyczny pod względem doboru alfabetu, ale wymaga występowania wszystkich użytych znaków w treści wiadomości to przedstawione rozwiązanie zakłada poprawność wprowadzonego alfabetu. Domyślnie alfabet składa się z dużych liter alfabetu łacińskiego, małych liter alfabetu, cyfr oraz znaków specjalnych umieszczonych w alfabecie w wymienionej kolejności. Do odczytu wartości znaku (pozycji a alfabecie) została użyta funkcja pozycja(), która szuka znaku c w podanym tekście txt. Funkcja zakłada poprawność danych wejściowych!

  1. int pozycja(char* txt, char c) {
  2.   int i = 0;
  3.   while (txt[i] != c)
  4.     i++;
  5.   return i;
  6. }

Szyfrowanie

Podczas działania funkcji niektóre wartości są losowane, dlatego należy pamiętać o dołączeniu co najmniej biblioteki cstdlib oraz zainicjowaniu silnika losującego przed jego użyciem.

Funkcja szyfrująca dane przyjmuje trzy argumenty: alfabet - alfabet według, którego są szyfrowane dane, txt - wiadomość do zaszyfrowania oraz n - na ile tekstów ma być rozbita wiadomość. Funkcja zwraca listę list typu char**.

  1. char** szyfruj(char* alfabet, char* txt, int n) {
  2.   char** lista = new char*[n];
  3.   int dl = strlen(txt);
  4.   for (int i = 0; i < n; i++) {
  5.     lista[i] = new char[dl];
  6.     lista[i][dl] = '\0';
  7.   }
  8.   for (int i = 0; txt[i]; i++) {
  9.     int a = 0;
  10.     int p = pozycja(alfabet, txt[i]);
  11.     int j = rand() % n;
  12.     for (int k = 1; k < n; k++) {
  13.       lista[(j + k) % n][i] = alfabet[rand() % strlen(alfabet)];
  14.       a += lista[(j + k) % n][i];
  15.     }
  16.     lista[j][i] = (p + strlen(alfabet)) - (a % strlen(alfabet));
  17.   }
  18.   return lista;
  19. }

(2. - 7.) Utwórz listę list do których będą wstawione wylosowane i wyliczone znaki. Należy pamiętać, aby każdy z tekstów miał na końcu znak końca danych \0. (8.) Dla każdego znaku: (9.) ustaw sumę wylosowanych znaków na 0 i (10.) pobierz wartość szyfrowanego znaku. (11.) Wylosuj numer tekstu do którego przypisany zostanie znak korygujący. (12. - 15.) Wypełnij pozostałe wiadomości losowymi znakami pamiętając, aby zsumować ich wartości do zmiennej a. (16.) Oblicz znak korygujący wszystkie losowe wartości. Po zaszyfrowaniu wszystkich znaków (18.) zwróć utworzoną listę tekstów.

Deszyfrowanie

Funkcja deszyfrująca przyjmuje trzy argumenty: alfabet - alfabet według, którego są szyfrowane dane, lista - lista zawierająca wszystkie teksty szyfrujące wiadomość oraz n - na ile tekstów ma być rozbita wiadomość. Funkcja zwraca ciąg rozszyfrowanych znaków.

  1. char* rozszyfruj(char* alfabet, char** lista, int n) {
  2.   char* txt = new char[strlen(lista[0])];
  3.   txt[strlen(lista[0])] = '\0';
  4.   for (int i = 0; txt[i]; i++) {
  5.     int a = 0;
  6.     for (int j = 0; j < n; j++)
  7.       a += lista[j][i];
  8.     txt[i] = alfabet[a % strlen(alfabet)];
  9.   }
  10.   return txt;
  11. }

(2.) Zaalokuj miejsce w pamięci pod tekst wynikowy. (3.) Dopisz znak końca danych. (4.) W celu rozszyfrowania każdego znaku: (5. - 7.) oblicz sumę znaków szyfrujących i (8.) dopisz odpowiednik znak do tekstu wynikowego. (10.) Zwróć rozszyfrowany tekst.

Testowanie funkcji

Poniższa funkcja main() sprawdza poprawność działania napisanych funkcji. Po uruchomieniu programu należy wpisać liczbę, która określi na ile tekstów ma zostać rozbita wiadomość, a następnie wpisać treść wiadomości. Potem na ekran zostanie wypisanych n utworzonych wiadomości, a potem rozszyfrowana wiadomość na podstawie informacji szyfru.

  1. int main () {
  2.   srand(time(0));
  3.   char alfabet[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz023456789 .,?!:;\0";
  4.   int n;
  5.   cin >> n;
  6.   char* txt = new char[512];
  7.   cin.ignore();
  8.   cin.getline(txt, 512);
  9.   char** lista = szyfruj(alfabet, txt, n);
  10.   cout << "Zakodowane wiadomosci:\n";
  11.   for (int i = 0; i < n; i++)
  12.     cout << lista[i] << endl;
  13.   char* txtr = rozszyfruj(alfabet, lista, n);
  14.   cout << endl << txtr << endl;
  15.   for (int i = 0; i < n; i++)
  16.     delete lista[i];
  17.   delete lista, txt, txtr;
  18.   system("pause");
  19.   return 0;
  20. }