PL 
EnglishDomyślny
Українська💻 Suma kontrolna CRC
Zobacz, jak cykliczny kod nadmiarowy wykrywa błędy w cyfrowej transmisji danych.
O sumie kontrolnej CRC
Cykliczna kontrola nadmiarowa (CRC) to kod wykrywający błędy, obliczany przez potraktowanie bloku danych jako wielomianu nad GF(2) — binarnym ciałem, gdzie cała arytmetyka jest modulo 2 (XOR) — i podzielenie go przez ustalony wielomian generujący. Reszta z tego dzielenia jest dołączana do danych; odbiorca ponownie oblicza dzielenie i flaguje każdą niezgodność jako błąd transmisji. CRC-32, zdefiniowany przez wielomian generujący 0x04C11DB7, jest używany w ramkach Ethernet, archiwach ZIP, obrazach PNG oraz w pakiecie protokołów TCP/IP, oferując gwarantowane wykrywanie wszystkich błędów pojedynczego bitu, wszystkich błędów dwubitowych, wszystkich nieparzystych liczb błędów bitowych oraz wszystkich błędów seryjnych krótszych niż 32 bity.
Symulator wizualizuje dzielenie długie XOR krok po kroku, pokazując każdą pośrednią resztę oraz obwód rejestru przesuwnego, który wykonuje to samo obliczenie w sprzęcie. Możesz przełączać się między ustawieniami CRC-8, CRC-16 i CRC-32, edytować wiadomość wejściową oraz wprowadzać błędy pojedynczych lub wielu bitów, by zweryfikować wykrywanie.
Najczęściej zadawane pytania
Dlaczego dla CRC używa się arytmetyki nad GF(2) (XOR)?
Arytmetyka GF(2) nie ma przeniesień, co czyni obliczanie CRC niezwykle efektywnym zarówno w sprzęcie, jak i w oprogramowaniu: dodawanie staje się XOR, mnożenie staje się AND, a dzielenie wielomianowe można zaimplementować jako rejestr przesuwny ze sprzężeniem zwrotnym (LFSR) taktowany raz na bit. Struktura algebraiczna wielomianów GF(2) czyni też formalne dowody wykrywania błędów wykonalnymi przy użyciu teorii kodowania.
Jakie typy błędów CRC-32 gwarantuje wykryć?
CRC-32 wykrywa: wszystkie błędy pojedynczego bitu; wszystkie błędy dwubitowe (dla wiadomości krótszych niż 2³² − 1 bitów); wszystkie nieparzyste liczby błędów bitowych (ponieważ 0x04C11DB7 jest podzielne przez (x+1)); wszystkie błędy seryjne o długości ≤ 32 bity; oraz dużą część (1 − 2⁻³²) dłuższych błędów seryjnych. NIE gwarantuje wykrycia wszystkich losowych błędów wielobitowych — do tego stosuje się silniejsze kody, takie jak Reed-Solomon.
Jak rejestr przesuwny ze sprzężeniem zwrotnym (LFSR) oblicza CRC w sprzęcie?
LFSR to łańcuch przerzutników, których odgałęzienia sprzężenia zwrotnego odpowiadają jedynkowym bitom wielomianu generującego. Każdy cykl zegara przesuwa jeden bit danych wejściowych i wykonuje na nim XOR ze sprzężeniem zwrotnym z odgałęzień. Po przetaktowaniu wszystkich bitów danych zawartość rejestru to reszta CRC. Przetwarza to jeden bit na cykl przy pełnej prędkości linii — miliardy bitów na sekundę we współczesnych układach ASIC Ethernet.
Dlaczego różne implementacje CRC-32 dają różne wyniki?
Istnieje kilka wariantów CRC-32: wariant Ethernet/ZIP/PNG (wielomian 0x04C11DB7, wartość początkowa 0xFFFFFFFF, odbite wejście/wyjście, końcowy XOR 0xFFFFFFFF) oraz wariant Castagnoliego CRC-32C (wielomian 0x1EDC6F41) używany w iSCSI, SCTP i ext4. Mieszanie wariantów powoduje niezgodności sum kontrolnych. Model Rocksoft definiuje 7 parametrów w pełni określających algorytm CRC.
Czy CRC nadaje się do kryptograficznej kontroli integralności?
Nie. CRC to prosty kod wykrywający błędy, a nie funkcja skrótu kryptograficznego. Przeciwnik, który może modyfikować wiadomość, może trywialnie ponownie obliczyć CRC i sfałszować ważną sumę kontrolną. Do wykrywania manipulacji w kontekstach bezpieczeństwa używaj kodu uwierzytelniania wiadomości (MAC), takiego jak HMAC-SHA256, lub kryptograficznego skrótu, takiego jak SHA-3. CRC nadaje się jedynie do wykrywania przypadkowego uszkodzenia w zaufanych kanałach.
Jak programowe obliczanie CRC wykorzystuje tabele przeglądowe?
Przetwarzanie po jednym bicie na raz jest wolne w oprogramowaniu. Zamiast tego wstępnie oblicza się tabelę o 256 wpisach: table[b] = CRC pojedynczego bajtu b z dopełnieniem zerami. Przetwarzanie każdego bajtu danych wejściowych wymaga wtedy tylko jednego odczytu tabeli, jednego XOR i jednego przesunięcia — sprawiając, że oparte na tabeli CRC-32 oblicza się z prędkością kilku GB/s na współczesnych procesorach. Procesory x86 z zestawem instrukcji SSE4.2 mają dedykowaną instrukcję CRC32 dla CRC-32C.
Jaka jest różnica między CRC-8, CRC-16 a CRC-32?
Liczba wskazuje stopień wielomianu generującego oraz szerokość sumy kontrolnej w bitach. CRC-8 (8-bitowa reszta) jest używany w protokołach wbudowanych, takich jak SMBus i 1-Wire, gdzie rozmiar kodu jest cenny. CRC-16 (16-bitowy) jest popularny w protokołach szeregowych (MODBUS, pakiety danych USB) i wykrywa wszystkie błędy seryjne do 16 bitów. CRC-32 (32-bitowy) daje prawdopodobieństwo fałszywie ujemne 1 na 4 miliardy i jest standardem dla systemów plików i pakietów sieciowych.
Czy dwie różne wiadomości mogą dać ten sam CRC (kolizja)?
Tak — kolizje istnieją, ponieważ CRC mapuje dowolnie długie wiadomości na sumę kontrolną o stałej długości (np. 32 bity). Mając poprawną parę wiadomość+CRC, zawsze można skonstruować inną wiadomość z tym samym CRC, dołączając starannie dobrane bity. Prawdopodobieństwo, że losowe uszkodzenie wytworzy ten sam CRC-32, wynosi 2⁻³² ≈ 2,3×10⁻¹⁰, co jest pomijalne dla komunikacji, ale nie dla scenariuszy adwersaryjnych.
Czym jest wielomian generujący i jak jest wybierany?
Wielomian generujący g(x) określa właściwości wykrywania błędów CRC. Dobry generator musi być pierwotny (by wykrywać wszystkie błędy o nieparzystej liczbie bitów) lub przynajmniej zawierać (x+1) jako czynnik. Wielomian CRC-32 0x04C11DB7 został zaprojektowany, by maksymalizować wykrywanie błędów seryjnych dla długości ramek Ethernet. Dobór optymalnych wielomianów dla konkretnych długości kodu i modeli błędów to aktywny obszar badań teorii kodowania.