矛与盾的较量——CRC原理篇
点击次数：60 次 发布日期：2008-11-10 08:14:51 作者：源代码网
CRC有什么用呢？它的应用范围很广泛，最常见的就是在网络传输中进行信息的校对。其实我们大可以把它应用到软件保护中去，因为它的计算是非常非常非常严格的。严格到什么程度呢？你的程序只要被改动了一个字节（甚至只是大小写的改动），它的值就会跟原来的不同。Hoho，是不是很厉害呢？所以只要给你的“原”程序计算好CRC值，储存在某个地方，然后在程序中随机地再对文件进行CRC校验，接着跟第一次生成并保存好的CRC值进行比较，如果相等的话就说明你的程序没有被修改/破解过，如果不等的话，那么很可能你的程序遭到了病毒的感染，或者被Cracker用16进制工具暴力破解过了。 废话说完了，我们先来看看CRC的原理。 （由于CRC实现起来有一定的难度，所以具体怎样用它来保护文件，留待下一节再讲。） 首先看两个式子： 式一：9 / 3 = 3 （余数 = 0） 式二：(9 + 2 ) / 3 = 3 （余数 = 2） 在小学里我们就知道，除法运算就是将被减数重复地减去除数X次，然后留下余数。 所以上面的两个式子可以用二进制计算为：（什么？你不会二进制计算？我倒～～～） 式一： 1001 --> 9 0011 - --> 3 --------- 0110 --> 6 0011 - --> 3 --------- 0011 --> 3 0011 - --> 3 --------- 0000 --> 0，余数 一共减了3次，所以商是3，而最后一次减出来的结果是0，所以余数为0 式二： 1011 --> 11 0011 - --> 3 软件开发网 www.mscto.com --------- 1000 --> 8 0011 - --> 3 --------- 0101 --> 5 0011 - --> 3 --------- 0010 --> 2,余数 一共减了3次，所以商是3，而最后一次减出来的结果是2，所以余数为2 看明白了吧？很好，let’s go on! 二进制减法运算的规则是，如果遇到0-1的情况，那么要从高位借1，就变成了(10+0)-1=1 CRC运算有什么不同呢？让我们看下面的例子： 这次用式子30 / 9，不过请读者注意最后的余数： 11110 --> 30 1001 - --> 9 --------- 1100 --> 12 （很奇怪吧？为什么不是21呢？） 1001 - --> 9 -------- 101 --> 3，余数 --> the CRC! 软件开发网 www.mscto.com 这个式子的计算过程是不是很奇怪呢？它不是直接减的，而是用XOR的方式来运算（程序员应该都很熟悉XOR吧），最后得到一个余数。 对啦，这个就是CRC的运算方法，明白了吗？CRC的本质是进行XOR运算，运算的过程我们不用管它，因为运算过程对最后的结果没有意义；我们真正感兴趣的只是最终得到的余数，这个余数就是CRC值。 进行一个CRC运算我们需要选择一个除数，这个除数我们叫它为“poly”，宽度W就是最高位的位置，所以我刚才举的例子中的除数9，这个poly 1001的W是3，而不是4，注意最高位总是1。（别问为什么，这个是规定） 如果我们想计算一个位串的CRC码，我们想确定每一个位都被处理过，因此，我们要在目标位串后面加上W个0位。现在让我们根据CRC的规范来改写一下上面的例子： Poly = 1001，宽度W = 3 位串Bitstring = 11110 Bitstring + W zeroes = 11110 + 000 = 11110000 11110000 1001|||| - ------------- 1100||| 1001||| - ------------ 1010|| 1001|| - ----------- 0110| 0000| - ---------- 1100 1001 - --------- 101 --> 3，余数 --> the CRC! 还有两点重要声明如下： 1、只有当Bitstring的最高位为1，我们才将它与poly进行XOR运算，否则我们只是将Bitstring左移一位。 2、XOR运算的结果就是被操作位串Bitstring与poly的低W位进行XOR运算，因为最高位总为0。 呵呵，是不是有点头晕脑胀的感觉了？看不懂的话，再从头看一遍，其实是很好理解的。（就是一个XOR运算嘛！） 好啦，原理介绍到这里，下面我讲讲具体怎么编程。 由于速度的关系，CRC的实现主要是通过查表法，对于CRC-16和CRC-32，各自有一个现成的表，大家可以直接引入到程序中使用。（由于这两个表太长，在这里不列出来了，请读者自行在网络上查找，很容易找到的。） 如果我们没有这个表怎么办呢？或者你跟我一样，懒得自己输入？不用急，我们可以“自己动手，丰衣足食”。 你可能会说，自己编程来生成这个表，会不会太慢了？其实大可不必担心，因为我们是在汇编代码的级别进行运算的，而这个表只有区区256个双字，根本影响不了速度。 这个表的C语言描述如下： for (i = 0; i < 256; i++) { crc = i; for (j = 0; j < 8; j++) { if (crc & 1) crc = (crc >> 1) ^ 0xEDB88320; else crc >>= 1; } crc32tbl[i] = crc; } 生成表之后，就可以进行运算了。 我们的算法如下： 1、将寄存器向右边移动一个字节。 2、将刚移出的那个字节与我们的字符串中的新字节进行XOR运算，得出一个指向值表table[0..255]的索引。 3、将索引所指的表值与寄存器做XOR运算。 4、如果数据没有全部处理完，则跳到步骤1。 这个算法的C语言描述如下： temp = (oldcrc ^ abyte) & 0x000000FF; crc = (( oldcrc >> 8) & 0x00FFFFFF) ^ crc32tbl[temp]; return crc; 好啦，所有的东东都说完啦，最后献上一个完整的Win32Asm例子，请读者仔细研究吧！ （汇编方面的CRC-32资料极少啊，我个人认为下面给出的是很宝贵的资料。） ;**************************************************** ;程序名称：演示CRC32原理 ;作者：罗聪 ;日期：2002-8-24 ;出处：http://laoluoc.yeah.net（老罗的缤纷天地） ;注意事项：如欲转载，请保持本程序的完整，并注明：转载自“老罗的缤纷天地”（http://laoluoc.yeah.net） ; ;特别感谢Win32ASM高手—— dREAMtHEATER 为我的代码作了相当好的优化！ ;请各位前去 http://NoteXPad.yeah.net 下载他的小巧的“cool 记事本”—— NoteXPad 来试用！（100% Win32ASM 编写） ; ;**************************************************** .386 .model flat, stdcall option casemap:none include windows.inc include kernel32.inc include user32.inc includelib kernel32.lib includelib user32.lib WndProc proto :DWORD, :DWORD, :DWORD, :DWORD init_crc32table proto arraycrc32 proto .const IDC_BUTTON_OPEN equ 3000 IDC_EDIT_INPUT equ 3001 .data szDlgName db "lc_dialog", 0 szTitle db "CRC demo by LC", 0 szTemplate db "字符串 ""%s"" 的 CRC32 值是：%X", 0 crc32tbl dd 256 dup(0) ;CRC-32 table szBuffer db 255 dup(0) .data? szText db 300 dup(?) .code main: invoke GetModuleHandle, NULL invoke DialogBoxParam, eax, offset szDlgName, 0, WndProc, 0 invoke ExitProcess, eax WndProc proc uses ebx hWnd:HWND, uMsg:UINT, wParam:WPARAM, lParam:LPARAM .if uMsg == WM_CLOSE invoke EndDialog, hWnd, 0 .elseif uMsg == WM_COMMAND mov eax,wParam mov edx,eax shr edx,16 movzx eax, ax 源代码网推荐 源代码网供稿. |
