Strona główna » Algorytmy » Szyfry » Szyfr Komórkowy
 

Szyfr Komórkowy

O szyfrze

Do szyfrowania będziemy potrzebowali klawiaturę z klasycznych telefonów, która poglądowo wygląda tak:

1     2 abc 3 def 
4 ghi 5 jkl 6 mno 
7 pqrs8 tuv 9 wxyz
 *0  _  #

Chcąc z klawiatury napisać literę k należało nacisnąć przycisk z 5 2 razy. Szyfrowanie opiera się właśnie na metodzie wpisywania. Każdą literę szyfrujemy jako dwie cyfry rozdzielone przecinkiem. Pierwsza cyfra to cyfra występująca na danym przycisku, a druga cyfr to ile razy taki przycisk należy nacisnąć. Kolejne znaki oddzielamy średnikiem. Zakładamy, że podkreślnik to przycisk 0, znak 1, a spacja to przycisk 1, znak 1.

Przykładowo szyfrując wyraz informacja: szukamy i, znajduje się pod przyciskiem z cyfrą 4 i jest trzecią literą, więc zapisujemy jako 4,3. Czynność powtarzamy dla każdej litery:

Literainformacja
Szyfrogram4,36,23,36,37,36,12,12,35,12,1

Teraz odczytując kolejne zaszyfrowane znaki i oddzielając średnikiem odczytujemy szyfrogram 4,3;6,2;3,3;6,3;7,3;6,1:2,1;2,3;5,1;2,1.

Chcąc odszyfrować należy pamiętać, że bierzemy każdą parę cyfr rozdzieloną przecinkiem i pierwsza cyfra wskaże nam na który przycisk patrzymy, a druga cyfra, którą n-tą cyfrę mamy wybrać. Przykładowo mając 2,3 patrzymy na przycisk o numerze 2 i wybieramy 3 literę.

Implementacja

Strategia zapisu klawiszy

Do przechowywania wyglądu klawiatury nie będziemy używać tablic, ani funkcji switch - wystarczy nam zwykłe pojedyncze słowo. Zakładamy, że znaki grupujemy według cyfry występującej na danym klawiszu. Następnie sortujemy grupy według ich "numeru". Kolejne grupy rozdzielamy średnikiem:

  1. _; ;abc;def;ghi;jkl;mno;pqrs;tuv;wxyz

Takie rozwiązanie pozwoli nam na proste wyszukiwanie znaku na klawiaturze i jeśli zajdzie potrzeba to zamiana małych liter z klawiatury na duże, aby i te móc zaszyfrować:

  1. _; ;ABC;DEF;GHI;JKL;MNO;PQRS;TUV;WXYZ

Założenia

Na wejściu otrzymujemy ciąg złożonych z małych litera alfabetu łacińskiego, znaki spacji oraz podkreślnika. Nasze zadanie polega na zaszyfrowaniu wprowadzonego tekstu zgodnie szyfrem komórkowym i wypisanie go na wyjście.

Przykładowo dla danych:

  1. informacja

otrzymamy:

  1. 4,3;6,2;3,3;6,3;7,3;6,1:2,1;2,3;5,1;2,1

Szyfrowanie

Nasza funkcja będzie przyjmowała dwa argumenty: keyboard - ciąg znaków opisujący jak wygląda znak oraz txt - tekst, który mamy zaszyfrować:

  1. char* cipher(const char* keyboard, const char* txt){
  2.   int dl = strlen(txt)*4;
  3.   char* wynik = new char[dl];

(2.) Wyliczamy długość tekstu wynikowego i (3.) alokujemy pamięć pod wynik.

  1.   for(int i = 0; txt[i]; i++){
  2.     int group=0, pos=0, j=0;
  3.     while(keyboard[j]!=txt[i]){
  4.       if(keyboard[j]==';'){
  5.         group++;
  6.         pos = 0;
  7.       } else {
  8.         pos++;
  9.       }
  10.       j++;
  11.     }

(4.) Dla każdego znaku rozpoczynamy szyfrowanie. (5.) Deklarujemy zmienne pomocnicze, które pomogą zapamiętać gdzie został odnaleziony i-ty znak na klawiaturze. (6.) Wyszukiwanie znaku prowadzimy, aż na j-tym miejscu znajdziemy żądany znak. (7.) Jeśli podczas przeszukiwania znajdziemy średnik to znaczy, że (8.) mamy nową grupę i (9.) pozycje liczymy od nowa. Jeśli jednak znak nie jest średnikiem to (11.) zwiększamy pozycję pos znaku w grupie. (13.) Na koniec każdej iteracji zwiększamy j o jeden.

  1.     wynik[4*i] = group + '0';
  2.     wynik[4*i + 1] = ',';
  3.     wynik[4*i + 2] = pos + '1';
  4.     wynik[4*i + 3] = ';';
  5.   }
  6.   wynik[dl - 1] = '\0';
  7.   return wynik;
  8. }

Wszystkie wyliczone wartości odpowiednio zapisujemy w tablicy wynik: (15.) Numer grupy (począwszy od zera), (16.) przecinek, (17.) Numer pozycji znaku w grupie (począwszy od jeden) oraz (18.) znak rozdzielający średnik. Po zaszyfrowaniu ostatniego znaku: (20.) Dopisujemy znak \0 oraz (21.) zwracamy wynik.

Deszyfrowanie

Podczas deszyfrowania również przyjmiemy tylko dwa argumenty: keyboard - ciag znaków opisujący jak wygląda znak oraz txt - tekst, który mamy zaszyfrować:

  1. char* decipher(const char* keyboard, const char* txt){
  2.   int dl = strlen(txt)/4 + 1;
  3.   char* wynik = new char[dl];

Deszyfrowanie rozpoczynamy od (2.) obliczenia długości tekstu wynikowego oraz alokacji pamięć pod tekst jawny.

  1.   for(int i = 0; i < dl; i++){
  2.     int group=txt[4*i] - '0', pos=txt[4*i+2] - '1';
  3.     int sgroup=0, spos=0, sj=0;
  4.     while(!(sgroup == group && spos == pos)){
  5.       if(keyboard[sj]==';'){
  6.         sgroup++;
  7.         spos = 0;
  8.       } else {
  9.         spos++;
  10.       }
  11.       sj++;
  12.     }

(4.) Dla każdego znaku obliczamy w której grupie group i na jakiej pozycji pos znajduje się znak. (5.) Deklarujemy też sgroup, spos, sj, które pomogą nam sprawdzić właściwości aktualnie przeglądanego znaku na klawiaturze. (6.) Tym razem przeszukujemy klawiaturę aż numer grupy i pozycja znalezionego znaku odpowiada tym odczytanym z szyfrogramu.

  1.     wynik[i]=keyboard[sj];
  2.   }
  3.   wynik[dl] = '\0';
  4.   return wynik;
  5. }

(16.) Odpowiedni znak przepisujemy do wynik. (18.) Dopisujemy znak \0 i (19.) zwracamy wynik.

Testowanie funkcji

Funkcja main(), która przetestuje działanie programu wygląda następująco:

  1. int main () {
  2.   char* keyboard = "_; ;abc;def;ghi;jkl;mno;pqrs;tuv;wxyz";
  3.   char* txt = new char[128];
  4.   cin.getline(txt, 128);
  5.   char* txtc = cipher(keyboard, txt);
  6.   cout << txtc << endl;
  7.   char* txtd = decipher(keyboard, txtc);
  8.   cout << txtd << endl;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz kod klawiatury, która będzie szyfrować nie tylko małe znaki alfabetu łacińskiego, ale również cyfry.

Przykładowo dla danych:

  1. informacja 2016
otrzymujemy:
  1. 4,4;6,3;3,4;6,4;7,4;6,2;2,2;2,4;5,2;2,2;1,2;2,1;0,1;1,1;6,1

Zadanie 2

Napisz funkcję, która przy pomocy domyślnej klawiatury zaszyfruje i odszyfruje duże i małe litery. Zakładamy, że cyfry użyte do szyfrowania małych liter są dalej rozdzielone przecinkiem, ale cyfry zaszyfrowanych dużych liter będą rozdzielone kropką.

Przykładowo dla danych:

  1. TOP Secret
otrzymujemy:
  1. 8.2;6.4;7.2;1,2;7.5;3,3;2,4;7,4;3,3;8,2