Strona główna » Algorytmy » Szyfry » Szyfr Macierzowo-Kwadratowy
1011

Szyfr Macierzowo-Kwadratowy

Zasada szyfrowania

W celu zaszyfrowania tekstu zapisujemy na początek w tabelce, która swoim wyglądem przypomina macierz. Pierwszy znak zapisujemy w pierwszym wierszu i pierwszej kolumnie. W tabelce o n kolumnach wszystkie znaki od 1 do n-tego zapisujemy w pierwszym wierszu. Do drugiego wiersza przechodzą znaki od pozycji n + 1 do 2n. Tekst szyfrujemy odczytując kolejne kolumny od góry do dołu, od lewej do prawej i zapisując dane koło siebie. Zaszyfrowane dane możemy odczytać szyfrując ponownie w ten sam sposób. Tabelka, zgodnie z zasadą szyfrowania, musi mieć tyle samo wierszy jak i kolumn. Może to spowodować, że w tabelce będzie więcej dostępnych pól niż znaków w tekście. Wolne pola możemy uzupełnić wybranym znakiem. (W przypadku programu zalecam użycie znaku spacji.)

Przykłady

Tekst o n2 znakach

Weźmy teraz przykładowo tekst KOMPUTERY. Jego długość wynosi 9 znaków, więc dane przepiszemy do tablicy o wymiarach 3 x 3:

KOM
PUT
ERY

Zgodnie z szyfrowaniem odczytujemy, że tekst wynikowy to KPEOURMTY. Spróbujmy teraz rozszyfrować dane. W tym celu wystarczy ponownie utworzyć tabelkę i zapisać w niej dane:

KPE
OUR
MTY

Zaszyfrowanym tekstem był wyraz KOMPUTERY.

Inna długość tekstu

Zmieniamy teraz szyfrowane słowo na INFORMACJA. Zwiększenie długość tekstu szyfrowanego wymusza utworzenie nowe, większej tabelki. Ze względu na fakt, że tabelka ma być kwadratowa to rozmiary nowej tabelki to będzie 4 x 4. W tym przykładzie w wolne pola wpiszemy spacje:

INFO
RMAC
JA
 

Na podstawie tabelki łatwo odczytujemy tekst wynikowy: IRJ NMA FA  OC  . Bardzo ważne, aby zauważyć ile spacji jest pomiędzy każdym wyrazem. Pominięcie dowolnej spacji może spowodować, że danego tekstu nie będzie można rozszyfrować.

Implementacja

W celu zaszyfrowania tekstu przy pomocy programu nie będziemy zapisywać tworzyć tabelki jak powyżej - wiązałoby się to z dodatkowym zużyciem pamięci. Warto zauważyć, że znak zapisany na pozycji [a, b] jest przenoszony na pozycję [b, a].

  1. char* cipher (const char* txt) {
  2.   int txt_length = strlen(txt);
  3.   int dl = sqrt(txt_length);
  4.   if(dl * dl < txt_length) dl++;

(1.) Funkcja cipher() przyjmuje jeden argument txt - tekst do zaszyfrowania i zwraca tekst zaszyfrowany. (2.) Odczytujemy długość txt i zapisujemy do zmiennej txt_length. (3.) Rozmiar tabelki n przyjmujemy, że jest pierwiastkiem długości tekstu txt. (4.) Może się jednak okazać, że uzyskamy tabelkę za małą - sam krok (3.) zadziała, gdy długość tekstu jest postaci n2. Tu jednak dla postaci n2 + k i k < n po obcięciu części ułamkowej uzyskamy n. Żeby uniknąć problemu zwiększamy długość dl o ile jest mniejsze od długości dl.

  1.   char* wynik = new char[dl * dl + 1];
  2.   for(int i = 0; i < dl; i++){
  3.     for(int j = 0; j < dl; j++){
  4.       if(j*dl+i < txt_length){
  5.         wynik[i*dl+j] = txt[j*dl+i];
  6.       } else {
  7.         wynik[i*dl+j] = ' ';
  8.       }
  9.     }
  10.   }
  11.   wynik[dl*dl] = '\0';
  12.   return wynik;
  13. }

(5.) Alokujemy pamięć pod tekst wynikowy. Tekst możemy podzielić na dl grup po dl znaków, dlatego (6.) dla każdej grupy, (7.) dla każdego znaku: (8.) sprawdzamy czy pobierany znak istnieje. (9.) Jeśli tak to zapisujemy go pod odpowiednia pozycją w wynik. (11.) Jeśli jednak nie to pod odpowiednią pozycją zapisujemy znak wolny. (15.) Dopisujemy na końcu znak końca danych i (16.) zwracamy wynik.

Testowanie funkcji

Przykładowe wykorzystanie funkcji cipher():

  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 = cipher(txtc);
  7.   cout << txtd << endl;
  8.   delete[] txt, txtc, txtd;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz funkcję cipher(), która będzie szyfrowała zgodnie z Szyfrem Macierzowym-Kwadratowym. Wolne pola powinny być wypełnione losowymi znakami od A do Z.

Przykładowo dla danych:

  1. INFORMACJA
otrzymujemy:
  1. IRJSNMAHFAGHOCSL