CRC校驗碼算法
循环冗余校验(英语:Cyclic redundancy check,通称“CRC”)是一种根据网上数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数,主要用来检测或校验数据传输或者保存后可能出现的错误。
由于本函数易于用二进制的计算机硬件使用、容易进行数学分析并且尤其善于检测传输通道干扰引起的错误,因此获得广泛应用。此方法是由W. Wesley Peterson于1961年发表。
CRC是什么
设计冗余码的原则就是:用最小的代价,检测(纠正)最多的错误。
CRC是一种优秀的检错码。它的计算原理,说白了就是作除法。把比特流看作多项式的系数。设定一个生成多项式(generator polynomial)作为除数。数据流看作被除数。发送方需要在数据流末尾加上一段冗余码,使得组合后的新数据流能够整除除数。
名称 | 生成多项式 | 简记式 |
---|---|---|
CRC-4 | x4+x+1 | 0x03 |
CRC-8 | x8+x5+x4+1 | 0x31 |
CRC-8 | x8+x2+x1+1 | 0x07 |
CRC-8 | x8+x6+x4+x3+x2+x1 | 0x5E |
CRC-12 | x12+x11+x3+x+1 | 0x080F |
CRC-16 | x16+x15+x2+1 | 0x8005 |
CRC16-CCITT | x16+x12+x5+1 | 0x1021 |
CRC-32 | x32+x26+x23+...+x2+x+1 | 0x04C11DB7 |
这段冗余码就是所谓的CRC(如何计算?在数据流末尾补CRC长度的0,然后做除法得到的余数就是了。)发送方计算好CRC后,把它加到末尾。然后接收方通过传过来的数据做除法计算余数,如果余数不为0,就说明有错误发生。
这个除法与普通的十进制除法不同,它是模2除法。换句话说,CRC的计算就是:基于有限域GF(2)(即除以2的同余)的多项式环。
CRC具有线性的性质。它适合用来“对抗自然”,即排除随机干扰,但并不适合防御恶意的人为修改。所以CRC被用于通信,而不是网络安全领域。
正向算法
假设数据传输过程中需要发送15位的二进制信息g=101001110100001
,这串二进制码可表示为代数多项式g(x) = x^14+x^12+x^9+x^8+x^7+x^5+1
,其中g中第k位的值,对应g(x)中x^k
的系数。将g(x)乘以x^m,既将g后加m个0,然后除以m阶多项式h(x),得到的(m-1)阶余项r(x)对应的二进制码r就是CRC编码。
h(x)可以自由选择或者使用国际通行标准,一般按照h(x)的阶数m,将CRC算法称为CRC-m,比如CRC-32、CRC-64等。g(x)和h(x)的除运算,可以通过g和h做xor(异或)运算。
举一个例子使用CRC-8算法求101001110100001的效验码.CRC-8标准的h(x) = x8+x7+x6+x4+x^2+1,既h是9位的二进制串111010101。
经过迭代运算后,最终得到的r是10001100,这就是CRC效验码。
- 每次迭代,根据gk的首位决定b,b是与gk进行运算的二进制码。若gk的首位是1,则b=h;若gk的首位是0,则b=0,或者跳过此次迭代,上面的例子中就是碰到0后直接跳到后面的非零位。
- 每次迭代,gk的首位将会被移出,所以只需考虑第2位后计算即可。这样就可以舍弃h的首位,将b取h的后m位。比如CRC-8的h是111010101,b只需是11010101。
- 每次迭代,受到影响的是gk的前m位,所以构建一个m位的寄存器S,此寄存器储存gk的前m位。每次迭代计算前先将S的首位抛弃,将寄存器左移一位,同时将g的后一位加入寄存器。
蓝色表示寄存器S的首位,是需要移出的,b根据S的首位选择0或者h。黄色是需要移入寄存器的位。S'是经过位移后的S。
查表算法
同样是上面的那个例子,将数据按每4位组成1个block,这样g就被分成6个block。
下面的表展示了4次迭代计算步骤,灰色背景的位是保存在寄存器中的。
经4次迭代,B1被移出寄存器。被移出的部分,不我们关心的,我们关心的是这4次迭代对B2和B3产生了什么影响。注意表中红色的部分,先作如下定义:
B23 = 00111010 |
4次迭代对B2和B3来说,实际上就是让它们与b1,b2,b3,b4做了xor计算,可以证明xor运算满足交换律和结合律,于是:B23 xor (b1 xor b2 xor b3 xor b4) = B23 xor b'
b1是由B1的第1位决定的,b2是由B1迭代1次后的第2位决定(既是由B1的第1和第2位决定),同理,b3和b4都是由B1决定。通过B1就可以计算出b'
另外,B1由4位组成,其一共2^4有种可能值。于是我们就可以想到一种更快捷的算法,事先将b'所有可能的值,16个值可以看成一个表;
这样就可以不必进行那4次迭代,而是用B1查表得到b'值,将B1移出,B3移入,与b'计算,然后是下一次迭代。
可看到每次迭代,寄存器中的数据以4位为单位移入和移出,关键是通过寄存器前4位查表获得,这样的算法可以大大提高运算速度。
上面的方法是半字节查表法,另外还有单字节和双字节查表法,原理都是一样的——事先计算出28或216个b'的可能值,迭代中使用寄存器前8位或16位查表获得b'。
反向算法
之前讨论的算法可以称为正向CRC算法,意思是将g左边的位看作是高位,右边的位看作低位。G的右边加m个0,然后迭代计算是从高位开始,逐步将低位加入到寄存器中。在实际的数据传送过程中,是一边接收数据,一边计算CRC码,正向算法将新接收的数据看作低位。
逆向算法顾名思义就是将左边的数据看作低位,右边的数据看作高位。这样的话需要在g的左边加m个0,h也要逆向,例如正向CRC-16算法h=0x4c11db8,逆向CRC-16算法h=0xedb88320。b的选择0还是h,由寄存器中右边第1位决定,而不是左边第1位。寄存器仍旧是向左位移,就是说迭代变成从低位到高位。
工程常用CRC校验
- 余数初始值:即在计算开始前,先给变量CRC赋的初值。
- 结果异或值:即在计算结束后,得到的变量CRC与这个值进行异或操作,就得到了最终的校验值。
- 输入数据反转:即在计算开始前,将需要校验的数据反转,如数据位1011,反转后为1101。
- 输出数据反转:即在计算结束后,与结果异或值异或之前,计算值反转,如计算结果为1011,反转后为1101。
CRC算法名称 | 多项式公式 | 宽度 | 多项式(16进制) | 初始值(16进制) | 结果异或值(16进制) | 输入值反转 | 输出值反转 |
---|---|---|---|---|---|---|---|
CRC-4/ITU | x4+x+1 | 4 | 03 | 00 | 00 | true | true |
CRC-5/EPC | x4+x3+1 | 5 | 09 | 09 | 00 | false | false |
CRC-5/ITU | x5+x4+x2+1 | 5 | 15 | 00 | 00 | true | true |
CRC-5/USB | x5+x2+1 | 5 | 05 | 1F | 1F | true | true |
CRC-6/ITU | x6+x+1 | 6 | 03 | 00 | 00 | true | true |
CRC-7/MMC | x7+x3+1 | 7 | 09 | 00 | 00 | false | false |
CRC-8 | x8+x2+x+1 | 8 | 07 | 00 | 00 | false | false |
CRC-8/ITU | x8+x2+x+1 | 8 | 07 | 00 | 55 | false | false |
CRC-8/ROHC | x8+x2+x+1 | 8 | 07 | FF | 00 | true | true |
CRC-8/MAXIM | x8+x5+x4+1 | 8 | 31 | 00 | 00 | true | true |
CRC-16/IBM | x16+x15+x2+1 | 16 | 8005 | 0000 | 0000 | true | true |
CRC-16/MAXIM | x16+x15+x2+1 | 16 | 8005 | 0000 | FFFF | true | true |
CRC-16/USB | x16+x15+x2+1 | 16 | 8005 | FFFF | FFFF | true | true |
CRC-16/MODBUS | x16+x15+x2+1 | 16 | 8005 | FFFF | 0000 | true | true |
CRC-16/CCITT | x16+x12+x5+1 | 16 | 1021 | 0000 | 0000 | true | true |
CRC-16/CCITT-FALSE | x16+x12+x5+1 | 16 | 1021 | FFFF | 0000 | false | false |
CRC-16/x5 | x16+x12+x5+1 | 16 | 1021 | FFFF | FFFF | true | true |
CRC-16/XMODEM | x16+x12+x5+1 | 16 | 1021 | 0000 | 0000 | false | false |
CRC-16/DNP | x16+x13+x12+x11+x10+x8+x6+x5+x2+1 | 16 | 3D65 | 0000 | FFFF | true | true |
CRC-32 | x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 | 32 | 04C11DB7 | FFFFFFFF | FFFFFFFF | true | true |
CRC-32/MPEG-2 | x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 | 32 | 04C11DB7 | FFFFFFFF | 00000000 | false | false |
接下来以CRC-16/IBM校验为例,讲解工程中使用的CRC校验编程实现。具体实现时,以字节为单位进行计算。
- 预置1个16位的变量CRC,存放校验值,首先根据表3-1赋初值0x0000;
- 将第1个字节按照表看是否需要反转,若需要,则按反转,若不需要,直接进入第3步。这里需要反转;
- 把第1个字节按照步骤2处理后,与16位的变量CRC的高8位相异或,把结果放于变量CRC,低8位数据不变;
- 把变量CRC的内容左移1位(朝高位)用0填补最低位,并检查左移后的移出位;
- 如果移出位为0:重复第4步(再次左移一位);如果移出位为1,变量CRC与多项式8005(1000 0000 0000 0101)进行异或;
- 重复步骤4和5,直到左移8次,这样整个8位数据全部进行了处理;
- 重复步骤2到步骤6,进行通讯信息帧下一个字节的处理;
- 将该通讯信息帧所有字节按上述步骤计算完成后,将得到的16位变量CRC按照表3-1看是否需要反转,这里需要反转;
- 最后,与结果异或值异或,得到的变量CRC即为CRC校验值;