Strona główna » Algorytmy » Szyfry » Kodowanie Base64
 

Kodowanie Base64

Wstęp

Kodowanie Base64 jest to kodowanie, które pozwala przechowywać binarne dane zapisane przy pomocy kodu ASCII jako zwykły, czytelny tekst. W ten sposób dane mogę być bezpiecznie przesłane przez sieć bez obaw, że część wiadomości podczas przesyłania zniknie. Mogłoby się to zdarzyć, ponieważ różne serwery różnie interpretują dane i mogłoby się zdarzyć, że jeden z użytych serwerów wcześniej zakończył przesył danych niż powinien. Obecnie kodowanie Base64 jest bardzo popularne w Internecie. W tym kodowaniu są zapisywane załączniki w poczcie mailowej czy niektóre obrazki w Internecie.

Algorytm

Kodowanie Base64 składa się z zaledwie 64 znaków: wszystkich liter alfabetu łacińskiego, zarówno małych (a - z) i dużych (A - Z), cyfr (0 - 9) oraz dwóch znaków dodatkowych. Według oryginalnej konwencji są nimi znak plus + oraz dzielenia /. Ze względu na fakt, że informacje w tym kodowaniu mogą zostać przesłane w pasku URL przeglądarki to zaczęło się przyjmować, że pierwszym znakiem dodatkowym jest myślnik -, a drugim podkreślnik _.

W celu zamiany kodu ASCII na Base64 należy najpierw zapisać dane w postaci binarnej. Standardowo jeden znak reprezentuje 8 bitów. Base64 obejmuje 64 znaki, dlatego koduje każde kolejne 6 bitów informacji zapisanej binarnie. Pobrana wartość jest zamieniana na wartość dziesiętną. Następnie na podstawie tej wartości należy odczytać z tabelki jaki znak powinien zostać dopisany do wyniku. Poniższa tabelka była stosowana podczas pierwszej wersji tego kodowania:

Kod0123456789101112131415
ZnakABCDEFGHIJKLMNOP
Kod16171819202122232425262728293031
ZnakQRSTUVWXYZabcdef
Kod32333435363738394041424344454647
Znakghijklmnopqrstuv
Kod48495051525354555657585960616263
Znakwxyz0123456789+/

W przypadku, gdy na koniec został 1 lub dwa znaki to grupy bez żadnej wartości na podstawie znaków to należy dostawić znak =. Niektóre standardy Base64 tego jednak nie przewidują i zerowych grup 6 bitowych na końcu nie zaznaczają w żaden sposób.

Przykład

Szyfrując przykładowo słowo Test należy pogrupować znaki w grupy po 3 znaki: Tes oraz t (drugim przypadek zostanie opisany poniżej):

Tes
84101115
010101000110010101110011
2162151
VGVz

Zakodowane pierwszy trzy litery to ciąg znaków VGVz. Teraz można przejść do kodowania pojedynczego znaku. Ze względu na fakt, że jest tylko jeden to nieustawione sekcje po 6 bitów będą zastąpione przez =:

t
11697107
011101000000000000000000
29000
dA==

Ze względu na fakt, że jeden znak ma 8 bitów to ustawia on dwa znaki kodujące, dlatego pierwsza sekcja 000000 jest kodowana jako znak A, ale pozostałe nie są modyfikowane przez żaden znak, więc są zastępowane przez znak =. Ostatecznie zakodowany tekst Test to VGVzdA==.

W celu odczytania zakodowanej informacji należy zamienić wszystkie litery z tekstu zakodowanego na zapis binarny zgodnie z wartościami w tabelce, a następnie zapisać jeno koło drugiego. Drugi etap będzie polegał na grupowaniu bitów po 8, a następnie zamianie ich na konkretne znaki zgodnie z kodowaniem ASCII.

Implementacja

Kodowanie

W celu zakodowania danych najlepiej użyć manipulatorów bitów. Pozwoli to na napisanie najbardziej efektywnego kodu. Przykładowy kod zamieniający kodowanie ASCII na Base64 wygląda następująco:

  1. char* koduj_base64(char* data) {
  2.   char* table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  3.   int dl = (strlen(data) + 2) / 3;
  4.   int ibit = 7, ibajt = 0, izapis = 0;
  5.   char* wynik = new char[dl * 4 + 1];

(1.) Funkcja koduj_base64() przyjmuje tylko jeden argument data - tekst do zakodowania. Na sam koniec program zwróci tekst zapisany przy pomocy Base64. (2.) Zapamiętanie tabelki według której odbywa się kodowanie. (3.) Obliczenie z ilu grup 4 znaków 6 bitowych będzie składał się tekst wynikowy. Dodanie 2 pozwala na doliczenie grupy, która może mieć mniej niż 4 znaki 6 bitowe. Taka sytuacja ma miejsce kiedy długość tekstu nie jest wielokrotnością 3. (4.) Zadeklarowanie czterech indeksów: ibit - określa bit do pobrania z ibajtowego znaku, ibajt - określa aktualnie odczytywany znak z data oraz izapis - pamięta na której pozycji został zapisany ostatni znak dopisany do wyniku. (5.) Rezerwacja dla każdej grupy czterech bajtów oraz dodatkowego bajta dla znaku końca danych.

  1.   while (data[ibajt]) {
  2.     int val = 0;
  3.     for (int i = 5; i >= 0; i--) {
  4.       val |= ((data[ibajt] >> ibit) & 1) << i;
  5.       ibit--;
  6.       if (ibit == -1) {
  7.         ibit = 7;
  8.         ibajt++;
  9.       }
  10.     }
  11.     wynik[izapis++] = table[val];
  12.   }

(6.) Dopóki istnieją znaki do odczytania z tekstu do zakodowania to: (7.) ustal odczytaną wartość na 0. (8. - 17.) Odczytaj kolejne 6 bitów tekstu: (9.) pobierz odpowiedni bit i dopisz go do odczytywanej wartości val. (10.) Przejdź do następnego bitu i (11.) sprawdź czy nie trzeba przejść do następnego bitu. Jeśli tak to (12.) ustal odczytywanie następnego bajta od początku i (13.) zwiększ indeks odczytywanego bajtu. Na koniec (16.) każdej iteracji dopisz do wyniku znak reprezentowany przez wartość zmiennej val.

  1.   while (izapis % 4 != 0) {
  2.     wynik[izapis++] = '=';
  3.   }
  4.   wynik[izapis] = '\0';
  5.   return wynik;
  6. }

Na koniec pozostaje kwestia dopisania znaków =, które oznaczają, że kodowany tekst nie wykorzystał wszystkich miejsc w grupach, dlatego (18.) dla każdego takiego miejsca: (19.) dopisz znak. Na sam koniec funkcji: (21.) dopisz znak końca danych i (22.) zwróć wynik.

Dekodowanie

Podczas dekodowania istnieje potrzeba odnalezienia najpierw wartości znaku według określonej tablicy i dopiero jej zapis binarny należy dopisać do wyniku. Do wyszukiwania wartości znaku algorytm posługuje się funkcją znajdzPozycje(), który dla danego tekstu data zwraca pozycję znaku c. (W przypadku braku znaku -1, ale zakładamy poprawność zapisu Base64, dlatego nie ma to znaczenia co zwróci funkcja w tym przypadku).

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

Wtedy do dekodowania posłuży funkcja dekoduj_base64(), która przyjmuje argument data - tekst do rozkodowania i zwróci dane zapisane binarne według tablicy ASCII.

  1. char* dekoduj_base64(char* data) {
  2.   char* table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  3.   int dl = strlen(data) / 4;
  4.   int ibit = 5, ibajt = 0, izapis = 0, izapisbit = 7;
  5.   char* wynik = new char[dl * 3 + 1];
  6.   int valr = 0;

(2.) Zadeklaruj dane tablicy. (3.) Oblicz ile grup zostało zakodowanych. (4.) Zadeklaruj 4 różne indeksy: ibit - aktualnie odczytywany bit z ibajta tekstu zakodowanego, ibajt - aktualnie rozkodowywany znak tekstu zakodowanego, izapis - aktualnie zapisywany bajt tekstu rozkodowanego oraz izapisbit - określa, który bit bajta wynikowego jest aktualnie modyfikowany. (5.) Zadeklaruj tablicę wynikową wiedząc, że każda grupa to trzy rozkodowane znaki. (6.) Zadeklaruj zmienną pomocniczą do buforowania odczytanych bitów.

  1.   while (data[ibajt]) {
  2.     int val = znajdzPozycje(table, data[ibajt]);
  3.     for (int i = 5; i >= 0; i--) {
  4.       valr |= ((val >> i) & 1) << izapisbit;
  5.       ibit--;
  6.       if (ibit == -1) {
  7.         ibit = 5;
  8.         ibajt++;
  9.       }
  10.       izapisbit--;
  11.       if (izapisbit == -1) {
  12.         izapisbit = 7;
  13.         wynik[izapis++] = valr;
  14.         if (valr == '=') {
  15.           while (!data[ibajt])
  16.             ibajt++;
  17.         }
  18.         valr = 0;
  19.       }
  20.     }
  21.   }

(7.) Dla każdego zakodowanego znaku: (8.) znajdź wartość w tabelce i (9.) rozpocznij przepisywanie wszystkich 6 bitów: (10.) dopisz bit do zmiennej valr. (11.) Zmniejsz indeks odczytywanego bitu z pobranej wartości i (12.) jeśli zostały odczytane wszystkie bity to (13.) przejdź do następnego bitu w (14.) następnym bajcie. (16.) Zmniejsz również indeks zapisywanego bitu. (17.) Jeśli już zostało zapisane 8 bitów to: (18.) wróć rozpocznij przepisywanie od nowa i (19.) dopisz odczytaną wartość do tekstu wynikowego. Jeśli (20.) następny znak to znak równości to (21. - 23.) przesuń indeks odczytywanego znaku z data na znak końca danych. Jednak, aby następna iteracja została wykonana prawidłowo to (25.) należy zresetować odczytywaną wartość valr.

  1.   wynik[izapis - 2] = '\0';
  2.   return wynik;
  3. }

Na koniec działania funkcji należy (28.) dopisać znak końca danych na odpowiednim miejscu i (29.) zwrócić tekst wynikowy.

Testowanie funkcji

Działanie funkcji można sprawdzić przy pomocy poniższej funkcji. Po uruchomieniu wystarczy wpisać żądany tekst i zatwierdzić, aby program wypisał zakodowaną tekst zakodowany w Base64.

  1. int main () {
  2.   char* txt = new char[512];
  3.   cin.getline(txt, 512);
  4.   char* txtk = koduj_base64(txt);
  5.   cout << txtk << endl;
  6.   char* txtr = dekoduj_base64(txtk);
  7.   cout << txtr << endl;
  8.   delete[] txt, txtk, txtr;
  9.   system("pause");
  10.   return 0;
  11. }