Strona główna » Algorytmy » Szyfry » Szyfr Rozbieżny
 

Szyfr Rozbieżny

https://mattomatti.com/a35p

O szyfrze

Szyfrowanie

Szyfrowanie polega na rozłożeniu każdego słowa na dwa nowe słowa. Pierwszy wyraz składa się z liter rozkładanego słowa na pozycjach nieparzystych, a drugi wyraz to wszystkie pozostałe wyrazy. Dwa nowe wyrazy rozdzielamy znakiem spacji jak również wszystkie nowo powstałem pary w ten sposób otrzymujemy szyfrogram. Rozparzmy szyfrowanie na przykładowym wyrażeniu TAJNA INFORMACJA. Pierwszy wyraz to TAJNA: tworzymy pierwszy wyraz z liter na pozycjach nieparzystych TJA, a potem drugi z pozostałych liter AN. W ten sposób zaszyfrowany wyraz TAJNA to TJA AN, a INFORMACJA to IFRAJ NOMCA. Kompletny szyfrogram to połączenie wszystkich powstałych wyrażeń rozdzielając znakiem przerwy czyli TJA AN IFRAJ NOMCA.

Deszyfrowanie

Deszyfrowanie w szyfrze Rozbieżnym polega na braniu kolejnych dwóch par wyrazów tekstu zaszyfrowanego. Następnie w każdej parze bierzemy drugi wyraz i wstawiamy kolejne litery pomiędzy kolejne pary liter wyrazu pierwszego. Wszystkie rozszyfrowane wyrazy zapisujemy koło siebie i rozdzielamy spacją. W ten sposób otrzymujemy tekst jawny z szyfrogramu. Przykładowo weźmy NW OA IFRAJ NOMCA. Patrzymy na pierwszą parę wyrazów: NW OA, a następnie wstawiamy litery z drugiego wyrazu do pierwszego: NOWA (kursywą zostały zapisane znaki z drugiego wyrazu). To samo wykonujemy dla drugiej pary IFRAJ NOMCA to INFORMACJA. Odszyfrowane wyrazu zapisujemy koło siebie i otrzymujemy tekst jawny NOWA INFORMACJA.

Warto zauważyć

Dowolny wyraz (lub znak) długości jeden całkowicie psuje algorytm szyfrowania i deszyfrowania, dlatego należy takie elementy usunąć przed szyfrowaniem. Jedną z metod wykrywania pojedynczych znaków polega na obliczeniu różnicy długości pary wyrazów, ponieważ w każdej parze różnica między wyrazami zawsze wynosi 0 lub 1.

Implementacja

Założenia

Na wejściu otrzymamy tekst do zaszyfrowania. Zakładamy, że nie występują tam pojedyncze znaki. Na wyjście zostanie wypisany zaszyfrowany tekst.

  1. TEKST DO ZASZYFROWANIA

otrzymamy szyfrogram:

  1. TKT ES DO O ZSYRWNA AZFOAI

Szyfrowanie

Na początek wyliczamy długość tekstu wynikowego. Będziemy korzystać z tego, że między każdym wyrazem jest znak przerwy co oznacza, że długość tekstu wynikowego jest dłuższa o ilość spacji + 1.

  1. char* cipher(const char* txt){
  2.   int dl = strlen(txt) + 1;
  3.   for(int i = 0; txt[i]; i++)
  4.     if(txt[i]==' ')
  5.       dl++;
  6.   char* wynik = new char[dl+1];
  7.   int from = 0, to = 0, x = 0;

(2.) Ustalamy długość początkową tekstu jako długość tekstu jawnego. Dodajemy jeden, ponieważ za ostatnim wyrazem nie ma spacji. (3.) Sprawdzamy wszystkie znaki do zaszyfrowania i (4.) jeśli jest znakiem przerwy to (5.) zwiększamy długość tekstu wynikowego. (6.) Alokujemy pamięć pod tekst wynikowy. (7.) Deklarujemy zmienne pomocnicze: from - będzie wskazywać początek wyrazu, to - wskaże gdzie kończy się wyraz oraz x - będzie przechowywać, który znak wyniku aktualnie zapisujemy.

  1.   for(; txt[to-1];){
  2.     while(txt[to]!=' '&&txt[to]!='\0')
  3.       to++;
  4.     for(int j = from; j < to; j+=2)
  5.       wynik[x++]=txt[j];
  6.     wynik[x++]=' ';
  7.     for(int j = from + 1; j < to; j+=2)
  8.       wynik[x++]=txt[j];
  9.     wynik[x++]=' ';
  10.     from = to+1;
  11.     to = from;
  12.   }
  13.   wynik[dl+1]='\0';
  14.   return wynik;
  15. }

(8.) Rozpoczynamy przepisywanie tekstu, aż do znaku \0. (9.) Sprawdzamy gdzie kończy się wyraz, dlatego (10.) zwiększamy to, aż będzie wskazywać znak spacji, albo znak końca tablicy znaków. Następnie (11. - 12.) rozpoczynamy przepisywanie kolejnych znaków wyrazu o indeksach nieparzystych. Dopisujemy znak spacji. Potem (14. - 15.) robimy to samo dla pozostałych znaków. Ponownie dopisujemy znak spacji. Ostatnim krokiem iteracji jest zresetowanie pozycji wyrazu - ustawiamy (17.) zmienną from i (18.) to za znakiem spacji. (20.) Dopisujemy na końcu znak \0 i (21.) zwracamy wynik.

Deszyfrowanie

Podczas deszyfrowania wyliczamy na początek długość tekstu wynikowego. Korzystamy z tego, że w tekście jawnym powinno być dwa razy mniej znaków przerwy.

  1. char* decipher(const char* txt){
  2.   int dl = strlen(txt);
  3.   bool mode = false;
  4.   for(int i = 0; txt[i]; i++){
  5.     if(txt[i]==' '){
  6.       if(!mode){
  7.         dl--;
  8.       }
  9.       mode = !mode;
  10.     }
  11.   }
  12.   char* wynik = new char[dl+1];
  13.   int from = 0, to = 0, to2 = 0, x = 0;

(2.) Ustalamy długość tekstu wynikowego jako długość szyfrogramu. (3.) Deklarujemy zmienną mode, która pomoże nam określić czy mamy odjąć dany znak przerwy czy nie. (4.) Dla każdego znaku w szyfrogramie - (5.) jeśli jest znakiem spacji to (6.) sprawdzamy czy mamy (7.) zmniejszyć długość tekstu wynikowego. Następnie (9.) negujemy wartość zmiennej mode. W ten sposób otrzymujemy prawidłową długość tekstu wynikowego.

(12.) Alokujemy pamięć pod tekst wynikowy. (13.) Podczas deszyfrowania użyjemy następujących zmiennych from - początek pierwszego wyrazu w każdej parze, to - pozycja końca pierwszego wyrazu i początku drugiego, to2 - pozycja końca drugiego wyrazu oraz x - wskaże, który znak tekstu wynikowego aktualnie przepisujemy.

  1.   for(; x<dl;){
  2.     while(txt[to]!=' '&&txt[to]!='\0')
  3.       to++;
  4.     to2 = to + 2;
  5.     while(txt[to2]!=' '&&txt[to2]!='\0')
  6.       to2++;
  7.     for(int j = 0; from + j < to; j++)
  8.       wynik[x+2*j]=txt[from+j];
  9.     for(int j = 0; to + 1 + j < to2; j++)
  10.       wynik[x+2*j + 1]=txt[to+j+1];
  11.     x+=to-from + to2-to - 1;
  12.     wynik[x++]=' ';
  13.     from = to2+1;
  14.     to = from;
  15.   }
  16.   wynik[dl]='\0';
  17.   return wynik;
  18. }

(14.) Dopóki nie wyjdziemy poza zakres tekstu wynikowego: (15. - 16.) Ustalamy koniec wyrazu pierwszego. (17.) Drugi wyraz zaczyna się po znaku spacji, dlatego rozpoczynamy poszukiwanie końca wyrazu drugiego od pozycji to+2. (18. - 19.) Szukamy końca wyrazu drugiego. (20. - 21.) Przepisujemy wszystkie znaki z pierwszego wyrazu na odpowiednie pozycje. To samo (22. - 23.) robimy dla znaków wyrazu drugiego. (24.) Przesuwamy wskaźnik x za wszystkie dotąd zapisane znaki. (25.) Dopisujemy znak spacji. (26. - 27.) Resetujemy pozycję aktualnie odczytywanego wyrazu. (29.) Dopisujemy na końcu znak \0 i (30.) zwracamy wynik.

Testowanie funkcji

Funkcja main(), która przetestuje działanie programu wygląda następująco:

  1. int main () {
  2.   char* txt = new char[128];
  3.   cin.getline(txt, 128);
  4.   char* txtc = cipher(txt);
  5.   cout << txtc << endl;
  6.   char* txtd = decipher(txtc);
  7.   cout << txtd << endl;
  8.   delete txt, txtc, txtd;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Zmodyfikuj działanie kodu źródłowego, aby jako pierwszy wyraz w zaszyfrowanym wyrażeniu były znaki o pozycjach parzystych, a potem wyraz ze znakami na pozycjach nieparzystych. Każda para zaszyfrowanego wyrazu powinna być zamieniona miejscami.

Przykładowo dla danych:

  1. DRUGA METODA SZYFROWANIA

otrzymujemy:

  1. RG DUA EOA MTD ZFOAI SYRWNA