CRC算法原理及C语言实现 .doc

资源描述

《CRC算法原理及C语言实现 .doc》由会员分享，可在线阅读，更多相关《CRC算法原理及C语言实现 .doc（39页珍藏版）》请在三一办公上搜索。

1、（一）CRC算法原理及C语言实现 1.CRC原理介绍 CRC的英文全称为Cyclic Redundancy Check（Code），中文名称为循环冗余校验（码）。它是一类重要的线性分组码，编码和解码方法简单，检错和纠错能力强，在通信领域广泛地用于实现差错控制。 CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的，而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数，在CRC运算中我们称之为poly，而宽度W就是poly最高位的位置。比如poly 1001的W是3，而不是4。注意最高位总是1，当你选定一个宽度，那么你只需要选择低W各位的值。假如我们想计算一个位串的CRC码，并

2、要保证每一位都要被处理，因此我们需要在目标位串后面加上W个0。下面举例说明CRC算法的过程。在此例中，我们假设位串为110101101。Poly(除数) = 10011（宽度W = 4）Bitstring + W个0 = 110101101 0000 10011/ 1101011010000/110000101 （我们不关心此运算的商） 10011| -| 10011| 10011| -| 00001| 00000| -| 00010| 00000| -| 00101| 00000| -| 01010| 00000| -| 10100| 10011| -| 01110| 00000| -|

3、11100 10011 - 1111 - 余数 - CRC！计算过程总结如下：1. 只有当位串的最高位为1，我们才将它与poly做XOR运算，否则我们只是将位串左移一位。2. 异或运算的结果实质上是被操作位串与poly的低W位进行运算的结果，因为最高位总为0。2.CRC原理及其逆向破解方法：2.1介绍：这篇短文包含CRC原理介绍和其逆向分析方法,很多程序员和破解者不是很清楚CRC的工作原理,而且几乎没人知道如何逆向分析它的方法，事实上它是非常有用的。首先，这篇教程教你一般如何计算CRC，你可以将它用在数据代码保护中。第二，主要是介绍如何逆向分析CRC-32，你可以以此来分析程序中的CRC保护（

4、象反病毒编码）。当然有很多有效的工具用来对付CRC，但我怀疑它是否会说明原理。我要告诉你，这篇短文里中应用了很多数学知识，这不会影响一些人，而且会被一般的程序员与逆向分析者很好理解，为什么？那么如果你不知道数学是如何被应用在CRC中，我建议你可以停止继续学习了。所以我假定你们（读者）都是具备二进制算术知识的。2.2第一部分：CRC 介绍,CRC是什么和计算CRC的方法2.2.1循环冗余码 CRC我们都知道CRC，甚至你没有印象，但当你想到那些来自诸如RAR，ZIP等压缩软件发给你由于错误连接和其他一些意外原因导致的文件错误的恼人的消息时，你就会知道。CRC是块数据的计算值，比如对每一个文件进行

5、压缩，在一个解压缩过程中，程序会从新计算解压文件的CRC值，并且将之与从文件中读取的CRC值进行比对，如果值相同，那么正确。在CRC-32中，会有1/232的可能性发生对确认数据更改的校验错误。很多人认为CRC就是循环冗余校验。假如CRC真的就是循环冗余校验，那么很多人都错用了这个术语。你不能说这个程序的CRC是12345678。人们也常说某一个程序有CRC校验，而不说是循环冗余校验校验。结论：CRC 代表循环冗余码，而不是循环冗余校验。计算是如何完成的呢？好，主要的想法就是将一个文件看成一个被一些数字分割的很长的位字串，这里会有一个余数CRC！你总会有一个余数(可以是0)，它至多比除数

6、小1。(9/3=3 余数=0 ；(9+2)/3=3 余数=2)(或者它本身就包含一个除数在其中)。在这里CRC计算方法与除法有一点点区别，除法就是将被减数重复的减去除数X次，然后留下余数。如果你希望得到原值，那么你就要把除数乘上X次，然后加上余数。CRC计算使用特殊的减法与加法完成的，也就是一种新的算法。计算中每一位计算的进位值被忽略了。看如下两个例子，（1）是普通减法，（2）和（3）是特殊的。（1）（2）（3）1101101010100+0=00-0=01010 1111 +1111 0+1=1 *0-1=11+0=11-0=1001101010101*1+1=01-1=0在（1）中

7、，右数第二列可以看成是0 -1= -1，因此要从高位借1，就变成(10+0)-1=1， (这就象普通的by-paper十进制减法)。特例（2,3）中，1+1会有正常的结果10，“1”是计算后的进位，这个值被忽略了。特殊情况0-1应该有正常结果“-1”就要退到下一位。这个值也被忽略了，假如你对编程有一定了解，这就象XOR 操作或者更好。现在来看一个除法的例子:在普通算法中:1001/11110001101 13 9/12013 1001 - 09 -| - -| 1100 30 | 1001 - 27 - - - 0110 3 - 余数 0000 - - 1100 1001 - - 011 -

8、 3, 余数在CRC算法中:1001/11110001110 9/12014 余数为 6 1001 - - 1100 1001 - - 1010 1001 - - 0110 0000 - - 110 - 余数(例 3)这个除法的商并不重要，也没必要去记住，因为他们仅仅是一组无关紧要的位串。真正重要的是余数！它就是这个值，可以说比原文件还重要的值，他就是基本的CRC。过度到真正的CRC码计算。进行一个CRC计算我们需要选则一个除数，从现在起我们称之为poly。宽度W就是最高位的位置，所以这个poly 1001的W 是3，而不是4。注意最高位总是1，当你选定一个宽度，那么你只需要选择低W各位的值

9、。假如我们想计算一个位串的CRC码，我们想确定每一个位都被处理过，因此，我们要在目标位串后面加上W个0位。在此例中，我们假设位串为110101101。请仔细分析下面一个例子：Poly = 10011，宽度 W=4位串 Bitstring Bitstring + W zeros = 110101101 + 000010011/1101011010000110000101 (我们不关心此运算的商) 10011| - -| 10011| 10011| - -| 00001| 00000| - -| 00010| 00000| - -| 00101| 00000| - -| 01010| 00000

10、| - -| 10100| 10011| - -| 01110| 00000| - -| 11100 10011 - - 1111 - 余数 - the CRC!(例 4)重要两点声明如下:1、只有当Bitstring的最高位为1，我们才将它与poly做XOR运算，否则我们只是将Bitstring左移一位。2、XOR运算的结果就是被操作位串bitstring与低W位进行XOR运算，因为最高位总为0。算法设计: 你们都应知道基于位运算的算法是非常慢的而且效率低下，但如果将计算放在每一字节上进行，那么效率将大大提高。不过我们只能接受poly的宽度W是8的倍数(一个字节；)。可以形象的看成这样一个宽

11、度W为32的poly(W=32)： 3 2 1 0 byte +-+-+-+-+Pop! -| | | | |- bitstring with W zero bits added, in this case 32 +-+-+-+-+ 1 this is the poly, 4*8 bits(figure 1) 这是一个你用来存放暂时CRC结果的寄存器，现在我称它为CRC寄存器或者寄存器。你从右至左移动位串，当从左边移出的位是1，则整个寄存器被与poly的低W位进行XOR运算。(此例中为32)。事实上，我们精确的完成了上面除法所做的事情。移动前寄存器值为:10110100，当从右边移入4位时，左

12、边的高4位将被移出，此例中1011将被移出，而1101被移入。情况如下:当前8位CRC寄存器 : 01001101刚刚被移出的高4位 : 1011我们用此poly : 1 0101 1100，0x5C 宽度 W=8现在我们用如前介绍的方法来计算寄存器的新值。顶部寄存器- -101101001101 高四位和当前寄存器值101011100 + (*1) Poly 放在顶部最高位进行XOR运算 (因为那里是1)-000110101101 运算结果现在我们仍有一位1在高4位:0001 10101101 上一步结果 1 01011100+ (*2) Poly 放在顶部的最低位进行XOR运算 (因为那

13、里是1)-0000 11110001 第二步运算结果现在顶部所有位均为0，所以我们不需要在与poly进行XOR运算你可以得到相同的结果如果你先将(*1)与(*2)做XOR然后将结果与记存器值做XOR.这就是标准XOR运算的特性:(a XOR b) XOR c = a XOR (b XOR c) 由此,推出如下的运算顺序也是正确的.101011100 poly (*1) 放在顶部最高位101011100+ polys (*2) 放在顶部最低位-101110111100 (*3) XOR运算结果The result (*3) 将(*3)与寄存器的值做XOR运算1011 101111001011 0

14、1001101+ 如右:-0000 11110001你看到了吗？得到一样的结果！现在(*3)变的重要了，因为顶部为1010则(3)的值总是等于10111100(当然是在一定的条件之下),这意味着你可以预先计算出任意顶部位结合的XOR值。注意，顶部结果总是0，这就是组合XOR操作导致的结果。(翻译不准确,保留原文) 现在我们回到figure 1，对每一个顶部字节的值都做移出操作，我们可以预先计算出一个值。此例中，它将是一个包含256个double word(32 bit)双字的表。(附录中CRC-32的表).(翻译不准确,保留原文) 用伪语言表示我们的算法如下: While (byte stri

15、ng is not exhausted) Begin Top = top_byte of register ; / (register value8)Register = Register shifted 8 bits left ORred with a new byte from string ;/ (register value8) Register = Register XORred by value from precomputedTable at position Top ; End / Register crc_tableTopnew byte from string;direct

16、 table算法: 上面提到的算法可以被优化，字节串中的字节在被用到之前没有必要经过整个寄存器。用这个新的算法，我们可以直接用一个字节去XOR一个字节串通过将此字节移出记存器。结果指向预先计算的表中的一个值，这个值是用来被记存器的值做XOR运算的。我不十分确切的知道为什么这会得到同样的结果(这需要了解XOR运算的特性)，但是这又极为便利，因为你无须在你的字节串后填充0字节/位。(如果你知道原理，请告诉我。) 让我们来实现这个算法: +- byte string (or file) 字节串,(或是文件) | v 3 2 1 0 byte 字节 | +-+-+-+-+XOR-: : : : :

17、+-+-+-+-+ | | | | | +-+-+-+-+(figure 2)reflected direct Table 算法: 由于这里有这样一个与之相对应的“反射”算法，事情显得复杂了。一个反射的值/寄存器就是将它的每一位以此串的中心位为标准对调形成的。例如:0111011001就是1001101110的反射串。他们提出“反射”是因为UART(一种操作IO的芯片)发送每一个字节时是先发最没用的0位,最后再发最有意义的第7位，这与正常的位置是相逆的。除了信息串不做反射以外，在进行下一步操作前，要将其余的数据都做反射处理。所以在计算值表时，位向右移，且poly也是作过反射处理的。当然,在

19、记存器向右移动一个字节。2. 将刚移出的那个字节与byte string中的新字节做XOR运算,得出一个指向值表table0.255的索引。3. 将索引所指的表值与记存器做XOR运算.4. 如数据没有全部处理完,则跳到步骤1.下面是这个算法的简单的可执行汇编源码:完整的CRC-32标准所包含的内容:Name : CRC-32Width : 32Poly : 04C11DB7Initial value : FFFFFFFFReflected : TrueXOR out with : FFFFFFFF作为对你好奇心的奖励, 这里是CRC-16标准: :)Name : CRC-16Width : 1

20、6Poly : 8005Initial value : 0000Reflected : TrueXOR out with : 0000XOR out with 是为了最终得到CRC而用来与寄存器最后结果做XOR运算的值。假如你想了解一些关于reversed逆向CRC poly的话,请看我的参考文章. 我是在16位DOS模式下用的32位编码，因此你会在这个程序中看到很多32位与16位混合的编码.当然这是很容易转换成纯32位编码的。注意这个程序是经过完整测试并且能够正常运行的.下面的Java 和 C 代码都是由这个汇编代码而来的. 底下的这段程序就是用来计算CRC-32 table的: xor e

21、bx, ebx ;ebx=0, 将被用做一个指针.InitTableLoop: xor eax, eax ;eax=0 为计算新的entry. mov al, bl ;al-bl ;生成入口. xor cx, cxentryLoop: test eax, 1 jz no_topbit shr eax, 1 xor eax, poly jmp entrygoonno_topbit: shr eax, 1entrygoon: inc cx test cx, 8 jz entryLoop mov dword ptrebx*4 + crctable, eax inc bx test bx, 256 j

22、z InitTableLoop注释: - crctable 是一个包含256个dword的数组. - 由于使用反射算法，eax被向右移。 - 因此最低的8位被处理了.用Java和C写的代码如下(int is 32 bit):for (int bx=0; bx256; bx+) int eax=0; eax=eax&0xFFFFFF00+bx&0xFF; / 就是 mov al,bl 指令 for (int cx=0; cx=1; eax=poly; else eax=1; crctablebx=eax;下面的汇编代码是用来计算CRC-32的:computeLoop: xor ebx, ebx

23、xor al, si mov bl, al shr eax, 8 xor eax, dword ptr4*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=crcTableebx;

24、eax=0xFFFFFFFF; 现在我们已经完成了本文的第一部分:CRC原理部分，所以如果你希望能够对CRC做更深的研究，那么我建议你去读在本文最后给出连接上的资料，我读了，好了，终于到了本文最有意思的部分：CRC的逆向分析!-2.3第二部分：CRC的逆向分析我遇到了很多障碍，当我思考如何破解CRC时，我试图使用一些特殊顺序的字节使CRC无效。但我没有做到.后来我意识到这种方法是行不通的，因为CRC内建了一些处理过程，无论你改变任何位它都不会出问题。真正的CRC就是在不断变化的，总是在变化的找一些CRC程序，你可以自己尝试一下。现在我知道我只能“纠正”在CRC后面的那些我想改变的字节。所以

25、我要构造一个字节序列，它可以将CRC转化成任何我想要的样子! 具体实现这个想法一个字节串? 01234567890123456789012345678901234567890123456789012You want to change from this byte to this one.就是位置9-26。同时我们需要额外的4个字节用来在最后恢复原始字节串。当你计算CRC-32时，从0-8都没有问题，直到第9位，修补过的字节串会使CRC发生根本的改变。即使当走过了第26位，以后的字节都没有改变，你也不可能在得到原始的CRC了，不可能了!你读过后面的段落时就会明白为什么。简而言之，当你修改一个

26、字节串时，要保证CRC不变。1. 计算并保存从19位的CRC.2. 继续计算直到第27位还有额外的4字节并保存结果.3. 用1的值来计算新的字节串和额外4字节的CRC(对应patch后的新的CRC值),并将之保存.4. 现在我们得到了一个新的CRC,但是我们希望将它还原成原先的CRC,所以我们用逆向算法来计算那额外的4字节.13就是实际的情况,下面你将学到最关键的部分4.反转CRC-16 我想,先来介绍计算逆CRC-16对于你来说会简单些.好的,我们现在处在一个恰当的位置,在以修改代码后面,就是你想将CRC还原的地方.我们知道原始的CRC(是在patch代码之前计算出来的)还有这个当前的记存

27、器值.现在我们的目的就是计算可以改变当前记存器值到原始记存器值的两个字节. 首先,我们用正常的方法计算这两个未知字节的CRC.我们设他们为X,Y.设记存器为a1,a0,只有0不能用来作为变量(00).:)在来看一下我们的CRC算法,figure3,更好的理解下面我要做的.好,我们开始:用这两字节串X Y 字节是从左边开始被处理的.记存器现在是a1 a0.用+来表示XOR运算(和第一部分中用的一样)处理第一个字节, X:a0+X 这是顶部字节的计算结果 (1)b1 b0 这是(1)在表中索引对象.00 a1 向右移动记存器.00+b1 a1+b0 上面两行对应位做XOR运算.现在记存器为: (b

28、1) (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(是原始的C

29、RC),而且你知道在变换之前的记存器的值(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!如前所述,现在你用

30、哪个查找程序在表中查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

31、,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=A7X=a0+(1) =AD+4F =E2结论:将CRC 记存器的值从 DEAD 变为 1234 我们需要这两个字节 E2 A7 (以此顺序). 你看,破解CRC校验你需要反向计算,还有要记住的就是计算过程中的值.当你在用汇编编写查找表程序时,要注意intel在小模式中是反向存储值的.现在你可能已经明白如何去破解这个CRC-16了.下面介绍如何在C

32、RC-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+b

33、1) (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 右

34、移记存器.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

展开阅读全文