CRC算法原理及C語(yǔ)言實(shí)現(xiàn)

1、（一）crc算法原理及c語(yǔ)言實(shí)現(xiàn) 1.crc原理介紹 crc的英文全稱為cyclic redundancy check（code），中文名稱為循環(huán)冗余校驗(yàn)（碼）。它是一類重要的線性分組碼，編碼和解碼方法簡(jiǎn)單，檢錯(cuò)和糾錯(cuò)能力強(qiáng)，在通信領(lǐng)域廣泛地用于實(shí)現(xiàn)差錯(cuò)控制。 crc計(jì)算與普通的除法計(jì)算有所不同。普通的除法計(jì)算是借位相減的，而crc計(jì)算則是異或運(yùn)算。任何一個(gè)除法運(yùn)算都需要選取一個(gè)除數(shù)，在crc運(yùn)算中我們稱之為poly，而寬度w就是poly最高位的位置。比如poly 1001的w是3，而不是4。注意最高位總是1，當(dāng)你選定一個(gè)寬度，那么你只需要選擇低w各位的值。假如我們想計(jì)算一個(gè)位串的crc碼，并

2、要保證每一位都要被處理，因此我們需要在目標(biāo)位串后面加上w個(gè)0。下面舉例說(shuō)明crc算法的過(guò)程。 在此例中，我們假設(shè)位串為110101101。poly(除數(shù)) = 10011（寬度w = 4）bitstring + w個(gè)0 = 110101101 0000 10011/ 1101011010000/110000101 （我們不關(guān)心此運(yùn)算的商） 10011| -| 10011| 10011| -| 00001| 00000| -| 00010| 00000| -| 00101| 00000| -| 01010| 00000| -| 10100| 10011| -| 01110| 00000| -|

3、11100 10011 - 1111 - 余數(shù) - crc！計(jì)算過(guò)程總結(jié)如下：1. 只有當(dāng)位串的最高位為1，我們才將它與poly做xor運(yùn)算，否則我們只是將位串左移一位。2. 異或運(yùn)算的結(jié)果實(shí)質(zhì)上是被操作位串與poly的低w位進(jìn)行運(yùn)算的結(jié)果，因?yàn)樽罡呶豢倿?。2.crc原理及其逆向破解方法：2.1介紹：這篇短文包含crc原理介紹和其逆向分析方法,很多程序員和破解者不是很清楚crc的工作原理,而且?guī)缀鯖]人知道如何逆向分析它的方法，事實(shí)上它是非常有用的。首先，這篇教程教你一般如何計(jì)算crc，你可以將它用在數(shù)據(jù)代碼保護(hù)中。第二，主要是介紹如何逆向分析crc-32，你可以以此來(lái)分析程序中的crc保護(hù)（

4、象反病毒編碼）。當(dāng)然有很多有效的工具用來(lái)對(duì)付crc，但我懷疑它是否會(huì)說(shuō)明原理。我要告訴你，這篇短文里中應(yīng)用了很多數(shù)學(xué)知識(shí)，這不會(huì)影響一些人，而且會(huì)被一般的程序員與逆向分析者很好理解，為什么？那么如果你不知道數(shù)學(xué)是如何被應(yīng)用在crc中，我建議你可以停止繼續(xù)學(xué)習(xí)了。所以我假定你們（讀者）都是具備二進(jìn)制算術(shù)知識(shí)的。2.2第一部分：crc 介紹,crc是什么和計(jì)算crc的方法2.2.1循環(huán)冗余碼 crc我們都知道crc，甚至你沒有印象，但當(dāng)你想到那些來(lái)自諸如rar，zip等壓縮軟件發(fā)給你由于錯(cuò)誤連接和其他一些意外原因?qū)е碌奈募e(cuò)誤的惱人的消息時(shí)，你就會(huì)知道。crc是塊數(shù)據(jù)的計(jì)算值，比如對(duì)每一個(gè)文件進(jìn)行

5、壓縮，在一個(gè)解壓縮過(guò)程中，程序會(huì)從新計(jì)算解壓文件的crc值，并且將之與從文件中讀取的crc值進(jìn)行比對(duì)，如果值相同，那么正確。在crc-32中，會(huì)有1/232的可能性發(fā)生對(duì)確認(rèn)數(shù)據(jù)更改的校驗(yàn)錯(cuò)誤。 很多人認(rèn)為crc就是循環(huán)冗余校驗(yàn)。假如crc真的就是循環(huán)冗余校驗(yàn)，那么很多人都錯(cuò)用了這個(gè)術(shù)語(yǔ)。你不能說(shuō)這個(gè)程序的crc是12345678。人們也常說(shuō)某一個(gè)程序有crc校驗(yàn)，而不說(shuō)是 循環(huán)冗余校驗(yàn) 校驗(yàn)。結(jié)論：crc 代表循環(huán)冗余碼，而不是循環(huán)冗余校驗(yàn)。計(jì)算是如何完成的呢？好，主要的想法就是將一個(gè)文件看成一個(gè)被一些數(shù)字分割的很長(zhǎng)的位字串，這里會(huì)有一個(gè)余數(shù)crc！你總會(huì)有一個(gè)余數(shù)(可以是0)，它至多比除數(shù)

6、小1。(9/3=3 余數(shù)=0 ；(9+2)/3=3 余數(shù)=2)(或者它本身就包含一個(gè)除數(shù)在其中)。在這里crc計(jì)算方法與除法有一點(diǎn)點(diǎn)區(qū)別，除法就是將被減數(shù)重復(fù)的減去除數(shù)x次，然后留下余數(shù)。如果你希望得到原值，那么你就要把除數(shù)乘上x次，然后加上余數(shù)。crc計(jì)算使用特殊的減法與加法完成的，也就是一種新的算法。計(jì)算中每一位計(jì)算的進(jìn)位值被忽略了。 看如下兩個(gè)例子，（1）是普通減法，（2）和（3）是特殊的。 （1） （2） （3）1101101010100+0=00-0=01010 1111 +1111 0+1=1 *0-1=11+0=11-0=1001101010101*1+1=01-1=0在（1）中

7、，右數(shù)第二列可以看成是0 -1= -1，因此要從高位借1，就變成(10+0)-1=1， (這就象普通的by-paper十進(jìn)制減法)。特例（2,3）中，1+1會(huì)有正常的結(jié)果10，“1”是計(jì)算后的進(jìn)位，這個(gè)值被忽略了。特殊情況0-1應(yīng)該有正常結(jié)果“-1”就要退到下一位。這個(gè)值也被忽略了，假如你對(duì)編程有一定了解，這就象xor 操作或者更好。 現(xiàn)在來(lái)看一個(gè)除法的例子:在普通算法中:1001/11110001101 13 9/12013 1001 - 09 -| - -| 1100 30 | 1001 - 27 - - - 0110 3 - 余數(shù) 0000 - - 1100 1001 - - 011 -

8、 3, 余數(shù)在crc算法中:1001/11110001110 9/12014 余數(shù)為 6 1001 - - 1100 1001 - - 1010 1001 - - 0110 0000 - - 110 - 余數(shù)(例 3)這個(gè)除法的商并不重要，也沒必要去記住，因?yàn)樗麄儍H僅是一組無(wú)關(guān)緊要的位串。真正重要的是余數(shù)！它就是這個(gè)值，可以說(shuō)比原文件還重要的值，他就是基本的crc。過(guò)度到真正的crc碼計(jì)算。 進(jìn)行一個(gè)crc計(jì)算我們需要選則一個(gè)除數(shù)，從現(xiàn)在起我們稱之為poly。寬度w就是最高位的位置，所以這個(gè)poly 1001的w 是3，而不是4。注意最高位總是1，當(dāng)你選定一個(gè)寬度，那么你只需要選擇低w各位的值

9、。 假如我們想計(jì)算一個(gè)位串的crc碼，我們想確定每一個(gè)位都被處理過(guò)，因此，我們要在目標(biāo)位串后面加上w個(gè)0位。在此例中，我們假設(shè)位串為110101101。請(qǐng)仔細(xì)分析下面一個(gè)例子：poly = 10011，寬度 w=4位串 bitstring bitstring + w zeros = 110101101 + 000010011/1101011010000110000101 (我們不關(guān)心此運(yùn)算的商) 10011| - -| 10011| 10011| - -| 00001| 00000| - -| 00010| 00000| - -| 00101| 00000| - -| 01010| 00000

10、| - -| 10100| 10011| - -| 01110| 00000| - -| 11100 10011 - - 1111 - 余數(shù) - the crc!(例 4)重要兩點(diǎn)聲明如下:1、只有當(dāng)bitstring的最高位為1，我們才將它與poly做xor運(yùn)算，否則我們只是將bitstring左移一位。2、xor運(yùn)算的結(jié)果就是被操作位串bitstring與低w位進(jìn)行xor運(yùn)算，因?yàn)樽罡呶豢倿?。算法設(shè)計(jì): 你們都應(yīng)知道基于位運(yùn)算的算法是非常慢的而且效率低下，但如果將計(jì)算放在每一字節(jié)上進(jìn)行，那么效率將大大提高。不過(guò)我們只能接受poly的寬度w是8的倍數(shù)(一個(gè)字節(jié)；)?？梢孕蜗蟮目闯蛇@樣一個(gè)寬

11、度w為32的poly(w=32)： 3 2 1 0 byte +-+-+-+-+pop! -| | | | |- bitstring with w zero bits added, in this case 32 +-+-+-+-+ 1 this is the poly, 4*8 bits(figure 1) 這是一個(gè)你用來(lái)存放暫時(shí)crc結(jié)果的寄存器，現(xiàn)在我稱它為crc寄存器或者寄存器。你從右至左移動(dòng)位串，當(dāng)從左邊移出的位是1，則整個(gè)寄存器被與poly的低w位進(jìn)行xor運(yùn)算。(此例中為32)。事實(shí)上，我們精確的完成了上面除法所做的事情。移動(dòng)前寄存器值為:10110100，當(dāng)從右邊移入4位時(shí)，左

12、邊的高4位將被移出，此例中1011將被移出，而1101被移入。情況如下:當(dāng)前8位crc寄存器 : 01001101剛剛被移出的高4位 : 1011我們用此poly : 1 0101 1100，0x5c 寬度 w=8現(xiàn)在我們用如前介紹的方法來(lái)計(jì)算寄存器的新值。頂部 寄存器- -101101001101 高四位和當(dāng)前寄存器值101011100 + (*1) poly 放在頂部最高位進(jìn)行xor運(yùn)算 (因?yàn)槟抢锸?)-000110101101 運(yùn)算結(jié)果現(xiàn)在我們?nèi)杂幸晃?在高4位:0001 10101101 上一步結(jié)果 1 01011100+ (*2) poly 放在頂部的最低位進(jìn)行xor運(yùn)算 (因?yàn)槟?/p>

13、里是1)-0000 11110001 第二步運(yùn)算結(jié)果現(xiàn)在頂部所有位均為0，所以我們不需要在與poly進(jìn)行xor運(yùn)算你可以得到相同的結(jié)果如果你先將(*1)與(*2)做xor然后將結(jié)果與記存器值做xor.這就是標(biāo)準(zhǔn)xor運(yùn)算的特性:(a xor b) xor c = a xor (b xor c) 由此,推出如下的運(yùn)算順序也是正確的.101011100 poly (*1) 放在頂部最高位101011100+ polys (*2) 放在頂部最低位-101110111100 (*3) xor運(yùn)算結(jié)果the result (*3) 將(*3)與寄存器的值做xor運(yùn)算1011 101111001011 0

14、1001101+ 如右:-0000 11110001你看到了嗎？得到一樣的結(jié)果！現(xiàn)在(*3)變的重要了，因?yàn)轫敳繛?010則(3)的值總是等于10111100(當(dāng)然是在一定的條件之下),這意味著你可以預(yù)先計(jì)算出任意頂部位結(jié)合的xor值。注意，頂部結(jié)果總是0，這就是組合xor操作導(dǎo)致的結(jié)果。(翻譯不準(zhǔn)確,保留原文) 現(xiàn)在我們回到figure 1，對(duì)每一個(gè)頂部字節(jié)的值都做移出操作，我們可以預(yù)先計(jì)算出一個(gè)值。此例中，它將是一個(gè)包含256個(gè)double word(32 bit)雙字的表。(附錄中crc-32的表).(翻譯不準(zhǔn)確,保留原文) 用偽語(yǔ)言表示我們的算法如下: while (byte stri

15、ng is not exhausted) begin top = top_byte of register ; / (register value8)register = register shifted 8 bits left orred with a new byte from string ;/ (register value8) register = register xorred by value from precomputedtable at position top ; end / register crc_tabletopnew byte from string;direct

16、 table算法: 上面提到的算法可以被優(yōu)化，字節(jié)串中的字節(jié)在被用到之前沒有必要經(jīng)過(guò)整個(gè)寄存器。用這個(gè)新的算法，我們可以直接用一個(gè)字節(jié)去xor一個(gè)字節(jié)串通過(guò)將此字節(jié)移出記存器。結(jié)果指向預(yù)先計(jì)算的表中的一個(gè)值，這個(gè)值是用來(lái)被記存器的值做xor運(yùn)算的。 我不十分確切的知道為什么這會(huì)得到同樣的結(jié)果(這需要了解xor運(yùn)算的特性)，但是這又極為便利，因?yàn)槟銦o(wú)須在你的字節(jié)串后填充0字節(jié)/位。(如果你知道原理，請(qǐng)告訴我。) 讓我們來(lái)實(shí)現(xiàn)這個(gè)算法: +- byte string (or file) 字節(jié)串,(或是文件) | v 3 2 1 0 byte 字節(jié) | +-+-+-+-+xor-: : : : :

17、+-+-+-+-+ | | | | | +-+-+-+-+(figure 2)reflected direct table 算法: 由于這里有這樣一個(gè)與之相對(duì)應(yīng)的“反射”算法，事情顯得復(fù)雜了。一個(gè)反射的值/寄存器就是將它的每一位以此串的中心位為標(biāo)準(zhǔn)對(duì)調(diào)形成的。例如:0111011001就是1001101110的反射串。 他們提出“反射”是因?yàn)閡art(一種操作io的芯片)發(fā)送每一個(gè)字節(jié)時(shí)是先發(fā)最沒用的0位,最后再發(fā)最有意義的第7位，這與正常的位置是相逆的。 除了信息串不做反射以外，在進(jìn)行下一步操作前，要將其余的數(shù)據(jù)都做反射處理。所以在計(jì)算值表時(shí)，位向右移，且poly也是作過(guò)反射處理的。當(dāng)然,在

18、計(jì)算crc時(shí)，寄存器也要向右移，而且值表也必須是反射過(guò)的. byte string (or file) -+ | 1. 表中每一個(gè)入口都是反射的. byte 3 2 1 0 v 2. 初始化記存器也是反射的. +-+-+-+-+ | 3. 但是byte string中的數(shù)據(jù)不是反射的, | | | | |-xor 因?yàn)槠渌亩甲鲞^(guò)反射處理了. +-+-+-+-+ | | | xor v | +-+-|-+-+ | | | | | | | 值表 +-+-+-+-+ | : : : : : -+ +-+-+-+-+ | | | | | +-+-+-+-+(figure 3)我們的算法如下:1. 將

19、記存器向右移動(dòng)一個(gè)字節(jié)。2. 將剛移出的那個(gè)字節(jié)與byte string中的新字節(jié)做xor運(yùn)算,得出一個(gè)指向值表table0.255的索引。3. 將索引所指的表值與記存器做xor運(yùn)算.4. 如數(shù)據(jù)沒有全部處理完,則跳到步驟1.下面是這個(gè)算法的簡(jiǎn)單的可執(zhí)行匯編源碼:完整的crc-32標(biāo)準(zhǔn)所包含的內(nèi)容:name : crc-32width : 32poly : 04c11db7initial value : ffffffffreflected : truexor out with : ffffffff作為對(duì)你好奇心的獎(jiǎng)勵(lì), 這里是crc-16標(biāo)準(zhǔn): :)name : crc-16width : 1

20、6poly : 8005initial value : 0000reflected : truexor out with : 0000xor out with 是為了最終得到crc而用來(lái)與寄存器最后結(jié)果做xor運(yùn)算的值。假如你想了解一些關(guān)于reversed逆向crc poly的話,請(qǐng)看我的參考文章. 我是在16位dos模式下用的32位編碼，因此你會(huì)在這個(gè)程序中看到很多32位與16位混合的編碼.當(dāng)然這是很容易轉(zhuǎn)換成純32位編碼的。注意這個(gè)程序是經(jīng)過(guò)完整測(cè)試并且能夠正常運(yùn)行的.下面的java 和 c 代碼都是由這個(gè)匯編代碼而來(lái)的. 底下的這段程序就是用來(lái)計(jì)算crc-32 table的: xor e

21、bx, ebx ;ebx=0, 將被用做一個(gè)指針.inittableloop: xor eax, eax ;eax=0 為計(jì)算新的entry. mov al, bl ;al-bl ;生成入口. xor cx, cxentryloop: test eax, 1 jz no_topbit shr eax, 1 xor eax, poly jmp entrygoonno_topbit: shr eax, 1entrygoon: inc cx test cx, 8 jz entryloop mov dword ptrebx*4 + crctable, eax inc bx test bx, 256 j

22、z inittableloop注釋: - crctable 是一個(gè)包含256個(gè)dword的數(shù)組. - 由于使用反射算法，eax被向右移。 - 因此最低的8位被處理了.用java和c寫的代碼如下(int is 32 bit):for (int bx=0; bx256; bx+) int eax=0; eax=eax&0xffffff00+bx&0xff; / 就是 mov al,bl 指令 for (int cx=0; cx=1; eax=poly; else eax=1; crctablebx=eax;下面的匯編代碼是用來(lái)計(jì)算crc-32的:computeloop: xor ebx, ebx

23、xor al, si mov bl, al shr eax, 8 xor eax, dword ptr4*ebx+crctable inc si loop computeloop xor eax, 0ffffffffh注釋: - ds:si 指向?qū)⒁惶幚淼腷yte string信息流. - cx 信息流的長(zhǎng)度. - eax 是當(dāng)前的crc. - crctable是用來(lái)計(jì)算crc的值表. - 此例中記存器的初始值為: ffffffff. - 要將中間值與ffffffffh做xor才能得到crc下面是java和c寫的代碼:for (int cx=0; cx=8; eax=crctableebx;

24、eax=0xffffffff; 現(xiàn)在我們已經(jīng)完成了本文的第一部分:crc原理部分，所以如果你希望能夠?qū)rc做更深的研究，那么我建議你去讀在本文最后給出連接上的資料，我讀了，好了，終于到了本文最有意思的部分：crc的逆向分析!-2.3第二部分：crc的逆向分析 我遇到了很多障礙，當(dāng)我思考如何破解crc時(shí)，我試圖使用一些特殊順序的字節(jié)使crc無(wú)效。但我沒有做到.后來(lái)我意識(shí)到這種方法是行不通的，因?yàn)閏rc內(nèi)建了一些處理過(guò)程，無(wú)論你改變?nèi)魏挝凰疾粫?huì)出問(wèn)題。真正的crc就是在不斷變化的，總是在變化的找一些crc程序，你可以自己嘗試一下。 現(xiàn)在我知道我只能“糾正”在crc后面的那些我想改變的字節(jié)。所以

25、我要構(gòu)造一個(gè)字節(jié)序列，它可以將crc轉(zhuǎn)化成任何我想要的樣子! 具體實(shí)現(xiàn)這個(gè)想法一個(gè)字節(jié)串? 01234567890123456789012345678901234567890123456789012you want to change from this byte to this one.就是位置9-26。同時(shí)我們需要額外的4個(gè)字節(jié)用來(lái)在最后恢復(fù)原始字節(jié)串。 當(dāng)你計(jì)算crc-32時(shí)，從0-8都沒有問(wèn)題，直到第9位，修補(bǔ)過(guò)的字節(jié)串會(huì)使crc發(fā)生根本的改變。即使當(dāng)走過(guò)了第26位，以后的字節(jié)都沒有改變，你也不可能在得到原始的crc了，不可能了!你讀過(guò)后面的段落時(shí)就會(huì)明白為什么。簡(jiǎn)而言之，當(dāng)你修改一個(gè)

26、字節(jié)串時(shí)，要保證crc不變。1. 計(jì)算并保存從19位的crc.2. 繼續(xù)計(jì)算直到第27位還有額外的4字節(jié)并保存結(jié)果.3. 用1的值來(lái)計(jì)算新的字節(jié)串和額外4字節(jié)的crc(對(duì)應(yīng)patch后的新的crc值),并將之保存.4. 現(xiàn)在我們得到了一個(gè)新的crc,但是我們希望將它還原成原先的crc,所以我們用逆向算法 來(lái)計(jì)算那額外的4字節(jié).13就是實(shí)際的情況,下面你將學(xué)到最關(guān)鍵的部分4.反轉(zhuǎn)crc-16 我想,先來(lái)介紹計(jì)算逆crc-16對(duì)于你來(lái)說(shuō)會(huì)簡(jiǎn)單些.好的,我們現(xiàn)在處在一個(gè)恰當(dāng)?shù)奈恢?在以修改代碼后面,就是你想將crc還原的地方.我們知道原始的crc(是在patch代碼之前計(jì)算出來(lái)的)還有這個(gè)當(dāng)前的記存

27、器值.現(xiàn)在我們的目的就是計(jì)算可以改變當(dāng)前記存器值到原始記存器值的兩個(gè)字節(jié). 首先,我們用正常的方法計(jì)算這兩個(gè)未知字節(jié)的crc.我們?cè)O(shè)他們?yōu)閤,y.設(shè)記存器為a1,a0,只有0不能用來(lái)作為變量(00).:)在來(lái)看一下我們的crc算法,figure3,更好的理解下面我要做的.好,我們開始:用這兩字節(jié)串x y 字節(jié)是從左邊開始被處理的.記存器現(xiàn)在是a1 a0.用+來(lái)表示xor運(yùn)算(和第一部分中用的一樣)處理第一個(gè)字節(jié), x:a0+x 這是頂部字節(jié)的計(jì)算結(jié)果 (1)b1 b0 這是(1)在表中索引對(duì)象.00 a1 向右移動(dòng)記存器.00+b1 a1+b0 上面兩行對(duì)應(yīng)位做xor運(yùn)算.現(xiàn)在記存器為: (b

28、1) (a1+b0)處理第二個(gè)字, y:(a1+b0)+y 此輪頂部字節(jié)的計(jì)算結(jié)果(2)c1 c0 這是(2)在表中的索引對(duì)象.00 b1 向右移動(dòng)記存器.00+c1 b1+c0 上面兩行對(duì)應(yīng)位做xor運(yùn)算.最后記存器就是: (c1) (b1+c0)我用一點(diǎn)不同的方法來(lái)表示:a0 + x =(1) 在表中指向b1 b0.a1 + b0 + y =(2) 在表中指向c1 c0. b1 + c0=d0 記存器中新的低位字節(jié). c1=d1 記存器中新的高位字節(jié). (1) (2)wow! 請(qǐng)大家暫時(shí)記住上面的信息:)別著急, 下面給出一個(gè)有具體值的例子. 如果你想要的記存器的值是d1 d0(是原始的c

29、rc),而且你知道在變換之前的記存器的值(a1 a0).那么你將要送如什么樣的2個(gè)字節(jié)進(jìn)記存器來(lái)做crc計(jì)算呢? 好了,現(xiàn)在我們的工作應(yīng)該從幕后走到臺(tái)前來(lái)了.d0一定是bi+c0,并且d1一定是c1.但是這到底是怎么回事,我聽到你這樣問(wèn)了,你能知道b1和c0的值嗎?你還記得哪個(gè)值表嗎?你只需要在表中查找c0 c1這個(gè)字的值就可以了因?yàn)槟阒纁1.所以你需要編寫一個(gè)查找程序.假如你找到了這個(gè)值,一定要記住這個(gè)值的索引,因?yàn)檫@就是找出未知的兩個(gè)頂部字節(jié),舉例來(lái)說(shuō):(1)和(2)! 所以,現(xiàn)在你找到了c1 c0,那么如何來(lái)得到b1 b0呢?如果b1+c0=d0那么b1=d0+c0!如前所述,現(xiàn)在你用

30、哪個(gè)查找程序在表中查b1 b0的值.現(xiàn)在我們得到了所有計(jì)算x和y所需要的值.cool huh? a1+b0+y=(2) so y=a1+b0+(2)a0+x=(1) so x=a0+(1)實(shí)例.讓我們來(lái)看看這個(gè)具體值的例子:-register before: (a1=)de (a0=)ad-wanted register: (d1=)12 (d0=)34在附錄的crc-16的表中查找以12開頭值的入口.這里入口38h的值為12c0.試這找一找是否還有以12開頭的值的入口.你不可能在找到的,因?yàn)槲覀冇?jì)算每一中頂部字節(jié)組合而得的值的入口,一共是256個(gè)值,記住!現(xiàn)在我們知道(2)=38,c1=12

31、,c0=c0,所以b1=c0+34=f4,現(xiàn)在查找以f4開頭的b1的入口.這里入口4fh的值是f441.我們還知道 (1)=4f,b1=f4,b0=41,現(xiàn)在所有我們需要的都已經(jīng)清楚了,接下來(lái)我們計(jì)算x,y.y=a1+b0+(2)=de+41+38=a7x=a0+(1) =ad+4f =e2結(jié)論:將crc 記存器的值從 dead 變?yōu)?1234 我們需要這兩個(gè)字節(jié) e2 a7 (以此順序). 你看,破解crc校驗(yàn)?zāi)阈枰聪蛴?jì)算,還有要記住的就是計(jì)算過(guò)程中的值.當(dāng)你在用匯編編寫查找表程序時(shí),要注意intel在小模式中是反向存儲(chǔ)值的.現(xiàn)在你可能已經(jīng)明白如何去破解這個(gè)crc-16了.下面介紹如何在c

32、rc-32中實(shí)現(xiàn).破解 crc-32現(xiàn)在我們來(lái)看crc-32,和crc-16是一樣容易的(可能一樣的不容易你認(rèn)為).這里你操作的對(duì)象是4個(gè)字節(jié)的而不是2字節(jié)的.繼續(xù)向下看,將它與上面crc-16版本做對(duì)比.設(shè)4字節(jié)串 x y z w , 從左邊開始處理.設(shè)記存器為 a3 a2 a1 a0注意a3是msb,而a0是lsb處理第一個(gè)字節(jié), x:a0+x 這是頂部字節(jié)的計(jì)算結(jié)果(1).b3 b2 b1 b0 這是(1)在表中索引對(duì)象序列.00 a3 a2 a1 右移記存器.00+b3 a3+b2 a2+b1 a1+b0 上面兩行對(duì)應(yīng)位做xor運(yùn)算.現(xiàn)在記存器是: (b3) (a3+b2) (a2+b

33、1) (a1+b0)processing second byte, y:(a1+b0)+y 這是頂部字節(jié)的計(jì)算結(jié)果(2).c3 c2 c1 c0 這是(2)在表中索引對(duì)象序列.00 b3 a3+b2 a2+b1 右移記存器.00+c3 b3+c2 a3+b2+c1 a2+b1+c0 上面兩行對(duì)應(yīng)位做xor運(yùn)算.現(xiàn)在記存器是: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)processing third byte, z:(a2+b1+c0)+z 這是頂部字節(jié)的計(jì)算結(jié)果(3).d3 d2 d1 d0 這是(3)在表中索引對(duì)象序列.00 c3 b3+c2 a3+b2+c1 右

34、移記存器.00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 上面兩行對(duì)應(yīng)位做xor運(yùn)算.現(xiàn)在記存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)processing fourth byte, w:(a3+b2+c1+d0)+w 這是頂部字節(jié)的計(jì)算結(jié)果(4).e3 e2 e1 e0 這是(4)在表中索引對(duì)象序列.00 d3 c3+d2 b3+c2+d1 右移記存器.00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 上面兩行對(duì)應(yīng)位做xor運(yùn)算.最后,記存器為: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0

35、)我用一個(gè)不同一點(diǎn)的方法來(lái)表示:a0 + x =(1) 在表中指向 b3 b2 b1 b0 a1 + b0 + y =(2) 在表中指向 c3 c2 c1 c0 a2 + b1 + c0 + z =(3) 在表中指向 d3 d2 d1 d0 a3 + b2 + c1 + d0 + w =(4) 在表中指向 e4 e3 e2 e1 b3 + c2 + d1 + e0 =f0 c3 + d2 + e1 =f1 d3 + e2 =f2 e3 =f3 (1) (2) (3) (4)(figure 4)這里是用的與crc-16同樣的方法來(lái)實(shí)現(xiàn)的,我會(huì)給出一個(gè)具體值的例子.查找用附錄中crc-32的值表.

36、take for crc register before, a3 a2 a1 a0 - ab cd ef 66take for crc register after, f3 f2 f1 f0 - 56 33 14 78 (wanted value)我們開始:first byte of entries entry valuee3=f3 =56 - 35h=(4) 56b3c423 for e3 e2 e1 e0d3=f2+e2 =33+b3 =e6 - 4fh=(3) e6635c01 for d3 d2 d1 d0c3=f1+e1+d2 =14+c4+63 =b3 - f8h=(2) b366

37、7a2e for c3 c2 c1 c0b3=f0+e0+d1+c2=78+23+5c+66=61 - deh=(1) 616bffd3 for b3 b2 b1 b0now we have all needed values, thenx=(1)+ a0= de+66=b8y=(2)+ b0+a1= f8+d3+ef=c4z=(3)+ c0+b1+a2= 4f+2e+ff+cd=53w=(4)+d0+c1+b2+a3=35+01+7a+6b+ab=8e(final computation)結(jié)論:要將 crc-32 的記存器的值從 abcdef66 改變到 56331478 我們需要這樣一個(gè)字

38、節(jié)序列: b8 c4 53 8ecrc-32的破解算法 假如你考慮手動(dòng)計(jì)算這個(gè)可以還原crc記存器的字節(jié)序列,那么這將很難變成一個(gè)簡(jiǎn)潔的算法. 看看下面這個(gè)最后計(jì)算的附加版本: positionx =(1) + a0 0y =(2) + b0 + a1 1z =(3) + c0 + b1 + a2 2w =(4) + d0 + c1 + b2 + a3 3f0= e0 + d1 + c2 + b3 4f1= e1 + d2 + c3 5f2= e2 + d3 6f3= e3 7(figure 5) 它就等同于figure 4,只不過(guò)是一些值/字節(jié)被交換了.這種方法可以幫助我們構(gòu)造一個(gè)簡(jiǎn)潔的算法

39、.這里我們用一個(gè)8字節(jié)的緩沖區(qū),0-3位我們放置a0到a3,4-7位我們放置f0到f3.象以前一樣,我們用這個(gè)已知值e3(由figure 5中得知)在表中查出(e3 e2 e1 e0),并且象圖5(figure 5)中所示,將它們放到第4位(position 4),我們馬上得到了d3的值.因?yàn)閒2=e2+d3,所以f2+e2=d3.又因?yàn)?4)已知(入口值),我們照樣把它也放到位置3.然后在用d3查表得到(d3 d2 d1 d0),同上也將他們放到圖中所述位置.同樣,由于有f1+e1+d2=c3在位置5上. 我們繼續(xù)做直到將b3 b2 b1 b0放到位置1,對(duì)了，就是它! et voila!此

40、時(shí),緩沖區(qū)的第3-第0字節(jié)中已經(jīng)包含全部元素,用來(lái)計(jì)算xw! 算法總結(jié)如下:1.對(duì)于這個(gè)8字節(jié)的緩沖區(qū),03字節(jié)放入a0.a3(crc記存器起始值),47字節(jié)放入f0.f3 (目標(biāo)記存器的值).2.取出位置7的已知值,查表得到相應(yīng)值.3.將查出值放如圖5相應(yīng)位置,其實(shí)就是做xor運(yùn)算.(為了直觀,可以擬定此圖)4.將入口字節(jié)放入圖中.也是做xor運(yùn)算.5.繼續(xù)做2,3兩步3次,同時(shí)每次降低1個(gè)位置 position 5 to 4, 4 to 3 and so on.算法的實(shí)現(xiàn): 現(xiàn)在是時(shí)候給出代碼了.下面就是用匯編寫成的可執(zhí)行的crc-32算法(用其他語(yǔ)言也一樣簡(jiǎn)單,對(duì)于其他的crc-32標(biāo)準(zhǔn)

41、也一樣).注意在匯編中(計(jì)算機(jī)里)雙字在讀寫操作中順序都是反著的.就是逆向順序.crcbefore dd (?)wantedcrc dd (?)buffer db 8 dup (?) mov eax, dword ptrcrcbefore ;/* mov dword ptrbuffer, eax mov eax, dword ptrwantedcrc ; step 1 mov dword ptrbuffer+4, eax ;*/ mov di, 4computereverseloop: mov al, byte ptrbuffer+di+3 ;/* call gettableentry ; s

42、tep 2 */ xor dword ptrbuffer+di, eax ; step 3 xor byte ptrbuffer+di-1, bl ; step 4 dec di ;/* jnz computereverseloop ; step 5 */notes:-registers eax, di bx are usedimplementation of gettableentrycrctable dd 256 dup (?) ;should be defined globally somewhere & initialized of course mov bx, offset crctable-1gettableentryloop: add bx, 4 ;points to (crctable-1)+k*4 (k:1.256) cmp bx, al ;must always find the valu