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也是作过反射处理的。当然,在
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CRC 算法 原理 语言 实现
链接地址:https://www.31doc.com/p-3257860.html