Linjer bruger formen “ALGORITME værdi” efterfulgt af en indrykket parameterlinje, så et kopieret resultat altid siger, hvilket parametersæt der producerede det.
CRC — cyklisk redundanskontrol, forklaret fra bunden
I én sætning: en CRC behandler dataene som ét gigantisk binært tal, dividerer det med et fast “generator”-tal ved hjælp af XOR i stedet for subtraktion og rapporterer resten — et kompakt fingeraftryk, der ændrer sig voldsomt, selv når en enkelt bit i inputtet vendes, hvorfor alt fra PNG-filer til Modbus-ledninger bærer en.
Hvad en CRC egentlig er
Divisionsbilledet. Stil bytene op som ét langt binært tal. Vælg en divisor — polynomiet, f.eks. 0x04C11DB7 for CRC-32. Udfør binær lang division, hvor “subtraktion” er XOR-operationen: når den førende bit i den løbende rest er 1, XOR'es divisoren ind, skift til venstre, gentag. Når hele beskeden er gennemløbet, er det, der er tilbage i registret, CRC'en. Ingen nøgler, ingen tabeller i definitionen — blot division med en rest.
De fem parametre. To systemer kan begge sige “CRC-32” og stadig være uenige, fordi navnet alene ikke fastlægger noget. Den fulde opskrift kræver fem værdier: poly (divisoren), init (hvad registret starter som — alle nuller lader førende nulbytes forsvinde, alle etaller gør det ikke), refin/refout (om hver inputbyte — og det endelige register — er bit-omvendt, en arv fra seriel hardware, der sendte bits mindst betydende først), og xorout (en endelig XOR-maske, så en række efterstillede nuller stadig ændrer svaret). Denne side udskriver alle fem ved siden af hvert resultat netop af den grund.
Hvorfor den opdager fejl. En velvalgt divisor gør, at resten af en besked og resten af den samme besked med nogle få vendte bit adskiller sig med overvældende sandsynlighed: en god CRC-32 fanger alle 1-bit- og 2-bit-fejl, alle ulige antal bitfejl og enhver skur af op til 32 sammenhængende ødelagte bit — garanteret, ikke probabilistisk. Den garanti handler om utilsigtet korruption, og det er det, der gør CRC'er til det rigtige værktøj til støjende ledninger og ustabile diske.
Hvad en CRC ikke er
Ikke en kryptografisk hash. Der er ingen hemmelighed og ingen envejsegenskab: enhver, der kender parametrene, kan forfalske en besked med en vilkårlig CRC, på millisekunder, ved at tilføje fire korrigerende bytes. En CRC opdager uheld, aldrig modstandere. Til downloads, der verificeres mod ukendte, betyder signaturer noget — se i stedet Hash-generatoren (MD5/SHA/BLAKE2). Den side forklarer også, hvorfor MD5 og SHA-1 er udgået til fjendtlige sammenhænge, mens SHA-256 står.
Ikke en fejlkorrigerende kode. En CRC fortæller, at noget ændrede sig, ikke hvad der ændrede sig. Reparation af fejl i farten er opgaven for koder som Reed–Solomon eller Hamming, der bevidst gemmer redundant struktur, en dekoder kan vende.
Ikke komprimering eller kryptering. Resten er nogle få bytes uanset inputstørrelse, og ud fra den kan inputtet ikke genskabes — men i modsætning til en kryptografisk hash er det blot fordi information blev kasseret, ikke fordi inversion er svær.
Familierne på denne side
CRC-32-kvadrupletterne. Fire af denne sides poster deler poly 0x04C11DB7 og producerer stadig forskellige værdier: ISO-HDLC (reflekteret, init/xorout alle-etaller) er “den” CRC-32 i zlib, gzip, PNG og ZIP; BZIP2 er den samme matematik ureflekteret; MPEG-2 er BZIP2 uden endelig XOR; POSIX starter fra nul og er grundlaget for cksum-kommandoen (som desuden tilføjer filens længde til divisionen, så cksum af en fil og CRC-32/POSIX af de samme bytes er forskellige). CRC-32C (Castagnoli, poly 0x1EDC6F41) er den femte søskende: et andet poly valgt for bedre fejldetektionsydelse, og det, moderne x86- og ARM-CPU'er kan beregne i hukommelseshastighed med én instruktion.
CRC-64-kvartetten. XZ bruger ECMA-182-polynomiet i reflekteret form med alle-etaller-init og xorout; ECMA-182 selv er den ureflekterede original med nul-init fra DLT-1-båndstandarden; GO-ISO er Gos crc64.ISO, et lille poly 0x1B, stadig reflekteret; REDIS bruger et poly valgt for god lavine-effekt i hash-slot-tildeling. Fireogtres bit er den størrelse, hvor CRC'er begynder at blive brugt som hashfunktioner (bucketing) snarere end rene checksummer.
Adler-32 er outsideren: den er slet ikke en division. Den summerer bytene (A, startende ved 1) og summerer disse summer (B), begge modulo 65521, og sammenkæder de to 16-bit-summer. Den er hurtigere end CRC-32 i software, og zlib bruger den til deflate-strømme — men for korte input (under nogle få hundrede bytes) bærer summen for lidt information, og netop derfor skifter zlib tilbage til CRC-32 for små blokke.
CRC-8 og CRC-16 overlever der, hvor bytes er dyre: CRC-8/CCITT (poly 0x07) beskytter enkelte headerbytes i SMBus- og mobilradioprotokoller; CRC-16/CCITT-FALSE beskytter chipkortblokke; CRC-16/MODBUS er checksummen i hver Modbus RTU-ramme på fabriksgulve verden over.
Hvor hver enkelt bruges
| Parametersæt | Findes i |
|---|
| CRC-32/ISO-HDLC | zlib, gzip, PNG, ZIP, Ethernet (FCS), mange arkivformater |
| CRC-32C | iSCSI, ext4, btrfs, ZFS, SSE4.2/ARMv8 hardware-CRC32C-instruktion |
| CRC-32/BZIP2 | .bz2-arkivstrøm |
| CRC-32/MPEG-2 | MPEG-2-transportstrømme |
| CRC-32/POSIX & cksum | Output fra POSIX-kommandoen cksum (cksum file.txt) |
| CRC-16/MODBUS | Modbus RTU-rammer (industrielle PLC'er, målere, invertere) |
| CRC-16/CCITT-FALSE | chipkort, X.25-lignende forbindelser, nogle GPS-protokoller |
| CRC-8/CCITT | SMBus (PEC-byte), mobilradio-headers |
| CRC-64/XZ | .xz-containerens integritetskontroller |
| CRC-64/ECMA-182 | ECMA-182 / DLT-1-båndstandard |
| CRC-64/GO-ISO | Gos standardbibliotek crc64.ISO |
| CRC-64/REDIS | Redis-klyngens hash-slot-tildeling |
| Adler-32 | zlib-strømme (deflate), andre hurtige checksum-sammenhænge |
Ankertabellen — check(“123456789”)
CRC-kataloget konventionen er at offentliggøre resultatet for ASCII-strengen 123456789 (9 bytes). Hver værdi nedenfor kan reproduceres på denne side: skriv 123456789 i tekstfeltet, markér algoritmen, og klik på Beregn.
| Parametersæt | Bredde | Kontrolværdi (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 |
Kilder: hver værdi er krydstjekket af en uafhængig bitvis referenceimplementering og, hvor en findes, mod systembiblioteket, der leverer algoritmen (zlib for CRC-32 og Adler-32; Greg Cook-CRC-kataloget for resten).
Almindelige fejl
- “CRC-32” uden parametre. Mellem ISO-HDLC, BZIP2, MPEG-2, POSIX og CRC-32C cirkulerer fem forskellige værdier under det samme navn. Registrér altid poly/init/refin/refout/xorout sammen med resultatet — denne side udskriver dem automatisk.
- At sammenligne en fils CRC-32 med dens
cksum-output. Forskellige algoritmer: cksum tilføjer længden og bruger en anden init. Tallene vil ikke stemme, og begge er “rigtige”.
- At stole på CRC mod manipulation. At forfalske en matchende CRC er en klassisk øvelse (patch de sidste 4 bytes). Brug en nøglet MAC (HMAC) eller en signatur, når den anden part kan være fjendtlig.
- At forvente lavine-effekt. En CRC er lineær: beslægtede beskeder giver beslægtede CRC'er. Fint til støj, forkert til hashing — hvis der er brug for bucketing, er CRC-64 eller en egentlig hash tryggere end CRC-32.
- Hex-tekst vs. bytes. Strengen
"123456789" (9 ASCII-bytes, 31 32 33 34 35 36 37 38 39) og tallet 0x123456789 er forskellige input med forskellige CRC'er. Brug fanen Hexbytes, når kildedata virkelig er binære.
Ofte stillede spørgsmål
Hvorfor matcher min CRC-32 ikke den i ZIP-filen? ZIP'ens CRC-32 er ISO-HDLC over de ukomprimerede data. Sørg for, at de samme bytes er hashet (ikke den komprimerede strøm), den samme tilstand (Tekst vs. Hex) og det samme parametersæt — parameterlinjen under hvert resultat er der for at gøre den kontrol øjeblikkelig.
Hvad er bedst, CRC-32C eller CRC-32? Til fejldetektion af tilfældige fejl fanger begge alle skurer op til 32 bit; CRC-32C klarer sig bedre på nogle fejlmønstre og er den, der har CPU-instruktioner — praktisk talt gratis i gigabit-hastighed. Grunden til, at CRC-32/ISO-HDLC overlever, er kompatibilitet: tredive års arkiver taler den.
Er CRC-64 stærkere end CRC-32? Den opdager længere skurer (op til 64 bit) og kolliderer langt mindre, når den bruges til bucketing, men den kan lige så let forfalskes — bredden giver detektionsgarantier, ikke sikkerhed.
Kan en CRC vendes for at afsløre inputtet? Nej — uendeligt mange input deler en CRC. Men i modsætning til en kryptografisk hash kan en angriber konstruere et input med enhver CRC, de vælger, og det er den forstand, hvor den slet ikke er envejs.
