Strona główna » Algorytmy » Szyfry » Szyfr Cadenus
****
 

Szyfr Cadenus

Szyfr

Szyfr Cadenusego jest to szyfr, który dokonuje podwójnej transpozycji tekstu jawnego na podstawie klucza. Szyfrowany tekst ze względu na specyfikę wymaga, aby szyfrowany tekst jawny był długości, który jest wielokrotnością liczby 25. W celu dokonania zaszyfrowania potrzebny jest klucz, który ma długość, która wynosi tyle co długość tekstu jawnego podzielona przez 25. Klucz musi składać się tylko z liter alfabetu łacińskiego.

W celu zaszyfrowania należy wyliczyć n, które jest długością tekstu jawnego podzieloną przez 25. Następnie dane zapisuje się do tabeli o szerokości n i wysokości 25. Znaki tekstu jawnego wpisuje się wierszami do kolejnych pól tabeli. Następnie należy przesunąć dane w kolumnie o k znaków pionowo w dół, gdzie liczba k to indeks litery w alfabecie litery przypisanej do kolumny. W przypadku tego szyfru z alfabetu została usunięta litera V. W celu odszyfrowania danych należy dokonać najpierw transpozycji kolumn w pionie, a potem zamienić odpowiednio kolumny.

Przykład

Weżmy przykładowo tekst jawny "szyfr cadenusa pozwala na zaszyfrowanie tekstow o długosci bedacej wielokrotnoscia dwudziestupieciu". Tekst ma długość 100, więc klucz szyfrujący musi mieć 4 znaki. Na potrzeby przykładu kluczem będzie wyraz "AUTO".

Na początek warto przyjrzeć się kluczowi. Posortowany wyraz AUTO to AOTU czyli kolumny tekstu tabeli tekstu jawnego powinny zostać zamienione następująco: 1 i 3 kolumna nie zostają zamienione, ale 2 zamienia się z 4 na miejsca. Podczas wykonywania drugiej transpozycji należy przesunąć pionowo w dół pierwszą kolumnę o 0 pozycji, drugą o 14, trzecią o 20 i ostatnią o 19.

Tekst jawny
Wpisania tekstu jawnego
AUTO
szyf
r ca
denu
sa p
ozwa
la n
a za
szyf
rowa
nie
teks
tow
o dl
ugos
ci b
edac
ej w
ielo
krot
nosc
ia d
wudz
iest
u pi
eciu
I transpozycja
Tabela po zamianie kolumn
AOTU
sfyz
rac
dune
sp a
oawz
ln a
aaz
sfyz
rawo
n ei
tske
t wo
old
usog
cb i
ecad
ew j
iole
ktor
ncso
id a
wzdu
itse
uip
euic
II transpozycja
Przesuwanie kolumn pionowo
AOTU
s za
rly
dswz
sbeo
ocki
lwwe
aodo
sto
rc g
ndai
tz d
ttlj
oioe
uusr
cf o
eada
eusu
ippe
kai
nnyc
iacz
wfn
ia e
u wa
es z

Odczytanym szyfrogramem jest "s zarly dswzsbeoockilwweaodosto rc gndaitz dttljoioeuusrcf oeadaeusuippekai nnyciaczwfn ia eu waes z". Jak można zauważyć tekst jest całkowicie nieczytelny. Należy jednak pamiętać, że szyfrowany tekst powinien mieć usunięte znaki interpunkcyjne oraz wszystkie znaki małe lub wielkie, aby nie dawały żadnych wskazówek.

Implementacja

Przedstawiona poniżej implementacja szyfru Cadenusego wczyta od użytkownika tekst jawny oraz klucz, a następnie wypisze szyfrogram oraz tekst rozszyfrowany. Tekst jawny to dowolny zestaw znaków, ale klucz musi zostać zapisany przy pomocy wielkich liter. Program nie będzie sprawdzał poprawności danych wejściowych.

Klucz

Tekstu nie można zaszyfrować bez znajomości zamiany podczas I transpozycji funkcja prepareKey() ma za zadanie na podstawie klucza key utworzyć nową listę na której i-ta pozycja będzie oznaczać numer kolumny do której ma zostać przepisana i-ta kolumna. Jako drugi argument jest przekazywany wskaźnik na miejsce w pamięci zmiennej dl_key.

  1. int* prepareKey(const char* key, int &dl_key) {
  2.   dl_key = strlen(key);
  3.   int* L = new int[dl_key];
  4.   for (int i = 0; i < dl_key; i++)
  5.     L[i] = i;
  6.   char* K = new char[dl_key];
  7.   for (int i = 0; i < dl_key; i++)
  8.     K[i] = key[i];

(2.) Na początek określ długość klucza i (3.) utwórz nową tablicę indeksów dla każdej kolumny i (4. - 5.) wypełnij ją wartościami od 0 do dl_key - 1. Następnie wykonaj kopię (6. - 8.) podanego klucza, ponieważ przekazanego klucza nie można zmienić.

  1.   char t;
  2.   int t2;
  3.   for (int i = 0; i < dl_key - 1; i++) {
  4.     for (int j = 0; j < dl_key - i - 1; j++) {
  5.       if (K[j] > K[j + 1]) {
  6.         t = K[j];
  7.         K[j] = K[j + 1];
  8.         K[j + 1] = t;
  9.         t2 = L[j];
  10.         L[j] = L[j + 1];
  11.         L[j + 1] = t2;
  12.       }
  13.     }
  14.   }

(9. - 22.) W celu wyznaczenia I transpozycji należy wiedzieć jak posortowane zostaną znaki klucza. W tym celu utworzone zostają pary <K[i], L[i]>, a następnie zostają posortowane według K. W ten sposób po posortowaniu danych otrzymuje się tablice w której wartość na pozycji i oznacza indeks kolumny do przepisania do i-tej kolumny podczas I transpozycji.

  1.   int* przes = new int[dl_key];
  2.   for (int i = 0; i < dl_key; i++)
  3.     przes[L[i]] = i;
  4.   delete K, L;
  5.   return przes;
  6. }

Jednak bardziej przydatne będzie tablica, która pod pozycją i powie na którą kolumnę ma się zamienić kolumna i. Wystarczy do tego wykonać (23. - 25.) odpowiednią zamianę. Przed (27.) zwróceniem tablicy wynikowej należy (26.) usunąć tablice pomocnicze K i L.

II transpozycja

Podczas drugiej transpozycji należy przesunąć tekst o numer pozycji litery w alfabecie. Funkcja posinAlphabet() dla danej litery c zwraca taką informację pamiętając, że litera A ma indeks 0, a litera V zostaje pominięta.

  1. int posinAlphabet(char c) {
  2.   if (c >= 'W') {
  3.     return c - 'A' - 1;
  4.   } else {
  5.     return c - 'A';
  6.   }
  7. }

Szyfrowanie

Podczas szyfrowani danych istnieje możliwość skorzystania z indeksów w celu dokonywania bezpośredniego ustawiania szyfrowanych danych do szyfrogramu. Jak wiadomo tekst w tabeli znajduje się w 25 wierszach po n znaków. Oznacza to, że pierwsza transpozycja to 25 razy wykonana ta sama zamiana dla każdego wiersza. Przykładowo jeśli pierwsza kolumna ma zostać zamieniona z drugą to znaki o indeksie nk zostaną zamienione ze znakami nk + 1.

Pozostaje jeszcze kwestia drugiej transpozycji. Jak wiadomo II transpozycja o p znaków zamieni listę k = {0, 1, 2, ..., n - 1, n} na k = {p, p + 1, p + 2, ..., n - p - 1, n - p}, dlatego początkowy indeks można ustalić na dowolny z listy i w celu przejścia do pomiętych p indeksów należy użyć reszty z dzielenia przez długość tekstu.

  1. char* cipher(const char* txt, const char* key) {
  2.   int dl_txt = strlen(txt);
  3.   int dl_key = 0;
  4.   int* L = prepareKey(key, dl_key);
  5.   for (int j = 0; j < dl_key; j++) {
  6.     L[j] = (L[j] + posinAlphabet(key[j]) * dl_key) % dl_txt;
  7.   }
  8.   char* txtc = new char[strlen(txt) + 1];
  9.   for (int i = 0; i < 25; i++) {
  10.     for (int j = 0; j < dl_key; j++) {
  11.       txtc[L[j]] = txt[i * dl_key + j];
  12.       L[j] = (L[j] + dl_key) % dl_txt;
  13.     }
  14.   }
  15.   txtc[dl_txt] = '\0';
  16.   return txtc;
  17. }

(2.) Pobierz długość tekstu i (3.) zainicjalizuj długość klucza. (4.) Pobierz indeksy zamiany kolumn na podstawie klucza i (5. - 7.) przesuń każdy indeks początkowy o odpowiednią wartość na podstawie litery przypisanej do kolumny. (8.) Utwórz tablicę pod szyfrogram. (9.) Dla każdego wiersza i (10.) każdego znaku w tabeli: (11.) dopisz w szyfrogramie kolejny znak z tekstu jawnego i (12.) przejdź do następnego indeksu. Na koniec (15.) wstaw znak końca danych i (16.) zwróć tekst wynikowy.

Deszyfrowanie

Podczas deszyfrowanie danych należy wykonać dokładnie te same kroki, ale należy zmienić kierunek przekazywania odczytanej litery, ponieważ teraz znak należy pobrać do szyfrogramu i zapisać do tablicy zawierającej tekst jawny.

  1. char* decipher(const char* txtc, const char* key) {
  2.   int dl_txt = strlen(txtc);
  3.   int dl_key = 0;
  4.   int* L = prepareKey(key, dl_key);
  5.   for (int j = 0; j < dl_key; j++) {
  6.     L[j] = (L[j] + posinAlphabet(key[j]) * dl_key) % dl_txt;
  7.   }
  8.   char* txt = new char[strlen(txtc) + 1];
  9.   for (int i = 0; i < 25; i++) {
  10.     for (int j = 0; j < dl_key; j++) {
  11.       txt[i * dl_key + j] = txtc[L[j]];
  12.       L[j] = (L[j] + dl_key) % dl_txt;
  13.     }
  14.   }
  15.   txt[dl_txt] = '\0';
  16.   return txt;
  17. }

Testowanie funkcji

Napisane funkcję szyfrujące i deszyfrujące można przetestować przy pomocy poniższej funkcji main():

  1. int main() {
  2.   char* txt = new char[512];
  3.   char* key = new char[16];
  4.   cout << "Podaj tekst do zaszyfrowania:\n";
  5.   cin.getline(txt, 512);
  6.   cout << "Podaj klucz szyfrujacy: ";
  7.   cin.getline(key, 16);
  8.   char* txt_c = cipher(txt, key);
  9.   cout << "\nSzyfrogram to:\n" << txt_c;
  10.   char* txt_d = decipher(txt_c, key);
  11.   cout << "\nTekst jawny to:\n" << txt_d;
  12.   delete txt, key, txt_c, txt_d;
  13.   system("pause");
  14.   return 0;
  15. }

Zadania

Zadanie 1

Napisz implementację szyfru Cadenusego tak, aby użytkownik mógł podać również alfabet na podstawie którego określona jest druga transpozycja. Program nie musi sprawdzać poprawności danych, ale można przyjąć, że każdy alfabet ma długość 25 znaków oraz wszystkie znaki znajdujące się w kluczu występują również w podanym alfabecie.

Przykładowo dla danych:

  1. szyfr cadenusa pozwala na zaszyfrowanie tekstow o dlugosci bedacej wielokrotnoscia dwudziestu pieciu
  2. AUTO
  3. ZYXWUTSRQPONMLKJIHGFEDCBA

Program wypisze na ekran:

  1. rc udwdesos otpclcizady szcertnani ztuwatf oazzuuyocpwieaeeenkoiaw kfdgnaoii dwsaji eullresoosba