原创 矛与盾的较量（2）——CRC原理篇

看到大家有用到CRC校验，现在发几篇这方面的资料，希望对大家有所帮助。

 

上一节我们介绍了花指令，不过花指令毕竟是一种很简单的东西，基本上入了门的Cracker都可以对付得了。所以，我们很有必要给自己的软件加上更好的保护。CRC校验就是其中的一种不错的方法。

CRC是什么东西呢？其实我们大家都不应该会对它陌生，回忆一下？你用过RAR和ZIP等压缩软件吗？它们是不是常常会给你一个恼人的“CRC校验错误”信息呢？我想你应该明白了吧，CRC就是块数据的计算值，它的全称是“Cyclic Redundancy Check”，中文名是“循环冗余码”，“CRC校验”就是“循环冗余校验”。（哇，真拗口，希望大家不要当我是唐僧，呵呵。^_^）

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
---------
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        --> 5，余数 --> the CRC!

这个式子的计算过程是不是很奇怪呢？它不是直接减的，而是用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        --> 5，余数 --> 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         .if edx == BN_CLICKED             .IF eax == IDCANCEL                 invoke EndDialog, hWnd, NULL             .ELSEIF eax == IDC_BUTTON_OPEN || eax == IDOK                         ;******************************************                 ;关键代码开始：（当当当当……）                 ;******************************************                 ;取得用户输入的字符串：                 invoke GetDlgItemText, hWnd, IDC_EDIT_INPUT, addr szBuffer, 255                 ;初始化crc32table：                 invoke init_crc32table                 ;下面赋值给寄存器ebx，以便进行crc32转换：                 ;EBX是待转换的字符串的首地址：                 lea ebx, szBuffer                 ;进行crc32转换：                 invoke arraycrc32                 ;格式化输出：                 invoke wsprintf, addr szText, addr szTemplate, addr szBuffer, eax                 ;好啦，让我们显示结果：                 invoke MessageBox, hWnd, addr szText, addr szTitle, MB_OK             .ENDIF         .endif     .ELSE         mov eax,FALSE         ret     .ENDIF     mov eax,TRUE     ret WndProc endp ;********************************************************** ;函数功能：生成CRC-32表 ;********************************************************** init_crc32table    proc         ;如果用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 = crc;         ;    }         ;         ;呵呵，让我们把上面的语句改成assembly的：         mov     ecx, 256        ; repeat for every DWORD in table         mov     edx, 0EDB88320h $BigLoop:         lea     eax, [ecx-1]         push    ecx         mov     ecx, 8 $SmallLoop:         shr     eax, 1         jnc     @F         xor     eax, edx @@:         dec     ecx         jne     $SmallLoop         pop     ecx         mov     [crc32tbl+ecx*4-4], eax         dec     ecx         jne     $BigLoop         ret init_crc32table      endp ;************************************************************** ;函数功能：计算CRC-32 ;************************************************************** arraycrc32    proc         ;计算 CRC-32 ，我采用的是把整个字符串当作一个数组，然后把这个数组的首地址赋值给 EBX，把数组的长度赋值给 ECX，然后循环计算，返回值（计算出来的 CRC-32 值）储存在 EAX 中：         ;         ; 参数：         ;       EBX = address of first byte         ; 返回值：         ;       EAX = CRC-32 of the entire array         ;       EBX = ?         ;       ECX = 0         ;       EDX = ?         mov     eax, -1 ; 先初始化eax         or      ebx, ebx         jz      $Done   ; 避免出现空指针 @@:         mov     dl, [ebx]         or      dl, dl         je      $Done    ;判断是否对字符串扫描完毕                  ;这里我用查表法来计算 CRC-32 ，因此非常快速：         ;因为这是assembly代码，所以不需要给这个过程传递参数，只需要把oldcrc赋值给EAX，以及把byte赋值给DL：         ;         ; 在C语言中的形式：         ;         ;   temp = (oldcrc ^ abyte) & 0x000000FF;         ;   crc  = (( oldcrc >> 8) & 0x00FFFFFF) ^ crc32tbl[temp];         ;         ; 参数：         ;       EAX = old CRC-32         ;        DL = a byte         ; 返回值：         ;       EAX = new CRC-32         ;       EDX = ?                        xor     dl, al         movzx   edx, dl         shr     eax, 8         xor     eax, [crc32tbl+edx*4]                  inc     ebx                 jmp     @B $Done:         not     eax         ret arraycrc32      endp end main ;********************    over    ******************** ;by LC

下面是它的资源文件：

#include "resource.h" #define IDC_BUTTON_OPEN    3000 #define IDC_EDIT_INPUT 3001 #define IDC_STATIC -1 LC_DIALOG DIALOGEX 10, 10, 195, 60 STYLE DS_SETFONT | DS_CENTER | WS_MINIMIZEBOX | WS_VISIBLE | WS_CAPTION |     WS_SYSMENU CAPTION "lc’s assembly framework" FONT 9, "宋体", 0, 0, 0x0 BEGIN     LTEXT           "请输入一个字符串（区分大小写）：",IDC_STATIC,11,7,130,10     EDITTEXT        IDC_EDIT_INPUT,11,20,173,12,ES_AUTOHSCROLL     DEFPUSHBUTTON   "Ca&lc",IDC_BUTTON_OPEN,71,39,52,15 END