Strona główna » Algorytmy » Szyfry » Scytale

Scytale

Szyfrowanie

Scytale to urządzenie używane w Starożytnej Grecji do szyfrowania wiadomości polegające na transpozycji liter napisanej wiadomości. Samo narzędzie składało się z kija odpowiedniej grubości oraz materiału na którym była zapisywana wiadomość. Wiadomość podczas pisania i odczytywania musiała zostać nawinięta na kij - tylko w ten sposób literki ustawiały się w odpowiedniej kolejności i rzędami czytając można było odszyfrować wiadomość. Dużą rolę odgrywała tutaj grubość - jeśli była inna niż grubość kija na którym została narysowana to nie można było uzyskać zaszyfrowanej wiadomości.

Zaletą takiego rozwiązania był fakt, że wiadomość pisała się w sposób naturalny, a sam sposób nawinięcia materiału sprawiał, że po odwinięciu wiadomość byłą odszyfrowana. Dodatkową zaletą był fakt, że materiał na którym była napisana wiadomość mogła być cienkim paskiem, który można było używać zamiast normalnego paska w ten sposób dodatkowo ukrywając ją od oczu przeciwnika.

Szyfrowanie

Przypuśćmy, że chcemy zaszyfrować wiadomość o treści TAJNA INFORMACJA. Z wiadomości warto usunąć przerwy oraz wszelkie znaki interpunkcyjne, ponieważ na podstawie ich występowania można łatwiej złamać szyfrogram. W tym przypadku wystarczy usunąć tylko jedną spację przez pozostaje zapisać 15 liter TAJNAINFORMACJA. Do tego wystarczyłby kij o podstawie trójkąta gdzie na każdej ściance można by zapisać 5 liter. Wtedy dane na urządzeniu byłyby zapisane jako 3 linie po 5 liter:

  1. TAJNA
  2. INFOR
  3. MACJA

Po zdjęciu z urządzenia wiadomość brzmi TIMANAJFCNOJARA i dopiero po ponownym nawinięciu będzie możliwe odczytanie zaszyfrowanego tekstu.

Analiza

Szyfrogram w rzeczywistości jest transpozycją kolumn na wiersze co znacząco upraszcza implementację zadania w wybranym języku programowania.

Implementacja

W celu uproszczenia przechowywania danych i kodu program będzie operował na tablicy jednowymiarowej. Funkcja szyfrująca będzie przyjmowała dwie dodatnie liczby całkowite h - ilość linijek na urządzeniu oraz w - ile liter ma każdy z wierszy oraz w*h liter szyfrowanej wiadomości. Zakładamy, że wiadomość zawsze wypełnia w całości dostępne pola na urządzeniu. Poza tym warto skorzystać z własności, że transpozycja transpozycji tabeli A da tabele A. Z tego względu można napisać wspólną funkcję change() dla szyfrowania i deszyfrowania.

  1. char* change(const char* txt, int h, int w){
  2.   int dl = strlen(txt);
  3.   char* wynik = new char[dl + 1];
  4.   for(int i = 0, o = 0; i < w; i++){
  5.     for(int j = 0; j < h; j++){
  6.       wynik[i*h+j] = txt[j*w+i];
  7.     }
  8.   }
  9.   wynik [dl] = '\0';
  10.   return wynik;
  11. }

(1.) Funkcja change() zwróci ciąg znaków na podstawie argumentów: txt - tekst do zaszyfrowania, h - ile boków ma kij oraz w - ile liter mieści się na jednym boku. (2.) Pobranie długości tekstu wejściowego. (3.) Alokacja pamięci pod tekst wynikowy. (4. - 8.) Wykonanie transpozycji. (9.) Dopisanie znaku końca danych i (10.) zwrócenie wyniku.

Korzystanie z funkcji

Teraz funkcję tę można wykorzystać do napisania funkcji cipher() i decipher(). W przypadku pierwszej funkcji zmienne podaje się takie jak na wejsciu. W przypadku deszyfrowania należy zamienić wartości w i h miejscami, aby transpozycja została wykonana prawidłowo.

  1. char* cipher(const char* txt, int h, int w){
  2.   return change(txt, h, w);
  3. }
  4. char* decipher(const char* txt, int h, int w){
  5.   return change(txt, w, h);
  6. }

Tego typu zapis pozwala na przekazywanie danych w tej samej kolejności do każdej funkcji, ale program sam stwierdzi, że podczas deszyfrowania należy zamienić wartości miejscami.

Testowanie funkcji

Poniższy program wczytuje od użytkownika dwie wartości h i w, a następnie w*h znaków do zaszyfrowania. Na wyjście zostaje wypisana zaszyfrowana i odszyfrowana wiadomość.

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

Program przykładowo rozpozna poniższe dane:

  1. 3 5
  2. TAJNAINFORMACJA

Zadania

Zadanie 1

Program nie jest odporny na złe dane wejściowe. Napisz program tak, aby użytkownikowi pokazała się informacja jeśli wprowadzi złe dane.

Dla poniższych danych program ma stwierdzić problem z szerokością wiersza:

  1. 3 a
  2. COSTAM

Program powinien także rozpoznać czy dane nie są za długie, albo zbyt krótkie. Przykładowe błędne dane to:

  1. 3 2
  2. COSTAMY