关于CRC码的基本知识.doc
《关于CRC码的基本知识.doc》由会员分享,可在线阅读,更多相关《关于CRC码的基本知识.doc(32页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、关于CRC码的基本知识一、 CRC码工作原理1。 CRC校验原理 CRC的英文全称为Cyclic Redundancy Check(Code),中文名称为循环冗余校验(码)。它是一类重要的线性分组码,编码和解码方法简单,检错和纠错能力强,在通信领域广泛地用于实现差错控制。 CRC计算与普通的除法计算有所不同。普通的除法计算是借位相减的,而CRC计算则是异或运算。任何一个除法运算都需要选取一个除数,在CRC运算中我们称之为poly,而宽度W就是poly最高位的位置。比如poly 1001的W是3,而不是4.注意最高位总是1,当你选定一个宽度,那么你只需要选择低W各位的值。假如我们想计算一个位串的
2、CRC码,并要保证每一位都要被处理,因此我们需要在目标位串后面加上W个0。 CRC校验原理看起来比较复杂,因为大多数书上基本上是以二进制的多项式形式来说明的.其实很简单的问题,其根本思想就是先在要发送的帧后面附加一个数(这个就是用来校验的校验码,但要注意,这里的数也是二进制序列的,下同),生成一个新帧发送给接收端。当然,这个附加的数不是随意的,它要使所生成的新帧能与发送端和接收端共同选定的某个特定数整除(注意,这里不是直接采用二进制除法,而是采用一种称之为“模2除法”)。到达接收端后,再把接收到的新帧除以(同样采用“模2除法)这个选定的除数。因为在发送端发送数据帧之前就已通过附加一个数,做了“
3、去余”处理(也就已经能整除了),所以结果应该是没有余数。如果有余数,则表明该帧在传输过程中出现了差错.【说明】“模2除法”与“算术除法”类似,但它既不向上位借位,也不比较除数和被除数的相同位数值的大小,只要以相同位数进行相除即可。模2加法运算为:1+1=0,0+1=1,0+0=0,无进位,也无借位;模2减法运算为:1-1=0,01=1,1-0=1,0-0=0,也无进位,无借位。相当于二进制中的逻辑异或运算。也就是比较后,两者对应位相同则结果为“0”,不同则结果为“1”。如100101除以1110,结果得到商为11,余数为1,如图5-9左图所示。如1111=101,如图5-9右图所示。图5-9“
4、模2除法和“模2乘法”示例 具体来说,CRC校验原理就是以下几个步骤: (1)先选择(可以随机选择,也可按标准选择,具体在后面介绍)一个用于在接收端进行校验时,对接收的帧进行除法运算的除数(是二进制比较特串,通常是以多项方式表示,所以CRC又称多项式编码方法,这个多项式也称之为“生成多项式)。 (2)看所选定的除数二进制位数(假设为k位),然后在要发送的数据帧(假设为m位)后面加上k1位“0”,然后以这个加了k-1个“0“的新帧(一共是m+k1位)以“模2除法方式除以上面这个除数,所得到的余数(也是二进制的比特串)就是该帧的CRC校验码,也称之为FCS(帧校验序列)。但要注意的是,余数的位数一
5、定要是比除数位数只能少一位,哪怕前面位是0,甚至是全为0(附带好整除时)也都不能省略。 (3)再把这个校验码附加在原数据帧(就是m位的帧,注意不是在后面形成的m+k-1位的帧)后面,构建一个新帧发送到接收端,最后在接收端再把这个新帧以“模2除法”方式除以前面选择的除数,如果没有余数,则表明该帧在传输过程中没出错,否则出现了差错。 通过以上介绍,大家一定可以理解CRC校验的原理,并且不再认为很复杂吧。 从上面可以看出,CRC校验中有两个关键点:一是要预先确定一个发送端和接收端都用来作为除数的二进制比特串(或多项式);二是把原始帧与上面选定的除进行二进制除法运算,计算出FCS。前者可以随机选择,也
6、可按国际上通行的标准选择,但最高位和最低位必须均为“1,如在IBM的SDLC(同步数据链路控制)规程中使用的CRC16(也就是这个除数一共是17位)生成多项式g(x)=x16+x15+x2+1(对应二进制比特串为:11000000000000101);而在ISO HDLC(高级数据链路控制)规程、ITU的SDLC、X.25、V。34、V。41、V。42等中使用CCITT-16生成多项式g(x)=x16+x15+x5+1(对应二进制比特串为:11000000000100001)。2。CRC校验码的计算示例 由以上分析可知,既然除数是随机,或者按标准选定的,所以CRC校验的关键是如何求出余数,也就
7、是CRC校验码。 下面以一个例子来具体说明整个过程。现假设选择的CRC生成多项式为G(X)= X4+ X3+ 1,要求出二进制序列10110011的CRC校验码。下面是具体的计算过程: (1)首先把生成多项式转换成二进制数,由G(X)= X4+ X3+ 1可以知道(,它一共是5位(总位数等于最高位的幂次加1,即4+1=5),然后根据多项式各项的含义(多项式只列出二进制值为1的位,也就是这个二进制的第4位、第3位、第0位的二进制均为1,其它位均为0)很快就可得到它的二进制比特串为11001。 (2)因为生成多项式的位数为5,根据前面的介绍,得知CRC校验码的位数为4(校验码的位数比生成多项式的位
8、数少1)。因为原数据帧10110011,在它后面再加4个0,得到101100110000,然后把这个数以“模2除法”方式除以生成多项式,得到的余数,即CRC校验码为0100,如图5-10所示。注意参考前面介绍的“模2除法运算法则。图5-10 CRC校验码计算示例 (3)把上步计算得到的CRC校验码0100替换原始帧101100110000后面的四个“0,得到新帧101100110100。再把这个新帧发送到接收端。 (4)当以上新帧到达接收端后,接收端会把这个新帧再用上面选定的除数11001以“模2除法方式去除,验证余数是否为0,如果为0,则证明该帧数据在传输过程中没有出现差错,否则出现了差错.
9、 通过以上CRC校验原理的剖析和CRC校验码的计算示例的介绍,大家应该对这种看似很复杂的CRC校验原理和计算方法应该比较清楚了. 下面大家做一个练习,假设CRC生成多项式为G(X)= X5+ X4+X+1,要发送的二进制序列为100101110,求CRC校验码是多少。二、 CRC码典型应用CRC(CyclicRedundancyCheck,直译:循环冗余校验)技术是一项很成熟的技术,在众多领域有广泛的应用,在数据存储和通信传输应用中处处都可以看到它的身影.最常用的CRC校验形式有CRC16,CRC32两种形式,采用CRC-16校验,可以保证在1014位码元中只含有一位未被检测出的错误,采用CR
10、C32校验的出错概率比CRC-16还低105倍。CRC的主要特点就是:检错能力极强,开销很小,易于实现。从性能和开销上综合考虑,其远远优于奇偶校验及算术和校验等方式。因此,很多软件在加密保护时都将CRC技术应用其中。CRC校验的原理解析 在实际应用中,根据环境和需求的变化,CRC形成了多种变形方式。比如:通讯协议X。25的帧检错序列采用的是CRCCCITT方式,ARJ、LHA、ZIP等压缩软件采用的是CRC32方式,磁盘驱动器的读写采用的是CRC-16方式,GIF、TIFF等图像存储格式也使用CRC作为检错技术。目前,比较流行的CRC形式主要是:CRC16(CRC-CCITT)、CRC32两种
11、,CRC-4、CRC8、CRC-12等形式的应用比较少见.其实,虽然有这么多种变形方式,但其原理是完全相同的,只是在实现上有一点变化而已,下面我们就对其原理进行一番解剖,希求通透. CRC的算法本质是(模-2)除法的余数运算,使用的除数不同,CRC的类型也就不一样。CRC的算法其实是采用了多项式编码的方法,您可以将要被处理的数据块M看成一个n阶的二进制多项式,其形式如下:a是对应的阶数(位数)的值;x是对应的“模(进制)”数,由于我们处理的都是二进制数,所以x就是2了。下面我们用一个数进行解释吧:有一个二进制数M=10010101,其对应的多项式就可以表示为:CRC校验就是基于这种多项式进行的
12、运算,其乘除法运算过程与普通代数多项式的乘除法相同,其加减法运算以2为模,加减时不进(借)位,实际上与逻辑异或(XOR)运算是一致的. 通常,根据多项表达(运算)式的不同,就形成了不同的CRC形式,以下是各种常用的多项表达(运算)式:这些多项表达式的值就是(模2)除法的除数,只要能确定使用哪一种多项式(也就是对应除数),您就可以很简单的获取CRC检验码了.下面就给您介绍CRC检验码的计算过程:1、先确定您要使用的CRC校验形式,以此确定对应除数(用G来表示)和选定阶数(用r来表示).(如果选择CRC4的话,r就等于4,选择CRC-16话,r就等于16,以此类推。)2、在待处理的数据块M后附加上
13、r个0。假设原始数据块的长度是m位的话,附加之后的长度就变成m+r位了,我们用M来代表附加后的值。3、用第一步选择的生成多项式的值(即对应除数G)来除第二步附加0后生成的值(M),循环计算,一直到余数的阶数小于等于r-1,这时所得到的余数(用Y表示)就是原始数据M经过所选择的CRC校验形式所生成的CRC校验码。 如果您想将生成的校验码与原始数据进行复合,只需要用第二步生成的(M)以模2的方法减去得到的CRC校验码(Y),所得到的值就是包含了CRC校验码的数据串M.(不过在软件加密过程中可能用不到这一步)。 只需要三步,就可以得到CRC的校验码。举个例子:设原始数据M1100110100选择CR
14、C4的形式,则G24211910011(二进制)rG的二进制位数减1514对原始数据M进行处理,在其尾部附加r个0,即:M=M+0000=11001101000000再用G循环除M:其实校验码生成的过程就是一个循环移位的运算,位与位之间就是异或(XOR)运算。 一个数据的校验过程是这样的,如果有大量数据(比如说一个可执行程序或一个压缩包)将如何进行校验呢?其实很简单,只要将一个文件看成一个被一些数字分割的很长的位字串就可以了,只是这个位字串比较TA而已,你只要按标准的方式对这个比较长的位字串进行(模-2)除法运算,就一定会得到一个余数-CRC校验码,而这个校验码就是这个文件的CRC校验值.CR
15、C校验的代码实现 好了,理论上的准备是很多了,现在要用进入实践了。下面,我们将给您提供一段很简单而实用的代码,用来实现CRC-32校验,最终,我会用这段代码实现软件加密保护。 大家可以看到,上面生成CRC校验码的过程中,使用了大量的位运算和逻辑操作。而我想告诉大家的是,基于位运算的算法是非常慢的而且效率很低。因此,在实际使用中不推荐使用“计算法”来生成CRC校验码,而建议使用“查表法”来进行CRC校验码计算。查表法又是什么方法呢?这里我不做过多的分析,简单的说,它是利用预先计算出的标准码表(对应不同的校验形式有不同的码表,见附表1、2),用简单的移位和XOR操作,快速计算出CRC校验码的方法.
16、具体的算法就是:(1)将上次计算出的CRC校验码右移一个字节;(2)将移出的这个字节与新的要校验的字节进行XOR运算;(3)用运算出的值在预先生成码表中进行索引,获取对应的值(称为余式);(4)用获取的值与第(1)步右移后的值进行XOR运算;(5)如果要校验的数据已经处理完,则第(4)步的结果就是最终的CRC校验码。如果还有数据要进行处理,则再转到第(1)步运行。看上面的过程是十分简单的,不好理解的可能是“预先生成的码表”。其实这个码表就是28的数组,为什么是8次方呢?因为我们是用字节来进行运算的,而一个字节是8位,所以就是2的8次方了.因此这个码表就是拥有256值的数组,对应的每个值实际上就
17、是0-255以对应的CRC多项表达式(见原理分析)为权的CRC码。如CRC-16的多项表达式就是,CRC-32的多项表达式就是:附表1、2中分别给出了对应两种形式的码表(汇编格式),您只要复制到您的代码中即可使用(可能要做一些修饰)。 如果您不想将这么一大堆码表复制到您的代码中,也可以使用动态生成码表(不过是给256个数字进行CRC计算而已)。下面是生成CRC-32码表的代码(c语言):/-/GenCrc32Tbl函数动态生成CRC32的预置码表/Code:Chenji/-unsignedintCRC。/在Windows下编程,int的大小是32位unsignedintCRC_32_Tbl25
18、6。/用来保存码表voidGenCrc32Tbl()for(inti=0.i256。+i)/用+i以提高效率CRC=i;for(intj=0.j8。+j)/这个循环实际上就是用”计算法”来求取CRC的校验码if(CRC&1)CRC=(CRC1)0xEDB88320;else/0xEDB88320就是CRC-32多项表达式的值CRC=1;CRC_32_Tbli=CRC。/- 上面的代码其实就已经实现了用“计算法”求取CRC校验码的过程,只要做些修改就可以完全实现.您只要将上面的代码复制到程序中,并调用GenCrc32Tbl函数,就可以在CRC_32_Tbl中生成CRC-32的预置码表。有了码表,
19、用“查表法”计算CRC-32计算校验码就易如反掌了。根据上面介绍的算法,用C语言只需要一行就可以实现。CRC32=CRC_32_Tbl(CRC32((unsigned_int8*)p)i)0xff(CRC328);下面是完整的一个实现函数,更加简单:/-/CalcCRC32函数计算出给定数据串的CRC-32校验码/Code:Chenji/-unsignedintCalcCRC32(void*DataBuff,unsignedintBufLen)/DataBuff是指向数据串的指针,BufLen是数据串的长度unsignedintCRC32=0xffffffff;/设置初始值for(unsign
20、edlongi=0;iBufLen;+i)CRC32=CRC_32_Tbl(CRC32((unsigned_int8*)DataBuff)i)&0xff(CRC328);/如果你的编译器不支持unsigned_int8定义,请试用unsignedcharreturnCRC32;/-怎么样,用查表法计算CRC校验码是不是很简单,很快捷?您只要将上面的代码复制您的程序中,赋与对应的参数,就可以实CRC32校验了。CRC校验在软件加密保护中的攻与防 上面用大篇幅介绍CRC的原理与实现,都是为现在的实战打基础,现在我们就要用实战来校验了. 大家已经知道,CRC校验生成的结果只是一个Long型的整数,市
21、面上一些软件是如何将这个整数应用在软件加密保护中呢?这里我给大家介绍两种常用的方式:1、是对程序自身的进行保护。首先对原始可执行程序进行CRC校验,同时保存校验结果(可以保存在注册表、配置文件或可执行程序本身)。在程序运行时,对程序自身进行CRC校验,并将运算出的结果与保存的原始结果进行比较,如果不相同,就说明程序已经被修改(最有可能是被破解或被病毒感染)。即使只有1Bit的修改,都会被CRC检查出来,所以用CRC做自校验相当有效。2、用CRC校验算法,对注册名和注册码进行变形运算和判断,以此做为注册保护和授权的手段。这两种方式在软件保护上的运用十分广泛。可以说,每一种软件加壳(加密)保护软件
22、(如upx,Aspack,FSG等)都使用了CRC进行自身校验保护。为了证明CRC在软件加密保护上的效果,我制作了一套测试用例,大家可以在上下载CRCTest.rar压缩包,按本文进行测试和分析。压缩包中有两个可执行程序:crctest.exe和Makecrc.exe.其中crctest.exe就是我们要进行分析的对象,界面如下:软件已经进行了CRC外壳校验保护,同时,使用CRC32算法做注册码校验,可以说将CRC在软件加密保护上的应用全部发挥出来了。MakeCrc。exe是配套工具,用来给上面的程序注入CRC保护码和计算注册码。 现在,可以打开crctest。exe文件,并随意输入注册名和注
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 关于 CRC 基本知识
限制150内