CRC原理

明亮 posted @ 2013年9月22日 17:08 in 【C/C++】 , 2265 阅读
本文发表于:http://fml927.is-programmer.com

矛与盾的较量(2)——CRC原理篇

 

下载本节例子程序 (4.29 KB)


(特别感谢汇编高手 dREAMtHEATER 对我的代码作出了相当好的优化!请参观他的主页

上一节我们介绍了花指令,不过花指令毕竟是一种很简单的东西,基本上入了门的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 (= 0; i < 256; i++)
{
    crc = i;
    for (= 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



下面是它的资源文件:
 


#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对你的文件进行保护。(呵呵,好戏在后头……)

 

老罗
2002-8-26

 

  • 无匹配
  • 无匹配
NCERT English Questi 说:
2022年9月27日 13:38

Teaching Staff of Leading Educational Institutes have prepared these NCERT 10th Class English Sample Papers 2023 all important questions which has been repeatedly asked in previous years old exams. NCERT English Question Paper Class 10 These NCERT English Question Bank for Reading, Writing, Grammar and Literature questions are prepared from the newly revised syllabus which is listed here.Teaching Staff of Leading Educational Institutes have prepared these NCERT 10th Class English Sample Papers 2023 all important questions which has been repeatedly asked in previous years old exams.

먹튀대피소 说:
2024年12月05日 13:53

Only then can we fulfill our dreams. When we will try to fulfill our dream in a very good way. Here you will be given advice on how to join the Best IAS coaching institute in Delhi. For this you will get a good solid way to achieve your goals in the specified time frame. For which

References 说:
2024年12月05日 13:54

Start being true conservatives?  You mean everyone should be an ignorant, uneducated bible-beater getting all information from talk radio?  Support for the paranoid, anti-government movement that is the libertarian/tea bagger agenda is an act of shear stupidity.  I really wish you would wake up to the fact that you don't represent the views of sensible americans.  All your movement will ever accomplish is to make life better for the ruling wealthy and the corporations through which they profit (while the masses suffer).   Please keep those f***ed up views off this site and down in that sh*thole known as Texas where they belong.  Believe it or not, you can speak out against the drug war without insulting educated progressives with your silly beliefs.  

먹튀뱅크 说:
2024年12月05日 13:55

i find issues i have been looking for. You have got a clever yet attractivel in your site with effective and useful statistics. It's miles blanketed very satisfactory post with quite a few our assets. Thanks for percentage. I revel in this put up

check here 说:
2024年12月05日 13:56

The anti-marijuana crowd likes to portray marijuana users as Cheech & Chong stoner-types who are perpetually high and unable to function in society (as in Cheech & Chong's 1978 film, Up In Smoke). But now the Drug Warriors somehow think that pot smokers, during the depths of their THC-induced stupor, can suddenly develop and then execute a master plan to hold America hostage until their incarcerated comrades are freed? These two images are in conflict with one another. Either smoking marijuana makes you a lazy underachiever whose brain cells are all destroyed, or it makes you a drug-crazed "Reefer Madness" lunatic/terrorist/Super-Genius. But it can't be both.

토토마트 说:
2024年12月05日 13:57

Hello! I just now wish to provide a huge thumbs up for the great information you could have here during this post. We are coming back to your website for further soon

click here 说:
2024年12月05日 13:59

The anti-marijuana crowd likes to portray marijuana users a to hold America hostage until their incarcerated comrades are freed? These two images are in conflict with one another. Either smoking marijuana makes you a lazy underachiever whose brain cells are all destroyed, or it makes you a drug-crazed "Reefer Madness" lunatic/terrorist/Super-Genius. But it can't be both.

토토경비대 说:
2024年12月05日 14:00

Thank you for every one of your work on this blog. My mother enjoys going through investigation and it’s really easy to see why. My partner and i learn all about the powerful way you offer informative solutions via this website and invigorate participation from other ones on this subject matter then our child is actually studying a great deal. Have fun with the rest of the year. You’re the one conducting a fantastic job.

토토경비대 说:
2024年12月05日 14:00

Thank you for every one of your work on this blog. My mother enjoys going through investigation and it’s really easy to see why. My partner and i learn all about the powerful way you offer informative solutions via this website and invigorate participation from other ones on this subject matter then our child is actually studying a great deal. Have fun with the rest of the year. You’re the one conducting a fantastic job.

check here 说:
2024年12月05日 14:01

The reasoning behind this drill had nothing to do with pot growers. They could have been ComicCon nerds holding a rare green isotope. The point of this drill was HOW the fed and sister agencies deal with an attack on one of our more sensitive targets: the dam. While I'm certain that quite a few of you may be happy not to have to enjoy the 'evils' of electricity or fresh water; I would like to see the dam in continued operation.

View data 说:
2024年12月05日 14:02

Standard sessions allow me to share the simplest way to thanks a lot for ones hard work, which in turn means that I am just traveling to the web page every day, seeking brand-new, exciting information. A lot of, bless you!

토토디펜드 说:
2024年12月05日 14:04

whoah this blog is great i like reading your articles. Keep up the great paintings! You know, a lot of individuals are looking around for this info, you can aid them greatly

get more info 说:
2024年12月05日 14:06

Hey what a brilliant post I have come across and believe me I have been searching out for this similar kind of post for past a week and hardly came across this. Thank you very much and will look for more postings from you

contents 说:
2024年12月05日 14:19

IceCream Screen Recorder Crack is one of the high-quality software on this planet with the reason of assisting the consumer in taking pictures of the som

read more 说:
2024年12月05日 14:24

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. Thanks

website 说:
2024年12月05日 14:36

Seriously, no one disrespects cops more than I do, but even I'm not falling for this one.  The drug warriors involved in this exercise cannot possibly be stupid enough to believe this scenario.  The thing about drug warriors is that they don't mind acting stupid if it will further their cause.  Since they can no longer even pretend that pot is dangerous, they have to pretend the pot USERS are.  And pretend that they're actually going to protect the public.  Marijuana terrorism.  Boy, this is even better than exploding meth labs.

check here 说:
2024年12月05日 14:48

Hello! I just now wish to provide a huge thumbs up for the great information you could have here during this post. We are coming back to your website for further soon

good contents 说:
2024年12月05日 14:52

I would like to thnkx for the efforts you have put in writing this site. I’m hoping the same high-grade site post from you in the upcoming as well. In fact your creative writing abilities has inspired me to get my own site now. Really the blogging is spreading its wings fast. Your write up is a great example of it. rentacarkosovo 

website 说:
2024年12月05日 14:58

Hello ! I am a student writing a report on the subject of your post.Your article is an article with all the content and topics. I've ever wanted . Thanks to this, it will be of great help to the report I am preparing now.Thanks for your hard work. And if you have time, please visit my site as well. is one very interesting post. like the way you write and I will bookmark your blog to my favorites. Strong blog. I acquired various nice information

information 说:
2024年12月05日 15:06

I’m impressed, I have to admit. Really rarely will i encounter a blog that’s both educative and entertaining, and without a doubt, you may have hit the nail to the head. Your concept is outstanding; the thing is something too few consumers are speaking intelligently about. We are very happy i always stumbled across this in my seek out something in regards to this

information 说:
2024年12月05日 15:14

Great blog here! Additionally your website quite a bit up very fast! What web host are you the use of? Can I am getting your affiliate hyperlink on your host? I desire my web site loaded up as quickly as yours lol

get more info 说:
2024年12月05日 15:28

This is really exciting, You’re a tremendously trained article author. I’ve joined with your feed and also anticipate enjoying the awesome write-ups. Incidentally, I’ve got shared the blog throughout our social networking sites.

먹튀사이트 说:
2024年12月05日 15:35

The anti-marijuana crowd likes to portray marijuana users as Cheech & Chong stoner-types who are perpetually high and unable to function in society (as in Cheech & Chong's 1978 film, Up In Smoke). But now the Drug Warriors somehow think that pot smokers, during the depths of their THC-induced stupor, can suddenly develop and then execute a master plan to hold America hostage until their incarcerated comrades are freed? These two images are in conflict with one another. Either smoking marijuana makes you a lazy underachiever whose brain cells are all destroyed, or it makes you a drug-crazed "Reefer Madness" lunatic/terrorist/Super-Genius. But it can't be both.

spotterdayinfraero 说:
2024年12月05日 15:37

Thank you for every one of your work on this blog. My mother enjoys going through investigation and it’s really easy to see why. My partner and i learn all about the powerful way you offer informative solutions via this website and invigorate participation from other ones on this subject matter then our child is actually studying a great deal. Have fun with the rest of the year. You’re the one conducting a fantastic job.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter