当前位置：首页 > backend >正文

《从理论到实践：CRC校验的魔法之旅》

backend 2025/5/20 12:14:47

循环冗余校验（Cyclic Redundancy Check ,CRC ）是一种用于检测数据传输或存储过程中错误的算法。他通过计算数据的校验值（也称为CRC码），并在数据接收端验证校验值是饭否正确，从而检测数据是否在传输过程中被篡改或损坏
CRC的基本原理：基于多项式除法，将数据视为一个大的二进制属于，并用一个预定义的多项式（称为生成多项式）进行除法运算。生成多项式的选择对CRC的性能至关重要。
1. 生成多项式：一个预定义的多项式，用于生成CRC码。
  例如，CRC-32使用的是生成多项式x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1--这个多项式是规定的。
2. 数据块：要校验的数据被视为一个大的二进制数。
3. 余数：通过多项式除法计算得到的余数，称为CRC码。
CRC的计算过程
1. 数据块扩展：在数据块的末尾添加若干个0，零的数量取决于生成多项式的阶数
2. 多项式除法：将扩展后的数据块除以生成多项式，得到余数
3. 生成CRC码：将余数作为CRC码附加到原始数据块的末尾
4. 传输数据：将包含CRC码的数据块传输到接收端
5. 验证：接收端使用相同的生成多项式对接收到的数据块进行除法运算，如果余数为0，则认为数据未被篡改
CRC的优点
1. 高效性：CRC算法计算速度快，适合实时数据传输
2. 可靠性：能够检测到大多数类型的错误，包括单比特错误、双比特错误、突发错误等
3. 简单性：实现简单，硬件和软件实现都比较容易
CRC的常见应用
1. 数据通信：在以太网、串行通信等协议中广泛使用CRC来就检测数据传输错误
2. 存储设备：硬盘、光盘等存储设备使用CRC来检测数据读写错误
3. 文件系统：如FAT、NTFS等文件系统使用CRC来就按测文件数据的完整性
4. 网络协议：如TCP/IP协议栈中的某些层使用CRC来确保数据的完整性
CRC的局限性
1. 无法检测所有错误
2. 安全性不足：主要用于错误检测，而不是加密或认证。恶意攻击者可能能够篡改数据并生成新的CRC码，使得篡改后的数据通过CRC校验
CRC的变种：
1. CRC-8：适用于较小的数据块
2. CRC-16：适用于中等大小的数据块
3. CRC-32：最常见的CRC变种，适用于较大的数据块
4. CRC-64：用于非常大的数据块，提供更高的可靠性
CRC计算示例
1. 计算之前需要知道的：生成多项式为G(x)=x^4+x+1对应的二进制序列为10011，这是因为多项式的每一项x^n对应于二进制序列中的第n+1位（从右向左技术，最右边的位是第0位）
2. 异或的规则--相同为0相反为1
  0 XOR 0 = 0
  0 XOR 1 = 1
  1 XOR 0 = 1
  1 XOR 1 = 0
3. 题目：终端发送帧序列为1101011111，使用生成多项式为G(x)=x^4+x+1校验后发出的帧为序列为11010111110010