A sorok „ALGORITMUS érték” alakúak, amelyet behúzott paramétersor követ, így a másolt eredmény mindig megmondja, melyik paraméterkészlet hozta létre.
CRC — ciklikus redundanciaellenőrzés, a semmiből elmagyarázva
Egy mondatban: a CRC az adatot egy óriási bináris számként kezeli, elosztja egy rögzített „generátor” számmal kivonás helyett XOR-művelettel, és a maradékot jelenti — kompakt ujjlenyomat, amely drasztikusan változik, ha a bemenet akár egyetlen bitje megfordul, ezért hordoz CRC-t mindent a PNG-fájloktól a Modbus-vezetékekig.
Mi valójában a CRC
Az osztás képe. Az üzenet bájtjait egyetlen hosszú bináris számként kell felfogni. Egy osztó (a polinom) választandó, például a CRC-32-höz a 0x04C11DB7. Bináris hosszú osztás végezhető, ahol a „kivonás” az XOR művelet: valahányszor a futó maradék vezető bitje 1, XOR-ral hozzáadódik az osztó, majd balra léptetés, és az ismétlés. Miután az egész üzenet végigment, a regiszterben maradt érték a CRC. Nincsenek kulcsok, nincsenek táblázatok a definícióban — csak osztás maradékkal.
Az öt paraméter. Két rendszer is mondhatja, hogy „CRC-32”, és mégis eltérhet, mert a név önmagában nem rögzít semmit. A teljes recepthez öt érték kell: poly (az osztó), init (a regiszter kezdőértéke — csupa nulla esetén a vezető nulla bájtok eltűnnek, csupa egyes esetén nem), refin/refout (hogy minden bemeneti bájt — és a végső regiszter — bitjei megfordulnak-e, ami a soros hardver öröksége, amely a legkisebb helyértékű bitet küldte elsőként), és xorout (egy végső XOR-maszk, hogy a záró nullák sorozata is megváltoztassa az eredményt). Ezért az oldal minden eredmény mellett mind az öt értéket kiírja.
Miért észleli a hibákat. Jól megválasztott osztó mellett egy üzenet maradéka és ugyanazon üzenet maradéka néhány megfordított bittel nagy valószínűséggel eltér: egy jó CRC-32 elkapja az összes 1 bites és 2 bites hibát, az összes páratlan számú bithibát, és az összes legfeljebb 32 egymás utáni sérült bitből álló sávot — garantáltan, nem valószínűségi alapon. Ez a garancia a véletlen sérülésre vonatkozik, és ezért a CRC a megfelelő eszköz zajos vezetékekhez és hibás lemezekhez.
Mi nem a CRC
Nem kriptográfiai kivonat. Nincs titok és nincs egyirányúság: bárki, aki ismeri a paramétereket, milliszekundumok alatt bármilyen CRC-jű üzenetet hamisíthat, négy korrekciós bájt hozzáfűzésével. A CRC véletlen hibákat észlel, ellenségeket soha. Idegenektől származó, ellenőrzendő letöltéseknél az aláírások számítanak — helyette ez a Kivonatgenerátort (MD5/SHA/BLAKE2). Ez az oldal azt is elmagyarázza, miért vonták vissza az MD5-öt és a SHA-1-et ellenséges környezetben, míg a SHA-256 megáll.
Nem hibajavító kód. A CRC azt jelzi, hogy valami megváltozott, de azt nem, hogy mi változott. A hibák menet közbeni javítása olyan kódok feladata, mint a Reed–Solomon vagy a Hamming, amelyek szándékosan tárolnak olyan redundáns szerkezetet, amelyet a dekóder invertálni tud.
Nem tömörítés és nem titkosítás. A maradék a bemenet méretétől függetlenül néhány bájt, és ebből a bemenet nem állítható helyre — de a kriptográfiai kivonattal ellentétben ez csak azért van így, mert információ veszett el, nem azért, mert az invertálás nehéz.
Az oldal családjai
A CRC-32 négy rokona. Az oldal négy bejegyzése ugyanazt a 0x04C11DB7 polinomot osztja meg, mégis különböző értékeket ad: az ISO-HDLC (tükrözött, init/xorout csupa egyes) a zlib, gzip, PNG és ZIP „valódi” CRC-32-je; a BZIP2 ugyanaz a matematika tükrözetlenül; az MPEG-2 a BZIP2 végső XOR nélkül; a POSIX nullától indul, és a cksum parancs alapja (amely a fájlhosszt is hozzáfűzi az osztáshoz, így egy fájl cksum-ja és ugyanezen bájtok CRC-32/POSIX-e eltér). A CRC-32C (Castagnoli, 0x1EDC6F41 polinom) az ötödik testvér: másik polinom, amelyet jobb hibafelismerési teljesítményre választottak, és amelyet a modern x86- és ARM-processzorok egyetlen utasítással, memória-sebességgel számolnak.
A CRC-64 négyese. Az XZ a tükrözött alakú ECMA-182 polinomot használja, csupa egyes init- és xorout-értékkel; az ECMA-182 ellenben a nem tükrözött, nulla-init eredeti a DLT-1 szalagos szabványból; a GO-ISO a Go crc64.ISO függvénye, egy apró 0x1B polinommal, szintén tükrözve; a REDIS olyan polinomot használ, amelyet a jó lavinahatásért választottak a hash-slot kiosztásnál. A hatvannégy bit az a méret, ahol a CRC-k már hash-függvényként (csoportosításra) kezdenek működni, nem tiszta ellenőrző összegként.
Az Adler-32 a kívülálló: egyáltalán nem osztás. Összegzi a bájtokat (A, 1-től indulva), és összegzi ezeket az összegeket (B), mindkettő 65521 szerint vett maradékkal, majd összefűzi a két 16 bites összeget. Szoftverben gyorsabb, mint a CRC-32, és a zlib deflate-folyamokhoz használja — de rövid bemeneteknél (néhány száz bájt alatt) az összeg túl kevés információt hordoz, ezért vált a zlib kis blokkoknál vissza CRC-32-re.
A CRC-8 és a CRC-16 ott marad fenn, ahol a bájtok drágák: a CRC-8/CCITT (0x07 polinom) egyetlen fejlécbájtot véd SMBus- és mobilrádió-protokollokban; a CRC-16/CCITT-FALSE chipkártya-blokkokat véd; a CRC-16/MODBUS minden Modbus RTU-keret ellenőrző összege a gyártósorokon világszerte.
Hol él mindegyik
| Paraméterkészlet | Hol található |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), számos archívumformátum |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, SSE4.2/ARMv8 hardveres CRC32C-utasítás |
| CRC-32/BZIP2 | .bz2 archívum-folyam |
| CRC-32/MPEG-2 | MPEG-2 transzportfolyamok |
| CRC-32/POSIX & cksum | POSIX cksum parancs kimenete (cksum file.txt) |
| CRC-16/MODBUS | Modbus RTU-keretek (ipari PLC-k, mérők, inverterek) |
| CRC-16/CCITT-FALSE | chipkártyák, X.25-közeli kapcsolatok, néhány GPS-protokoll |
| CRC-8/CCITT | SMBus (PEC-bájt), mobilrádió-fejlécek |
| CRC-64/XZ | .xz tároló integritásellenőrzései |
| CRC-64/ECMA-182 | ECMA-182 / DLT-1 szalagos szabvány |
| CRC-64/GO-ISO | Go szabványkönyvtár crc64.ISO |
| CRC-64/REDIS | Redis-fürt hash-slot-kiosztás |
| Adler-32 | zlib-folyamok (deflate), más gyors ellenőrző összeg kontextusok |
A horgonytáblázat — check(„123456789”)
A CRC-katalógus szokása, hogy a 123456789 ASCII-sztring (9 bájt) eredményét közzéteszik. Az alábbi minden érték reprodukálható ezen az oldalon: a Szöveg mezőbe a 123456789 beírásával, az algoritmus bejelölésével és a Számítás gomb megnyomásával.
| Paraméterkészlet | Szélesség | Ellenőrző érték (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 |
Források: minden értéket független, bitenkénti referencia-implementáció ellenőriz, és ahol van, az algoritmust szállító rendszerkönyvtár is (zlib a CRC-32-höz és az Adler-32-höz; a többihez a Greg Cook CRC-katalógus).
Gyakori hibák
- „CRC-32” paraméterek nélkül. Az ISO-HDLC, a BZIP2, az MPEG-2, a POSIX és a CRC-32C között öt különböző érték kering ugyanazon név alatt. Az eredménnyel mindig rögzíteni kell a poly/init/refin/refout/xorout paramétereket — ez az oldal kiírja őket.
- Egy fájl CRC-32-jének összevetése a
cksum kimenetével. Különböző algoritmusok: a cksum hozzáfűzi a hosszt, és más init-et használ. A számok nem fognak egyezni, és mindkettő „helyes”.
- CRC-ben bízni a manipuláció ellen. Egyező CRC hamisítása tankönyvi feladat (az utolsó 4 bájt módosításával). Kulcsos MAC-et (HMAC) vagy aláírást kell használni, ha a másik fél rosszindulatú lehet.
- Lavinahatásra számítani. A CRC lineáris: a kapcsolódó üzenetek kapcsolódó CRC-ket adnak. Zajra rendben van, kivonatolásra helytelen — ha csoportosításra van szükség, a CRC-64 vagy egy valódi kivonat biztonságosabb, mint a CRC-32.
- Hex-szöveg vs. bájtok. A
"123456789" sztring (9 ASCII-bájt, 31 32 33 34 35 36 37 38 39) és a 0x123456789 szám különböző bemenetek, eltérő CRC-vel. Ha a forrásadat valóban bináris, a Hex-bájtok fület kell használni.
GYIK
Miért nem egyezik a CRC-32 a ZIP-fájlban lévővel? A ZIP CRC-32-je ISO-HDLC a ki nem tömörített adatokon. Ellenőrizendő, hogy ugyanazok a bájtok legyenek hashelve (nem a tömörített adatfolyam), ugyanaz a mód (Szöveg vagy Hex), és ugyanaz a paraméterkészlet — az egyes eredmények alatt megjelenő paramétersor pedig azt teszi, hogy ez az ellenőrzés azonnal elvégezhető legyen.
Melyik a jobb, a CRC-32C vagy a CRC-32? A véletlen hibák felismeréséhez mindkettő elkap minden legfeljebb 32 bites sávot; a CRC-32C egyes hibamintázatokon jobban teljesít, és ehhez processzorutasítás is tartozik — gigabites sebességnél gyakorlatilag ingyenes. A CRC-32/ISO-HDLC azért marad fenn, mert a kompatibilitás miatt: harminc év archívumai ezt beszélik.
Erősebb-e a CRC-64, mint a CRC-32? Hosszabb sávokat (legfeljebb 64 bitig) észlel, és csoportosításra használva jóval ritkábban ütközik, de ugyanúgy hamisítható — a szélesség észlelési garanciákat ad, nem biztonságot.
Visszafejthető-e egy CRC, hogy felfedje a bemenetet? Nem — végtelen sok bemenet osztozik ugyanazon a CRC-n. Egy kriptográfiai kivonattal ellentétben azonban egy támadó tetszőleges CRC-jű bemenetet elő tud állítani, és ebben az értelemben egyáltalán nem egyirányú.
