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

Szyfr Bacona

Opis szyfru

Szyfr Bacona to rodzaj steganografii - pozwala ukryć wiadomość niż ją faktycznie zaszyfrować. Metoda wymyślona przez Francisa Bacona w 1605. Do szyfrowania została opracowana specjalna tabelka, która wskazuje jaką literę zamienić na jaką. Znaki takie jak spacja, kropka nie są szyfrowane. Poziom zabezpieczenia danych tym szyfrem jest bardzo niskie.

aAAAAA
bAAAAB
cAAABA
dAAABB
eAABAA
fAABAB
gAABBA
hAABBB
i, jABAAA
kABAAB
lABABA
mABABB
nABBAA
oABBAB
pABBBA
qABBBB
rBAAAA
sBAAAB
tBAABA
u, vBAABB
wBABAA
xBABAB
yBABBA
zBABBB

Implementacja

Szyfrowanie

W celu optymalizacji wykorzystania pamięci naszym pierwszym krokiem będzie policzenie jak długi będzie tekst wynikowy. Funkcja kodująca encodeTxt() będzie przyjmowała argument będący tekstem do zakodowania i zwróci wskaźnik na nowy łańcuch wynikowy, który będzie tekstem zakodowanym.

  1. char* encodeTxt (char* text) {
  2.   int dl = 0;
  3.   for(int i=0; text[i]; i++){
  4.     if(text[i]>='a' && text[i]<='z'){
  5.       dl+=5;
  6.     } else {
  7.       dl++;
  8.     }
  9.   }

(1.) Deklarujemy funkcje encodeTxt(). (2.) Deklarujemy zmienną dl, która będzie przechowywać długość tekstu wynikowego. (3.) Dla każdego znaku w tekście: (4.) sprawdzamy czy jest małą literą: jeśli tak to zwiększamy dl o 5, bo na tyle zostanie zamieniona litera. Jeśli jednak nie jest literą to (7.) zwiększamy długość tekstu wynikowego tylko o jeden.

  1.   char* code = new char[dl + 1];
  2.   for(int i=0, j=0; text[i]; i++){
  3.     if(text[i]>='a' && text[i]<='z'){
  4.       if(text[i]>='j') text[i]--;
  5.       if(text[i]>='v') text[i]--;
  6.       for(int t=16; t>0; t/=2){
  7.         code[j++]=(t & (text[i]-'a')) ? 'B' : 'A';
  8.       }
  9.     } else {
  10.       code[j++]=text[i];
  11.     }
  12.   }

(10.) Deklarujemy tekst wynikowy o długości dl wcześniej wyliczonej. Dodajemy jeden, aby na końcu można było umieścić znak końca tekstu \0. (11.) Rozpoczynamy pętle dla każdego znaku w tekście do zaszyfrowania. Deklarujemy tutaj zmienna i i j. Zmienna i pomoże nam określić, który znak tekstu do zaszyfrowania przeglądamy, a j, który znak w zakodowanym tekście szyfrujemy.

(12.) Jeśli dany znak jest literą to go szyfrujemy. Najprostszym sposobem byłoby wczytać tabelkę do programu i się do niej odwoływać. Niemniej warto zauważyć, że jeśli zamienić A na 0 i B na 1 to otrzymamy kolejne wartości binarne począwszy od 0, więc wystarczy odczytać kolejne bity danej litery, aby zamienić ją na postać binarną i zapisać przy pomocy A i B. Należy zauważyć, że I/J oraz U/V zamieniają się na ten sam zestaw znaków, więc (13.) jeśli znak jest J lub po to musimy odjąć 1, a jeśli (14.) jest on V lub literą po V to znowu musimy odjąć 1.

Do zamiany z liczby na postać binarną posłużymy się operatorem bitowym &. (15. - 17.) Pobieramy kolejno 6, 4, ... , 1 wartość bitu znaku pomniejszonego o znak 'a', ponieważ a ma mieć wartość binarną 0. Jeśli wczytany bit jest 1 to wpisujemy B w przeciwnym wypadku A. Za każdym razem zwiększamy tylko wskaźnik j, który wskazuje, który znak tekstu zaszyfrowanego zapisujemy. Jeśli jednak podany znak nie jest literą to tylko go przepisujemy.

  1.   code[dl]='\0';
  2.   return code;
  3. }

Przed (24.) zwróceniem wyniku (23.) dopisujemy do łańcucha znaków znak końca linii.

Deszyfrowanie

Podczas dekodowania również najpierw ustalimy długość tekstu, a potem zamienimy tekst:

  1. char* decodeTxt (char* text) {
  2.   int dl = 0;
  3.   for(int i=0; text[i]; i++){
  4.     if(text[i]=='A' || text[i]=='B'){
  5.       i+=4;
  6.     }
  7.     dl++;
  8.   }

(1.) Deklarujemy funkcje. (2.) Deklarujemy zmienną dl, która będzie przechowywać długość tekstu wynikowego. (3.) Dla każdego znaku w tekście, który (4.) jest znakiem A lub B przesuwamy przeszukiwany indeks o 4. Za każdym razem (5.) zwiększamy długość tekstu o 1.

  1.   char* code = new char[dl + 1];
  2.   for(int i=0, j=0; text[i]; i++){
  3.     if(text[i]=='A' || text[i]=='B'){
  4.       char character = 'a';
  5.       for(int t=16; t>0; t/=2){
  6.         if(text[i++]=='B'){
  7.           character+=t;
  8.         }
  9.       }
  10.       if(character>='j') character++;
  11.       if(character>='v') character++;
  12.       code[j++]=character;
  13.       i--;
  14.     } else {
  15.       code[j++]=text[i];
  16.     }
  17.   }

(8.) Deklarujemy tekst wynikowy o długości dl wcześniej wyliczonej. Dodajemy jeden, aby na końcu można było umieścić znak końca tekstu \0. (9.) Rozpoczynamy pętle dla każdego znaku w tekście do zaszyfrowania. Deklarujemy tutaj zmienna i i j. Zmienna i pomoże nam określić, który znak tekstu do zaszyfrowania przeglądamy, a j, który znak w zakodowanym tekście szyfrujemy.

(10.) Jeśli jest literą A lub B to deklarujemy character do którego będziemy dodawać kolejne odczytane wartości. (11. - 15.) Dla pięciu kolejnych liter sprawdzamy czy znak jest literą B. Jeśli jest to dodajemy wartość t do znaku character. (16. 17.) Pamiętamy o ponownym przesunięciu o tyle ile przesunęliśmy znak podczas szyfrowania. (18.) Wyliczony kod znaku dopisujemy do tekstu wynikowego. (19.) Podczas operacji w (13.) przesunęliśmy indeks na następny znak po 5 do sprawdzenia, dlatego cofamy o jeden, aby podczas kolejnej iteracji wskaźnik wskazywał właściwy kolejny znak.

W przypadku, gdy wczytany znak do zaszyfrowania nie jest literą A lub B to tylko go przepisujemy.

  1.   code[dl]='\0';
  2.   return code;
  3. }

Przed (27.) zwróceniem wyniku (26.) dopisujemy do łańcucha znaków znak końca linii.

Testowanie funkcji

Poniższa funkcja main() wczyta od użytkownika tekst do zaszyfrowania, a następnie wypisze szyfrogram, a potem rozkoduje szyfrogram. Ma to na celu sprawdzenie poprawności działania funkcji.

  1. int main () {
  2.   char* text = new char[128];
  3.   cin.getline(text, 128);
  4.   char* encodedTxt = encodeTxt(text);
  5.   cout << encodedTxt << endl;
  6.   char* decodedTxt = decodeTxt(encodedTxt);
  7.   cout << decodedTxt << endl;
  8.   delete[] text, encodedTxt, decodedTxt;
  9.   system("pause");
  10.   return 0;
  11. }

Zadania

Zadanie 1

Napisz algorytm o podobnym działaniu, który: