Wiersze mają postać „ALGORYTM wartość” po której następuje wcięty wiersz parametrów, więc skopiowany wynik zawsze mówi, który zestaw parametrów go wytworzył.
CRC — cykliczny kontrolny sumą (redundancy check), wyjaśniony od podstaw
W jednym zdaniu: CRC traktuje dane jako jedną ogromną liczbę binarną, dzieli ją przez ustaloną liczbę „generującą”, używając XOR zamiast odejmowania, i podaje resztę — zwarty odcisk palca, który zmienia się gwałtownie nawet przy odwróceniu jednego bitu wejścia, dlatego każdy plik PNG i każde przewody Modbus go niosą.
Czym naprawdę jest CRC
Obraz dzielenia. Ustaw bajty jako jedną długą liczbę binarną. Wybierz dzielnik — wielomian, np. 0x04C11DB7 dla CRC-32. Wykonaj binarne dzielenie długie, gdzie „odejmowanie” to operacja XOR: zawsze gdy wiodący bit bieżącej reszty wynosi 1, XOR-uj dzielnik, przesuń w lewo i powtórz. Gdy przejdzie cała wiadomość, to, co zostaje w rejestrze, jest CRC. Bez kluczy, bez tablic w samej definicji — tylko dzielenie z resztą.
Pięć parametrów. Dwa systemy mogą oba mówić „CRC-32” i mimo to się nie zgadzać, bo sama nazwa nic nie ustala. Pełny przepis wymaga pięciu wartości: poly (dzielnik), init (od czego zaczyna się rejestr — same zera sprawiają, że wiodące zerowe bajty znikają, same jedynki nie), refin/refout (czy każdy bajt wejścia — i końcowy rejestr — jest odwracany bitowo, spuścizna sprzętu szeregowego, który wysyłał bity od najmniej znaczącego), oraz xorout (końcowa maska XOR, dzięki której seria końcowych zer nadal zmienia wynik). Ta strona wypisuje wszystkie pięć obok każdego wyniku właśnie dlatego.
Dlaczego wykrywa błędy. Dobrze dobrany dzielnik sprawia, że reszta wiadomości i reszta tej samej wiadomości z kilkoma odwróconymi bitami różnią się z ogromnym prawdopodobieństwem: dobry CRC-32 łapie wszystkie błędy 1-bitowe i 2-bitowe, wszystkie nieparzyste liczby błędów bitowych oraz każdą serię do 32 kolejnych uszkodzonych bitów — gwarantowanie, a nie probabilistycznie. Ta gwarancja dotyczy przypadkowego uszkodzenia i to czyni CRC właściwym narzędziem dla zaszumionych przewodów i zawodnych dysków.
Czym CRC nie jest
Nie jest skrótem kryptograficznym. Nie ma tu sekretu ani jednokierunkowości: każdy, kto zna parametry, może sfałszować wiadomość z dowolnym CRC w milisekundach, dopisując cztery bajty korygujące. CRC wykrywa przypadki, nigdy przeciwników. Do pobrań weryfikowanych wobec obcych ważne są podpisy — zobacz zamiast tego Generator skrótów (MD5/SHA/BLAKE2). Tamta strona wyjaśnia też, dlaczego MD5 i SHA-1 wycofano w środowiskach wrogich, a SHA-256 pozostaje.
Nie jest kodem korygującym błędy. CRC mówi że coś się zmieniło, a nie co się zmieniło. Naprawianie błędów w locie to zadanie kodów takich jak Reeda–Solomona czy Hamminga, które celowo przechowują nadmiarową strukturę, którą dekoder potrafi odwrócić.
Nie kompresja i nie szyfrowanie. Reszta to kilka bajtów niezależnie od rozmiaru wejścia i z niej nie da się odzyskać wejścia — ale w przeciwieństwie do skrótu kryptograficznego wynika to po prostu z tego, że informacja została odrzucona, a nie z tego, że odwracanie jest trudne.
Rodziny na tej stronie
Czwórka CRC-32. Cztery pozycje tej strony mają wspólny wielomian 0x04C11DB7 i mimo to dają różne wartości: ISO-HDLC (odwrócony, init/xorout = jedynki) to „ten” CRC-32 z zlib, gzip, PNG i ZIP; BZIP2 to ta sama matematyka nieodwrócona; MPEG-2 to BZIP2 bez końcowego XOR; POSIX zaczyna od zera i jest podstawą polecenia cksum (które dodatkowo dopisuje do dzielenia długość pliku, więc cksum pliku i CRC-32/POSIX tych samych bajtów się różnią). CRC-32C (Castagnoli, wielomian 0x1EDC6F41) to piąty krewniak: inny wielomian dobrany pod lepszą wydajność wykrywania błędów, i ten, który nowoczesne procesory x86 i ARM liczą z prędkością pamięci jedną instrukcją.
Czwórka CRC-64. XZ używa wielomianu ECMA-182 w formie odwróconej z init i xorout ustawionymi na jedynki; ECMA-182 to oryginał nieodwrócony z zerowym init ze standardu taśmy DLT-1; GO-ISO to crc64.ISO z biblioteki standardowej Go, mały wielomian 0x1B, nadal odwrócony; REDIS używa wielomianu dobranego pod dobry efekt lawinowy przy przydziale slotów haszujących. Sześćdziesiąt cztery bity to rozmiar, przy którym CRC zaczyna być używane jako funkcje haszujące (koszyki), a nie czyste sumy kontrolne.
Adler-32 to outsider: wcale nie jest dzieleniem. Sumuje bajty (A, zaczynając od 1) i sumuje te sumy (B), obie modulo 65521, a potem łączy dwie 16-bitowe sumy. Jest szybszy od CRC-32 w oprogramowaniu, a zlib używa go w strumieniach deflate — ale dla krótkich wejść (poniżej kilkuset bajtów) suma niesie zbyt mało informacji, dlatego zlib dla małych bloków wraca do CRC-32.
CRC-8 i CRC-16 przetrwały tam, gdzie bajty są drogie: CRC-8/CCITT (wielomian 0x07) chroni pojedyncze bajty nagłówka w SMBus i protokołach radia komórkowego; CRC-16/CCITT-FALSE chroni bloki kart chipowych; CRC-16/MODBUS to suma kontrolna każdej ramki Modbus RTU w fabrykach na całym świecie.
Gdzie każdy z nich występuje
| Zestaw parametrów | Występuje w |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), wiele formatów archiwów |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, instrukcja sprzętowa CRC32C SSE4.2/ARMv8 |
| CRC-32/BZIP2 | strumień archiwum .bz2 |
| CRC-32/MPEG-2 | strumienie transportowe MPEG-2 |
| CRC-32/POSIX & cksum | wynik polecenia POSIX cksum (cksum plik.txt) |
| CRC-16/MODBUS | ramki Modbus RTU (sterowniki PLC, liczniki, falowniki) |
| CRC-16/CCITT-FALSE | karty chipowe, łącza pokrewne X.25, niektóre protokoły GPS |
| CRC-8/CCITT | SMBus (bajt PEC), nagłówki radia komórkowego |
| CRC-64/XZ | kontrole integralności kontenera .xz |
| CRC-64/ECMA-182 | ECMA-182 / standard taśmy DLT-1 |
| CRC-64/GO-ISO | Biblioteka standardowa Go crc64.ISO |
| CRC-64/REDIS | Przydział slotów haszujących klastra Redis |
| Adler-32 | strumienie zlib (deflate), inne konteksty szybkiej sumy kontrolnej |
Tabela punktów odniesienia — check(„123456789”)
Konwencja katalogu CRC polega na publikowaniu wyniku dla łańcucha ASCII 123456789 (9 bajtów). Każda poniższa wartość jest odtwarzalna na tej stronie: wpisz 123456789 w polu Tekst, zaznacz algorytm i kliknij Oblicz.
| Zestaw parametrów | Szerokość | Wartość kontrolna (hex) |
|---|
| CRC-8/CCITT | 8 | 0xf4 |
| CRC-16/CCITT-FALSE | 16 | 0x29b1 |
| CRC-16/MODBUS | 16 | 0x4b37 |
| CRC-32/ISO-HDLC | 32 | 0xcbf43926 |
| CRC-32C | 32 | 0xe3069283 |
| CRC-32/BZIP2 | 32 | 0xfc891918 |
| CRC-32/MPEG-2 | 32 | 0x0376e6e7 |
| CRC-32/POSIX | 32 | 0x765e7680 |
| cksum (POSIX command) | 32 | 0x377a6011 |
| CRC-64/XZ | 64 | 0x995dc9bbdf1939fa |
| CRC-64/ECMA-182 | 64 | 0x6c40df5f0b497347 |
| CRC-64/GO-ISO | 64 | 0xb90956c775a41001 |
| CRC-64/REDIS | 64 | 0xe9c6d914c4b8d9ca |
| Adler-32 | 32 | 0x091e01de |
Źródła: każda wartość została sprawdzona krzyżowo przez niezależną bitową implementację referencyjną i, gdzie istnieje, przez bibliotekę systemową dostarczającą algorytm (zlib dla CRC-32 i Adler-32; katalog CRC Grega Cooka dla reszty).
Typowe błędy
- „CRC-32” bez parametrów. Między ISO-HDLC, BZIP2, MPEG-2, POSIX i CRC-32C krąży pięć różnych wartości pod tą samą nazwą. Zawsze zapisuj poly/init/refin/refout/xorout razem z wynikiem — ta strona wypisuje je automatycznie.
- Porównywanie CRC-32 pliku z wynikiem
cksum. Różne algorytmy: cksum dopisuje długość i używa innego init. Liczby się nie zgodzą, a oba wyniki są „poprawne”.
- Ufanie CRC wobec manipulacji. Sfałszowanie pasującego CRC to klasyczne ćwiczenie (wystarczy poprawić ostatnie 4 bajty). Użyj MAC z kluczem (HMAC) lub podpisu, gdy druga strona może być wroga.
- Oczekiwanie efektu lawinowego. CRC jest liniowe: powiązane wiadomości dają powiązane CRC. Nadaje się do szumu, nie do haszowania — jeśli potrzebne są koszyki, CRC-64 albo prawdziwy skrót jest bezpieczniejszy niż CRC-32.
- Tekst szesnastkowy a bajty. Ciąg
"123456789" (9 bajtów ASCII, 31 32 33 34 35 36 37 38 39) i liczba 0x123456789 to różne wejścia z różnymi CRC. Użyj zakładki Bajty szesnastkowe, gdy dane źródłowe są naprawdę binarne.
FAQ
Dlaczego mój CRC-32 nie zgadza się z tym w pliku ZIP? CRC-32 w ZIP to ISO-HDLC liczony na danych nieskompresowanych. Upewnij się, że haszowano te same bajty (nie strumień skompresowany), ten sam tryb (tekst czy szesnastkowy) i ten sam zestaw parametrów — wiersz parametrów wypisany pod każdym wynikiem służy właśnie do tego, by sprawdzenie było natychmiastowe.
Który jest lepszy, CRC-32C czy CRC-32? Do wykrywania przypadkowych błędów oba łapią wszystkie serie do 32 bitów; CRC-32C radzi sobie lepiej z niektórymi wzorcami błędów i ma instrukcje w procesorze — przy prędkościach gigabitowych jest praktycznie darmowy. Powodem, dla którego przetrwał CRC-32/ISO-HDLC, jest zgodność: trzydzieści lat archiwów mówi tym językiem.
Czy CRC-64 jest silniejszy niż CRC-32? Wykrywa dłuższe serie (do 64 bitów) i znacznie rzadziej koliduje przy użyciu do koszyków, ale da się go równie łatwo sfałszować — szerokość kupuje gwarancje wykrywania, a nie bezpieczeństwo.
Czy CRC można odwrócić, by odsłonić wejście? Nie — nieskończenie wiele wejść dzieli to samo CRC. Ale w przeciwieństwie do skrótu kryptograficznego napastnik może skonstruować wejście o dowolnym wybranym CRC, i w tym sensie wcale nie jest jednokierunkowe.
