Algorytmy

Ukrywanie tekstu

W ostatnim czasie pojawiło się kilka artykułów na temat sposobu ukrywania plików w obrazkach. Jest to bardzo dobry sposób bezpiecznego przesyłania e-maili. Jak wiadomo w prosty sposób można przechwycić tekst przysłany drogą elektroniczną. Dużo trudniej jest wyciągnąć tekst z plików binarnych (np. dźwięk, filmy oraz właśnie obrazki).


Wbrew pozorom ukrycie tekstu w obrazku jest łatwe, jak zobaczymy dużo więcej wysiłku zabierze nam obsługa formatu graficznego, niż samo kodowanie informacji w nim. Aby maksymalnie uprościć rozważania oraz implementację, przyjąłem, że ukrywać będziemy tylko tekst, a obrazkiem, w którym będziemy to robić będzie bitmapa systemu Windows. Nadaje się ona bardzo dobrze do tego celu z kilku powodów:
ma prosty format
nie stosuje kompresji stratnej (takiej, jak np. JPEG). Stosowanie kompresji stratnej uniemożliwia prawidłowe odczytanie zapisanej informacji
jest DUŻA, dzięki temu można w niej dużo ukryć. Jeżeli komuś przeszkadza jej rozmiar np. w przesyłaniu e-mailem, to można po zapisaniu w niej informacji zamienić BMP w jakiś plik graficzny z kompresją bezstrantą (np. GIF). Po przesłaniu i przetworzeniu z powrotem w BMP można spokojnie odczytać informacje.


Przejdźmy teraz do opisu zapisywania informacji w bitmapie. Jak wiadomo w plikach BMP każdy piksel jest opisany za pomocą jednego z 256 kolorów (8-bit) lub za pomocą trójki bajtów (24-bit), które opisują zawartość koloru czerwonego, zielonego i niebieskiego.
W dalszym opisie posłużę się wersją 8-bit, choć wszystko będzie prawidłowo działać także dla wersji 24-bit.
Jeśli utworzymy nową, 8 bitową bitmapę składającą się z jednego punktu w kolorze białym, to punkt ten zostanie opisany za pomocą liczby 255D (FFH). Jest to numer koloru białego, jak nietrudno się domyśleć punkt czarny będzie opisany przez liczę 0. Ponieważ przyjęliśmy, że bitmapa ma 8-bitową paletę kolorów, to każdy piksel będzie opisany przez 8-bitową liczbę, tzn. liczbę z zakresu <0;255>. Jeśli nasza bitmapa byłaby 24-bitowa, to każdy punkt byłby opisany przez 3 bajty (3*8=24).
Format BMP opisuje ciąg pikseli, z których składa się obrazek, czyli jeżeli utworzymy 8-bitową bitmapę składającą się z 4 punktów, to w bitmapie zostaną one opisane jako 4 bajty charakteryzujące kolor odpowiedniego punktu. Np niech obrazek będzie kwadratem z bokiem o długości 2 punkty, i niech pierwsza linia będzie biała a druga czarna. W bitmapie będziemy mieli następujący zapis: FF FF 00 00, czyli w systemie dziesiętnym 255 255 0 0 ( 255-kolor biały, 0- czarny).


Aby z powyższego ciągu móc zbudować kwadrat musimy wiedzieć, jaka jest długość i wysokość obrazka. Te informacje, a także inne (liczba bitów na kolor, rozdzielczość i inne) są zapisane w nagłówku bitmapy. Tak więc bitmapa jest zbudowana z nagłówku zawierającego ważne informacje oraz z obszaru danych zawierającego ciąg bajtów opisujące kolejne punkty obrazu. Ciekawostką jest fakt, że obszar danych zawiera opis obrazu od jego ostatniego punktu (tzn. prawy, dolny róg). Czyli rysując obrazek wprost z obszaru danych otrzymamy obrazek odwrócony dołem do góry i lewą stroną na prawą. To jednak nam nie przeszkadza.


Skoro już wiemy, jak są kodowane poszczególne punkty rysunku przejdźmy do problemu ukrycia w nich informacji. Załóżmy, że mamy obrazek składający się z jednej linii 8 punktów, czyli bitmapa ma rozmiar 8*1. Obszar danych będzie się składał z 8 bajtów opisujących kolejne punkty, np. 23 45 128 248 53 76 54 91. Po zamianie tych wartości na system binarny otrzymamy: 00010111 00101101 10000000 11111000 00110101 01001100 00110110 01011011. Podkreślone bity są tzw. bitami najmłodszymi. Mają one najmniejszy wpływ na wartość liczby (jeśli ostatni bit ma wartość 0, to liczba jest parzysta, jeśli 1 to nieparzysta). Widać więc, że zmieniając ostatni bit liczby zmieniamy jej wartość tylko o 20=1, podczas gdy zmieniając np. ostatni (najstarszy) bit zmieniamy wartość o 27=128. Jeżeli chcemy manipulować kolorami poszczególnych punktów zmieniając te kolory w najmniejszym stopniu, to musimy zmieniać właśnie najmłodszy bit. Każdy znak ASCII ma 8-bitowy kod, więc do zapisania każdego znaku musimy zmienić najmłodszy bit 8 punktów. Powiedzmy, że chcemy w naszym obrazku ukryć literę 'a'. Jej kod ASCII ma wartość 97, czyli 01100001. Modyfikując kolory 8 punktów naszego przykładowego obrazka otrzymamy obszar taki danych: 00010110 00101101 10000001 11111000 00110100 01001100 00110110 01011011. Czcionką pogrubioną zaznaczyłem te bity, które musieliśmy zmienić (gdyż oryginalna wartość była inna niż ta, którą potrzebujemy). Widać teraz, że najmłodsze bity powyższych 8 punktów wyznaczają ciąg 8 bitów będący kodem ASCII litery 'a', którą ukryliśmy. Zapisując ją w obrazku zmieniliśmy wartość koloru co najwyżej o 1 (choć aż w 5 przypadkach nie musieliśmy niczego zmieniać). Dzięki temu różnica między oryginalną bitmapą a bitmapą zmodyfikowaną jest bardzo mała.


W taki właśnie sposób możemy zakodować kolejne znaki naszego tekstu, do opisania każdego potrzebujemy 8 punktów rysunku. Widać więc, że rysunek musi mieć 8 razy więcej pikseli niż tekst liter. Dodatkowo potrzebujemy jeszcze jednego znaku, który powie nam, że ukrywany tekst się już skończył. Ja w mojej implementacji na końcu tekstu dodaję ciąg 8 wyzerowanych bitów, co oznacza, że bajty po nim nie przechowują już żadnej interesującej dla mnie informacji tekstowej.



W implementacji tego algorytmu musimy najpierw wyczytać kilka ważnych informacji z nagłówka bitmapy:
od 10 do 14 bajtu od początku bitmapy znajduje się czterobajtowa liczba będąca wskaźnikiem do obszaru danych. Liczba ta jest nam potrzebna, gdyż dopiero od tej pozycji możemy zacząć kodować informacje, cały nagłówek musi pozostać niezmieniony
od 18 do 22 bajtu znajduje się szerokość obrazka w punktach. Wartość ta będzie nam potrzebna do obliczenia liczby nieznaczących zer na końcu każdego wiersza (zob. niżej)
od 34 do 38 bajtu znajduje się długość obszaru danych, wartość ta musi być ośmiokrotnie większa od wielkości pliku tekstowego
Odczytując czterobajtowe liczby musimy pamiętać o sposobie kodowania przyjętym w komputerach klasy PC: starsze bity znajdują się po prawej stronie, tzn. po odczytaniu czterech bajtów musimy zamienić je miejscami, np. odczytaliśmy adres obszaru danych: bajty A, B C i D w takiej właśnie kolejności i mają one wartości: A=54, B=4, C=0, D=0. Zamieniamy system na binarny i otrzymujemy: A=00110110, B=00000100, C=00000000, D=00000000. Scalamy bajty w następujący sposób: DCBA i otrzymujemy następującą liczbę: 00000000000000000000010000110110. Po zamianie z powrotem na system dziesiętny otrzymamy 1078. Wiemy więc, że obszar danych rozpoczyna się w 1078 bajcie.


Przy omawianiu nagłówku bitmapy wspomniałem, że przyda się nam szerokość obrazka. Po co? Po ciągu opisującym każdy wiersz obrazka znajduje się ciąg bajtów o wartości 0. Może być ich 0, 1, 2 lub 3. Nigdzie nie znalazłem opisu znaczenia tych zer, ale wygląda to na coś w stylu sumy kontrolnej. Liczba zer na końcu wierszu jest opisana wzorem: K=(szerokość obrazka modulo 4). Czyli jeżeli nasz obrazek składa się z kolumny bitów (szerokość wiersza=1), to po każdym 1 bajcie nastąpią 3 zera, (1 mod 4)=3. jeżeli nasz obrazek ma wymiary 3*4, to obszar danych będzie ciągiem (bi_j oznacza bajt opisujący i-ty punkt w j-tej kolumnie) : b1_1 b2_1 b3_1 0 b1_2 b2_2 b3_2 0 b1_3 b2_3 b3_3 0 b1_4 b2_4 b3_4 0. Czyli liczba zer pomiędzy wierszami wynosi (3 mod 4)=1.
Dla obrazka o szerokości 4 nie będzie zer, gdyż (4 mod 4)=0.
Bajtów tych lepiej nie zmieniać, niektóre programy graficzne mogą badać ich wartość i w przypadku gdy nie będzie to 0, wyświetlą komunikat, że obrazek zawiera błąd.



Przykładowy program prezentujący działanie algorytmu znajduje się na stronie: http://download.4programmers.net/bmp-hide.zip

Michał Knasiecki