关于CRC那些不得不说的事

关于 CRC 相关内容,有遗忘,也有学到新东西,遂写下此文,记录于此

CRC原理

CRCCyclic Redundancy Check),是循环冗余校验码,主要用于传输数据的正确性校验。说简单点,就是原始 k 位数据后面添加一个 r 位的冗余码,构成 n=k+r 位数据

CRC 是基于 GF(2) 的多项式的计算。可以证明存在一个最高次幂为 n-k=r 的多项式 G(x) ,根据 G(x) 可以生成 k 位信息的校验码,而 G(x) 叫做这个 CRC 码的生成多项式(Poly),也叫生成项

根据 k 值的不同,就产生了不同的CRC码的生成多项式,常见的有

  • $CRC16 =x^{16}+x^{15}+x^5+1$
  • $CRC16-CCITT =x^{16}+x^{12}+x^5+1$
  • $CRC32 =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$

其中,一般 ziprar 会用 CRC32

实现算法

根据 CRC 的原理,可以得到它的基本算法流程:

  • 将 $k$ 位数据转成对应的 $GF(2)$ 多项式 $M(x)$
  • 将多项式 $M(x)$ 左移 $r$位,形成多项式 $M'(x)= M(x)*x^r$
  • 用多项式 $M'(x)$ 除以生成项 $G(x)$得到的余数多项式 $R(x)$ ,余数多项式对应的数值就是校验码
  • 发送方通过指定的 $CRC$ 多项式产生 $r$ 位的 $CRC$ 校验码,形成添加了校验码的数据
  • 接收方则通过该 $CRC$ 多项式来验证收到的添加校验码的数据的 $CRC$ 校验码是否为0

直接法(MSB)

上面的思路是人可以理解的思路,为了电脑能够实现,直接计算法的思路就是每次取一部分数据计算

由于是 GF(2) 上的除法,所以每次都是消 1 的过程,那么生成项的高位就可以不用,生成项 Polyr+1 位 ,所以只需要设计一个 r 位寄存器

伪算法如下:

set register=r*0; //设置寄存器为r个0
移位 M << r;      // 在原始数据M后面添加r个0
while( 还有剩余原始数据要处理) {
    从 M 的左边(高位)读1位数据到 resgiser 低位
    将 regitser 左移1位
    if (regitser 左移的是 1){
        register = register xor Poly 
    }  
}

反向算法(LSB)

在大多数硬件系统的传输中,普遍先发送 LSBleast significant bit)。于是出现了反向校验算法。顾名思义,就是将左边的数据看作低位,右边的数据看作高位

伪算法如下:

set register=r*0; //设置寄存器为r个0
while( 还有剩余原始数据要处理) {
    从 M 的左边(低位)读1位数据到 resgiser 低位
    将 regitser 左移1位
    if (读取的 M 是 1){
        register = register xor 逆向Poly 
    }  
}

查表法

数据量大的时候,直接法速度比较慢,查表法便得到了应用。下面便以一个例子来说明查表法的由来

以 $G(x)=x^4+x^3+1$ (即为11001) 为例,设原数据为 1011,有以下计算过程:

    B1      B2
1 0 1 1 | 0 0 0 0
1 1 0 0 | 1 0 0 0       --->a1
-----------------
  1 1 1 | 1 0 0 0
  1 1 0 | 0 1 0 0       --->a2
  ---------------
    0 1 | 1 1 0 0
    0 0 | 0 0 0 0       --->a3
    -------------
      1 | 1 1 0 0
      1 | 1 0 0 1       --->a4
      -----------
          0 1 0 1       --->CRC    

可以看到经过 4 次迭代,B1 被移除。同时显然 CRC = a1 ^ a2 ^ a3 ^ a4 ^ B2 ,定义 A = a1 ^ a2 ^ a3 ^ a4,显然 A 只与 B1 有关,且 CRC = A ^ B2

所以当 B1 被移除后,只需要知道 A 的值,就能计算出 CRC,于是计算时可以一次移除 4位。于此同时 A 的值便是查表法中的表

根据上面的计算,由于 B20,因此 A = CRC。同时可以观察到对于 A 的计算,便是对 B1 块求 CRC 校验值的过程。所以对于表的计算就是对移除数据求 CRC

下面以单字节查表的 CRC32为例,了解算法的具体实现

直接查表法
实现代码如下:

unsigned int r=0;
while(len--){
    r = (r<<8 | *p++) ^ table[ (r>>24) & 0xff ];
}
// for循环的目的是给计算的数据进行补0操作
for(i=0; i<W/8; i++){
    r = (r<<8) ^ table[ (r>>24) & 0xff ];
}

算法流程:

  • 32 位寄存器 r 移除高字节,用于查表
  • 寄存器 r 的其余 3 字节拼接上数据字节
  • 将两者异或得到结果,持续直到计算完

可以用图来帮助理解代码:

            CRC寄存器
          3   2   1   0
        +---------------+  (移入1字节)
    +--<|   |   |   |   | <-----------msg
    |   +---------------+
(移出1字节)     ^
    |           |(XOR)
    |   +---------------+
    |   |               |
    +-->|     TABLE     |
        |               |
        +---------------+

改进查表法
由上图可知,寄存器 r 最开始 4 字节的移动其实没有意义,因为任何值与 0 异或都不改变

同时根据算法,数据第一个字节查表时,整个有效的 CRC计算才算开始,最后一个字节查表时,整个有效的 CRC 计算才算结束

所以实现代码如下:

unsigned int r=0;
while(len--){
    r = (r<<8) ^ table[ (r>>24) ^ *p++ ];
}

算法流程:

  • 32 位寄存器 r 移除高字节,用高字节和数据字节异或,查表
  • 寄存器 r 的其余 3 字节左移 1 字节
  • 将两者异或得到结果,持续直到计算完

可以用图来帮助理解代码:

            CRC寄存器
    +--<msg
    |     3   2   1   0
    |   +---------------+
    +--<|   |   |   |   | 
    |   +---------------+
(移出1字节)     ^
    |           |(XOR)
    |   +---------------+
    |   |               |
    +-->|     TABLE     |
        |               |
        +---------------+

数据字节还没加入时,CRC 中相当于存了叠加态,等该加入数据字节时,直接利用 CRC 最高字节的叠加态和数据字节异或直接查表

反向改进查表法

需要将message的移动方向逆向,在计算表时,所使用的的除数多项式也得将顺序调转。所以实现代码如下:

unsigned int r=0;
while(len--){
    r = (r>>8) ^ table[ (r ^ *p++) & 0xff ];
}

算法流程:

  • 32 位寄存器 r 移除低字节,用低字节和数据字节异或,查表
  • 寄存器 r 的其余 3 字节右移 1 字节
  • 将两者异或得到结果,持续直到计算完

可以用图来帮助理解代码:

            CRC寄存器
                      msg>----+
          3   2   1   0       |
        +---------------+     |
        |   |   |   |   |>----+
        +---------------+     | 
                ^        (移出1字节)
                |(XOR)        |
        +---------------+     |
        |               |     |
        |     TABLE     |<----+
        |               |
        +---------------+

一般来讲,目前的 CRC 实现算法都是反向改进查表法。由于考虑到数据存在 0x00 数据,寄存器用 0xFFFFFFFF 进行初始化,就可以避免异或结果为 0的情况

四字节序列算法

针对 CRC32 的反向改进查表法,由于寄存器右移 8位,寄存器的高 8 位只由表中数据决定

r = (r>>8) ^ table[ (r ^ *p++) & 0xff ];

通过这种特点,可以找到一个四字节序列并将其附加到任何消息中,并获得任何所需的结果CRC散列

原理

下列过程显示了 CRC 算法如何将散列转换为所需的 CRC:AA BB CC DDxx 值为添加四字节序列之前的消息的 CRC

        CRC寄存器
    xx  xx  xx  xx
    00  xx  xx  xx
    DD3 ??  ??  ??  添加第一个字节
    --------------
    DD3 ??  ??  ??
    00  DD3 ??  ??
    CC2 ??  ??  ??  添加第二个字节
    --------------
    CC2 DD2 ??  ??
    00  CC2 DD2 ??
    BB1 ??  ??  ??  添加第三个字节
    --------------
    BB1 CC1 DD1 ??
    00  BB1 CC1 DD1
    AA  ??  ??  ??  添加第四个字节
    --------------
    AA  BB  CC  DD

所以需要最终查找到table中最高字节为别为 AABB1CC2DD3 的索引(即为添加的四字节序列)

首先根据上述过程可以定义如下

初始化:
CRC   = AA  BB  CC  DD
CRC11 = BB1 CC1 DD1 00
CRC22 = CC2 DD2 00  00
CRC33 = DD3 00  00  00

四次迭代之间的关系:
CRC11 = (CRC   ^ T[i3]) << 8 
CRC22 = (CRC11 ^ T[i2]) << 8
CRC33 = (CRC22 ^ T[i1]) << 8 

求解:
CRC   >> 24 == AA
CRC11 >> 24 == BB1
CRC22 >> 24 == CC2
CRC33 >> 24 == DD3
满足等式的i3,i2,i1,i0索引

所以根据上述问题,可以得到一个快速查找四字节序列的方法

  • 建立一个索引表,根据查表法中表的值的高字节做索引,表的索引做值
  • 根据上述等式,每次计算 CRCCRC11CRC22CRC33,并取高字节查索引表,得到逆向的四字节序列,翻转即可

由于可以快速查找到 CRC 对应的四字节序列,那么对于五字节、六字节来说,只需先添加一字节或者两字节,再利用四字节序列算法,也可以快速的得到。更多的字节出现的冲突更多,一般也没什么意义

应用

快速计算 CRC32 对应的 4,5,6 字节,可以用于加密 ZIP 中短文本的明文获取(需要限制添加的字节和四字节序列都在可打印字符中)

具体的实现可以见https://github.com/fromhex/gocrc32

参考

https://python.iitter.com/other/35811.html
https://www.cnblogs.com/masonzhang/p/10261855.html
http://www.danielvik.com/2010/10/calculating-reverse-crc.html
http://www.danielvik.com/2012/01/finding-reverse-crc-patch-with-readable.html
https://github.com/theonlypwner/crc32
tag(s): CRC
show comments
Edit with markdown