CRC — 迴圈冗餘校驗,從零講起
一句話概括:CRC 把你的資料當作一個巨大的二進位制數,用一個固定的“生成數”以 XOR 代替減法做除法,並報告餘數 — 一個緊湊的指紋,輸入哪怕翻轉一個位元都會劇烈改變,這正是從 PNG 檔案到 Modbus 線路都在用它校驗的原因。
CRC 究竟是什麼
除法圖景。把你的位元組排成一個長長的二進位制數。選一個除數 — 即多項式,例如 CRC-32 的 0x04C11DB7。執行二進位制長除法,其中“減法”就是 XOR 操作:只要執行餘數的最高位是 1,就 XOR 進除數,左移,重複。整條訊息走完之後,暫存器裡剩下的就是 CRC。沒有金鑰,定義裡也沒有查表 — 只是有餘數的除法。
五個引數。兩套系統都可以自稱“CRC-32”卻互相不一致,因為名字本身什麼也沒定。完整的配方需要五個值:poly(除數)、init(暫存器的起始值 — 全零會讓開頭的零位元組憑空消失,全一不會)、refin/refout(每個輸入位元組 — 以及最終暫存器 — 是否按位反轉,這是“低位先發”的序列硬體留下的遺產)、xorout(最終 XOR 掩碼,讓一串結尾零也能改變結果)。本頁在每個結果旁列印全部五個值,正是為此。
為什麼它能檢錯。選得好的除數能讓“訊息的餘數”與“同一訊息翻轉若干位元後的餘數”以壓倒性機率不同:一個好的 CRC-32 能抓住全部 1 位元和 2 位元錯誤、全部奇數個位元錯誤,以及所有不超過 32 個連續損壞位元的突發錯誤 — 這是保證,不是機率。這一保證針對的是意外損壞,也正是 CRC 成為嘈雜線路與不穩定磁碟首選工具的原因。
CRC 不是什麼
不是密碼學雜湊。它沒有秘密可言,也沒有單向性:任何知道引數的人都能在幾毫秒內追加四個修正位元組,偽造出任意想要的 CRC。CRC 檢測的是意外,從來不是對手。要核對陌生人釋出的下載內容,簽名才有意義 — 請改用 雜湊生成器(MD5/SHA/BLAKE2)。那一頁還解釋了為什麼 MD5 和 SHA-1 在對抗性場合已退役,而 SHA-256 依然可用。
不是糾錯碼。CRC 告訴你有東西變了,而不是什麼變了。即時修復錯誤是 Reed–Solomon、Hamming 這類碼的工作,它們刻意儲存可供解碼器還原的冗餘結構。
不是壓縮,也不是加密。無論輸入多大,餘數都只有幾個位元組,而且無法從餘數恢復輸入 — 但與密碼學雜湊不同,這僅僅是因為資訊被丟棄了,而不是因為求逆困難。
本頁的各大家族
CRC-32 四胞胎。本頁有四項共用多項式 0x04C11DB7 卻給出不同結果:ISO-HDLC(反射,init/xorout 全一)就是 zlib、gzip、PNG、ZIP 所說的“那個”CRC-32;BZIP2 是同一數學的非反射版;MPEG-2 是沒有最終 XOR 的 BZIP2;POSIX 從零起步,是 cksum 命令的基礎(後者在除法前額外附加檔案長度,所以同一檔案的 cksum 與其位元組的 CRC-32/POSIX 不同)。CRC-32C(Castagnoli,多項式 0x1EDC6F41)是第五個兄弟:為更好的檢錯效能另選的多項式,也是現代 x86 與 ARM CPU 能用一條指令以記憶體速度計算的那個。
CRC-64 四重奏。XZ 用 ECMA-182 多項式的反射形式,init 和 xorout 全一;ECMA-182 本身是 DLT-1 磁帶標準裡零初始化的非反射原版;GO-ISO 是 Go 的 crc64.ISO,一個極小的多項式 0x1B,同樣反射;REDIS 的多項式則是為雜湊槽分配的良好雪崩性而選。64 位正是 CRC 開始被當作雜湊函式(分桶)而非純粹校驗和使用的分水嶺。
Adler-32 是局外人:它根本不做除法。它對位元組求和(A,從 1 開始),再對這些和求和(B),兩者都對 65521 取模,然後把兩個 16 位和拼接起來。它在軟體中比 CRC-32 快,zlib 用它處理 deflate 流 — 但對短輸入(幾百位元組以下)求和攜帶的資訊太少,這正是 zlib 對小塊改回 CRC-32 的原因。
CRC-8 與 CRC-16 活在位元組很金貴的地方:CRC-8/CCITT(多項式 0x07)保護 SMBus 與蜂窩射頻協議裡的單個頭部位元組;CRC-16/CCITT-FALSE 守衛智慧卡資料塊;CRC-16/MODBUS 是全世界工廠車間裡每條 Modbus RTU 幀的校驗和。
各演算法的用武之地
| 引數集 | 見於 |
| CRC-32/ISO-HDLC | zlib、gzip、PNG、ZIP、乙太網路(FCS)、多種歸檔格式 |
| CRC-32C | iSCSI、ext4、btrfs、ZFS、SSE4.2/ARMv8 硬體 CRC32C 指令 |
| CRC-32/BZIP2 | .bz2 歸檔流 |
| CRC-32/MPEG-2 | MPEG-2 傳輸流 |
| CRC-32/POSIX & cksum | POSIX cksum 命令輸出(cksum file.txt) |
| CRC-16/MODBUS | Modbus RTU 幀(工業 PLC、儀表、逆變器) |
| CRC-16/CCITT-FALSE | 智慧卡、X.25 類鏈路、部分 GPS 協議 |
| CRC-8/CCITT | SMBus(PEC 位元組)、蜂窩射頻頭部 |
| CRC-64/XZ | .xz 容器完整性校驗 |
| CRC-64/ECMA-182 | ECMA-182 / DLT-1 磁帶標準 |
| CRC-64/GO-ISO | Go 標準庫 crc64.ISO |
| CRC-64/REDIS | Redis 叢集雜湊槽分配 |
| Adler-32 | zlib 流(deflate)、其他快速校驗和場景 |
錨點表 — check(“123456789”)
CRC 目錄的慣例是釋出 ASCII 字串 123456789(9 位元組)的結果。下表每個值都能在本頁復現:在文本框輸入 123456789,勾選演算法,點選“計算”。
| 引數集 | 寬度 | 校驗值(十六進位制) |
| 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 |
資料來源:每個值都經獨立的按位參考實現交叉驗證,並在存在系統庫實現的地方與系統庫核對(CRC-32 與 Adler-32 對 zlib,其餘對照 Greg Cook 的 CRC 目錄)。
常見錯誤
- 沒有引數的“CRC-32”。ISO-HDLC、BZIP2、MPEG-2、POSIX 和 CRC-32C 共五個不同值都頂著同一個名字流通。務必把 poly/init/refin/refout/xorout 隨結果一起記錄 — 本頁已經替你印好了。
- 拿檔案的 CRC-32 與它的
cksum 輸出比較。這是兩種演算法:cksum 會附加檔案長度且用不同的 init。數字不會一致,而兩個都“對”。
- 指望 CRC 抵禦篡改。偽造匹配的 CRC 是教科書練習(補最後 4 個位元組即可)。當對方可能懷有敵意時,請使用帶金鑰的 MAC(HMAC)或簽名。
- 期待雪崩效應。CRC 是線性的:相關的訊息給出相關的 CRC。對付噪聲沒問題,做雜湊就不對了 — 需要分桶時,CRC-64 或真正的雜湊都比 CRC-32 穩妥。
- 十六進位制文本與位元組混淆。字串
"123456789"(9 個 ASCII 位元組,31 32 33 34 35 36 37 38 39)和數字 0x123456789 是不同的輸入,CRC 也不同。源資料是真正的二進位制時,請用“十六進位制位元組”標籤頁。
常見問題
為什麼我的 CRC-32 與 ZIP 檔案裡的對不上?ZIP 的 CRC-32 是對未壓縮資料算的 ISO-HDLC。確認你雜湊的是同一批位元組(不是壓縮流)、同一模式(文本還是十六進位制)、同一引數集 — 每個結果下面印著的引數行就是為了讓這種核對一秒鐘完成。
CRC-32C 和 CRC-32 哪個更好?就意外檢錯而言,兩者都能抓住全部 32 位以內的突發錯誤;CRC-32C 在某些錯誤模式上表現更好,而且是有 CPU 指令的那個 — 千兆速度下幾乎免費。CRC-32/ISO-HDLC 能活下來靠的是相容性:三十年的存檔都說這門語言。
CRC-64 比 CRC-32 強嗎?它能檢測更長的突發(最長 64 位),用於分桶時碰撞少得多,但同樣可以被偽造 — 位寬買到的是檢錯保證,不是安全性。
CRC 能反推出輸入嗎?不能 — 無窮多個輸入共享同一個 CRC。但與密碼學雜湊不同,攻擊者可以構造出任意指定 CRC 的輸入,從這個意義上說它根本不單向。