Przeczytaj
Kompresja multimediów
Skąd wiemy, że pobrany z sieci plik jest tym samym, który został wysłany z serwera? Jeżeli nie dojdzie do zdarzeń takich jak zafałszowanie transmisji w wyniku ataku typu man‑in‑the‑middleman‑in‑the‑middle. jesteśmy w stanie (do pewnego stopnia) to sprawdzić.
We wcześniejszych e‑materiałach omawialiśmy mechanizmy kompresji, które pozwalają przekształcać informacje w taki sposób, aby wysyłane przez sieć dane miały mniejszą objętość. Załóżmy jednak, że na skutek zakłóceń na łączach do skompresowanego pliku, który odebraliśmy, wkradł się błąd. Może być to choćby jeden przekłamany bit, który spowoduje, że cała wiadomość zostanie błędnie zdekodowana.
Skoro jednak chodzi tylko o jeden bit, to skąd mamy wiedzieć, że doszło do przekłamania? Dekodowanie wiadomości może (choć nie musi) udać się nawet wtedy, gdy bity są zafałszowane.
Jeżeli wiadomością jest ciąg znaków, które w oryginale składały się na zdania w języku znanym odbiorcy, łatwo jest stwierdzić, że informacja została źle zdekodowana.
Co się jednak stanie, gdy pobierzemy plik wykonywalny? Dekompresujemy go (jeśli jest to konieczne) i próbujemy uruchomić. Niestety, pojawiają się komunikaty o błędach, a program nie działa.
Czy jesteśmy w stanie powiedzieć, że program jest wadliwy? A może po prostu brakuje nam jakiegoś sterownika? A może jednak plik, który pobraliśmy, nie jest tym samym, który został wysłany?
Spróbujemy odpowiedzieć na ostatnie z tych pytań.
Załóżmy, że posługujemy się następującymi słowami kodowymi:
A: 00
B: 01
C: 11
D: 10
Jeżeli otrzymamy wiadomość mającą postać: 00 01 11 10, możemy ją bez problemu odkodować. Otrzymamy ciąg „ABCD”.
Skąd jednak pewność, że taka właśnie wiadomość została wysłana? Poszczególne słowa kodowe różnią się pojedynczymi bitami. Nietrudno sobie wyobrazić, że dojdzie do przekłamania transmisji.
Kod, który służy do sprawdzenia, czy informacje (pliki) zostały przesłane poprawnie, nazywany jest kodem nadmiarowym.
Jedną z metod sprawdzenia poprawności danych jest kontrola parzystości. W jej przypadku do przesyłanej wiadomości dołącza się dodatkowy bit kontrolny.
Zależnie od przyjętej konwencji odbiorca wiadomości sprawdza wartość bitu parzystości lub bitu nieparzystości.
Bit parzystości ma wartość zero, jeżeli liczba znaków „1” w przesłanej wiadomości jest parzysta. Jeśli liczba jedynek jest nieparzysta, bit ten ma wartość jeden.
Bit nieparzystości ma wartość jeden, jeżeli liczba znaków „1” w wiadomości jest parzysta. Jeśli liczba jedynek jest nieparzysta, bit ten ma wartość zero.
Załóżmy, że mamy następujące słowa kodowe:
A: 00
B: 01
C: 11
D: 10
Wiadomość, którą otrzymaliśmy, to 00 01 11 10 1. Ostatni bit (znajdujący się najdalej po prawej stronie) jest bitem parzystości.
Ponieważ treść wiadomości zawiera cztery cyfry „1”, bit parzystości powinien mieć wartość 0. Należy przypuszczać, że treść wiadomości uległa przekłamaniu w czasie transmisji. W tej sytuacji możemy poprosić o ponowne przesłanie wiadomości.
Niestety, z tą metodą kontroli wiążą się pewne problemy.
Przede wszystkim nie wiadomo, czy przekłamaniu nie uległ bit parzystości. W takim przypadku bezbłędnie przekazana treść komunikatu uchodzi za zafałszowaną. Poza tym taka metoda sprawdzania poprawności danych zawodzi, gdy dojdzie do przekłamania parzystej liczby bitów wiadomości.
Wysyłamy wiadomość 00 01 11 10 wraz z bitem parzystości 0.
Odbiorca otrzymuje wiadomość 11 01 11 10 wraz z bitem parzystości 0.
W takiej sytuacji odbiorca nie jest w stanie się nawet zorientować, że pojawił się jakiś błąd.
Wysyłamy wiadomość 00 01 11 10 wraz z bitem parzystości 0.
Odbiorca otrzymuje wiadomość: 00 01 11 10 wraz z bitem parzystości 1.
Odbiorca błędnie uzna poprawną wiadomość za przekłamaną.
Metoda ta ma zatem wady, ale jest stosunkowo łatwa w implementacji. Przed wysłaniem danych należy użyć odpowiedniego wzoru, aby ustalić wartość bitu kontrolnego:
Gdzie:
symbole xIndeks dolny nn są poszczególnymi bitami wiadomości,
symbol „+” oznacza operację XOR.
Jeśli wynikiem obliczeń jest 0, liczba jedynek w wiadomości jest parzysta, Gdy wynik to 1, liczba jedynek jest nieparzysta.
Stosowanie bitów parzystości (nieparzystości) nie jest idealną metodą sprawdzania poprawności danych, jednak daje szansę wykrycia przekłamań. Wiadomość można podzielić na mniejsze bloki, a do każdego z nich dołączać bit parzystości. Wadą tej metody jest zwiększanie się liczby bitów kontrolnych wraz z rosnącą liczbą bloków wiadomości.
Istnieją również inne metody kontroli danych, pozwalające określić z większą pewnością, czy pobrany plik jest poprawny.
Wykorzystuje się przy tym tzw. sumy kontrolne. Jedną z nich jest CRC – cykliczny kod nadmiarowy (ang. Cycle Redundancy Check).
Sumę kontrolną CRC obliczamy w następujący sposób:
Wybieramy długość sumy kontrolnej; przyjmijmy, że będzie ona równa 4.
Na końcu wiadomości, dla której chcemy obliczyć CRC, dopisujemy 4 zera.
Wybieramy ciąg bitów, który posłuży do obliczenia wartości CRC. Jego długość musi być o 1 większa od długości kodu CRC; w opisanym przypadku wynosi ona 5. Nie każda sekwencja pięciu bitów się do zrealizowania tego algorytmu.
Wykonujemy wielokrotnie operację XOR, której jednym argumentem jest wiadomość, a drugim pięciobitowy ciąg wybrany w punkcie 3. Posuwamy się przy tym od lewej do prawej strony wiadomości ze skokiem o jeden bit. Na końcu pozostanie tylko 4‑cyfrowy kod CRC. Zastępujemy nim cztery zera dopisane do wiadomości w punkcie 2.
Operacja z punktu czwartego odpowiada dzieleniu wielomianów. Nie są one zapisane w postaci xIndeks górny 44+xIndeks górny 33+..., lecz reprezentowane przez ciąg zer i jedynek. Wartości 1 przypisuje się tym elementom wielomianu, które są mnożone przez niezerowe współczynniki. Inaczej mówiąc, zamiast „x”, które mnożone są przez liczbę różną od 0, zapisujemy 1, a dla „x” mnożonych przez 0 zapisujemy 0.
Przykładowo 1xIndeks górny 44+0x zapisalibyśmy jako: 1000, ponieważ zapis 1xIndeks górny 44+0xIndeks górny 33+0xIndeks górny 22+0x jest równoznaczny z 1xIndeks górny 44+0x
Osoba, która odbierze wiadomość, może posłużyć się tym samym kodem CRC. Jeżeli po wykonaniu operacji XOR na całym komunikacie otrzyma ciąg zer, będzie to oznaczało, że wiadomość nie jest zniekształcona.
Jak zaznaczyliśmy w punkcie trzecim, podczas realizacji algorytmu wykorzystuje się tylko wybrane ciągi bitów (wielomiany).
Wielomian dla CRC o długości 4 miałby postać: xIndeks górny 44+x+1. Przedstawiamy go jako ciąg bitów 10011. Najbardziej znacząca cyfra 1 oznacza xIndeks górny 44. Z kolei najmniej znacząca jedynka oznacza kończącą wielomian liczbę 1. Druga od prawej strony cyfra 1 odpowiada jednomianowi xIndeks górny 11, zaś dwa zera reprezentują niewystępujące w wielomianie elementy xIndeks górny 33 oraz xIndeks górny 22.
Oto kilka wielomianów, które mogą być wykorzystane do obliczania CRC:
xIndeks górny 33+x+1 (1011, co odpowiada zapisowi 1•xIndeks górny 3 Indeks górny koniec3 + 0•xIndeks górny 2 Indeks górny koniec2 + 1•x + 1)
xIndeks górny 44+x+1 (10011, co odpowiada zapisowi 1•xIndeks górny 4 Indeks górny koniec4 + 0•xIndeks górny 3 Indeks górny koniec3 + 0•xIndeks górny 2 Indeks górny koniec2 + x + 1)
xIndeks górny 55+xIndeks górny 33+1 (101001, co odpowiada zapisowi 1•xIndeks górny 5 Indeks górny koniec5 + 0•xIndeks górny 4 Indeks górny koniec4 + 1•xIndeks górny 3 Indeks górny koniec3 + 0•xIndeks górny 2 Indeks górny koniec2 + 0•x + 1)
xIndeks górny 66+x+1 (1000011, co odpowiada zapisowi 1•xIndeks górny 6 Indeks górny koniec6 + 0•xIndeks górny 5 Indeks górny koniec5 + 0•xIndeks górny 4 Indeks górny koniec4 + 0•xIndeks górny 3 Indeks górny koniec3 + 0•xIndeks górny 2 Indeks górny koniec2 + 1•x + 1)
Ponieważ długość wielomianu musi być większa o 1 od obliczonej sumy kontrolnej, przedstawione wielomiany nadają się do obliczania CRC o długościach (odpowiednio): 3, 4, 5 i 6. Długość sumy kontrolnej jest równa stopniowi wielomianustopniowi wielomianu.
Chcemy obliczyć CRC o długości równej 3 dla ciągu bitów 0001101011.
Dopisujemy na końcu trzy zera.
0001101011 000
Należy pamiętać o usunięciu nieznaczących zer z przodu. W ten sposób uzyskamy:
1101011 000
Następnie wykorzystujemy ciąg o 1 bit dłuższy od CRC. Odpowiada on wielomianowi xIndeks górny 33+x+1 (zapisanemu jako 1011).
Wykonujemy operację XOR od lewej po prawej strony wiadomości, przesuwając się o jeden bit. Pogrubione cyfry niżej oznaczają te bity, dla których wykonujemy operację XOR:
1101 011 000
1011
Otrzymujemy wynik:
0110 011 000
Przesuwamy się o bit w prawo i wykonujemy kolejną operację XOR:
0 1100 11 000
1011
Otrzymujemy wynik:
0 0111 11 000
Ponownie wykonujemy operację XOR:
00 1111 1000
1011
Otrzymujemy wynik:
00 0100 1000
Operację XOR wykonujemy ponownie:
000 1001 000
1011
Otrzymujemy wynik:
000 0010 000
Wykonujemy znowu operację XOR. Należy pamiętać, że musimy omijać nieznaczące zera:
00000 1000 0
1011
Otrzymujemy wynik:
00000 0011 0
Zapisujemy wynik oddzielając trzy ostatnie cyfry:
0000000 110
Kod CRC jest zapisany na trzech ostatnich bitach wyniku. Jego wartość wynosi zatem 110.
Zastępujemy ciągiem 100 trzy zera dopisane wcześniej do końca wiadomości. Przyjmuje ona zatem postać:
0001101011 110
Spróbujmy teraz wcielić się w osobę, która otrzymała naszą wiadomość i chce sprawdzić, czy komunikat jest poprawny.
Wykonujemy operację XOR ponownie. Pamiętamy o wykonywaniu operacji jedynie na jedynkach. Korzystamy ponownie z tego samego wielomianu.
Wykonujemy operację XOR:
1101 011 110
1011
Otrzymujemy wynik:
0110 011 110
Wykonujemy operację XOR:
0 1100 11110
1011
Otrzymujemy wynik:
0 0111 11110
Wykonujemy operację XOR:
00 1111 1110
1011
Otrzymujemy wynik:
00 0100 1110
Wykonujemy operację XOR:
000 1001 110
1011
Otrzymujemy wynik:
000 0010 110
Operację wykonujemy ponownie, pamiętając o pomijaniu zer:
00000 1011 0
1011
Otrzymujemy wynik:
00000 0000 0
Otrzymana wiadomość jest prawdopodobnie poprawna. W przypadku zafałszowania choćby jednego bitu nie otrzymalibyśmy ciągu złożonego z samych zer.
W praktyce używa się o wiele dłuższych wielomianów (i otrzymuje się znacznie dłuższe kody CRC).
Istnieje również tak zwany kod Hamminga, opracowany przez Richarda Hamminga, który umożliwia nie tylko wykrycie błędów, ale również wskazanie, na której pozycji doszło do przekłamania.
Do sprawdzenia poprawności informacji można również użyć funkcji skrótufunkcji skrótu, na przykład MD5, SHA‑1 lub SHA‑2.
Funkcje skrótu generują na podstawie wiadomości o dowolnej długości pewien ciąg znaków, który jest w dużej mierze unikatowy. Użyliśmy słów „w dużej mierze”, ponieważ w pewnych przypadkach możliwe są do odnalezienia duplikaty skrótów. Jednym z skrótów znanych większości administratorów systemów informatycznych, którzy używają algorytmu MD5, jest skrót „21232f297a57a5a743894a0e4a801fc3”, który możemy uzyskać po użyciu tego algorytmu na słowie „admin”.
Funkcje skrótu pozwalają teoretycznie dokonać jednoznacznej identyfikacji pliku (a więc także sprawdzenia jego poprawności) – o ile nie dojdzie do kolizji, czyli pojawienia się duplikatu skrótu dla różnych zestawów danych.
Skrót kryptograficzny ciągu znaków „Matura z informatyki” wygenerowany z zastosowaniem algorytmu MD5 wygląda następująco: „403318a3342be13336457b88b7ab9dfd**”**.
W przypadku ciągu „Matura z Informatyki” zastosowane tego samego algorytmu daje wynik: „15c6b203f5b25bbc8fae47b68c4f78f5”.
Jak widać, bardzo mała zmiana w tekście powoduje, że skróty znacząco się od siebie różnią.
Nie istnieje metoda pozwalająca odszyfrować skrót kryptograficzny, czyli odtworzyć na jego podstawie wiadomość oryginalną. Jest to bardzo istotne zwłaszcza wtedy, gdy używa się funkcji skrótu do zastosowań kryptograficznych. Wspomnieliśmy już jednak, że możliwe jest pojawienie się kolizji, czyli różnych kombinacji znaków, które mają identyczne skróty.
Numer PESEL jest jednym z najważniejszych identyfikatorów, jaki otrzymuje polski obywatel. Numer ten jest nadawany zgodnie z pewnymi zasadami; każdy może sprawdzić, czy ciąg cyfr podany jako numer PESEL jest poprawny.
Aby to zrobić, należy posłużyć się wzorem:
Symbol xIndeks dolny 00 oznacza cyfrę znajdująca się najdalej z lewej strony. Wynik obliczeń dla poprawnego numeru PESEL powinien być równy jego ostatniej cyfrze.
Pozostałe e‑materiały z serii
Słownik
rodzaj ataku hakerskiego polegający na przechwytywaniu wiadomości przez atakującego, modyfikowaniu jej treści i przesyłaniu zafałszowanych danych do odbiorcy
(inaczej: funkcja haszująca) funkcja przyporządkowująca dowolnie długiemu plikowi lub wiadomości pewien ciąg znaków o stałej długości, który wydaje się być losowy; funkcję haszujące są nieodwracalne
największy ze stopni jednomianów składających się na wielomian; najwyższa potęga zmiennej występująca w zapisie wielomianu (przykładowo, wielomian 2xIndeks górny 77 + xIndeks górny 66 - 4xIndeks górny 33 – 1 jest wielomianem stopnia siódmego)