Szyfr Budzik

Opis szyfrowania

Szyfr budzikowy utajnia informację łącząc każdą kolejną parę i zapisując je pod postacią budzika z godziną. Każdy znak z alfabetu łacińskiego ma odpowiadający mu dwucyfrowy kod. Numerowanie zaczynamy od 00, a nie od 01:

Litera	A	B	C	D	E	F	G	H	I	J	K	L	M
Odpowiednik	00	01	02	03	04	05	06	07	08	09	10	11	12

Litera	N	O	P	Q	R	S	T	U	V	W	X	Y	Z
Odpowiednik	13	14	15	16	17	18	19	20	21	22	23	24	25

Znak specjalny	(spacja)	\0
Odpowiednik	58	59

Szyfrując wybieramy parę jeszcze nie zaszyfrowanych liter. Zapiszemy je w postaci budzika. Budzik ma postać [AB:CD], gdzie za A wstawiamy pierwszą cyfrę z odpowiednika pierwszej litery w parze, a za C drugą. Analogicznie zastępujemy B i D dla drugiej litery w parze. Jednak może się zdarzyć, że uzyskamy godzinę nierealną - w takim przypadku z pary szyfrujemy wtedy tylko pierwszą literę. Wtedy za AB wpisujemy 23, a za CD wstawiamy kod szyfrowanej litery. W ten sam sposób szyfrujemy literę, która nie będzie miała pary.

Przykłady

Przykładowo wyraz SZYFR BUDZIK zaszyfrujemy następująco:

• dla pary znaków SZ i sprawdzamy czy jest możliwe zapisanie [12:95]. Godzina nierealna, więc szyfrujemy tylko literę S: [23:18] i ją usuwamy z listy niezaszyfrowanych znaków,
• bierzemy parę znaków ZY zamieniamy na [22:54], godzina możliwa, więc dopisujemy to do wyniku,
• dla pary znaków FR, sprawdzamy [01:57], możliwe, więc dopisujemy do wyniku,
• dla pary znaków B, sprawdzamy [50:81], z całą pewnoscią zła godzina, szyfrujemy tylko znak spacji: [23:58],
• dla pary znaków BU, sprawdzamy [02:10], możliwe, więc dopisujemy do wyniku,
• dla pary znaków DZ, sprawdzamy [02:35], dopisujemy do wyniku,
• dla pary znaków IK, sprawdzamy [01:81], niemożliwe, szyfrujemy tylko literę I: [23:08]
• została tylko litera K, dopisujemy [23:10]

Ostateczny wynik to [23:18][22:54][01:57][23:58][02:10][02:35][23:08][23:10]. Spróbujmy teraz prześledzić tok rozszyfrowywania informacji:

• [23:18]: AB to 23, a CD to 18, dopisujemy literę S do wyniku
• [22:54]: zamieniamy do postaci 25 i 24 i dopsiujemy odpowiednio Z i Y
• [01:58]: odczytujemy i dopisujemy 05 (F) i 18 (R)
• [23:58]: AB to 23, a CD to 58, więc dopisujemy znak spacji
• [02:10]: odczytujemy 01 (B) i 20 (U)
• [02:35]: odczytujemy 03 (D) i 25 (Z)
• [23:08]: AB to 23, więc dopisujemy I
• [23:10]: AB to 23, więc dopisujemy K

Rozszyfrowanie powiodło się: uzyskaliśmy ten sam tekst, który szyfrowaliśmy na początku tej sekcji: SZYFR BUDZIK.

Implementacja

Przed przystąpieniem do zadania warto dopisać kilka pomocniczych funkcji, które będą ułatwiać pisanie kodu. Pierwsza z funkcji będzie nazywać się charToValue() i będzie przyjmować argument c - pojedynczą literę. Wynikiem będzie Odpowiednik dla podanej litery:

1. int charToValue(char c){
2.   switch (c){
3.     case ' ': return 58;
4.     case '\0': return 59;
5.     default: return c - 'A';
6.   }
7. }

Przyda się również funkcja odwrotna do podanej. Na podstawie wartości Odpowiednika zostanie zwrócony odpowiedni znak:

1. char valueToChar(int a){
2.   switch (a){
3.     case 58: return ' ';
4.     case 59: return '\0';
5.     default: return 'A' + a;
6.   }
7. }

Szyfr znacząco polega na wybieraniu k-tej cyfry z liczby. Na potrzeby programu można napisać uproszczoną wersję funkcji. Przyjmować będzie argumenty a - liczba z której chcemy pobrać cyfrę oraz k - określi którą cyfrę od prawej strony:

1. int getDigit(int a, int k){
2.   if (k == 1) return a % 10;
3.   return a / 10;
4. }

Ostatnia funkcja sprawdzi czy podany czas jest prawidłowy czy nie:

1. bool checkTime(int hours, int minutes){
2.   return (hours < 24 && hours >= 0) && (minutes < 60 && minutes >= 0);
3. }

Szyfrowanie

Po napisaniu funkcji pomocniczej można przejść do właściwej funkcji szyfrującej:

1. char* cipher(char* data){
2.   int dl = 0;
3.   for(int j = 0; data[j];){
4.     int l1 = charToValue(data[j]);
5.     int l2 = charToValue(data[j + 1]);
6.     dl++;
7.     if(checkTime(getDigit(l1, 2) * 10 + getDigit(l2, 2), getDigit(l1, 1) * 10 + getDigit(l2, 1))){
8.       j+=2;
9.       if(l2 == 59) break;
10.     } else {
11.       j++;
12.     }
13.   }

Przed przystąpieniem do właściwego szyfrowania najpierw policzymy ile bajtów musimy zaalokować. W tym celu (2.) inicjalizujemy licznik dl na 0. (3.) Dla każdego znaku w podanym wyrażeniu: (4., 5.) obliczamy wartości numeryczne dla pierwszych dwóch niezaszyfrowanych znaków. (6.) Zwiększamy długość. (7.) Sprawdzamy czy możemy je zapisać razem. Jeśli tak to (8.) zwiększamy j o 2. W ten sposób "oznaczymy", że dane o mniejszym indeksie już są zaszyfrowane. (9.) Ze względu na możliwą nieparzystość długości data sprawdzamy czy nie pominęliśmy znaku \0. Jednak jeśli znaków nie możemy zapisać razem to (11.) zwiększamy j o 1.

14.   char* wynik = new char[dl*7];
15.   for(int i = 0, j = 0; data[j]; j += 2, i += 7){
16.     int l1 = charToValue(data[j]);
17.     int l2 = charToValue(data[j + 1]);
18.     wynik[i] = '[';
19.     wynik[i + 3] = ':';
20.     wynik[i + 6] = ']';
21.     if(checkTime(getDigit(l1, 2) * 10 + getDigit(l2, 2), getDigit(l1, 1) * 10 + getDigit(l2, 1))){
22.       wynik[i + 1] = getDigit(l1, 2) + '0';
23.       wynik[i + 2] = getDigit(l2, 2) + '0';
24.       wynik[i + 4] = getDigit(l1, 1) + '0';
25.       wynik[i + 5] = getDigit(l2, 1) + '0';
26.       if(l2 == 59) break;
27.     } else {
28.       wynik[i + 1] = '2';
29.       wynik[i + 2] = '3';
30.       wynik[i + 4] = getDigit(l1, 2) + '0';
31.       wynik[i + 5] = getDigit(l1, 1) + '0';
32.       j--;
33.     }
34.   }
35.   wynik[dl*7] = '\0';
36.   return wynik;
37. }

(14.) Znając długość tekstu wynikowego alokujemy tablicę wynikową. (15.) Rozpoczynamy pętle, która zaszyfruje każdy znak po kolei. Zmienna i będzie przechowywać w której grupie wyniku zapisujemy, a j - indeks ostatniego niezaszyfrowanego znaku. (16., 17.) Pobieramy Odpowiedniki pierwszych dwóch niezaszyfrowanych wyrazów. (18. - 20.) Dopisujemy na odpowiednich pozycjach odpowiednie znaki "budzika". (21.) Sprawdzamy czy możemy zapisać obydwa znaki razem. Jeśli tak to (22. - 25.) przepisujemy na odpowiednie pozycje cyfry obu liczb. (26.) Sprawdzamy czy nie powinniśmy przerwać wykonywania. Jednak jeśli nie możemy zapisać rozpatrywanej pary liczb (l1, l2) to (28. - 31.) dopisujemy 23 i cyfry pierwszej liczby. (32.) Zmniejszamy j o 1, ponieważ zapisaliśmy tylko jeden znak, a nie dwa jak to jest założone na początku pętli for. (35.) Na koniec dopisujemy znak końca danych i (36) zwracamy wynik.

Deszyfrowanie tekstu

Deszyfrowanie tekstu jest nieco prostsze, ponieważ wystarczy pogrupować znaki po 7 i odpowiednio je zinterpretować:

1. char* decipher(char* data){
2.   int dl = 0;
3.   for(int i = 0, j = 0; data[i]; i += 7){
4.     dl += (data[i+1] == '2' && data[i+2] == '3') ? 1 : 2;
5.   }

(2. - 5.) Na początek wyliczamy długość tekstu wynikowego. Warto tu pamiętać, że jeśli godzina to 23 to w bloku zaszyfrowany jest tylko jeden znak. W przeciwnym 2 znaki.

6.   char* wynik = new char[dl + 1];
7.   for(int i = 0, j = 0; data[i]; i += 7){
8.     int a = (data[i + 1]) - '0';
9.     int b = (data[i + 2]) - '0';
10.     int c = (data[i + 4]) - '0';
11.     int d = (data[i + 5]) - '0';
12.     if(a * 10 + b == 23){
13.       wynik[j++] = valueToChar(c * 10 + d);
14.     } else {
15.       wynik[j++] = valueToChar(a * 10 + c);
16.       wynik[j++] = valueToChar(b * 10 + d);
17.     }
18.   }
19.   wynik[dl] = '\0';
20.   return wynik;
21. }

(6.) Alokujemy pamięć pod wynik. (7.) Dla każdego znaku w tekście: (8. - 11.) wyliczamy wartości a, b, c, d. (12.) Jeśli zestawienie ab = 23 to (13.) dopisujemy jeden znak złożony z cd. W przeciwnym wypadku dopisujemy dwa znaki: (15.) złożony z wartości a i c oraz (16.) b i d. (19.) Dopisujemy znak końca danych i (20.) zwracamy wynik.

Testowanie funkcji

Poniższa funkcja main() pozwoli przetestować napisane funkcje.

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

Przykładowo po wpisaniu tekstu INFORMACJA otrzymamy:

1. [23:19][11:45][23:58][23:18][00:42][23:17][01:49]

• Kod źródłowy Implementacja