Sumy Kontrolne CRC: Wykrywanie Błędów Przy Użyciu Dzielenia Wielomianowego

Traktuj wiadomość jako wielomian

CRC (spójna kontrola redundancji) nie sumuje bajtów – dokonuje dzielenia wielomianowego w GF(2), polu dwuelementowym, gdzie dodawanie to XOR i nie ma przenoszenia. Bity wiadomości stają się współczynnikami binarnych wielomianów M(x), a nadawca dzieli je przez ustalony z góry wielomian generatora G(x), zachowując jedynie resztę jako kontrolny sumy:

wysłane = M(x) * x^r XOR reszta, gdzie reszta = [M(x)*x^r] mod G(x) odbiorca ponownie oblicza to dzielenie na otrzymanych bitach; reszta != 0 → błąd wykryty live demo · wybierz CRC-8/16/32, odwróć bit, obserwuj jego wykrycie● LIVE r jest stopniem G(x) – 8, 16 lub 32 dla typowych ustawień – a cała sztuczka działa, ponieważ dzielenie wielomianowe oparte na XOR-ze rozkłada się względem dodawania: reszta zanieczyszczonej wiadomości jest równa reszcie oryginalnej wiadomości XOR reszcie wzoru błędu. Oznacza to, że moc wykrywania błędów CRC całkowicie zależy od tego, które wzory błędów G(x) przypadkiem dzieli się bez reszty – jeśli to źle, błędy przechodzą niezauważone; wybierz go dobrze i określone klasy błędów są wychwytywane z pewnością.

transmitted = M(x) · x^r  XOR  remainder,  where remainder = [M(x)·x^r] mod G(x)
receiver recomputes the same division on the received bits;
remainder != 0  ⇒  error detected

Dlaczego CRC-32 tak niezawodnie wychwytuje błędy w postaci wybuchów

Generator wielomianu stopnia r gwarantuje wykrycie każdego błędu w postaci wybuchowej (burst error) o długości ≤ r – błąd w postaci wybuchowej to każdy błąd ograniczony do r lub mniej kolejnych bitów, co dokładnie odpowiada wzorowi szumu generowanemu przez zarysowany dysk twardy, słabnący kanał radiowy lub uszkodzone komórkę pamięci. Dlatego też CRC-32, standard używany w ramkach Ethernet, plikach PNG/zip oraz większości systemów przechowywania danych, z pewnością wychwytuje wszystkie błędy w postaci wybuchowej do 32 bitów, a także pojedyncze i podwójne błędy bitowe (jeśli G(x) jest dobrany tak, aby nie miał wspólnych czynników z (x+1)), oraz dowolną liczbę nieparzystych błędów bitowych, gdy G(x) zawiera czynnik (x+1). Nie gwarantuje jednak wykrycia każdego możliwego dłuższego lub specjalnie skonstruowanego wzoru błędu – korupcja, która przypadkowo jest dokładnym wielokrotnością G(x), generuje resztę równą zero i przechodzi niezauważona.

CRC nie jest bezpieczny kryptograficznie

Ponieważ CRC jest liniowy w nadzorowanym ciele finickim (GF(2)), atakujący, który potrafi odwrócić bity, może dokładnie obliczyć, które dodatkowe bity należy odwrócić, aby pozostawić sumę kontrolną niezmienioną – jest to obliczenie dwuliniowe, a nie przeszukiwanie brute-force. Dlatego CRC chroni jedynie przed szumem losowym, a nie przed celową intencją przeciwnika; TLS, podpisy kodu i przechowywanie haseł wykorzystują SHA-2/SHA-3 lub HMAC, które są zaprojektowane tak, aby żaden wydajny algorytm nie mógł znaleźć drugiego komunikatu o pasującym rozdziale. Pomylenie tych dwóch jest rzeczywistym, powtarzającym się błędem bezpieczeństwa – CRC-32 w protokole sieciowym stanowi kontrolę integralności przeciwko szumowi transmisji, a nigdy nie służy do uwierzytelniania.

Trzy popularne ustawienia domyślne

CRC-8 (SMBus) G(x) = x^8 + x^2 + x + 1 Sprawdzenie 8-bitowe, np. w magistralach czujników

CRC-16 (CCITT) G(x) = x^16 + x^12 + x^5 + 1 Sprawdzenie 16-bitowe, np. Bluetooth, XMODEM

CRC-32 (IEEE 802.3) G(x)= x^32+x^26+x^23+...+x^2+x+1 (0xEDB88320) Sprawdzenie 32-bitowe, np. Ethernet, zip, PNG

Wszystkie trzy implementowane są identycznie w sprzęcie i oprogramowaniu: przesuwane jest przez wiadomość przez liniowy reżyser zmian z powrotem (LFSR) połączony zgodnie z współczynnikami G(x), lub – znacznie szybciej – wstępnie oblicza się tabelę 256 wpisów, dzięki czemu każdy bajt kosztuje jedno sprawdzanie tabeli i jeden XOR zamiast ośmiu kroków przesunięcia i XOR. Każda nowoczesna karta sieciowa i kontroler pamięci masowej oblicza CRC-32 w dedykowanym krzemie, ponieważ operacja odbywa się na każdym pojedynczym ramce lub sektorze przechodzącym przez nią.

CRC-8   (SMBus)     G(x) = x^8  + x^2 + x  + 1                    8-bit check, e.g. sensor buses
CRC-16  (CCITT)     G(x) = x^16 + x^12 + x^5 + 1                  16-bit, e.g. Bluetooth, XMODEM
CRC-32  (IEEE 802.3) G(x)= x^32+x^26+x^23+...+x^2+x+1 (0xEDB88320) 32-bit, e.g. Ethernet, zip, PNG

Wykrywanie, a nie korekcja

Reszta z CRC informuje Cię jedynie o tym, że coś się zmieniło, nigdy o tym, co dokładnie i gdzie to się stało – nie da się odwrócić dzielenia i odzyskać oryginalnych bitów wyłącznie na podstawie niezerowej reszty. Jest to celowy kompromis: CRC wykorzystuje tylko r dodatkowych bitów do ochrony dowolnie długiego komunikatu, podczas gdy kod korekcyjny błędy, taki jak Reed-Solomon lub kod Haminga, potrzebuje proporcjonalnie większej redundancji, aby również zidentyfikować i naprawić uszkodzone bity.

W praktyce często stosuje się obie metody – Ethernet wykorzystuje CRC-32 wyłącznie do wykrywania uszkodzonych ramek i prosi o ponowne przesłanie, zamiast próbować korygować je na miejscu.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz CRC Checksum i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.