矛与盾的较量——CRC原理篇
   作者:老罗 于2002-10-9上传 

(文章摘自 老罗缤纷天地(http://www.luocong.com)

(特别感谢汇编高手 dREAMtHEATER 对我(老罗)的代码作出了相当好的优化!请参观他的主页http://notexpad.yeah.net/

上一节我们介绍了花指令,不过花指令毕竟是一种很简单的东西,基本上入了门的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        --> 3,余数 --> 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        --> 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
        .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[i] = 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


下面是它的.rc文件:

#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


如果你能够完全理解本节的内容,那么请留意我的下一讲,我将具体介绍如何运用CRC-32对你的文件进行保护。(呵呵,好戏在后头……)


欢迎访问AoGo汇编小站:http://www.aogosoft.com