Programowanie / Prog&Play
Obrazek zamiast Enigmy
Andrzej Stasiewicz
Zapewne słyszeli Państwo o możliwości ukrywania pewnych danych między pikselami map bitowych. Przyjrzyjmy się algorytmom tego interesującego zagadnienia
Czy w jednym obrazie można ukryć drugi tak, żeby nikt tego nie zauważył? A może nie obraz, a inne dane, np. przekazy tekstowe, tajne wiadomości, jakieś klucze i hasła?
Przyjrzyjmy się strukturze map bitowych i poszukajmy w nich takich schowków, w które można coś wpisać, nie psując samego obrazu. Oszacujemy również pojemność takich skrytek. Potem przygotujemy dwie aplikacje - jedna będzie umieszczać w nich nasze dane, a druga - wyciągać je stamtąd.
Zajmiemy się jednym typem map bitowych, w których każdy piksel jest opisany czterema bajtami (rysunek 1). Trzy z tych bajtów mają największe znaczenie, bo opisują amplitudy czerwieni, zieleni i błękitu piksela. Czwarty bajt jest niewykorzystany, ale nie nadaje się do naszych potrzeb z dwóch powodów: niektóre systemy jednak go wykorzystują, a w dodatku jest za słabo ukryty w strukturze obrazu. Umieszczenie w nim informacji nie byłoby dostatecznie finezyjnym szyfrowaniem danych.
PrawdziwyKolor Mamy wiele formatów map bitowych, ale najważniejszy jest ten, w którym każda z trzech składowych barwy zajmuje osiem bitów pamięci i w związku z tym może przyjmować jeden z 256 dostępnych stanów nasycenia. Format ten zazwyczaj jest nazywany TrueColor i szczególnie nadaje się do naszych potrzeb. | ||
Rysunek 1. Najpospolitsza mapa bitowa to ciąg czwórek bajtów, w których są zapisane amplitudy R, G i B poszczególnych pikseli. Kolejność kolorów może być inna. Jeden bajt jest niewykorzystany, a niektóre systemy zapisują w nim tzw. przezroczystość piksela.
Dokonamy prostego spostrzeżenia z dziedziny arytmetyki binarnej. Otóż modyfikowanie ciągu zer i jedynek ma bardzo duży wpływ na wartość, gdy zmieniane bity znajdują się z prawej strony, i bardzo mały, gdy zmieniane są bity z lewego końca (porównaj rysunek 2). Nawet wprowadzono nazwy bity starsze (bardziej z prawej strony) i młodsze (te z lewej) albo bardziej i mniej znaczące.
Rysunek 2. Modyfikowanie bitów młodszych nieznacznie zmienia wartość liczby zapisanej dwójkowo. Bity młodsze wykorzystamy do swoich celów, umieszczając w nich tajne informacje. Tylko ile ich możemy zająć? Ile możemy wykraść amplitudom kolorów R, G, B bez szkody dla obrazu?
Napiszemy program, który odczyta plik mapy bitowej, wyświetli obraz i umożliwi uszkodzenie określonej liczby bitów młodszych w kanałach R, G, B. Tak spreparowany obraz ponownie wyświetlimy i ocenimy jego jakość. Mamy nadzieję, że będzie można w ten sposób określać, ile bitów wolno wykradać amplitudom barw bez szkody dla jakości.
Klasyczny interfejs programu (porównaj rysunek 3) do obsługi map bitowych składa się z dwóch pól ScrollBox, które dostarczą suwaków przewijania dużych obrazów. Na tych polach znajdują się najważniejsze tutaj obrazy Image. U góry, w Panelu, który tylko rezerwuje miejsce na inne elementy interfejsu, znajdują się niezbędne przyciski oraz urządzenia do określania liczby uszkadzanych bitów młodszych. Programem takim zajmowaliśmy się już wielokrotnie i nie będę przypominać, jak się odczytuje i wyświetla mapę bitową z pliku dyskowego. Zainteresowanych Czytelników zapraszam do materiałów źródłowych, a my skoncentrujmy się na algorytmie uszkadzania:
Rysunek 3. Program umożliwia odczytanie obrazka i uszkodzenie określonej liczby bitów młodszych w każdym kanale barwowym. Uszkodzenie może polegać na wyzerowaniu bitów, ustawieniu ich w stany jedynek lub przypadkowym zmienianiu. Efekt jest zaskakujący - uszkodzenie nawet pięciu (z ośmiu) bitów w niewielkim stopniu narusza strukturę obrazka!
Najpierw odczytujemy ustawienia edytorków, określające liczbę bitów przeznaczonych do uszkodzenia. Potem - za pomocą dwóch standardowych pętli - przemierzamy obrazek i każdy jego piksel rozkładamy na amplitudy czerwieni, zieleni i błękitu. Następnie każdą amplitudę uszkadzamy wskazaną liczbę razy, kolejno zerując jej bity młodsze. Zajmuje się tym następująca funkcja elementarna:
Rysunek 4. Załóżmy, że w danej o nazwie bajt chcemy ustawić trzeci bit w stan 1 lub stan 0. Raczej nie znajdziemy gotowej funkcji, realizującej to zadanie. Przygotowujemy maskę wskazującą na wybrany bit (ma ona wartość dziesiętną 4), a na osiągnięcie wyżej wymienionego celu pozwalają proste operacje arytmetyki bitowej: w wypadku stanu 1 suma bitowa, a stanu 0 - negacja maski i iloczyn bitowy. Operacje te znajdziemy w każdym popularnym języku programowania.
Jak wskazuje nazwa funkcji, ustawia ona w zmiennej bajt bit o numerze poz w taki sposób, żeby przyjął wartość podaną w zmiennej bit (porównaj rysunek 4). Taką funkcję zazwyczaj musimy napisać sami. Ponieważ bitów jest niewiele, bo tylko osiem, po każdy sięgamy za pomocą zawczasu przygotowanej maski (moglibyśmy ją wyliczać programowo - każdy widzi, jaki ciąg wartości tam mamy). Zbiór gotowych masek umieszczamy w tablicy o nazwie maska (termin zwyczajowo stosowany na określenie ciągu binarnego tak dobranego, żeby pozwalał zaatakować określony układ bitów). To filtr na konkretny zestaw bitów - u nas na pojedyncze bity.
Drugą elementarną funkcją, jakby uzupełniającą powyższy algorytm, jest odczyt wskazanego bitu. Przyda nam się za chwilę, ale przytoczmy ją tutaj i zamknijmy temat sięgania po pojedyncze bity:
Wynik działania programu naprawdę zaskakuje. Uszkodzenie jednego czy dwóch bitów młodszych jest praktycznie niezauważalne w strukturze obrazu! Widoczny na zdjęciu, niedoskonały obraz czerwonego maka wytrzymuje uszkodzenie nawet czterch-pięciu bitów! Będą one naszymi mikroschowkami na tajne dane. Musimy jedynie uporządkować wszystko tak, aby w pojedynczych bitach zapisać (a potem z nich odczytać) większy ciąg danych, jakim niewątpliwie będzie ukrywany obrazek.
Zacznijmy od oszacowania przestrzeni, którą będziemy dysponować po przeznaczeniu na tajną skrytkę określonych liczb bitów. Jeśli obraz ma szer x wys pikseli, każdy piksel ma kanał R, z którego "wykradamy" il_r bitów, kanał G z il_g bitów i odpowiednio kanał B, to dysponujemy przestrzenią:
Bez trudu wyrazimy to w znacznie pospolitszym języku bajtów:
Od tej pory nasze kolejne programy będziemy uzupełniać algorytmem oceny rozmiaru tajnego schowka.
Teraz napiszemy program, który w młodszych bitach jednego obrazu umieści nie zera czy jedynki, a inny obrazek. Nie będzie to doskonałe rozwiązanie. Za chwilę napotkamy poważne problemy z odczytaniem tajnej fotografii, czyli wydobywaniem jej z młodszych bitów, niemniej jednak będzie to kolejny milowy krok w rozwoju naszej aplikacji.
Rysunek 5. Interfejs programu został wzbogacony: z lewej strony mamy obraz-nośnik, w środku obraz przeznaczony do ukrycia i z prawej złożenie tych obrazów. Jak widać, oddelegowano tutaj z każdego kanału barwowego aż po sześć bitów na obce dane, a mimo to obraz docelowy ciągle da się oglądać.
Interfejs programu zawiera dwa przyciski do odczytywania dwóch fotografii - raczej dużego nośnika i raczej małego obrazu do zaszyfrowania. Pokazuje też dostępną oraz wymaganą przestrzeń, mierzoną w bajtach (porównaj rysunek 5). Interesujące rzeczy zaczynają się dziać wtedy, gdy odczytamy oba obrazki, ustawimy rozmiary mikroprzestrzeni wykradanych z kanałów R, G, B i klikniemy przycisk z napisem Ukrywaj:
Rysunek 6. W dużym maku ukryto mały fiołek. Na lewym zdjęciu na bity fiołka oddelegowano po trzy młodsze bity w każdym kanale barwowym maka i żadnych zniekształceń praktycznie nie widać. Na środkowej fotografii oddelegowano po pięć bitów i już pojawiają się artefakty. Prawa fotografia jest nie do przyjęcia - po siedem bitów z każdych ośmiu pracuje na rzecz fiołka.
Najpierw przepisujemy obrazek wejściowy Image1 do obrazu docelowego Image3. Od tej pory będziemy pracować tylko na Image3. Przygotowujemy zmienne globalne, które zapamiętują aktualną pozycję w obrazku-nośniku. Ponieważ jest to dość skomplikowany fragment algorytmu, za chwilę wyjaśnimy go szczegółowo. Potem przemierzamy ukrywany obrazek, pobieramy kolor z każdego piksela i odczytujemy składową R tego koloru. Kolejno, bit po bicie, zapisujemy wszystkie osiem bitów tej składowej w obrazku docelowym. To samo robimy ze składową G i na koniec - składową B. Samym zapisem bitów zajmuje się zarysowana tutaj funkcja zapisz_bit(). Jest złożona, bo oprócz samej operacji zapisu, czyli ustawiania jakiegoś bitu, musi pilnować, w którym miejscu zapis się dokonuje. Do oznaczenia pozycji bitu, który jest przeznaczony do zapisania ukrywanego obrazka, służą aż cztery zmienne. X_POZ i Y_POZ wskazują piksel, którego bity akurat atakujemy. RGB_POZ oznacza kanał barwowy, który atakujemy. Jeśli wartość tej zmiennej wynosi 0, ustawiany bit znajduje się w obszarze zmiennej R, jeśli 1 - w G i 2 - w B. Ostatnia zmienna, BIT_POZ, określa, o który bit chodzi. Czwórka tych zmiennych przechowuje pozycję do zapisania kolejnego bitu, pochodzącego z ukrywanego obrazu.
Rysunek 7. Musimy zaopatrzyć nasze obrazy w nagłówki, zrozumiałe dla programu deszyfrującego. Umówimy się, że nasze nagłówki są zapisywane tymi technikami, o których tu dyskutujemy, ale zawsze na dwóch bitach wykradanych z kanałów R, G, B. Sam nagłówek niech liczy zawsze 72 bity i składa się z identyfikatora ustalonego z deszyfrującym, rozmiarów ukrytego obrazu i liczb określających rozmiary schowków w kanałach barwowych.
Po zapisaniu każdego bitu cztery zmienne pozycjonujące bit, X_POZ, Y_POZ, RGB_POZ oraz BIT_POZ, trzeba odpowiednio inkrementować, żeby zaczęły wskazywać miejsce zapisania następnego bitu. To wszystko może nie jest trudne, ale z pewnością wymaga skoncentrowania uwagi. Algorytm jest dość długi i prawdopodobnie uda się Państwu go zoptymalizować, a zainteresowanych organizacją tego wszystkiego zapraszam do materiałów źródłowych. Oto kluczowe punkty algorytmu:
Rysunek 8. Ta aplikacja przed ukrywanym obrazem wpisze 72 bity nagłówka. Użytkownik podaje identyfikator (jego wartość będzie wymagana do odszyfrowania obrazu) i rozmiary mikroschowków w kanałach R, G, B. Szerokość i wysokość ukrywanego obrazu są odczytywane automatycznie.
Skrótowo przytoczona funkcja zapisz_bit() sprawdza, czy w obrazku docelowym jest jeszcze miejsce na zapisanie jednobitowej danej. Jeśli tak, pobiera kolor kolejnego piksela, rozkłada go na składowe r, g, b i - zależnie od wskaźnika pozycji RGB_POZ - ustawia go w odpowiednim bajcie na pozycji BIT_POZ. Potem następuje zwiększenie wskaźników pozycji, aby te cztery kluczowe parametry wskazywały następny bit do ustawienia albo zasygnalizowały, że nośnik, czyli obrazek Image1, już się wyczerpał.
Mam nadzieję, że - spoglądając w materiały źródłowe - przebrną Państwo przez te nietrudne, ale dość soczyste algorytmy i napiszą aplikację do wpisywania jednego obrazka w drugi. Zatem pora napisać drugą - przeglądarkę tak spreparowanej pary obrazów (rysunek 9 i następny). Napotykamy tu jednak poważny problem z odtworzeniem ukrytego obrazka. Nie znamy jego rozmiarów, zatem nie wiemy, jak pociąć na wiersze masę pikseli, fragmentami powtykanych w młodsze bity obrazu głównego. Nie wiemy też, ile tych bitów szyfrujący przeznaczył na ukrywany obrazek (moglibyśmy się umówić, że zawsze deleguje np. po trzy, ale nie chcemy tak robić). Nie wiemy nawet, czy obrazek, który wpadł nam w ręce, zawiera tajną depeszę i czy deszyfrowanie w ogóle ma sens.
Rysunek 9. Rozkładaniem obrazu na nośnik i tajny obraz zajmuje się aplikacja deszyfrująca. Jednak nie każdy obraz ukrywa w sobie inny. Ten odczytano całkowicie przypadkowo i już po strukturze danych nagłówka widać, że coś jest nie w porządku. Potrzebna jest kontrola nagłówków, a ściślej - zapisanych w nich identyfikatorów, które stają się hasłem otwierającym sezam.
Musimy wrócić do aplikacji szyfrującej, aby zaproponować coś, co w terminologii map bitowych nazywa się nagłówkiem. Określi on wszystkie nieznane deszyfrującym wartości i pozwoli jednoznacznie stwierdzić, czy i jak obraz zaszyfrowano. Oto proponowana struktura nagłówka (porównaj rysunek 7):
Zapisując każdy ukrywany obraz, najpierw poświęcimy 72 bity na taki oto nagłówek. Po stronie odbiorczej zwrócimy szczególną uwagę na tajny identyfikator. Spytamy deszyfrującego o jego identyfikator. Jeśli będzie się zgadzał z identyfikatorem wpisanym w obraz, przystąpimy do deszyfrowania (rysunek 10).
Na zakończenie poświęćmy trochę uwagi aplikacji deszyfrującej. Realizuje ona jakby odwrotny ciąg czynności: najpierw odczytuje 72 bity nagłówka, zakładając, że zapisano je na każdych dwóch bitach początkowych pikseli. Potem następuje porównanie nagłówka odczytanego z podanym przez deszyfranta. Jeśli są zgodne, z dużym prawdopodobieństwem mamy tu zaszyty drugi obrazek. Ustalamy zatem rozmiary komponentu Image2 i przystępujemy do rekonstrukcji pikseli ukrytego obrazka.
Rysunek 10. Z odczytanego nagłówka wyciągamy identyfikator i porównujemy go z identyfikatorem podanym przez deszyfranta. Dopiero gdy okażą się zgodne, następuje odczytanie dalszych bitów i ekstrakcja ukrytego obrazu.
Najbardziej skomplikowaną funkcję zapisz_bit(), znaną z aplikacji szyfrującej, musimy teraz zastąpić jej odpowiednikiem odczytaj_bit():
Funkcja ta ma bardzo podobny rytm. Zamiast z elementarną funkcją ustaw_bit() pracuje z równie elementarną daj_bit(). W końcowej części zawiera taki sam algorytm modyfikowania czterech wskaźników pozycji bitu, aby wskazywały następny bit do odczytania. Ten nietrudny, ale dość długi i nieprzyjemny algorytm znajduje się w materiałach źródłowych. Odczytywane bity kolejno umieszczamy w amplitudach R, G, B i pracowicie rekonstruujemy wszystkie piksele ukrytego obrazka.