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

Szyfr Bazeries

https://mattomatti.com/a35au

Algorytm

Szyfrowanie

Szyfr Bazeries wykorzystuje do szyfrowanie dwa szachownice Polibiusza oraz klucz liczbę. Pierwsza z szachownic powstaje na podstawie alfabetu. Wybrany alfabet do szyfrowania (maksymalnie 25 znaków) należy wpisać pionowo do kolejnych kolumn. Z reguły w szyfrze Bazeries łączy się znaki I oraz J do I. Druga szachownica powstaje na podstawie klucza liczby zapisanego słownie. Do kolejnych pól kwadratu wpisywane są kolejne nie występujące wcześniej w zapisie słownym litery. Pozostałe wolne pola należy uzupełnić kolejnymi literami alfabetu, które jeszcze nie zostały wykorzystane. Dodatkowym zabezpieczeniem jest dokonanie transpozycji tekstu. Mianowicie z klucza pobierane są kolejne cyfry (c1, c2,.., cn) w sposób cykliczny. Następnie każde kolejne ck zostaje transponowane wspak.

Przykład

Przypuśćmy, że do zaszyfrowania jest tekst "DANE DO ZASZYFROWANIA" przy pomocy klucza liczby 312, który w zapisie słownym to "TRZYSTA DWANASCIE" (polskie znaki są usuwane). Wtedy do szyfrowania zostaną użyte następujące szachownice Polibiusza:

Szachownica "Alfabet"
AFLQV
BGMRW
CHNSX
DIOTY
EKPUZ
Szachownica "Liczba"
TRZYS
ADWNC
IEBFG
HKLMO
PQUVX

I etap szyfrowania polega na zastąpieniu znaków tekstu jawnego w szachownicy "Alfabet" na ich odpowiedniki w szachownicy "Liczba". W ten sposób powstaje wstępny szyfrogram "HTBP HL XTFXORNLCTBKT". Teraz należy podzielić tekst na grupy zgodnie z kluczem co ilustruje tabelka:

Klucz3123123123
Wstępny szyfrogramHTBP HL XTFXORNLCTBKT
SzyfrogramBTHPH X LTXFNROLTCTKB

Ostatecznie szyfrogram przyjmuje postać "BTHPH X LTXFNROLTCTKB". W celu odszyfrowania należy odwrotnie przyjąć szachownice. Transponowanie można zrobić po lub przez zamianą według szachownic.

Implementacja

Założenia

Zamieszczony niżej kod zakłada poprawność danych wejściowych. Tekst jawny oraz liczba słownie powinna być zapisany wielkimi literami, ale można używać innych znaków (błędne znaki zostaną usunięte lub nie zamienione). Klucz liczba powinien być złożony z samych cyfr.

Funkcje pomocnicze

Ze względu na fakt, że dopuszczone zostały znaki inne niż litery to przyda się funkcja isLetter(), która stwierdzi czy podany znak c jest dużą literą.

  1. bool isLetter(char c) {
  2.   return (c >= 'A' && c <= 'Z');
  3. }

Do wyszukiwania danych w tekście można skorzystać z funkcji find(), która przyjmuje trzy argumenty: data - tekst w którym szukany jest znak c, c - znak do wyszukiwania oraz max_i - ile pierwszych znaków ma być sprawdzonych pod kątem wyszukiwania znaku c.

  1. int find(const char* data, char c, int max_i) {
  2.   for (int i = 0; i < max_i; i++) {
  3.     if (data[i] == c) {
  4.       return i;
  5.     }
  6.   }
  7.   return -1;
  8. }

W celu uproszczenia kodu dopisane zostało krótkie przeciążenie funkcji find(), które w przypadku nie podania argumentu max_i przyjmuje, że znak c ma zostać wyszukiwany w całej tablicy znaków data.

  1. int find(const char* data, char c) {
  2.   return find(data, c, strlen(data));
  3. }

Szachownica "Alfabet"

Istnieje możliwość przechowywania szachownicy w tablicy dwuwymiarowej, ale zdecydowanie wygodniej będzie wykorzystać do tego celu tablicy jednowymiarowej. Funkcja squareAlphabet() zwraca szachownicę "Alfabet" zapisaną jak ciąg znaków tak jakby odczytywać szachownice wiersz po wierszu.

  1. char* squareAlphabet() {
  2.   char* squareA = new char[26];
  3.   for (int i = 0; i < 5; i++) {
  4.     for (int j = 0; j < 5; j++) {
  5.       char c = 'A' + i + j * 5;
  6.       if (c >= 'J')
  7.         c++;
  8.       squareA[i * 5 + j] = c;
  9.     }
  10.   }
  11.   squareA[25] = '\0';
  12.   return squareA;
  13. }

W trakcie uzupełniania tablicy znaków należy pamiętać, że (5.) znak J powinien zostać pominięty.

Szachownica "Liczba"

Tworzenie szachownicy na podstawie tekstu jest o wiele bardziej intuicyjne niż tworzenie szachownicy alfabetu, ponieważ nie trzeba zapisywać danych pionowo w kolumnach. Funkcja squareNumber() jako argument przyjmuje data - liczba zapisana słownie.

  1. char* squareNumber(const char* data) {
  2.   char* squareB = new char[26];
  3.   int iSave = 0;
  4.   for (int i = 0; data[i]; i++) {
  5.     if (isLetter(data[i]) && (find(squareB, data[i], iSave) == -1)) {
  6.       squareB[iSave++] = data[i];
  7.     }
  8.   }
  9.   for (int i = 'A'; i <= 'Z'; i++) {
  10.     if (i != 'J' && (find(squareB, i, iSave) == -1)) {
  11.       squareB[iSave++] = i;
  12.     }
  13.   }
  14.   squareB[25] = '\0';
  15.   return squareB;
  16. }

(2.) Deklaracja tablicy znaków i (3.) indeksu zapisu kolejnego znaku. (4.) Dla każdego znaku w data: (5.) sprawdź czy dany znak jest literą i jeśli tak to czy nie występuje w szachownicy. Jeśli oba warunki są spełnione to (6.) dopisz i-ty do szachownicy. Po zakończeniu przepisywania może okazać się, że pozostały wolne miejsca.

Pozostałe pola powinny zostać uzupełnione kolejnymi literami alfabetu. Z tego powodu (9.) dla każdego znaku w alfabecie: (10.) o ile nie jest literą J i nie występuje jeszcze w szachownicy to (11.) zostaje do niej dopisany. Na koniec (14.) można dopisać znak końca danych i (15.) zwróć wskaźnik na szachownice.

Transponowanie

Transponowanie odbywa się poprzez wywołanie funkcji transpose(), która przyjmuje dwa argumenty: data - tekst do transpozycji oraz key - liczba zapisana jako tekst. Funkcja zwraca wskaźnik na nową pozycję w pamięci.

  1. char* transpose(const char* data, const char* key) {
  2.   int dl = strlen(data);
  3.   int dl_key = strlen(key);
  4.   char* txt = new char[dl + 1];
  5.   for (int i = 0, k = 0; i < dl;) {
  6.     int sub = key[k] - '0';
  7.     if (i + sub >= dl)
  8.       sub = dl - i;
  9.     for (int j = 0; j < sub; j++)
  10.       txt[i + j] = data[i + sub - j-1];
  11.     i += sub;
  12.     k = (k + 1) % dl_key;
  13.   }
  14.   txt[dl] = '\0';
  15.   return txt;
  16. }

Pobierz (2.) długość tekstu jawnego oraz (3.) klucza. Potem (4.) alokuj pamięć pod tekst wynikowy. (5.) Rozpocznij transpozycję od znaku o indeksie i = 0 i od pierwszej cyfry klucza liczby k = 0. Kontynuuj wykonywanie dopóki są znaki do przepisania. (6.) Pobierz ile znaków zgrupować i (7.) sprawdź czy jest to możliwe. Jeśli nie to (8.) zmniejsz rozmiar grupy. Następnie (7. - 8.) przepisz odwracają wybraną grupę znaków. (9.) Wskaż ile znaków zostało dopisanych i (10.) wskaż, która cyfra określa rozmiar grupy w następnej iteracji. Na koniec (11.) dopisz znak końca danych i (12.) zwróć tekst wynikowy txt.

Zamian znaków

Funkcja change() zamienia znaki tekstu data na podstawie podanych szachownic squareA i squareB. Dane są szyfrowane poprzez znajdowanie odpowiedników znaków w szachownicy squareA w szachownicy squareB.

  1. void change(char* data, const char* squareA, const char* squareB) {
  2.   for (int i = 0; data[i]; i++) {
  3.     if (isLetter(data[i])) {
  4.       data[i] = squareB[find(squareA, data[i])];
  5.     }
  6.   }
  7. }

(3.) Należy tutaj pamiętać, że w szyfrowanym tekście mogą występować znaki inne niż litery. Należy ich wtedy nie modyfikować.

Szyfrowanie

Do zaszyfrowania danych służy funkcja cipher(), która przyjmuje trzy argumenty: data - tekst jawny, number - liczba zapisana jako ciąg znaków oraz spelledNumber - liczba zapisana słownie.

  1. char* cipher(const char* data, const char* number, const char* spelledNumber) {
  2.   char* squareA = squareAlphabet();
  3.   char* squareB = squareNumber(spelledNumber);
  4.   char* txt = transpose(data, number);
  5.   change(txt, squareA, squareB);
  6.   delete squareA, squareB;
  7.   return txt;
  8. }

(2. - 3.) Utwórz szachownice i (4.) utwórz wstępny, transponowany szyfrogram, a następnie (5.) go zaszyfruj. Usuń (6.) zbędne szachownice, a na koniec (7.) zwróć wskaźnik na szyfrogram.

Deszyfrowanie

Deszyfrowanie różni się jedynie sposobem podania szachownic do szyfrowania.

  1. char* decipher(const char* data, const char* number, const char* spelledNumber) {
  2.   char* squareA = squareAlphabet();
  3.   char* squareB = squareNumber(spelledNumber);
  4.   char* txt = transpose(data, number);
  5.   change(txt, squareB, squareA);
  6.   delete squareA, squareB;
  7.   return txt;
  8. }

Testowanie funkcji

Poniższa funkcja main() wczyta od użytkownika dane, wypisze szyfrogram oraz rozszyfrowany szyfrogram.

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

Zadania

Zadanie 1

Napisz wersję programu, która znajdzie pierwszą literę w alfabecie, który nie występuje w tekście jawnym. W przypadku, gdy taki znak nie istnieje funkcja powinna wypisać odpowiedni komunikat.

Przykładowo dla danych:

  1. INFORMACJA
  2. 312
  3. TRZYSTA DWANASCIE

wykluczonym znakiem z alfabetu jest litera B, a prawidłowym, wypisanym szyfrogramem jest:

  1. PFELWNKATT