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

Szyfr Grille

https://mattomatti.com/a35at

Nagłówek

Szyfr Grille został po raz pierwszy opracowany w 1550 roku. Według obecnych kryteriów podziału metod szyfrowania opisywana metoda podlega pod stegeanografie. Innymi słowy ukrycie tekstu wiadomości polega na ukryciu liter tekstu jawnego w gąszczu innych losowych znaków. Szyfr Grille polega na zapisaniu liter treści wiadomości w kolejnych wierszach w losowych miejscach w dowolnym kwadracie n x n. Kluczem jest tutaj specjalnie przygotowana kartka z wyciętymi otworami przez które widać tylko litery tekstu jawnego.

Przygotowana kartka papieru z losowymi znakami dla osoby postronnej zawiera tekst jawny, który można odczytać bez problemu, ale w gąszczu innych losowych znaków może się to okazać bardzo trudne bez ukrycia zbędnych znaków. Zadanie może okazać się trudniejsze jeśli losowe znaki mogą utworzyć jakiś losowy wyraz całkowicie niezwiązany z tekstem jawnym.

Przykład

Załóżmy, że do przekazania jest wiadomość o treść INFORMACJA. Na początek należy ustalić rozmiar tablicy. Rozmiar musi być taki, aby zmieścić wszystkie litery tekstu jawnego, ale żeby tablica nie składała się tylko z liter tekstu jawnego. W tym przypadku tablica 4x4 miałaby tylko 6 losowych pól, więc lepiej użyć tablicy co najmniej 5x5. Kolejne litery tekstu jawnego są wpisywane w losowe miejsca, ale odczytując je wierszami zachowują kolejność z tekstu jawnego.

I N
FO
R M
AC
J A

Teraz w rozrysowanej tablicy pozostało wiele różnych pól, więc można je uzupełnić losowymi znakami, a jak wcześniej wspomniałem można tego dokonać wpisując losowe wyrazy. Wpiszmy teraz wyrazy SZYFR, SEKRET, ITERACJA (zawiera część tekstu jawnego, dlatego może być mylące). Łącznie wszystkie wpisane wyrazy mają 29 znaków, ale niektóre się powtarzają więc, cztery powtórzone znaki można pominąć. (W tym przypadku np. ACJA z słowa ITERACJA.)

 
 
 
 
 
SISIN
ZTEFO
RYEKM
RACFE
RJTTA

Generalnie w trakcie tworzenie tego szyfru na kartce najpierw prościej byłoby stworzyć kartkę "klucz" i uzupełnić tekstem jawnym, ale w tym przypadku można utworzyć klucz w dowolnym momencie. Klucz umieszczony na tabelce można przesunąć. Spróbuj przeciągnąć go poza tabelkę, aby przekonać się jak dane są ukrywane.

Implementacja

Założenia

Kod źródłowy napisanego dalej programu będzie wczytywał od użytkownika zdanie do zaszyfrowania (zapisany w jednej linijce), a następnie klucz. Klucz będzie składał się z n wierszy po n wartości 0 i 1. W tym przypadku 1 to miejsce przeznaczone pod zapis tekstu jawnego. Program zwróci błąd, gdy zapisanie w tablicy tekstu jawnego będzie niemożliwe. Długość pojedynczego wiersza nie będzie przekraczać 127 znaków.

Klucz

Najtrudniejszą to wykonania w programie jest wczytanie klucza od którego wszystko zależy. Do wczytania klucza posłuży funkcja readKey(), która wczyta ze standardowego strumienia konsoli n wierszy po n znaków.

  1. char* readKey() {
  2.   char* keyf = new char[128];
  3.   cin.getline(keyf, 128);
  4.   int n = strlen(keyf);
  5.   char* key = new char[n*n + 1];
  6.   for (int i = 0; i < n; i++)
  7.     key[i] = keyf[i];
  8.   for (int i = 1; i < n; i++) {
  9.     cin.getline(&key[i * n], n + 1);
  10.   }
  11.   return key;
  12. }

(2.) Zadeklaruj zmienną do wczytania pierwszego wiersza i (3.) go wczytaj. Następnie na podstawie tego określ (4.) wymiary tablicy. (5.) Zadeklaruj tablicę do której zmieści się cała tabelka i (6. - 7.) przepisz dotychczasowy tekst do nowej tablicy. Ostatni etap polega na (8. - 10.) wczytaniu na kolejne miejsca kolejnych wierszy klucza i (11.) zwrócenia klucza wynikowego.

Mając już funkcję, która wczytuje klucz można napisać funkcję, która wypisze tabelkę na ekran. Wiadomo, że tablica jest kwadratowa, dlatego pierwiastek z długości klucza określi szerokość i wysokość tabeli. W takim razie funkcja writeData() ma następującą postać:

  1. void writeData(char* key) {
  2.   int n = (int)(sqrt(strlen(key)));
  3.   for (int i = 0; i < n; i++) {
  4.     for (int j = 0; j < n; j++) {
  5.       cout << key[i * n + j];
  6.     }
  7.     cout << endl;
  8.   }
  9. }

Szyfrowanie

Przed rozpoczęciem szyfrowania należy upewnić się, że wprowadzony klucz pomieści wszystkie znaki tekstu jawnego. W przypadku nadmiaru takich miejsc nie ma problemu, ponieważ losowe znaki na końcu tekstu jawnego będzie można łatwo odrzucić. Funkcja countPlace() sprawdza ile jest miejsc na tekst jawny poprzez liczenie wystąpień znaku 1. Jako jedyny argument należy przekazać klucz.

  1. int countPlace(char* key) {
  2.   int rozmiar = 0;
  3.   for (int i = 0; key[i]; i++) {
  4.     if (key[i] == '1') {
  5.       rozmiar++;
  6.     }
  7.   }
  8.   return rozmiar;
  9. }

W celu zaszyfrowania danych należy skorzystać z funkcji cipher(), która przyjmuje dwa argumenty: klucz key oraz tekst txt, który ma zostać umieszczony w szyfrogramie.

  1. char* cipher(char* key, char* txt) {
  2.   int txt_i = 0, txt_rozmiar = strlen(txt);
  3.   if (txt_rozmiar > countPlace(key)) {
  4.     cout << "Brak miejsc w kluczu" << endl;
  5.     throw;
  6.   }
  7.   else {
  8.     int n = strlen(key);
  9.     char* wynik = new char[n + 1];
  10.     for (int i = 0; i < n; i++) {
  11.       if (key[i] == '1' && txt_i < txt_rozmiar) {
  12.         wynik[i] = txt[txt_i++];
  13.       }
  14.       else {
  15.         wynik[i] = (rand() % ('Z' - 'A' + 1)) + 'A';
  16.       }
  17.     }
  18.     wynik[n] = '\0';
  19.     return wynik;
  20.   }
  21. }

(2.) Na początku zainicjalizuj zmienne: txt_i - indeks, który przechowuje, który znak będzie zapisywany z txt, txt_rozmiar - długość tekstu zapisywanego. (3.) Jeśli okaże się, że w danym kluczu jest za mało miejsca do zapisania danych to (4.) wypisz komunikat i (5.) zgłoś wyjątek. (7.) W przeciwnym wypadku: (8.) pobierz długość klucza i (9.) utwórz tablicę na szyfrogram. (10. - 17.) Utwórz szyfrogram przechodząc po każdym polu klucza i (11.) jeśli natrafisz na 1 w kluczu to (12.) dopisz kolejny znak z tekstu, a w przeciwnym (15.) wylosuj dowolny znak alfabetu łacińskiego. Następnie (15.) dopisz znak końca danych i (16.) zwróć wynik.

Deszyfrowanie

W celu rozszyfrowania danych należy skorzystać z funkcji decipher(), która na podstawienia podanego klucza key oraz szyfrogramu txtc zwróci tekst jawny.

  1. char* decipher(char* key, char* txtc) {
  2.   if (strlen(key) != strlen(txtc))
  3.     throw;
  4.   int txt_i = 0;
  5.   int txt_rozmiar = countPlace(key);
  6.   char* wynik = new char[txt_rozmiar + 1];
  7.   wynik[txt_rozmiar] = '\0';
  8.   for (int i = 0; txt_i < txt_rozmiar; i++) {
  9.     if (key[i] == '1') {
  10.       wynik[txt_i++] = txtc[i];
  11.     }
  12.   }
  13.   return wynik;
  14. }

Przed rozszyfrowaniem należy się upewnić, że (2.) oba teksty są równej długości. Jeśli nie to należy (3.) zwrócić wyjątek. Jeśli jednak mają tę samą długość to inicjalizuj zmienne (4.) txt_i, aby wiedzieć, który znak jest aktualnie zapisywany, (5.) txt_rozmiar, aby wiedzieć ile znaków tekstu jawnego jest w szyfrogramie oraz (6.) wynik do którego zostaną zapisane znaki i (7.) dopisać na jego końcu znak końca danych. Następnie (8. - 12.) dopóki nie zostaną przepisane znaki (9.) szukaj w kluczu 1 i jeśli znajdziesz to (10.) przepisz do wynik. Na koniec (13.) zwróć zmienną wynik.

Testowanie funkcji

W celu przetestowania napisanych funkcji można skorzystać z poniższej funkcji main(). Uwaga: funkcja nie obsługuje wyjątków! Spróbuj dodać tę funkcjonalność samodzielnie

  1. int main() {
  2.   srand(time(NULL));
  3.   cout << "Podaj tekst jawny:\n";
  4.   char* txt = new char[128];
  5.   cin.getline(txt, 128);
  6.   cout << "Podaj klucz:\n";
  7.   char* key = readKey();
  8.   char* txtc = cipher(key, txt);
  9.   cout << "Przykladowy szyfrogram:\n";
  10.   writeData(txtc);
  11.   cout << "Zakodowany tekst to:\n";
  12.   char* txtd = decipher(key, txtc);
  13.   cout << txtd << endl;
  14.   delete txt, txtc, txtd, key;
  15.   system("pause");
  16.   return 0;
  17. }

Zadania

Zadanie 1

Napisz program, która wczyta od użytkownika dwie linijki do zaszyfrowania, a następnie wpisze je do tabelki z kluczem uwzględniając fakt, że pierwszy tekst trafia na pozycje w kluczu z 1, a drugi z 2. Funkcja deszyfrująca nie musi zwracać w postaci char**, ale może wypisać dane bezpośrednio na ekran.

Przykładowo dla danych:

  1. TEST
  2. INFORMACJA
  3. 02012
  4. 00022
  5. 21002
  6. 12201
  7. 02002

Program wypisze szyfrogram, a potem odczyta z niego zaszyfrowane dane:

  1. ZIATN
  2. RDXFO
  3. REYIM
  4. SACAT
  5. ZJFGA
  7. TEST
  8. INFORMACJA