错误检测码 - 循环冗余校验

概念

CRC (Cyclic Redundancy Checksum) 是一种错误检测码，常用于数字网络和存储设备，以检测数字数据的意外更改。为尽量提高接收方收到数据的正确率，在接收方接收数据之前需要对数据进行错误检测，当且仅当检测的结果为正确时接收方才真正接收数据进行下一步操作。检测的方式有多种，常见的有奇偶校验(Parity Check)、因特网校验(Internet Checksum)和循环冗余校验(Cyclic Redundancy Check)。

历史

CRC 基于循环纠错码理论。 1961 年， W. Wesley Peterson 首次提出了使用系统循环码（即通过添加固定长度的校验值对消息进行编码）来检测通信网络中的错误。循环码不仅易于实现，而且特别适合检测突发错误：消息中连续的错误数据符号序列。这一点很重要，因为突发错误是许多通信信道（包括磁性和光学存储设备）中常见的传输错误。通常，对任意长度的数据块应用 n 位 CRC 将检测到不长于 n 位的任何单个错误突发，它将检测到的所有较长错误突发的比例约为( $1-2^{-n}$ )。

CRC 代码的规范需要定义所谓的生成多项式。该多项式成为多项式长除法中的除数，该除法将消息作为被除数，其中商被丢弃，余数成为结果。重要的声明是，多项式系数是根据有限域的算数计算的，因此加法运算总是可以按位并行执行（数字之间没有进位）。

实际上，所有常用的 CRC 都采用了两个元素的有限域 GF 。这两个元素通常称为 0 和 1 ，与计算机架构非常匹配。

当 CRC 的校验值为 n 位长时，该 CRC 称为 n 位 CRC 。对于给定的 n ，可能存在多个 CRC ，每个 CRC 都有不同的多项式。这样的多项式的最高次数为 n ，这意味着它有 n + 1 个项。换句话说，多项式的长度为 n + 1；其编码需要 n + 1 位。请注意，大多数多项式规范都会删除 MSb 或 LSb，因为它们始终为 1 。 CRC 和相关多项式通常具有 CRC-n-XXX 形式的名称，如下表所示。

最简单的错误检测系统，即奇偶校验位，实际上是 1 位 CRC ：它使用生成多项式 x + 1 （两个项），并具有名称 CRC-1 。

应用

支持 CRC 的设备在发送或存储的每个数据块计算一个较短并固定长度的二进制序列（通常称为校验值或 CRC ），将其附加到数据的末尾即形成了一个 码字 。

当一个设备接收或读取码字时，要么将其末尾的校验值与自行从数据块中新计算出的校验值进行比较，要么对整个码字执行 CRC 校验，并将得到的校验值与预期的残差常数进行比较。

如果 CRC 值不匹配，则该块包含数据错误。此时，设备可能会采取纠正措施，例如重新读取该数据块或重新请求数据发送。否则，数据将被视为无错误（尽管在很小的概率下，它可能含未检测到的错误；这是错误检查的本质所固有的缺陷）。

数据完整性

CRC 校验专门用于防止通信信道中常见的错误，并快速且合理地保证所传递消息的完整性。但是，此种校验方法并不适用于防止数据被可以更改。

首先，鉴于没有身份验证，攻击者可以编辑数据块并重新计算 CRC 校验值。当校验值与数据块一并存储时， CRC 和加密哈希函数本身无法防止故意修改数据。任何需要防范此类攻击的应用程序都必须使用加密身份验证机制，例如消息认证码或数字签名（通常是基于加密哈希函数）。

其次，与加密哈希函数不同的是， CRC 是一种容易逆推的函数，所以它并不适合作为数字签名。

第三， CRC 满足类似于线性函数（或更准确地说，仿射函数）的关系：

$$CRC (x \oplus y) = CRC (x) \oplus CRC (y) \oplus c$$

其中 c 取决于 x 和 y 的长度，也可以表述如下，其中 x、y 和 z 具有相同的长度:

$$CRC (x \oplus y \oplus z) = CRC (x) \oplus CRC (y) \oplus CRC (z)$$

因此，即使使用以 XOR 作为组合运算的流密码（或将其有效地转换为流密码的分组密码模式，例如 OFB 或 CFB ）对 CRC 进行加密，消息和相关的 CRC 都可以在不知道加密秘钥的情况下进行操纵；这是有线等效保密(WEP)协议众所周知的设计缺陷之一。