CRC（循环冗余校验）
CRC
Cyclic Redundancy Check
Cyclic Redundancy Check
循环冗余校验
设计者
W. Wesley Peterson
首次发布
1961年
类别
校验和算法
输出长度
8 / 16 / 32 / 64 bit
结构
多项式除法（LFSR）
速度
极快（~15 GB/s）
安全用途
不适用（仅错误检测）
标准
ISO/IEC 13239, ITU-T V.42
CRC（Cyclic Redundancy Check，循环冗余校验）是一类基于多项式除法的错误检测码，由 W. Wesley Peterson 于 1961 年提出。CRC 不是密码学哈希函数，而是用于检测数据传输或存储过程中发生的随机错误。它通过将数据视为一个大整数，用一个预定义的生成多项式去除，取余数作为校验值。
CRC 是目前使用最广泛的校验和算法之一，出现在几乎所有通信协议和文件格式中。不同的生成多项式产生不同的 CRC 变体，适用于不同的错误检测需求。
原理
CRC 的核心思想是将待校验的数据位串视为一个多项式的系数（即数据 1101 对应多项式 x³ + x² + 1），然后用一个预定义的生成多项式 G(x) 去除该多项式，得到的余数即为 CRC 校验值。
发送方:
1. 将数据 M(x) 左移 r 位（r 为生成多项式的阶数）
2. 用 G(x) 做模 2 除法，得到余数 R(x)
3. 发送 [数据 | R(x)]
接收方:
1. 用相同的 G(x) 除接收到的 [数据 | R(x)]
2. 若余数为 0 → 数据未出错
3. 若余数不为 0 → 检测到错误
模 2 除法等价于异或（XOR）运算，不涉及进位，因此 CRC 在硬件和软件中都极易高效实现。硬件通常使用线性反馈移位寄存器（LFSR）实现，软件则使用查表法加速。
常见 CRC 变体
| 名称 | 输出宽度 | 生成多项式 | 主要应用 |
|---|---|---|---|
| CRC-8 | 8 bit | 0x07 | SMBus, 1-Wire |
| CRC-16-CCITT | 16 bit | 0x1021 | X.25, Bluetooth, PPP |
| CRC-16-IBM | 16 bit | 0x8005 | USB, Modbus |
| CRC-32 | 32 bit | 0x04C11DB7 | Ethernet (IEEE 802.3), ZIP, PNG, GZIP, TCP |
| CRC-32C (Castagnoli) | 32 bit | 0x1EDC6F41 | iSCSI, SCTP, Btrfs, ext4 |
| CRC-64-ECMA | 64 bit | 0x42F0E1EBA9EA3693 | XZ Utils |
| CRC-64-WE | 64 bit | 0x42F0E1EBA9EA3693 | WorldEdit |
错误检测能力
n 位 CRC 可以检测：
- 所有长度 ≤ n 的突发错误（burst error）
- 所有影响奇数个位的错误（前提是生成多项式包含
x+1因子） - 所有双位错误（前提是生成多项式的最大公约数为 1）
- 长度 > n 的突发错误的概率为
1 - 2-n
CRC-32 可以检测所有 32 位以内的突发错误，以及约 99.99999998% 的更长突发错误。但 CRC 不能防御恶意篡改——攻击者可以轻易构造碰撞。
应用场景
- 网络协议：Ethernet（CRC-32）、TCP/UDP 校验、Bluetooth（CRC-16）
- 存储：磁盘控制器、RAID、文件系统（Btrfs 使用 CRC-32C）
- 压缩格式：ZIP、GZIP、PNG、Zstandard 均使用 CRC-32
- 嵌入式系统：CAN 总线（CRC-15）、Modbus（CRC-16）
- 软件分发：安装包完整性校验
优缺点
优点：
- 计算速度极快，可达内存带宽极限
- 硬件实现极其简单（仅需异或门和移位寄存器）
- 对随机错误的检测能力优秀
- 软件查表实现仅需要少量内存
缺点：
- 不具备密码学安全性，容易人为构造碰撞
- 对系统性错误模式的检测能力有限
- 输出长度短（通常 ≤ 64 bit），不适合作为唯一标识
与密码学哈希的关系
CRC 和密码学哈希函数虽然都能产生固定长度的摘要，但设计目标完全不同。CRC 追求速度和随机错误检测，而密码学哈希要求抗碰撞和抗原像攻击。在需要防范恶意篡改的场景中（如软件签名、数字证书），必须使用密码学哈希函数而非 CRC。CRC 适用于数据传输层的完整性校验，例如网络协议栈的链路层。
参考文献
- Peterson, W.W., Brown, D.T. (1961). "Cyclic Codes for Error Detection". Proceedings of the IRE. 49 (1): 228–235. doi:10.1109/JRPROC.1961.287814.
- ISO/IEC 13239:2002 — Information technology — Telecommunications and information exchange between systems — High-level data link control (HDLC) procedures.
- Williams, R. (1993). "A Painless Guide to CRC Error Detection Algorithms". Rocksoft Technical Report.
- ITU-T Recommendation V.42 (2002). "Error-correcting procedures for DCEs using asynchronous-to-synchronous conversion."