CRC算法原理

CRC校验算法

CRC(Cyclic Redundancy Check)循环冗余校验是常用的数据校验方法，讲CRC算法的文章很多，之所以还要写这篇，是想换一个方法介绍CRC算法，希望能让大家更容易理解CRC算法。

先说说什么是数据校验。数据在传输过程（比如通过网线在两台计算机间传文件）中，由于传输信道的原因，可能会有误码现象（比如说发送数字5但接收方收到的却是6），如何发现误码呢？方法是发送额外的数据让接收方校验是否正确，这就是数据校验。最容易想到的校验方法是和校验，就是将传送的数据(按字节方式)加起来计算出数据的总和，并将总和传给接收方，接收方收到数据后也计算总和，并与收到的总和比较看是否相同。如果传输中出现误码，那么总和一般不会相同，从而知道有误码产生，可以让发送方再发送一遍数据。 CRC校验也是添加额外数据做为校验码，这就是CRC校验码，那么CRC校验码是如何得到的呢？

非常简单，CRC校验码就是将数据除以某个固定的数（比如ANSI-CRC16中，这个数是0x18005），所得到的余数就是CRC校验码。

那这里就有一个问题，我们传送的是一串字节数据，而不是一个数据，怎么将一串数字变成一个数据呢？这也很简单，比如说2个字节B1，B2,那么对应的数就是(B1<<8)+B2；如果是3个字节B1，B2，B3，那么对应的数就是((B1<<16)+(B2<<8)+B3),比如数字是0x01,0x02,0x03，那么对应的数字就是0x10203；依次类推。如果字节数很多，那么对应的数就非常非常大，不过幸好CRC只需要得到余数，而不需要得到商。

从上面介绍的原理我们可以大致知道CRC校验的准确率，在CRC8中出现了误码但没发现的概率是1/256，CRC16的概率是1/65536，而CRC32的概率则是1/2^32，那已经是非常小了，所以一般在数据不多的情况下用CRC16校验就可以了，而在整个文件的校验中一般用CRC32校验。

这里还有个问题，如果被除数比除数小，那么余数就是被除数本身，比如说只要传一个字节，那么它的CRC就是它自己，为避免这种情况，在做除法之前先将它移位，使它大于除数，那么移多少位呢？这就与所选的固定除数有关了，左移位数比除数的位数少1，下面是常用标准中的除数：

CRC8：多项式是X8+X5+X4+1，对应的数字是0x131，左移8位

CRC12：多项式是X12+X11+X3+X2+1，对应的数字是0x180D，左移12位 CCITT CRC16：多项式是X16+X12+X5+1，对应的数字是0x11021，左移16位 ANSI CRC16：多项式是X16+X15+X2+1，对应的数字是0x18005，左移16位

CRC32：多项式是X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1，对应数字是0x104C11DB7，左移32

因此，在得到字节串对应的数字后，再将数字左移M位（比如ANSI-CRC16是左移16位），就得到了被除数。

好了，现在被除数和除数都有了，那么就要开始做除法求CRC校验码了。CRC除法的计算过程与我们笔算除法类似，首先是被除数与除数高位对齐后，被除数减去除数，得到了差，除数再与差的最高位对齐，进行减法，然后再对齐再减，直到差比除数小,这个差就是余数。不过和普通减法有差别的是，CRC的加(减)法是不进(借)位的，比如10减01，它的结果是11，而不是借位减法得到的01，因此，实际上CRC的加法和减法所得的结果是一样的，比如10加01的结果是11，10减01的结果也是11，这其实就是异或操作。虽然说了这么多也不一定能说清楚,我们还是看一段CRC除法求余程序吧:

/* 这段程序是求数据0x880000除以0x11021的余数 */

/* 这段程序其实也就是求字节0x88的CRC16校验码，因为0x88左移16位是0x880000 */ unsigned short crc16_div() {

unsigned long data = 0x880000; unsigned long ccitt16 = 0x11021;

/* 这是比较值,被除数与它比较看是否需要减去除数

注意,这里只需要与0x10000比较就可以了,而不需要与除数0x18005比较,这样可以少很多计算

而且余数的范围就在0-0xFFFF之间,而不是0-0x18004之间了 */ unsigned long cmp_value = 0x10000;

int i;

ccitt16 <<= 7; /* 左移7位,与被除数最高位对齐 */ cmp_value <<= 7; /* 左移7位,与被除数最高位对齐 */

while (cmp_value >= 0x10000) /* 循环直到差数比cmp_value小 */ {

if ((data & cmp_value) != 0) /* 最高位为1,则减去除数 */ {

data ^= ccitt16; /* 做CRC的减法,就是异或操作 */ }

else /* 最高位为0,不够减 */ {

/* 不作任何操作，只执行后面的移位操作 */ }

/* 得到了差,右移一位,与被除数下一位对齐 */ ccitt16 >>= 1; cmp_value >>= 1; }

/* 现在data的最低两个字节就是余数,也就是CRC校验码 */ return (data & 0xFFFF); }

好了，现在我们已经会计算0x88的CRC校验码了，它只是对0x880000做除法运算求余数而已，不过这只是求单字节的CRC校验码，那如果有十多个字节怎么办？我们的计算机也存不下那么大的数呀，看来我们还要对程序进行些改进，使它能对大数求除法了。 unsigned short crc16_div_2()

{

/* 这段程序也是求数据0x88的CRC校验码，与上一个程序crc16_div所得结果相同 */

/* 这里只需要直接传数据就可以，而不需要再事先移位 */ unsigned short data = 0x88;

/* 这里只需要2个字节0x1021，而不是0x11021，为什么不再需要最高位的1，看看代码就清楚了 */

unsigned short ccitt16 = 0x1021;

int i;

data <<= 8;

for (i=0; i<8; i++) {

if (data & 0x8000) /* 最高位为1,减去除数 */ {

data <<= 1; /* 将最高位的1移出,剩下的数与0x1021(而不是0x11021)异或,这是因为最高位的1与0x11021的最高位1异或后为0 */ data ^= ccitt16; }

else /* 最高位为0,不需要减去除数 */ {

data <<= 1; /* 直接移位 */ } }

return data; }

现在对单字节0x88求CRC16，我们只需要两字节short型的整数就行了，而不需要象以前必须用long型0x880000，其实不管多少字节，只用short型就能够计算它的CRC16。下面说说怎么求多字节的样验码：

当我们求得一个字节（比如0x88）的CRC校验码后，如果这时又有一个字节(比如0x23)加入，需要求校验码，该怎么办呢？以前得到的是0x880000除以0x11021的余数，但现在需要得到的是0x88230000除以0x11021的余数，以前求得的校验码是不是白费了？不是的，因为当我们得到0x880000除以0x11021的余数（这里余数是0x1080）后，需要求0x88230000除以0x11021的余数，只要将原来的余数0x1080左移8位除以0x11021就得到了0x98000000除以0x11021的余数<0x108000除以0x11021的余数>（想一想为什么），再加上0x230000除以0x11021的余数。这其实就是求0x108000+0x230000除以0x11021的余数.。因此根据这个方法，我们就可以写出求多个字节的CRC算法：

/* 这段代码是求ccitt-crc16的算法 参数： data:字节数据

crc:原来数据求得的crc校验码 返回值：

数据的ccitt-crc16校验码 */

unsigned short crc16_ccitt(unsigned char data, unsigned short crc) {

unsigned short ccitt16 = 0x1021;

int i;

crc ^= (data<<8); /* 新的数据与将原来的余数（就是crc）相加（加法就是异或操作） */

/* 求数据的CRC校验码 */ for (i=0; i<8; i++) {

if (crc & 0x8000) /* 最高位为1,减去除数 */ {

crc <<= 1; crc ^= ccitt16; }

else /* 最高位为0,不需要减去除数 */ {

crc <<= 1; /* 直接移位 */ } }

return crc; }

/* 这是个主程序，表示如何计算5个字节的CRC */ void main() {

int i;

unsigned short crc;

char data[5] = { 0x71, 0x88, 0x93, 0xa5, 0x13 }; /* 计算这5个数据的CRC校验码 */

crc = 0;

for (i=0; i<5; i++) {

crc = crc16_ccitt(data[i], crc);

}

printf(\}

好了，讲到这里CRC算法已经全部介绍完了。什么，讲完了？不对呀，我怎么记得CRC程序都有个数组叫CRC表什么的，你这里怎么没有？

呵呵，其实使用CRC表是为了节省一些运算时间，事先将算好的CRC保存在数组里，省得临时再计算，它保存的是0到0xff的CRC码，下面我们来自己生成一个CRC表： unsigned short CRC16_CCITT_TABLE[256];

void init_crc16_ccitt_table() {

int i;

for (i=0; i<256; i++) {

CRC16_CCITT_TABLE[i] = crc16_ccitt(i, 0); } }

上面只是一个字节的CRC表，那多个字节的CRC如何计算呢？与前面求多字节的CRC方法差不多，它的代码如下：

/* 这段代码是查表求ccitt-crc16的算法，它与前面的程序crc16_ccitt所得到的结果一样 参数： data:字节数据

crc:原来数据求得的crc校验码 返回值：

数据的ccitt-crc16校验码

*/

unsigned short crc16_ccitt_2(unsigned char data, unsigned short crc) {

unsigned char c;

c = crc >> 8; /* c的值为crc的高8位 */

crc <<= 8; /* crc现在的值变为低8位左移8位 */ crc ^= CRC16_CCITT_TABLE[data ^ c]; return crc; }

最后要说的是CRC的正序和反转问题，比如前面ccitt-crc16的正序是0x1021，如果是反转就是0x8408（就是将0x1021倒过来低位变高位）为什么要反转？这是因为数据传输可能是先传低位再传高位（比如串口就是低位在前高位在后）。反转的CRC算法与正序类似，只是需要注意移位的方向相反。

/* 这段代码是求ccitt-crc16的反转算法 参数： data:字节数据

crc:原来数据求得的crc反转校验码 返回值：

数据的ccitt-crc16反转校验码 */

unsigned short crc16_ccitt_r(unsigned char data, unsigned short crc) {

unsigned short ccitt16 = 0x8408;

int i;

crc ^= data; /* 新的数据与将原来的余数（就是crc）相加（加法就是异或操作）

*/

for (i=0; i<8; i++) {

if (crc & 1) /* 最低位为1,减去除数 */ {

crc >>= 1; crc ^= ccitt16; }

else /* 最低位为0,不需要减去除数 */ {

crc >>= 1; /* 直接移位 */ } }

return crc; }

/* 这段代码是查表求反转ccitt-crc16的算法，它与前面的程序crc16_ccitt_r所得到的结果一样 参数： data:字节数据

crc:原来数据求得的crc校验码 返回值：

数据的ccitt-crc16校验码 */

unsigned short crc16_ccitt_r2(unsigned char data, unsigned short crc) {

unsigned char c;

c = crc & 0xff; crc >>= 8;

crc ^= CRC16_CCITT_R_TABLE[data ^ c]; return crc; }

CRC算法及原理

CRC校验码的基本思想是利用线性编码理论， 在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（既CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共(k+r)位，最后发送出去。在接收端，则根据

信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。 在数据存储和数据通讯领域，CRC无处不在:著名的通讯协议X.25的FCS(帧检错序列)采用的是CRC. CCITT，ARJ、LHA等压缩工具软件采用的是CRC32，磁盘驱动器的读写采用了CRC16，通用的图像存储格式GIF、TIFF等也都用CRC作为

检错手段。

CRC的本质是模-2除法的余数，采用的除数不同，CRC的类型也就不一样。通

常，CRC的除数用生成多项式来表示。最常用的CRC码的生成多项式有

CRC16,CRC32.

以CRC16为例,16位的CRC码产生的规则是先将要发送的二进制序列数左移16位（既乘以2^16）后，再除以一个多项式，最后所得到的余数既是CRC码，如下式所示，其中K(X)表示n位的二进制序列数，G(X)为多项式，Q(X)为整数，

R(X)是余数（既CRC码）。 K(X)>>16=G(x)Q(x)+R(x)

求CRC码所采用模2加减运算法则，既是不带进位和借位的按位加减，这种加减运算实际上就是逻辑上的异或运算，加法和减法等价，乘法和除法运算与普通代数式的乘除法运算是一样，符合同样的规律。生成CRC码的多项式如下，其中CRC-16和CRC-CCITT产生16位的CRC码，而CRC-32则产生的是32位的CRC

码

接收方将接收到的二进制序列数（包括信息码和CRC码）除以多项式，如果余数为0，则说明传输中无错误发生，否则说明传输有误，关于其原理这里不再多述。用软件计算CRC码时，接收方可以将接收到的信息码求CRC码，比较结果和接收

到的CRC码是否相同。

CCITT推荐的高级数据链路控制规程HDLC的帧校验序列FCS中，使用CCITT-16即CRC16,其生成多项式为G(x)=x16+x12+x5+1, CRC-32的生成多项式为

G(x)=x32+x26+x23+x22+x16+x11+x10+x16+x8+x7+x5+x4+x2+x+1

CRC算法原理及C语言实现

CRC原理介绍:

CRC的英文全称为Cyclic Redundancy Check（Code），中文名称为循环冗余校验（码）。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。

CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的，而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数，在CRC运算中我们称之为poly，而宽度W就是poly最高位的位置。比如poly 1001的W是3，而不是4。注意最高位总是1，当你选定一个宽度，那么你只需要选择低W各位的值。假如我们想计算一个位串的CRC码，并要保证每一位都要被处理，因此我们需要在目标位串后面加上W个0。下面举例说明CRC算法的过程。

在此例中，我们假设位串为110101101。

Poly = 10011（宽度W = 4） Bitstring + W zeros = 110101101 0000

10011/1101011010000/110000101 （我们不关心此运算的商） 10011|||||||| -----|||||||| 10011||||||| 10011||||||| -----|||||||

00001|||||| 00000|||||| -----|||||| 00010||||| 00000||||| -----||||| 00101|||| 00000|||| -----|||| 01010||| 00000||| -----||| 10100|| 10011|| -----|| 01110| 00000| -----| 11100 10011 -----

1111 -> 余数 -> CRC！ 计算过程总结如下：

1. 只有当位串的最高位为1，我们才将它与poly做XOR运算，否则我们只是将位

串左移一位。

2. 异或运算的结果实质上是被操作位串与poly的低W位进行运算的结果，因为最高位总为0。

CRC原理及其逆向破解方法：

介绍：

这篇短文包含CRC原理介绍和其逆向分析方法,很多程序员和破解者不是很清楚了解

CRC的工作原理,而且几乎没人知道如何逆向分析它的方法,事实上它是非常有用的. 首先,这篇教程教你一般如何计算CRC,你可以将它用在数据代码保护中.第二,主要是

介绍如何逆向分析CRC-32,你可以以此来分析程序中的CRC保护（象反病毒编码）.当然

有很多有效的工具用来对付CRC,但我怀疑它是否会说明原理.

我要告诉你,这篇短文里中应用了很多数学知识,这不会影响一些人,而且会被一般的

程序员与逆向分析者很好理解.为什么？那么如果你不知道数学是如何被应用在CRC中,

我建议你可以停止继续学习了.所以我假定你们（读者）都是具备二进制算术知识的.

第一部分：CRC 介绍,CRC是什么和计算CRC的方法.

循环冗余码 CRC

我们都知道CRC.甚至你没有印象,但当你想到那些来自诸如RAR,ZIP等压缩软件发给你

由于错误连接和其他一些意外原因导致的文件错误的恼人的消息时,你就会知道.CRC是块

数据的计算值,比如对每一个文件进行压缩.在一个解压缩过程中,程序会从新计算解

压文件

的CRC值,并且将之与从文件中读取的CRC值进行比对,如果值相同,那么正确.在CRC-32中,

会有1/2^32的可能性发生对确认数据更改的校验错误.

很多人认为CRC就是循环冗余校验,假如CRC真的就是循环冗余校验,那么很多人都错用了

这个术语.你不能说\这个程序的CRC是12345678\人们也常说某一个程序有CRC校验,而不

说是 \循环冗余校验\校验.结论：CRC 代表循环冗余码,而不是循环冗余校验. 计算是如何完成的呢？好,主要的想法就是将一个文件看成一个被一些数字分割的很长的

位字串,这里会有一个余数---CRC！你总会有一个余数(可以是0),它至多比除数小一. (9/3=3 余数=0 ; (9+2)/3=3 余数=2) (或者它本身就包含一个除数在其中).

在这里CRC计算方法与除法有一点点区别,除法就是将被减数重复的减去除数X次,然后留下

余数.如果你希望得到原值,那么你就要把除数乘上X次,然后加上余数.

CRC计算使用特殊的减法与加法完成的.也就是一种新的\算法\计算中每一位计算的进位值 被\遗忘\了.

看如下两个例子,1是普通减法,2和3是特殊的. -+

(1) 1101 (2) 1010 1010 (3) 0+0=0 0-0=0 1010- 1111+ 1111- 0+1=1 *0-1=1 ---- ---- ---- 1+0=1 1-0=1

0011 0101 0101 *1+1=0 1-1=0

在(1)中,右数第二列可以看成是0-1=-1,因此要从高位借1,就变成(10+0)-1=1.(这就象普通

的'by-paper'十进制减法).特例(2,3)中,1+1会有正常的结果10,'1'是计算后的进位.这个值

被忽略了.特殊情况0-1应该有正常结果'-1'就要退到下一位.这个值也被忽略了.假如你对编程

有一定了解,这就象,XOR 操作或者更好. 现在来看一个除法的例子: 在普通算法中:

1001/1111000\\1101 13 9/120\\13 1001 - 09 -| ---- -- | 1100 30 | 1001 - 27 - ---- --

0110 3 -> 余数 0000 - ---- 1100 1001 - ----

011 -> 3, 余数

在CRC算法中:

1001/1111000\\1110 9/120\\14 余数为 6 1001 - ---- 1100 1001 - ---- 1010 1001 - ---- 0110 0000 - ----

110 -> 余数 (例 3)

这个除法的商并不重要,也没必要去记住,因为他们仅仅是一组无关紧要的位串.真正

重要的是余数!它就是这个值,可以说比原文件还重要的值,他就是基本的CRC.

过度到真正的CRC码计算.

进行一个CRC计算我们需要选则一个除数,从现在起我们称之为\宽度W就是最高位

的位置,所以这个poly 1001的W 是3,而不是4.注意最高位总是1,当你选定一个宽

度,那么你只

需要选择低W各位的值.

假如我们想计算一个位串的CRC码,我们想确定每一个位都被处理过,因此,我们要在目标

位串后面加上W个0位.在此例中,我们假设位串为1111.请仔细分析下面一个例子: Poly = 10011, 宽度 W=4 位串 Bitstring

Bitstring + W zeros = 110101101 + 0000

10011/1101011010000\\110000101 (我们不关心此运算的商) 10011|||||||| - -----|||||||| 10011||||||| 10011||||||| - -----||||||| 00001|||||| 00000|||||| - -----|||||| 00010||||| 00000||||| - -----||||| 00101|||| 00000|||| - -----|||| 01010|||

00000||| - -----||| 10100|| 10011|| - -----|| 01110| 00000| - -----| 11100 10011 - -----

1111 -> 余数 -> the CRC! (例 4)

重要两点声明如下:

1.只有当Bitstring的最高位为1,我们才将它与poly做XOR运算,否则我们只是将 Bitstring左移一位.

2.XOR运算的结果就是被操作位串bitstring与低W位进行XOR运算,因为最高位总为0.

算法设计:

你们都应知道基于位运算的算法是非常慢的而且效率低下.但如果将计算放在每一字节上

进行,那么效率将大大提高.不过我们只能接受poly的宽度是8的倍数(一个字节;).

可以形

象的看成这样一个宽度为32的poly(W=32): 3 2 1 0 byte +---+---+---+---+

Pop! <--| | | | |<-- bitstring with W zero bits added, in this case 32 +---+---+---+---+

1<--- 32 bits ---> this is the poly, 4*8 bits (figure 1)

这是一个你用来存放暂时CRC结果的记存器,现在我称它为CRC记存器或者记存器.你从右

至左移动位串,当从左边移出的位是1,则整个记存器被与poly的低W位进行XOR运算.(此例

中为32).事实上,我们精确的完成了上面除法所做的事情.

移动前记存器值为:10110100

当从右边移入4位时,左边的高4位将被移出,此例中1011将被移出,而1101被移入.

情况如下:

当前8位CRC记存器 : 01001101 刚刚被移出的高4位 : 1011

我们用此poly : 101011100, 宽度 W=8 现在我们用如前介绍的方法来计算记存器的新值. 顶部 记存器

---- --------

1011 01001101 高四位和当前记存器值

1010 11100 + (*1) Poly 放在顶部最高位进行XOR运算 (因为那里是1) -------------

0001 10101101 运算结果 现在我们仍有一位1在高4位: 0001 10101101 上一步结果

1 01011100+ (*2) Poly 放在顶部的最低位进行XOR运算 (因为那里是1) -------------

0000 11110001 第二步运算结果 ^^^^

现在顶部所有位均为0,所以我们不需要在与poly进行XOR运算

你可以得到相同的结果如果你先将(*1)与(*2)做XOR然后将结果与记存器值做XOR. 这就是标准XOR运算的特性:

(a XOR b) XOR c = a XOR (b XOR c) 由此,推出如下的运算顺序也是正确的. 1010 11100 poly (*1) 放在顶部最高位 1 01011100+ polys (*2) 放在顶部最低位 -------------

1011 10111100 (*3) XOR运算结果

The result (*3) 将(*3)与记存器的值做XOR运算 1011 10111100

1011 01001101+ 如右:

------------- 0000 11110001

你看到了吗?得到一样的结果!现在(*3)变的重要了,因为顶部为1010则(3)的值总是等于

10111100(当然是在一定的条件之下)这意味着你可以预先计算出任意顶部位结合的XOR值.

注意,顶部结果总是0,这就是组合XOR操作导致的结果.(翻译不准确,保留原文) 现在我们回到figure 1,对每一个顶部字节的值都做移出操作,我们可以预先计算出一个值.

此例中,它将是一个包含256个double word(32 bit)双字的表.(附录中CRC-32的表).

(翻译不准确,保留原文) 用伪语言表示我们的算法如下: While (byte string is not exhausted) Begin

Top = top_byte of register ;

Register = Register shifted 8 bits left ORred with a new byte from string ;

Register = Register XORred by value from precomputedTable at position Top ; End

direct table算法:

上面提到的算法可以被优化.字节串中的字节在被用到之前没有必要经过整个记村器.用

这个新的算法,我们可以直接用一个字节去XOR一个字节串通过将此字节移出记存器.结果

指向预先计算的表中的一个值,这个值是用来被记存器的值做XOR运算的. 我不十分确切的知道为什么这会得到同样的结果(这需要了解XOR运算的特性),但是这又

极为便利,因为你无须在你的字节串后填充0字节/位.(如果你知道原理,请告诉我:) 让我们来实现这个算法:

+----< byte string (or file) 字节串,(或是文件) |

v 3 2 1 0 byte 字节 | +---+---+---+---+

XOR---<| | | | | Register 记存器 | +---+---+---+---+ | | | XOR | ^

v +---+---|---+---+

| | | | | | Precomputed table 值表(用来进行操作) | +---+---+---+---+ +--->-: : : : : +---+---+---+---+

| | | | | +---+---+---+---+ (figure 2)

'reflected' direct Table 算法:

由于这里有这样一个与之相对应的'反射'算法,事情显得复杂了.一个反射的值/记存器

就是将它的每一位以此串的中心位为标准对调形成的.例如:0111011001就是1001101110 的反射串.

他们提出'反射'是因为UART(一种操作IO的芯片)发送每一个字节时是先发最没用的0位,

最后再发最有意义的第七位.这与正常的位置是相逆的.

除了信息串不做反射以外,在进行下一步操作前,要将其于的数据都做反射处理.所以在

计算值表时,位向右移,且poly也是作过反射处理的.当然,在计算CRC时,记存器也要向右

移,而且值表也必须是反射过的. byte string (or file) -->---+

| 1. 表中每一个入口都是反射的. byte 3 2 1 0 V 2. 初始化记存器也是反射的.

+---+---+---+---+ | 3. 但是byte string中的数据不是反射的, | | | | |>---XOR 因为其他的都做过反射处理了. +---+---+---+---+ |

| | XOR V ^ | +---+---|---+---+ | | | | | | | 值表 +---+---+---+---+ | : : : : : <---+ +---+---+---+---+ | | | | | +---+---+---+---+ (figure 3) 我们的算法如下:

1. 将记存器向右移动一个字节.

2. 将刚移出的哪个字节与byte string中的新字节做XOR运算, 得出一个指向值表table[0..255]的索引 3. 将索引所指的表值与记存器做XOR运算. 4. 如数据没有全部处理完,则跳到步骤1.

下面是这个算法的简单的可执行汇编源码:

完整的CRC-32标准所包含的内容: Name : \Width : 32 Poly : 04C11DB7

Initial value : FFFFFFFF Reflected : True XOR out with : FFFFFFFF

作为对你好奇心的奖励, 这里是CRC-16标准: :) Name : \Width : 16 Poly : 8005 Initial value : 0000 Reflected : True XOR out with : 0000

'XOR out with' 是为了最终得到CRC而用来与记存器最后结果做XOR运算的值. 假如你想了解一些关于'reversed'逆向CRC poly的话,请看我的参考文章.

我是在16位DOS模式下用的32位编码,因此你会在这个程序中看到很多32位与16位混合

的编码...当然这是很容易转换成纯32位编码的.注意这个程序是经过完整测试并且能够

正常运行的.下面的Java 和 C 代码都是由这个汇编代码而来的. 底下的这段程序就是用来计算CRC-32 table的: xor ebx, ebx ;ebx=0, 将被用做一个指针. InitTableLoop:

xor eax, eax ;eax=0 为计算新的entry. mov al, bl ;al<-bl

;生成入口. xor cx, cx entryLoop: test eax, 1 jz no_topbit shr eax, 1 xor eax, poly jmp entrygoon no_topbit:

shr eax, 1 entrygoon: inc cx test cx, 8 jz entryLoop

mov dword ptr[ebx*4 + crctable], eax inc bx test bx, 256 jz InitTableLoop

注释: - crctable 是一个包含256个dword的数组. - 由于使用反射算法,EAX被向右移. - 因此最低的8位被处理了. 用Java和C写的代码如下(int is 32 bit):

for (int bx=0; bx<256; bx++){ int eax=0;

eax=eax&0xFFFFFF00+bx&0xFF; // 就是 'mov al,bl' 指令 for (int cx=0; cx<8; cx++){ if (eax&&0x1) { eax>>=1; eax^=poly; }

else eax>>=1; }

crctable[bx]=eax; }

下面的汇编代码是用来计算CRC-32的: computeLoop: xor ebx, ebx xor al, [si] mov bl, al shr eax, 8

xor eax, dword ptr[4*ebx+crctable] inc si

loop computeLoop xor eax, 0FFFFFFFFh

注释: - ds:si 指向将要被处理的byte string信息流. - cx 信息流的长度. - eax 是当前的CRC.

- crctable是用来计算CRC的值表. - 此例中记存器的初始值为: FFFFFFFF.

- 要将中间值与FFFFFFFFh做XOR才能得到CRC 下面是Java和C写的代码: for (int cx=0; cx>=8; eax^=crcTable[ebx]; }

eax^=0xFFFFFFFF;

现在我们已经完成了本文的第一部分:CRC原理部分,所以如果你希望能够对CRC做更深

的研究,那么我建议你去读在本文最后给出连接上的资料,我读了.好了,终于到了本文最

有意思的部分,CRC的逆向分析!

------------------------------------------------------------------------------------ 第二部分 CRC的逆向分析:

我遇到了很多障碍,当我思考如何破解CRC时.我试图使用一些特殊顺序的字节使CRC无效.

但我没有做到...后来我意识到这种方法是行不同的,因为CRC内建了一些处理过程,

无论你

改变任何位它都不会出问题,真正的CRC就是在不断变化的,总是在变化的.找一些CRC程序,

你可以自己尝试一下.

现在我知道我只能'纠正'在CRC后面的那些我想改变的字节.所以我要构造一个字节序列,

它可以将CRC转化成任何我想要的样子!

具体实现这个想法

一个字节串? 01234567890123456789012345678901234567890123456789012

You want to change from ^ this byte to ^ this one. 就是位置9->26.

同时我们需要额外的4个字节用来在最后恢复原始字节串.

当你计算CRC-32时,从0-8都没有问题,直到第9位,修补过的字节串会使CRC发生根本的改变.

即使当走过了第26位,以后的字节都没有改变,你也不可能在得到原始的CRC了,不可能了!你读

过后面的段落时就会明白为什么.间而言之,当你修改一个字节串时,要保证CRC不变.

1. 计算并保存从1~9位的CRC.

2. 继续计算直到第27位还有额外的4字节并保存结果.

3. 用1的值来计算新的字节串和额外4字节的CRC(对应patch后的新的CRC值),

并将之保存.

4. 现在我们得到了一个新的CRC,但是我们希望将它还原成原先的CRC,所以我们用逆向算法

来计算那额外的4字节.

1~3就是实际的情况,下面你将学到最关键的部分4.

'反转'CRC-16

我想,先来介绍计算逆CRC-16对于你来说会简单些.好的,我们现在处在一个恰当的位置,

在以修改代码后面,就是你想将CRC还原的地方.我们知道原始的CRC(是在patch代码之前计

算出来的)还有这个当前的记存器值.现在我们的目的就是计算可以改变当前记存器值到原

始记存器值的两个字节.首先,我们用正常的方法计算这两个未知字节的CRC.我们设他们为

X,Y.设记存器为a1,a0,只有0不能用来作为变量(00).:)在来看一下我们的CRC算法,figure

3,更好的理解下面我要做的. 好,我们开始:

用这两字节串'X Y' 字节是从左边开始被处理的. 记存器现在是a1 a0.

用'+'来表示XOR运算(和第一部分中用的一样)

处理第一个字节, X:

a0+X 这是顶部字节的计算结果 (1) b1 b0 这是(1)在表中索引对象. 00 a1 向右移动记存器.

00+b1 a1+b0 上面两行对应位做XOR运算. 现在记存器为: (b1) (a1+b0)

处理第二个字, Y:

(a1+b0)+Y 此轮顶部字节的计算结果(2) c1 c0 这是(2)在表中的索引对象. 00 b1 向右移动记存器.

00+c1 b1+c0 上面两行对应位做XOR运算. 最后记存器就是: (c1) (b1+c0)

我用一点不同的方法来表示:

a0 + X =(1) 在表中指向b1 b0. a1 + b0 + Y =(2) 在表中指向c1 c0. b1 + c0=d0 记存器中新的低位字节. c1=d1 记存器中新的高位字节. (1) (2)

Wow! 请大家暂时记住上面的信息:) 别着急, 下面给出一个有具体值的例子.

如果你想要的记存器的值是d1 d0(是原始的CRC),而且你知道在变换之前的记存

器的值

(a1 a0)...那么你将要送如什么样的2个字节进记存器来做CRC计算呢? 好了,现在我们的工作应该从幕后走到台前来了.d0一定是bi+c0,并且d1一定是c1...

但是这到底是怎么回事,我听到你这样问了,你能知道b1和c0的值吗???你还记得哪个值表

吗?你只需要在表中查找c0 c1这个字的值就可以了因为你知道c1.所以你需要编写一个查

找程序.假如你找到了这个值,一定要记住这个值的索引,因为这就是找出未知的两个顶部

字节,举例来说:(1)和(2)!

所以,现在你找到了c1 c0,那么如何来得到b1 b0呢?如果b1+c0=d0那么b1=d0+c0!如前所

述,现在你用哪个查找程序在表中查b1 b0的值.现在我们得到了所有计算X和Y所需要的值. Cool huh?

a1+b0+Y=(2) so Y=a1+b0+(2) a0+X=(1) so X=a0+(1) 实例.

让我们来看看这个具体值的例子: -register before: (a1=)DE (a0=)AD -wanted register: (d1=)12 (d0=)34

在附录的CRC-16的表中查找以12开头值的入口.这里入口38h的值为12C0.试这

找一找是否还

有以12开头的值的入口.你不可能在找到的,因为我们计算每一中顶部字节组合而得的值的

入口,一共是256个值,记住!

现在我们知道(2)=38,c1=12,c0=C0,所以b1=C0+34=F4,现在查找以F4开头的b1的入口.这里

入口4Fh的值是F441.

我们还知道 (1)=4F,b1=F4,b0=41,现在所有我们需要的都已经清楚了,接下来我们计算X,Y.

Y=a1+b0+(2)=DE+41+38=A7 X=a0+(1) =AD+4F =E2

结论:将CRC 记存器的值从 DEAD 变为 1234 我们需要这两个字节 E2 A7 (以此顺序).

你看,破解CRC校验你需要反向计算,还有要记住的就是计算过程中的值.当你在用汇编编写

查找表程序时,要注意intel在小模式中是反向存储值的.现在你可能已经明白如何去破解这个

CRC-16了...下面介绍如何在CRC-32中实现.

破解 CRC-32

现在我们来看CRC-32,和CRC-16是一样容易的(可能一样的不容易你认为).这里你操作的对象

是4个字节的而不是2字节的.继续向下看,将它与上面CRC-16版本做对比.

设4字节串 X Y Z W , 从左边开始处理. 设记存器为 a3 a2 a1 a0 注意a3是MSB,而a0是LSB

处理第一个字节, X:

a0+X 这是顶部字节的计算结果(1). b3 b2 b1 b0 这是(1)在表中索引对象序列. 00 a3 a2 a1 右移记存器.

00+b3 a3+b2 a2+b1 a1+b0 上面两行对应位做XOR运算. 现在记存器是: (b3) (a3+b2) (a2+b1) (a1+b0) Processing second byte, Y:

(a1+b0)+Y 这是顶部字节的计算结果(2). c3 c2 c1 c0 这是(2)在表中索引对象序列. 00 b3 a3+b2 a2+b1 右移记存器.

00+c3 b3+c2 a3+b2+c1 a2+b1+c0 上面两行对应位做XOR运算. 现在记存器是: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0) Processing third byte, Z:

(a2+b1+c0)+Z 这是顶部字节的计算结果(3). d3 d2 d1 d0 这是(3)在表中索引对象序列.

00 c3 b3+c2 a3+b2+c1 右移记存器.

00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 上面两行对应位做XOR运算. 现在记存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0) Processing fourth byte, W:

(a3+b2+c1+d0)+W 这是顶部字节的计算结果(4). e3 e2 e1 e0 这是(4)在表中索引对象序列. 00 d3 c3+d2 b3+c2+d1 右移记存器.

00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 上面两行对应位做XOR运算. 最后,记存器为: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)

我用一个不同一点的方法来表示:

a0 + X =(1) 在表中指向 b3 b2 b1 b0 a1 + b0 + Y =(2) 在表中指向 c3 c2 c1 c0 a2 + b1 + c0 + Z =(3) 在表中指向 d3 d2 d1 d0 a3 + b2 + c1 + d0 + W =(4) 在表中指向 e4 e3 e2 e1 b3 + c2 + d1 + e0 =f0 c3 + d2 + e1 =f1 d3 + e2 =f2 e3 =f3 (1) (2) (3) (4) (figure 4)

这里是用的与CRC-16同样的方法来实现的,我会给出一个具体值的例子.查找用附录中

CRC-32的值表.

Take for CRC register before, a3 a2 a1 a0 -> AB CD EF 66

Take for CRC register after, f3 f2 f1 f0 -> 56 33 14 78 (wanted value) 我们开始:

First byte of entries entry value

e3=f3 =56 -> 35h=(4) 56B3C423 for e3 e2 e1 e0 d3=f2+e2 =33+B3 =E6 -> 4Fh=(3) E6635C01 for d3 d2 d1 d0 c3=f1+e1+d2 =14+C4+63 =B3 -> F8h=(2) B3667A2E for c3 c2 c1 c0 b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 for b3 b2 b1 b0

Now we have all needed values, then X=(1)+ a0= DE+66=B8 Y=(2)+ b0+a1= F8+D3+EF=C4 Z=(3)+ c0+b1+a2= 4F+2E+FF+CD=53 W=(4)+d0+c1+b2+a3=35+01+7A+6B+AB=8E (final computation)

结论:要将 CRC-32 的记存器的值从 ABCDEF66 改变到 56331478 我们需要这样一个字节

序列: B8 C4 53 8E

CRC-32的破解算法

假如你考虑手动计算这个可以还原CRC记存器的字节序列,那么这将很难变成一个

简洁的算法.

看看下面这个最后计算的附加版本: Position X =(1) + a0 0 Y =(2) + b0 + a1 1 Z =(3) + c0 + b1 + a2 2 W =(4) + d0 + c1 + b2 + a3 3 f0= e0 + d1 + c2 + b3 4 f1= e1 + d2 + c3 5 f2= e2 + d3 6 f3= e3 7 (figure 5)

它就等同于figure 4,只不过是一些值/字节被交换了.这种方法可以帮助我们构造一个

简洁的算法.这里我们用一个8字节的缓冲区,0-3位我们放置a0到a3,4-7位我们放置f0到

f3.象以前一样,我们用这个已知值e3(由figure 5中得知)在表中查出(e3 e2 e1 e0),并且

象图5(figure 5)中所示,将它们放到第4位(position 4),我们马上得到了d3的值.因为f2=

e2+d3,所以f2+e2=d3.又因为(4)已知(入口值),我们照样把它也放到位置3.然后在用d3查表

得到(d3 d2 d1 d0),同上也将他们放到图中所述位置.同样,由于有f1+e1+d2=c3在位置5上.

我们继续做直到将b3 b2 b1 b0放到位置1,对了，就是它! Et voila! 此时,缓冲区的第3-第0字节中已经包含全部元素,用来计算X~W!

算法总结如下:

1.对于这个8字节的缓冲区,0~3字节放入a0...a3(CRC记存器起始值),4~7字节放入f0...f3

(目标记存器的值).

2.取出位置7的已知值,查表得到相应值.

3.将查出值放如图5相应位置,其实就是做XOR运算.(为了直观,可以拟定此图) 4.将入口字节放入图中.也是做XOR运算.

5.继续做2,3两步3次,同时每次降低1个位置 position 5 to 4, 4 to 3 and so on.

算法的实现:

现在是时候给出代码了.下面就是用汇编写成的可执行的CRC-32算法(用其他语言也一样

简单,对于其他的CRC-32标准也一样).注意在汇编中(计算机里)双字在读写操作中顺序都是

反着的.就是逆向顺序. crcBefore dd (?) wantedCrc dd (?) buffer db 8 dup (?)

mov eax, dword ptr[crcBefore] ;/* mov dword ptr[buffer], eax

mov eax, dword ptr[wantedCrc] ; Step 1 mov dword ptr[buffer+4], eax ;*/ mov di, 4 computeReverseLoop:

mov al, byte ptr[buffer+di+3] ;/* call GetTableEntry ; Step 2 */ xor dword ptr[buffer+di], eax ; Step 3 xor byte ptr[buffer+di-1], bl ; Step 4 dec di ;/*

jnz computeReverseLoop ; Step 5 */ Notes:

-Registers eax, di bx are used Implementation of GetTableEntry

crctable dd 256 dup (?) ;should be defined globally somewhere & initialized of course

本文来源：https://www.bwwdw.com/article/hysg.html