Řádky mají tvar „ALGORITMUS hodnota“ následovaný odsazeným řádkem parametrů, takže zkopírovaný výsledek vždy říká, která sada parametrů jej vytvořila.
CRC — cyklický redundantní součet od základů
Jednou větou: CRC bere data jako jedno obrovské binární číslo, dělí je pevným „generujícím“ číslem pomocí XOR místo odčítání a hlásí zbytek — kompaktní otisk, který se dramaticky změní, i když se převrátí jediný bit vstupu, a proto každý od souborů PNG po vedení Modbus nese jeden.
Co CRC ve skutečnosti je
Obrázek dělení. Seřaďte své bajty jako jedno dlouhé binární číslo. Zvolte dělitele — polynom, např. 0x04C11DB7 pro CRC-32. Proveďte binární dlouhé dělení, kde „odčítání“ je operace XOR: kdykoli je nejvyšší bit běžícího zbytku 1, provede se XOR s dělitelem, posun doleva, opakování. Až projde celá zpráva, co zůstane v registru, je CRC. Žádné klíče, žádné tabulky v definici — jen dělení se zbytkem.
Těchto pět parametrů. Dva systémy mohou oba říkat „CRC-32“ a přesto nesouhlasit, protože samotný název nic nepevně nedefinuje. Úplný recept potřebuje pět hodnot: poly (dělitel), init (s čím registr začíná — samé nuly nechají úvodní nulové bajty zmizet, samé jedničky ne), refin/refout (zda je každý vstupní bajt — a konečný registr — bitově obrácen, což je odkaz sériového hardwaru, který posílal bity od nejméně významného), a xorout (konečná maska XOR, aby řada koncových nul stále měnila výsledek). Tato stránka vypisuje všech pět u každého výsledku přesně z tohoto důvodu.
Proč to odhaluje chyby. Dobře zvolený dělitel způsobí, že zbytek zprávy a zbytek téže zprávy s několika převrácenými bity se s drtivou pravděpodobností liší: dobré CRC-32 zachytí všechny chyby o 1 a 2 bitech, všechny liché počty bitových chyb a každý shluk až 32 po sobě jdoucích poškozených bitů — zaručeně, ne pravděpodobnostně. Tato záruka se týká nahodilého poškození a právě proto jsou CRC správným nástrojem pro hlučné dráty a vadné disky.
Čím CRC není
Není to kryptografický hash. Neexistuje žádné tajemství ani jednosměrnost: kdokoli, kdo zná parametry, může zprávu padělat s libovolným CRC, které chce, během milisekund, připojením čtyř opravných bajtů. CRC zachytí nehody, nikdy protivníky. Pro stahování, která ověřujete proti neznámým lidem, záleží na podpisech — místo toho viz Generátor hashů (MD5/SHA/BLAKE2). Tamní stránka také vysvětluje, proč jsou MD5 a SHA-1 pro nepřátelská nastavení vyřazeny, zatímco SHA-256 obstojí.
Není to kód pro opravu chyb. CRC vám řekne, že se něco změnilo, ne co se změnilo. Opravy chyb za běhu jsou úkolem kódů jako Reed–Solomon nebo Hamming, které záměrně ukládají redundantní strukturu, kterou dekodér dokáže invertovat.
Není to komprese ani šifrování. Zbytek má několik bajtů bez ohledu na velikost vstupu a z něj nelze vstup obnovit — ale na rozdíl od kryptografického hashe je to jen proto, že informace byla zahozena, ne proto, že by inverze byla těžká.
Rodiny na této stránce
Čtveřice CRC-32. Čtyři položky této stránky sdílejí poly 0x04C11DB7 a přesto dávají různé hodnoty: ISO-HDLC (obrácený, init/xorout samé jedničky) je „to“ CRC-32 zlib, gzip, PNG a ZIP; BZIP2 je stejná matematika neobrácená; MPEG-2 je BZIP2 bez závěrečného XOR; POSIX začíná od nuly a je základem příkazu cksum (který navíc připojuje k dělení délku souboru, takže cksum souboru a CRC-32/POSIX stejných bajtů se liší). CRC-32C (Castagnoli, poly 0x1EDC6F41) je pátý sourozenec: jiný poly zvolený pro lepší výkon detekce chyb a ten, který moderní procesory x86 a ARM dokážou spočítat rychlostí paměti jednou instrukcí.
Čtveřice CRC-64. XZ používá polynom ECMA-182 v obrácené formě s init a xorout samé jedničky; ECMA-182 sám je neobrácený původní variant s nulovým init z páskové normy DLT-1; GO-ISO je crc64.ISO z Go, malý poly 0x1B, stále obrácený; REDIS používá poly vybraný pro dobrý lavinový efekt při přiřazování slotů hashe. Šedesát čtyři bitů je velikost, kdy se CRC začínají používat jako hashovací funkce (rozdělování do košů), a ne jako čisté kontrolní součty.
Adler-32 je outsider: nejde vůbec o dělení. Sčítá bajty (A, začíná na 1) a sčítá tyto součty (B), obojí modulo 65521, a spojí oba 16bitové součty. Je v softwaru rychlejší než CRC-32 a zlib jej používá pro proudy deflate — ale u krátkých vstupů (pod několik set bajtů) nese součet příliš málo informace, a proto zlib pro malé bloky přepíná zpět na CRC-32.
CRC-8 a CRC-16 přežívají tam, kde jsou bajty drahé: CRC-8/CCITT (poly 0x07) chrání jednotlivé bajty hlaviček v protokolech SMBus a buněčných rádiových sítích; CRC-16/CCITT-FALSE hlídá bloky čipových karet; CRC-16/MODBUS je kontrolní součet každého rámce Modbus RTU v průmyslových provozech po celém světě.
Kde který žije
| Sada parametrů | Kde se vyskytuje |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), mnoho archivních formátů |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, hardwarová instrukce CRC32C v SSE4.2/ARMv8 |
| CRC-32/BZIP2 | Proud archivu .bz2 |
| CRC-32/MPEG-2 | Transportní proudy MPEG-2 |
| CRC-32/POSIX & cksum | Výstup příkazu POSIX cksum (cksum soubor.txt) |
| CRC-16/MODBUS | Rámce Modbus RTU (průmyslová PLC, měřiče, střídače) |
| CRC-16/CCITT-FALSE | čipové karty, spoje podobné X.25, některé protokoly GPS |
| CRC-8/CCITT | SMBus (bajt PEC), hlavičky buněčných rádií |
| CRC-64/XZ | Kontroly integrity kontejneru .xz |
| CRC-64/ECMA-182 | ECMA-182 / páskový standard DLT-1 |
| CRC-64/GO-ISO | Standardní knihovna Go crc64.ISO |
| CRC-64/REDIS | Přiřazování slotů hashe v clusteru Redis |
| Adler-32 | Proudy zlib (deflate), další kontexty rychlého kontrolního součtu |
Kotevní tabulka — check(“123456789”)
Katalog CRC má konvenci zveřejňovat výsledek pro ASCII řetězec 123456789 (9 bajtů). Každá hodnota níže se dá na této stránce zreprodukovat: do pole Text napište 123456789, zaškrtněte algoritmus a klikněte na Vypočítat.
| Sada parametrů | Šířka | Kontrolní hodnota (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 |
Zdroje: každá hodnota byla zkřížena nezávislou bitovou referenční implementací a tam, kde existuje, s systémovou knihovnou, která algoritmus dodává (zlib pro CRC-32 a Adler-32; katalog CRC Grega Cooka pro ostatní).
Časté chyby
- „CRC-32“ bez parametrů. Mezi ISO-HDLC, BZIP2, MPEG-2, POSIX a CRC-32C kolují pod stejným názvem pět různých hodnot. Vždy zaznamenejte poly/init/refin/refout/xorout spolu s výsledkem — tato stránka je vypisuje za vás.
- Porovnávání CRC-32 souboru s jeho výstupem
cksum. Jiné algoritmy: cksum připojuje délku a používá jiný init. Čísla se neshodnou a oba jsou „správně“.
- Důvěra v CRC proti manipulaci. Padělání odpovídajícího CRC je učebnicové cvičení (přepsat posledních 4 bajty). Použijte klíčovaný MAC (HMAC) nebo podpis, když může být druhá strana nepřátelská.
- Očekávání lavinového efektu. CRC je lineární: příbuzné zprávy mají příbuzná CRC. Dobré pro šum, špatné pro hashování — pokud potřebujete rozdělování do košů, je CRC-64 nebo skutečný hash bezpečnější než CRC-32.
- Hexadecimální text oproti bajtům. Řetězec
"123456789" (9 bajtů ASCII, 31 32 33 34 35 36 37 38 39) a číslo 0x123456789 jsou různé vstupy s různými CRC. Použijte záložku Hex bajty, když jsou vaše zdrojová data opravdu binární.
Časté dotazy
Proč se mi CRC-32 neshoduje s tím v souboru ZIP? CRC-32 v ZIPu je ISO-HDLC nad nekomprimovanými daty. Ujistěte se, že jste zahashovali tytéž bajty (ne komprimovaný proud), stejný režim (Text nebo Hex) a stejnou sadu parametrů — řádek parametrů vypsaný pod každým výsledkem slouží k tomu, aby byla kontrola okamžitá.
Které je lepší, CRC-32C, nebo CRC-32? Pro náhodné chyby obě zachytí všechny shluky chyb do 32 bitů; CRC-32C si v některých vzorcích chyb vede lépe a je ten, pro který existují instrukce CPU — při gigabitových rychlostech prakticky zadarmo. Důvod, proč přežívá CRC-32/ISO-HDLC, je kompatibilita: třicet let archivů mluví jeho jazykem.
Je CRC-64 silnější než CRC-32? Zachytí delší shluky (až 64 bitů) a při rozdělování do košů se kolizí výrazně méně, ale padělat se dá stejně snadno — šířka kupuje záruky detekce, ne bezpečnost.
Dá se CRC zpětně převést na vstup? Ne — nekonečně mnoho vstupů sdílí stejné CRC. Na rozdíl od kryptografického hashe ale útočník může zkonstruovat vstup s libovolným CRC, které zvolí, a v tomto smyslu není CRC vůbec jednosměrné.
