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:

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):

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 =:

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.

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

(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.

18.   while (izapis % 4 != 0) {
19.     wynik[izapis++] = '=';
20.   }
21.   wynik[izapis] = '\0';
22.   return wynik;
23. }

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.

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

(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.

28.   wynik[izapis - 2] = '\0';
29.   return wynik;
30. }

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. }

• Kod źródłowy Implementacja