CRC原理介紹:
CRC的英文全稱為Cyclic Redundancy Check（Code），中文名稱為循環(huán)冗余校驗（碼）。它是一類重要的線性分組碼，編碼和解碼方法簡單，檢錯和糾錯能力強(qiáng)，在通信領(lǐng)域廣泛地用于實現(xiàn)差錯控制。
CRC計算與普通的除法計算有所不同。普通的除法計算是借位相減的，而CRC計算則是異或運算。任何一個除法運算都需要選取一個除數(shù)，在CRC運算中我們稱之為poly，而寬度W就是poly最高位的位置。比如poly 1001的W是3，而不是4。注意最高位總是1，當(dāng)你選定一個寬度，那么你只需要選擇低W各位的值。假如我們想計算一個位串的CRC碼，并要保證每一位都要被處理，因此我們需要在目標(biāo)位串后面加上W個0。下面舉例說明CRC算法的過程。
在此例中，我們假設(shè)位串為110101101。
Poly = 10011（寬度W = 4）
Bitstring + W zeros = 110101101 0000
10011/1101011010000/110000101 （我們不關(guān)心此運算的商）
10011||||||||
-----||||||||
10011|||||||
10011|||||||
-----|||||||
00001||||||
00000||||||
-----||||||
00010|||||
00000|||||
-----|||||
00101||||
00000||||
-----||||
01010|||
00000|||
-----|||
10100||
10011||
-----||
01110|
00000|
-----|
11100
10011
-----
1111 -> 余數(shù) -> CRC！
計算過程總結(jié)如下：
1. 只有當(dāng)位串的最高位為1，我們才將它與poly做XOR運算，否則我們只是將位串左移一位。
2. 異或運算的結(jié)果實質(zhì)上是被操作位串與poly的低W位進(jìn)行運算的結(jié)果，因為最高位總為0?！?
CRC原理及其逆向破解方法：
介紹：
這篇短文包含CRC原理介紹和其逆向分析方法,很多程序員和破解者不是很清楚了解
CRC的工作原理,而且?guī)缀鯖]人知道如何逆向分析它的方法,事實上它是非常有用的.
首先,這篇教程教你一般如何計算CRC,你可以將它用在數(shù)據(jù)代碼保護(hù)中.第二,主要是
介紹如何逆向分析CRC-32,你可以以此來分析程序中的CRC保護(hù)（象反病毒編碼）.當(dāng)然
有很多有效的工具用來對付CRC,但我懷疑它是否會說明原理.
我要告訴你,這篇短文里中應(yīng)用了很多數(shù)學(xué)知識,這不會影響一些人,而且會被一般的
程序員與逆向分析者很好理解.為什么？那么如果你不知道數(shù)學(xué)是如何被應(yīng)用在CRC中,
我建議你可以停止繼續(xù)學(xué)習(xí)了.所以我假定你們（讀者）都是具備二進(jìn)制算術(shù)知識的.
第一部分：CRC 介紹,CRC是什么和計算CRC的方法.
循環(huán)冗余碼 CRC
我們都知道CRC.甚至你沒有印象,但當(dāng)你想到那些來自諸如RAR,ZIP等壓縮軟件發(fā)給你
由于錯誤連接和其他一些意外原因?qū)е碌奈募e誤的惱人的消息時,你就會知道.CRC是塊
數(shù)據(jù)的計算值,比如對每一個文件進(jìn)行壓縮.在一個解壓縮過程中,程序會從新計算解壓文件
的CRC值,并且將之與從文件中讀取的CRC值進(jìn)行比對,如果值相同,那么正確.在CRC-32中,
會有1/2^32的可能性發(fā)生對確認(rèn)數(shù)據(jù)更改的校驗錯誤.
很多人認(rèn)為CRC就是循環(huán)冗余校驗,假如CRC真的就是循環(huán)冗余校驗,那么很多人都錯用了
這個術(shù)語.你不能說"這個程序的CRC是12345678".人們也常說某一個程序有CRC校驗,而不
說是 "循環(huán)冗余校驗" 校驗.結(jié)論：CRC 代表循環(huán)冗余碼,而不是循環(huán)冗余校驗.
計算是如何完成的呢？好,主要的想法就是將一個文件看成一個被一些數(shù)字分割的很長的
位字串,這里會有一個余數(shù)---CRC！你總會有一個余數(shù)(可以是0),它至多比除數(shù)小一.
(9/3=3 余數(shù)=0 ; (9+2)/3=3 余數(shù)=2)
(或者它本身就包含一個除數(shù)在其中).
在這里CRC計算方法與除法有一點點區(qū)別,除法就是將被減數(shù)重復(fù)的減去除數(shù)X次,然后留下
余數(shù).如果你希望得到原值,那么你就要把除數(shù)乘上X次,然后加上余數(shù).
CRC計算使用特殊的減法與加法完成的.也就是一種新的"算法".計算中每一位計算的進(jìn)位值
被"遺忘"了.
看如下兩個例子,1是普通減法,2和3是特殊的.
-+
(1) 1101 (2) 1010 1010 (3) 0+0=0 0-0=0
1010- 1111+ 1111- 0+1=1 *0-1=1
---- ---- ---- 1+0=1 1-0=1
0011 0101 0101 *1+1=0 1-1=0
在(1)中,右數(shù)第二列可以看成是0-1=-1,因此要從高位借1,就變成(10+0)-1=1.(這就象普通
的'by-paper'十進(jìn)制減法).特例(2,3)中,1+1會有正常的結(jié)果10,'1'是計算后的進(jìn)位.這個值
被忽略了.特殊情況0-1應(yīng)該有正常結(jié)果'-1'就要退到下一位.這個值也被忽略了.假如你對編程
有一定了解,這就象,XOR 操作或者更好.
現(xiàn)在來看一個除法的例子:
在普通算法中:
1001/1111000\1101 13 9/120\13
1001 - 09 -|
---- -- |
1100 30 |
1001 - 27 -
---- --
0110 3 -> 余數(shù)
0000 -
----
1100
1001 -
----
011 -> 3, 余數(shù)
在CRC算法中:
1001/1111000\1110 9/120\14 余數(shù)為 6
1001 -
----
1100
1001 -
----
1010
1001 -
----
0110
0000 -
----
110 -> 余數(shù)
(例 3)
這個除法的商并不重要,也沒必要去記住,因為他們僅僅是一組無關(guān)緊要的位串.真正
重要的是余數(shù)!它就是這個值,可以說比原文件還重要的值,他就是基本的CRC.
過度到真正的CRC碼計算.
進(jìn)行一個CRC計算我們需要選則一個除數(shù),從現(xiàn)在起我們稱之為"poly".寬度W就是最高位
的位置,所以這個poly 1001的W 是3,而不是4.注意最高位總是1,當(dāng)你選定一個寬度,那么你只
需要選擇低W各位的值.
假如我們想計算一個位串的CRC碼,我們想確定每一個位都被處理過,因此,我們要在目標(biāo)
位串后面加上W個0位.在此例中,我們假設(shè)位串為1111.請仔細(xì)分析下面一個例子:
Poly = 10011, 寬度 W=4
位串 Bitstring
Bitstring + W zeros = 110101101 + 0000
10011/1101011010000\110000101 (我們不關(guān)心此運算的商)
10011|||||||| -
-----||||||||
10011|||||||
10011||||||| -
-----|||||||
00001||||||
00000|||||| -
-----||||||
00010|||||
00000||||| -
-----|||||
00101||||
00000|||| -
-----||||
01010|||
00000||| -
-----|||
10100||
10011|| -
-----||
01110|
00000| -
-----|
11100
10011 -
-----
1111 -> 余數(shù) -> the CRC!
(例 4)
重要兩點聲明如下:
1.只有當(dāng)Bitstring的最高位為1,我們才將它與poly做XOR運算,否則我們只是將
Bitstring左移一位.
2.XOR運算的結(jié)果就是被操作位串bitstring與低W位進(jìn)行XOR運算,因為最高位總為0.
算法設(shè)計:
你們都應(yīng)知道基于位運算的算法是非常慢的而且效率低下.但如果將計算放在每一字節(jié)上
進(jìn)行,那么效率將大大提高.不過我們只能接受poly的寬度是8的倍數(shù)(一個字節(jié);).可以形
象的看成這樣一個寬度為32的poly(W=32):
3 2 1 0 byte
+---+---+---+---+
Pop! <--| | | | |<-- bitstring with W zero bits added, in this case 32
+---+---+---+---+
1<--- 32 bits ---> this is the poly, 4*8 bits
(figure 1)
這是一個你用來存放暫時CRC結(jié)果的記存器,現(xiàn)在我稱它為CRC記存器或者記存器.你從右
至左移動位串,當(dāng)從左邊移出的位是1,則整個記存器被與poly的低W位進(jìn)行XOR運算.(此例
中為32).事實上,我們精確的完成了上面除法所做的事情.
移動前記存器值為:10110100
當(dāng)從右邊移入4位時,左邊的高4位將被移出,此例中1011將被移出,而1101被移入.
情況如下:
當(dāng)前8位CRC記存器 : 01001101
剛剛被移出的高4位 : 1011
我們用此poly : 101011100, 寬度 W=8
現(xiàn)在我們用如前介紹的方法來計算記存器的新值.
頂部 記存器
---- --------
1011 01001101 高四位和當(dāng)前記存器值
1010 11100 + (*1) Poly 放在頂部最高位進(jìn)行XOR運算 (因為那里是1)
-------------
0001 10101101 運算結(jié)果
現(xiàn)在我們?nèi)杂幸晃?在高4位:
0001 10101101 上一步結(jié)果
1 01011100+ (*2) Poly 放在頂部的最低位進(jìn)行XOR運算 (因為那里是1)
-------------
0000 11110001 第二步運算結(jié)果
^^^^
現(xiàn)在頂部所有位均為0,所以我們不需要在與poly進(jìn)行XOR運算
你可以得到相同的結(jié)果如果你先將(*1)與(*2)做XOR然后將結(jié)果與記存器值做XOR.
這就是標(biāo)準(zhǔn)XOR運算的特性:
(a XOR b) XOR c = a XOR (b XOR c) 由此,推出如下的運算順序也是正確的.
1010 11100 poly (*1) 放在頂部最高位
1 01011100+ polys (*2) 放在頂部最低位
-------------
1011 10111100 (*3) XOR運算結(jié)果
The result (*3) 將(*3)與記存器的值做XOR運算
1011 10111100
1011 01001101+ 如右:
-------------
0000 11110001
你看到了嗎?得到一樣的結(jié)果!現(xiàn)在(*3)變的重要了,因為頂部為1010則(3)的值總是等于
10111100(當(dāng)然是在一定的條件之下)這意味著你可以預(yù)先計算出任意頂部位結(jié)合的XOR值.
注意,頂部結(jié)果總是0,這就是組合XOR操作導(dǎo)致的結(jié)果.(翻譯不準(zhǔn)確,保留原文)
現(xiàn)在我們回到figure 1,對每一個頂部字節(jié)的值都做移出操作,我們可以預(yù)先計算出一個值.
此例中,它將是一個包含256個double word(32 bit)雙字的表.(附錄中CRC-32的表).
(翻譯不準(zhǔn)確,保留原文)
用偽語言表示我們的算法如下:
While (byte string is not exhausted)
Begin
Top = top_byte of register ;
Register = Register shifted 8 bits left ORred with a new byte from string ;
Register = Register XORred by value from precomputedTable at position Top ;
End
direct table算法:
上面提到的算法可以被優(yōu)化.字節(jié)串中的字節(jié)在被用到之前沒有必要經(jīng)過整個記村器.用
這個新的算法,我們可以直接用一個字節(jié)去XOR一個字節(jié)串通過將此字節(jié)移出記存器.結(jié)果
指向預(yù)先計算的表中的一個值,這個值是用來被記存器的值做XOR運算的.
我不十分確切的知道為什么這會得到同樣的結(jié)果(這需要了解XOR運算的特性),但是這又
極為便利,因為你無須在你的字節(jié)串后填充0字節(jié)/位.(如果你知道原理,請告訴我:)
讓我們來實現(xiàn)這個算法:
+----< byte string (or file) 字節(jié)串,(或是文件)
|
v 3 2 1 0 byte 字節(jié)
| +---+---+---+---+
XOR---<| | | | | Register 記存器
| +---+---+---+---+
| |
| XOR
| ^
v +---+---|---+---+
| | | | | | Precomputed table 值表(用來進(jìn)行操作)
| +---+---+---+---+
+--->-: : : : :
+---+---+---+---+
| | | | |
+---+---+---+---+
(figure 2)
'reflected' direct Table 算法:
由于這里有這樣一個與之相對應(yīng)的'反射'算法,事情顯得復(fù)雜了.一個反射的值/記存器
就是將它的每一位以此串的中心位為標(biāo)準(zhǔn)對調(diào)形成的.例如:0111011001就是1001101110
的反射串.
他們提出'反射'是因為UART(一種操作IO的芯片)發(fā)送每一個字節(jié)時是先發(fā)最沒用的0位,
最后再發(fā)最有意義的第七位.這與正常的位置是相逆的.
除了信息串不做反射以外,在進(jìn)行下一步操作前,要將其于的數(shù)據(jù)都做反射處理.所以在
計算值表時,位向右移,且poly也是作過反射處理的.當(dāng)然,在計算CRC時,記存器也要向右
移,而且值表也必須是反射過的.
byte string (or file) -->---+
| 1. 表中每一個入口都是反射的.
byte 3 2 1 0 V 2. 初始化記存器也是反射的.
+---+---+---+---+ | 3. 但是byte string中的數(shù)據(jù)不是反射的,
| | | | |>---XOR 因為其他的都做過反射處理了.
+---+---+---+---+ |
| |
XOR V
^ |
+---+---|---+---+ |
| | | | | | 值表
+---+---+---+---+ |
: : : : : <---+
+---+---+---+---+
| | | | |
+---+---+---+---+
(figure 3)
我們的算法如下:
1. 將記存器向右移動一個字節(jié).
2. 將剛移出的哪個字節(jié)與byte string中的新字節(jié)做XOR運算,
得出一個指向值表table[0..255]的索引
3. 將索引所指的表值與記存器做XOR運算.
4. 如數(shù)據(jù)沒有全部處理完,則跳到步驟1.
下面是這個算法的簡單的可執(zhí)行匯編源碼:
完整的CRC-32標(biāo)準(zhǔn)所包含的內(nèi)容:
Name : "CRC-32"
Width : 32
Poly : 04C11DB7
Initial value : FFFFFFFF
Reflected : True
XOR out with : FFFFFFFF
作為對你好奇心的獎勵, 這里是CRC-16標(biāo)準(zhǔn): :)
Name : "CRC-16"
Width : 16
Poly : 8005
Initial value : 0000
Reflected : True
XOR out with : 0000
'XOR out with' 是為了最終得到CRC而用來與記存器最后結(jié)果做XOR運算的值.
假如你想了解一些關(guān)于'reversed'逆向CRC poly的話,請看我的參考文章.
我是在16位DOS模式下用的32位編碼,因此你會在這個程序中看到很多32位與16位混合
的編碼...當(dāng)然這是很容易轉(zhuǎn)換成純32位編碼的.注意這個程序是經(jīng)過完整測試并且能夠
正常運行的.下面的Java 和 C 代碼都是由這個匯編代碼而來的.
底下的這段程序就是用來計算CRC-32 table的:
xor ebx, ebx ;ebx=0, 將被用做一個指針.
InitTableLoop:
xor eax, eax ;eax=0 為計算新的entry.
mov al, bl ;al<-bl
;生成入口.
xor cx, cx
entryLoop:
test eax, 1
jz no_topbit
shr eax, 1
xor eax, poly
jmp entrygoon
no_topbit:
shr eax, 1
entrygoon:
inc cx
test cx, 8
jz entryLoop
mov dword ptr[ebx*4 + crctable], eax
inc bx
test bx, 256
jz InitTableLoop
注釋: - crctable 是一個包含256個dword的數(shù)組.
- 由于使用反射算法,EAX被向右移.
- 因此最低的8位被處理了.
用Java和C寫的代碼如下(int is 32 bit):
for (int bx=0; bx<256; bx++){
int eax=0;
eax=eax&0xFFFFFF00+bx&0xFF; // 就是 'mov al,bl' 指令
for (int cx=0; cx<8; cx++){
if (eax&&0x1) {
eax>>=1;
eax^=poly;
}
else eax>>=1;
}
crctable[bx]=eax;
}
下面的匯編代碼是用來計算CRC-32的:
computeLoop:
xor ebx, ebx
xor al, [si]
mov bl, al
shr eax, 8
xor eax, dword ptr[4*ebx+crctable]
inc si
loop computeLoop
xor eax, 0FFFFFFFFh
注釋: - ds:si 指向?qū)⒁惶幚淼腷yte string信息流.
- cx 信息流的長度.
- eax 是當(dāng)前的CRC.
- crctable是用來計算CRC的值表.
- 此例中記存器的初始值為: FFFFFFFF.
- 要將中間值與FFFFFFFFh做XOR才能得到CRC
下面是Java和C寫的代碼:
for (int cx=0; cx>=8;
eax^=crcTable[ebx];
}
eax^=0xFFFFFFFF;
現(xiàn)在我們已經(jīng)完成了本文的第一部分:CRC原理部分,所以如果你希望能夠?qū)RC做更深
的研究,那么我建議你去讀在本文最后給出連接上的資料,我讀了.好了,終于到了本文最
有意思的部分,CRC的逆向分析!
------------------------------------------------------------------------------------
第二部分 CRC的逆向分析:
我遇到了很多障礙,當(dāng)我思考如何破解CRC時.我試圖使用一些特殊順序的字節(jié)使CRC無效.
但我沒有做到...后來我意識到這種方法是行不同的,因為CRC內(nèi)建了一些處理過程,無論你
改變?nèi)魏挝凰疾粫鰡栴},真正的CRC就是在不斷變化的,總是在變化的.找一些CRC程序,
你可以自己嘗試一下.
現(xiàn)在我知道我只能'糾正'在CRC后面的那些我想改變的字節(jié).所以我要構(gòu)造一個字節(jié)序列,
它可以將CRC轉(zhuǎn)化成任何我想要的樣子!
具體實現(xiàn)這個想法
一個字節(jié)串? 01234567890123456789012345678901234567890123456789012
You want to change from ^ this byte to ^ this one.
就是位置9->26.
同時我們需要額外的4個字節(jié)用來在最后恢復(fù)原始字節(jié)串.
當(dāng)你計算CRC-32時,從0-8都沒有問題,直到第9位,修補過的字節(jié)串會使CRC發(fā)生根本的改變.
即使當(dāng)走過了第26位,以后的字節(jié)都沒有改變,你也不可能在得到原始的CRC了,不可能了!你讀
過后面的段落時就會明白為什么.間而言之,當(dāng)你修改一個字節(jié)串時,要保證CRC不變.
1. 計算并保存從1~9位的CRC.
2. 繼續(xù)計算直到第27位還有額外的4字節(jié)并保存結(jié)果.
3. 用1的值來計算新的字節(jié)串和額外4字節(jié)的CRC(對應(yīng)patch后的新的CRC值),并將之保存.
4. 現(xiàn)在我們得到了一個新的CRC,但是我們希望將它還原成原先的CRC,所以我們用逆向算法
來計算那額外的4字節(jié).
1~3就是實際的情況,下面你將學(xué)到最關(guān)鍵的部分4.
'反轉(zhuǎn)'CRC-16
我想,先來介紹計算逆CRC-16對于你來說會簡單些.好的,我們現(xiàn)在處在一個恰當(dāng)?shù)奈恢?
在以修改代碼后面,就是你想將CRC還原的地方.我們知道原始的CRC(是在patch代碼之前計
算出來的)還有這個當(dāng)前的記存器值.現(xiàn)在我們的目的就是計算可以改變當(dāng)前記存器值到原
始記存器值的兩個字節(jié).首先,我們用正常的方法計算這兩個未知字節(jié)的CRC.我們設(shè)他們?yōu)?
X,Y.設(shè)記存器為a1,a0,只有0不能用來作為變量(00).:)在來看一下我們的CRC算法,figure
3,更好的理解下面我要做的.
好,我們開始:
用這兩字節(jié)串'X Y' 字節(jié)是從左邊開始被處理的.
記存器現(xiàn)在是a1 a0.
用'+'來表示XOR運算(和第一部分中用的一樣)
處理第一個字節(jié), X:
a0+X 這是頂部字節(jié)的計算結(jié)果 (1)
b1 b0 這是(1)在表中索引對象.
00 a1 向右移動記存器.
00+b1 a1+b0 上面兩行對應(yīng)位做XOR運算.
現(xiàn)在記存器為: (b1) (a1+b0)
處理第二個字, Y:
(a1+b0)+Y 此輪頂部字節(jié)的計算結(jié)果(2)
c1 c0 這是(2)在表中的索引對象.
00 b1 向右移動記存器.
00+c1 b1+c0 上面兩行對應(yīng)位做XOR運算.
最后記存器就是: (c1) (b1+c0)
我用一點不同的方法來表示:
a0 + X =(1) 在表中指向b1 b0.
a1 + b0 + Y =(2) 在表中指向c1 c0.
b1 + c0=d0 記存器中新的低位字節(jié).
c1=d1 記存器中新的高位字節(jié).
(1) (2)
Wow! 請大家暫時記住上面的信息:)
別著急, 下面給出一個有具體值的例子.
如果你想要的記存器的值是d1 d0(是原始的CRC),而且你知道在變換之前的記存器的值
(a1 a0)...那么你將要送如什么樣的2個字節(jié)進(jìn)記存器來做CRC計算呢?
好了,現(xiàn)在我們的工作應(yīng)該從幕后走到臺前來了.d0一定是bi+c0,并且d1一定是c1...
但是這到底是怎么回事,我聽到你這樣問了,你能知道b1和c0的值嗎???你還記得哪個值表
嗎?你只需要在表中查找c0 c1這個字的值就可以了因為你知道c1.所以你需要編寫一個查
找程序.假如你找到了這個值,一定要記住這個值的索引,因為這就是找出未知的兩個頂部
字節(jié),舉例來說:(1)和(2)!
所以,現(xiàn)在你找到了c1 c0,那么如何來得到b1 b0呢?如果b1+c0=d0那么b1=d0+c0!如前所
述,現(xiàn)在你用哪個查找程序在表中查b1 b0的值.現(xiàn)在我們得到了所有計算X和Y所需要的值.
Cool huh?
a1+b0+Y=(2) so Y=a1+b0+(2)
a0+X=(1) so X=a0+(1)
實例.
讓我們來看看這個具體值的例子:
-register before: (a1=)DE (a0=)AD
-wanted register: (d1=)12 (d0=)34
在附錄的CRC-16的表中查找以12開頭值的入口.這里入口38h的值為12C0.試這找一找是否還
有以12開頭的值的入口.你不可能在找到的,因為我們計算每一中頂部字節(jié)組合而得的值的
入口,一共是256個值,記住!
現(xiàn)在我們知道(2)=38,c1=12,c0=C0,所以b1=C0+34=F4,現(xiàn)在查找以F4開頭的b1的入口.這里
入口4Fh的值是F441.
我們還知道 (1)=4F,b1=F4,b0=41,現(xiàn)在所有我們需要的都已經(jīng)清楚了,接下來我們計算X,Y.
Y=a1+b0+(2)=DE+41+38=A7
X=a0+(1) =AD+4F =E2
結(jié)論:將CRC 記存器的值從 DEAD 變?yōu)?nbsp;1234 我們需要這兩個字節(jié) E2 A7 (以此順序).
你看,破解CRC校驗?zāi)阈枰聪蛴嬎?還有要記住的就是計算過程中的值.當(dāng)你在用匯編編寫
查找表程序時,要注意intel在小模式中是反向存儲值的.現(xiàn)在你可能已經(jīng)明白如何去破解這個
CRC-16了...下面介紹如何在CRC-32中實現(xiàn).
破解 CRC-32
現(xiàn)在我們來看CRC-32,和CRC-16是一樣容易的(可能一樣的不容易你認(rèn)為).這里你操作的對象
是4個字節(jié)的而不是2字節(jié)的.繼續(xù)向下看,將它與上面CRC-16版本做對比.
設(shè)4字節(jié)串 X Y Z W , 從左邊開始處理.
設(shè)記存器為 a3 a2 a1 a0
注意a3是MSB,而a0是LSB
處理第一個字節(jié), X:
a0+X 這是頂部字節(jié)的計算結(jié)果(1).
b3 b2 b1 b0 這是(1)在表中索引對象序列.
00 a3 a2 a1 右移記存器.
00+b3 a3+b2 a2+b1 a1+b0 上面兩行對應(yīng)位做XOR運算.
現(xiàn)在記存器是: (b3) (a3+b2) (a2+b1) (a1+b0)
Processing second byte, Y:
(a1+b0)+Y 這是頂部字節(jié)的計算結(jié)果(2).
c3 c2 c1 c0 這是(2)在表中索引對象序列.
00 b3 a3+b2 a2+b1 右移記存器.
00+c3 b3+c2 a3+b2+c1 a2+b1+c0 上面兩行對應(yīng)位做XOR運算.
現(xiàn)在記存器是: (c3) (b3+c2) (a3+b2+c1) (a2+b1+c0)
Processing third byte, Z:
(a2+b1+c0)+Z 這是頂部字節(jié)的計算結(jié)果(3).
d3 d2 d1 d0 這是(3)在表中索引對象序列.
00 c3 b3+c2 a3+b2+c1 右移記存器.
00+d3 c3+d2 b3+c2+d1 a3+b2+c1+d0 上面兩行對應(yīng)位做XOR運算.
現(xiàn)在記存器是: (d3) (c3+d2) (b3+c2+d1) (a3+b2+c1+d0)
Processing fourth byte, W:
(a3+b2+c1+d0)+W 這是頂部字節(jié)的計算結(jié)果(4).
e3 e2 e1 e0 這是(4)在表中索引對象序列.
00 d3 c3+d2 b3+c2+d1 右移記存器.
00+e3 d3+e2 c3+d2+e1 b3+c2+d1+e0 上面兩行對應(yīng)位做XOR運算.
最后,記存器為: (e3) (d3+e2) (c3+d2+e1) (b3+c2+d1+e0)
我用一個不同一點的方法來表示:
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同樣的方法來實現(xiàn)的,我會給出一個具體值的例子.查找用附錄中
CRC-32的值表.
Take for CRC register before, a3 a2 a1 a0 -> AB CD EF 66
Take for CRC register after, f3 f2 f1 f0 -> 56 33 14 78 (wanted value)
我們開始:
First byte of entries entry value
e3=f3 =56 -> 35h=(4) 56B3C423 for e3 e2 e1 e0
d3=f2+e2 =33+B3 =E6 -> 4Fh=(3) E6635C01 for d3 d2 d1 d0
c3=f1+e1+d2 =14+C4+63 =B3 -> F8h=(2) B3667A2E for c3 c2 c1 c0
b3=f0+e0+d1+c2=78+23+5C+66=61 -> DEh=(1) 616BFFD3 for b3 b2 b1 b0
Now we have all needed values, then
X=(1)+ a0= DE+66=B8
Y=(2)+ b0+a1= F8+D3+EF=C4
Z=(3)+ c0+b1+a2= 4F+2E+FF+CD=53
W=(4)+d0+c1+b2+a3=35+01+7A+6B+AB=8E
(final computation)
結(jié)論:要將 CRC-32 的記存器的值從 ABCDEF66 改變到 56331478 我們需要這樣一個字節(jié)
序列: B8 C4 53 8E
CRC-32的破解算法
假如你考慮手動計算這個可以還原CRC記存器的字節(jié)序列,那么這將很難變成一個
簡潔的算法.
看看下面這個最后計算的附加版本:
Position
X =(1) + a0 0
Y =(2) + b0 + a1 1
Z =(3) + c0 + b1 + a2 2
W =(4) + d0 + c1 + b2 + a3 3
f0= e0 + d1 + c2 + b3 4
f1= e1 + d2 + c3 5
f2= e2 + d3 6
f3= e3 7
(figure 5)
它就等同于figure 4,只不過是一些值/字節(jié)被交換了.這種方法可以幫助我們構(gòu)造一個
簡潔的算法.這里我們用一個8字節(jié)的緩沖區(qū),0-3位我們放置a0到a3,4-7位我們放置f0到
f3.象以前一樣,我們用這個已知值e3(由figure 5中得知)在表中查出(e3 e2 e1 e0),并且
象圖5(figure 5)中所示,將它們放到第4位(position 4),我們馬上得到了d3的值.因為f2=
e2+d3,所以f2+e2=d3.又因為(4)已知(入口值),我們照樣把它也放到位置3.然后在用d3查表
得到(d3 d2 d1 d0),同上也將他們放到圖中所述位置.同樣,由于有f1+e1+d2=c3在位置5上.
我們繼續(xù)做直到將b3 b2 b1 b0放到位置1,對了，就是它! Et voila!
此時,緩沖區(qū)的第3-第0字節(jié)中已經(jīng)包含全部元素,用來計算X~W!
算法總結(jié)如下:
1.對于這個8字節(jié)的緩沖區(qū),0~3字節(jié)放入a0...a3(CRC記存器起始值),4~7字節(jié)放入f0...f3
(目標(biāo)記存器的值).
2.取出位置7的已知值,查表得到相應(yīng)值.
3.將查出值放如圖5相應(yīng)位置,其實就是做XOR運算.(為了直觀,可以擬定此圖)
4.將入口字節(jié)放入圖中.也是做XOR運算.
5.繼續(xù)做2,3兩步3次,同時每次降低1個位置 position 5 to 4, 4 to 3 and so on.
算法的實現(xiàn):
現(xiàn)在是時候給出代碼了.下面就是用匯編寫成的可執(zhí)行的CRC-32算法(用其他語言也一樣
簡單,對于其他的CRC-32標(biāo)準(zhǔn)也一樣).注意在匯編中(計算機(jī)里)雙字在讀寫操作中順序都是
反著的.就是逆向順序.
crcBefore dd (?)
wantedCrc dd (?)
buffer db 8 dup (?)
mov eax, dword ptr[crcBefore] ;/*
mov dword ptr[buffer], eax
mov eax, dword ptr[wantedCrc] ; Step 1
mov dword ptr[buffer+4], eax ;*/
mov di, 4
computeReverseLoop:
mov al, byte ptr[buffer+di+3] ;/*
call GetTableEntry ; Step 2 */
xor dword ptr[buffer+di], eax ; Step 3
xor byte ptr[buffer+di-1], bl ; Step 4
dec di ;/*
jnz computeReverseLoop ; Step 5 */
Notes:
-Registers eax, di bx are used
Implementation of GetTableEntry
crctable dd 256 dup (?) ;should be defined globally somewhere & initialized of course
mov bx, offset crctable-1
getTableEntryLoop:
add bx, 4 ;points to (crctable-1)+k*4 (k:1..256)
cmp [bx], al ;must always find the value somewhere
jne getTableEntryLoop
sub bx, 3
mov eax, [bx]
sub bx, offset crctable
shr bx, 2
ret
On return eax contains a table entry, bx contains the entry number.
Outtro
好了...你終于讀到了本文的結(jié)尾.假如你認(rèn)為從此不管對什么樣的CRC保護(hù)都可以說bye
bye了,那么你錯了,不是的!很容易就可以寫出對付破解CRC的代碼的.想要成功的破解CRC
你需要知道在一個保護(hù)中,到底使用的是那一種CRC算法,并且要知道CRC的具體的計算位置.
比如說這里一種簡單的對策就是使用2種不同的CRC算法,或者可以結(jié)合其他的數(shù)據(jù)保護(hù)算法
共同使用.
無論如何...我希望所有這里所介紹的內(nèi)容都是受人關(guān)注的,并且我希望你(讀者)可以很
高興的讀著篇文章,就象我很高興寫一樣.
翻譯過程中難免有錯誤,不當(dāng)之處,請見諒. 譯者: arbiter
2001-2-8 22:41
Fnx go out to the beta-testers Douby/DREAD and Knotty Dread for the good
comments on my work which made it even better!
For a sample CRC-32 correcting patcher program visit my webpages:
http://surf.to/anarchriz -> Programming -> Projects
(it's still a preview but will give you a proof of my idea)
For more info on DREAD visit http://dread99.cjb.net
If you still have questions you can mail me at anarchriz@hotmail.com,
or try the channels #DreaD, #Win32asm, #C.I.A and #Cracking4Newbies (in that
order) on EFnet (on IRC).
CYA ALL! - Anarchriz
"The system makes its morons, then despises them for their ineptitude, and
rewards its 'gifted few' for their rarity." - Colin Ward
附錄:
CRC-16 Table
00h 0000 C0C1 C181 0140 C301 03C0 0280 C241
08h C601 06C0 0780 C741 0500 C5C1 C481 0440
10h CC01 0CC0 0D80 CD41 0F00 CFC1 CE81 0E40
18h 0A00 CAC1 CB81 0B40 C901 09C0 0880 C841
20h D801 18C0 1980 D941 1B00 DBC1 DA81 1A40
28h 1E00 DEC1 DF81 1F40 DD01 1DC0 1C80 DC41
30h 1400 D4C1 D581 1540 D701 17C0 1680 D641
38h D201 12C0 1380 D341 1100 D1C1 D081 1040
40h F001 30C0 3180 F141 3300 F3C1 F281 3240
48h 3600 F6C1 F781 3740 F501 35C0 3480 F441
50h 3C00 FCC1 FD81 3D40 FF01 3FC0 3E80 FE41
58h FA01 3AC0 3B80 FB41 3900 F9C1 F881 3840
60h 2800 E8C1 E981 2940 EB01 2BC0 2A80 EA41
68h EE01 2EC0 2F80 EF41 2D00 EDC1 EC81 2C40
70h E401 24C0 2580 E541 2700 E7C1 E681 2640
78h 2200 E2C1 E381 2340 E101 21C0 2080 E041
80h A001 60C0 6180 A141 6300 A3C1 A281 6240
88h 6600 A6C1 A781 6740 A501 65C0 6480 A441
90h 6C00 ACC1 AD81 6D40 AF01 6FC0 6E80 AE41
98h AA01 6AC0 6B80 AB41 6900 A9C1 A881 6840
A0h 7800 B8C1 B981 7940 BB01 7BC0 7A80 BA41
A8h BE01 7EC0 7F80 BF41 7D00 BDC1 BC81 7C40
B0h B401 74C0 7580 B541 7700 B7C1 B681 7640
B8h 7200 B2C1 B381 7340 B101 71C0 7080 B041
C0h 5000 90C1 9181 5140 9301 53C0 5280 9241
C8h 9601 56C0 5780 9741 5500 95C1 9481 5440
D0h 9C01 5CC0 5D80 9D41 5F00 9FC1 9E81 5E40
D8h 5A00 9AC1 9B81 5B40 9901 59C0 5880 9841
E0h 8801 48C0 4980 8941 4B00 8BC1 8A81 4A40
E8h 4E00 8EC1 8F81 4F40 8D01 4DC0 4C80 8C41
F0h 4400 84C1 8581 4540 8701 47C0 4680 8641
F8h 8201 42C0 4380 8341 4100 81C1 8081 4040
CRC-32 Table
00h 00000000 77073096 EE0E612C 990951BA
04h 076DC419 706AF48F E963A535 9E6495A3
08h 0EDB8832 79DCB8A4 E0D5E91E 97D2D988
0Ch 09B64C2B 7EB17CBD E7B82D07 90BF1D91
10h 1DB71064 6AB020F2 F3B97148 84BE41DE
14h 1ADAD47D 6DDDE4EB F4D4B551 83D385C7
18h 136C9856 646BA8C0 FD62F97A 8A65C9EC
1Ch 14015C4F 63066CD9 FA0F3D63 8D080DF5
20h 3B6E20C8 4C69105E D56041E4 A2677172
24h 3C03E4D1 4B04D447 D20D85FD A50AB56B
28h 35B5A8FA 42B2986C DBBBC9D6 ACBCF940
2Ch 32D86CE3 45DF5C75 DCD60DCF ABD13D59
30h 26D930AC 51DE003A C8D75180 BFD06116
34h 21B4F4B5 56B3C423 CFBA9599 B8BDA50F
38h 2802B89E 5F058808 C60CD9B2 B10BE924
3Ch 2F6F7C87 58684C11 C1611DAB B6662D3D
40h 76DC4190 01DB7106 98D220BC EFD5102A
44h 71B18589 06B6B51F 9FBFE4A5 E8B8D433
48h 7807C9A2 0F00F934 9609A88E E10E9818
4Ch 7F6A0DBB 086D3D2D 91646C97 E6635C01
50h 6B6B51F4 1C6C6162 856530D8 F262004E
54h 6C0695ED 1B01A57B 8208F4C1 F50FC457
58h 65B0D9C6 12B7E950 8BBEB8EA FCB9887C
5Ch 62DD1DDF 15DA2D49 8CD37CF3 FBD44C65
60h 4DB26158 3AB551CE A3BC0074 D4BB30E2
64h 4ADFA541 3DD895D7 A4D1C46D D3D6F4FB
68h 4369E96A 346ED9FC AD678846 DA60B8D0
6Ch 44042D73 33031DE5 AA0A4C5F DD0D7CC9
70h 5005713C 270241AA BE0B1010 C90C2086
74h 5768B525 206F85B3 B966D409 CE61E49F
78h 5EDEF90E 29D9C998 B0D09822 C7D7A8B4
7Ch 59B33D17 2EB40D81 B7BD5C3B C0BA6CAD
80h EDB88320 9ABFB3B6 03B6E20C 74B1D29A
84h EAD54739 9DD277AF 04DB2615 73DC1683
88h E3630B12 94643B84 0D6D6A3E 7A6A5AA8
8Ch E40ECF0B 9309FF9D 0A00AE27 7D079EB1
90h F00F9344 8708A3D2 1E01F268 6906C2FE
94h F762575D 806567CB 196C3671 6E6B06E7
98h FED41B76 89D32BE0 10DA7A5A 67DD4ACC
9Ch F9B9DF6F 8EBEEFF9 17B7BE43 60B08ED5
A0h D6D6A3E8 A1D1937E 38D8C2C4 4FDFF252
A4h D1BB67F1 A6BC5767 3FB506DD 48B2364B
A8h D80D2BDA AF0A1B4C 36034AF6 41047A60
ACh DF60EFC3 A867DF55 316E8EEF 4669BE79
B0h CB61B38C BC66831A 256FD2A0 5268E236
B4h CC0C7795 BB0B4703 220216B9 5505262F
B8h C5BA3BBE B2BD0B28 2BB45A92 5CB36A04
BCh C2D7FFA7 B5D0CF31 2CD99E8B 5BDEAE1D
C0h 9B64C2B0 EC63F226 756AA39C 026D930A
C4h 9C0906A9 EB0E363F 72076785 05005713
C8h 95BF4A82 E2B87A14 7BB12BAE 0CB61B38
CCh 92D28E9B E5D5BE0D 7CDCEFB7 0BDBDF21
D0h 86D3D2D4 F1D4E242 68DDB3F8 1FDA836E
D4h 81BE16CD F6B9265B 6FB077E1 18B74777
D8h 88085AE6 FF0F6A70 66063BCA 11010B5C
DCh 8F659EFF F862AE69 616BFFD3 166CCF45
E0h A00AE278 D70DD2EE 4E048354 3903B3C2
E4h A7672661 D06016F7 4969474D 3E6E77DB
E8h AED16A4A D9D65ADC 40DF0B66 37D83BF0
ECh A9BCAE53 DEBB9EC5 47B2CF7F 30B5FFE9
F0h BDBDF21C CABAC28A 53B39330 24B4A3A6
F4h BAD03605 CDD70693 54DE5729 23D967BF
F8h B3667A2E C4614AB8 5D681B02 2A6F2B94
FCh B40BBE37 C30C8EA1 5A05DF1B 2D02EF8D
CRC算法原理及C語言實現(xiàn)
對于RF通訊的通訊可靠性,有很強(qiáng)的檢錯能力的CRC.
這里列出了實際中8,16位單片機(jī)用到的CRC實用子程序.
1. 半字節(jié)16位CRC---halfBcal_crc
2.查表CRC---Bytecal_crc
3.位計算的CRC.----bitcal_crc
4.CRC檢錯的程序----IsCrc16
5.一個很不錯的CRC計算程序,--CRC16
同時本文列出了調(diào)用函數(shù)和例程
const code Ploy=0x1021;
#ifndef uchar
typedef unsigned char uchar;
#endif
#ifndef uint
typedef unsigned int uint;
#endif
static unsigned short crc; //16bit
unsigned int code crc_ta[16]={ /* CRC 半字節(jié)余式表 */ 0X0000,0X1021,0X2042, 0X3063, 0X4084, 0X50A5, 0X60C6, 0X70E7, 0X8108,0X9129,0XA14A,0XB16B,0XC18C,0XD1AD,0XE1CE,0XF1EF, };
unsigned int code crc_tab[256]={ /* CRC 余式表 */ 0X0000, 0X1021, 0X2042, 0X3063, 0X4084, 0X50A5, 0X60C6, 0X70E7, 0X8108, 0X9129, 0XA14A, 0XB16B, 0XC18C, 0XD1AD, 0XE1CE, 0XF1EF, 0X1231, 0X0210, 0X3273, 0X2252, 0X52B5, 0X4294, 0X72F7, 0X62D6, 0X9339, 0X8318, 0XB37B, 0XA35A, 0XD3BD, 0XC39C, 0XF3FF, 0XE3DE, 0X2462, 0X3443, 0X0420, 0X1401, 0X64E6, 0X74C7, 0X44A4, 0X5485, 0XA56A,0XB54B, 0X8528, 0X9509, 0XE5EE, 0XF5CF, 0XC5AC, 0XD58D, 0X3653, 0X2672, 0X1611, 0X0630, 0X76D7, 0X66F6, 0X5695, 0X46B4, 0XB75B,0XA77A, 0X9719, 0X8738, 0XF7DF, 0XE7FE, 0XD79D, 0XC7BC, 0X48C4,0X58E5, 0X6886, 0X78A7, 0X0840, 0X1861, 0X2802, 0X3823, 0XC9CC, 0XD9ED, 0XE98E, 0XF9AF, 0X8948, 0X9969, 0XA90A, 0XB92B, 0X5AF5, 0X4AD4, 0X7AB7, 0X6A96, 0X1A71, 0X0A50, 0X3A33, 0X2A12, 0XDBFD, 0XCBDC, 0XFBBF, 0XEB9E, 0X9B79, 0X8B58, 0XBB3B, 0XAB1A, 0X6CA6, 0X7C87, 0X4CE4, 0X5CC5, 0X2C22, 0X3C03, 0X0C60, 0X1C41, 0XEDAE, 0XFD8F, 0XCDEC, 0XDDCD, 0XAD2A, 0XBD0B, 0X8D68, 0X9D49, 0X7E97, 0X6EB6, 0X5ED5, 0X4EF4, 0X3E13, 0X2E32, 0X1E51, 0X0E70, 0XFF9F, 0XEFBE, 0XDFDD, 0XCFFC, 0XBF1B, 0XAF3A, 0X9F59, 0X8F78, 0X9188, 0X81A9, 0XB1CA, 0XA1EB, 0XD10C, 0XC12D, 0XF14E, 0XE16F, 0X1080, 0X00A1, 0X30C2, 0X20E3, 0X5004, 0X4025, 0X7046, 0X6067, 0X83B9, 0X9398, 0XA3FB, 0XB3DA, 0XC33D, 0XD31C, 0XE37F, 0XF35E, 0X02B1, 0X1290, 0X22F3, 0X32D2, 0X4235, 0X5214, 0X6277, 0X7256, 0XB5EA, 0XA5CB, 0X95A8, 0X8589, 0XF56E, 0XE54F, 0XD52C, 0XC50D, 0X34E2, 0X24C3, 0X14A0, 0X0481, 0X7466, 0X6447, 0X5424, 0X4405, 0XA7DB, 0XB7FA, 0X8799, 0X97B8, 0XE75F, 0XF77E, 0XC71D, 0XD73C, 0X26D3, 0X36F2, 0X0691, 0X16B0, 0X6657, 0X7676, 0X4615, 0X5634, 0XD94C, 0XC96D, 0XF90E, 0XE92F, 0X99C8, 0X89E9, 0XB98A, 0XA9AB, 0X5844, 0X4865, 0X7806, 0X6827, 0X18C0, 0X08E1, 0X3882, 0X28A3, 0XCB7D, 0XDB5C, 0XEB3F, 0XFB1E, 0X8BF9, 0X9BD8, 0XABBB, 0XBB9A, 0X4A75, 0X5A54, 0X6A37, 0X7A16, 0X0AF1, 0X1AD0, 0X2AB3, 0X3A92, 0XFD2E, 0XED0F, 0XDD6C, 0XCD4D, 0XBDAA, 0XAD8B, 0X9DE8, 0X8DC9, 0X7C26, 0X6C07, 0X5C64, 0X4C45, 0X3CA2, 0X2C83, 0X1CE0, 0X0CC1, 0XEF1F, 0XFF3E, 0XCF5D, 0XDF7C, 0XAF9B, 0XBFBA, 0X8FD9, 0X9FF8, 0X6E17, 0X7E36, 0X4E55, 0X5E74, 0X2E93, 0X3EB2, 0X0ED1, 0X1EF0 };
unsigned int halfBcal_crc(unsigned char *ptr, unsigned char len)
{
unsigned int crc;
unsigned char da;
crc=0;
while(len--!=0)
{
// da=((uchar)(crc/256))/16; /* 暫存CRC 的高四位 */
da=((unsigned char)(crc>>8))>>4;
crc<<=4; /* CRC 右移4 位，相當(dāng)于取CRC 的低12 位）*/
crc^=crc_ta[da^(*ptr/16)]; /* CRC 的高4 位和本字節(jié)的前半字節(jié)相加后查表計算CRC, 然后加上上一次CRC 的余數(shù) */
da=((unsigned char)(crc>>8))>>4; /* 暫存CRC 的高4 位 */
crc<<=4; /* CRC 右移4 位， 相當(dāng)于CRC 的低12 位） */
crc^=crc_ta[da^(*ptr&0x0f)]; /* CRC 的高4 位和本字節(jié)的后半字節(jié)相加后查表計算CRCＨ緩笤偌由仙弦淮蜟RC 的余數(shù) */
ptr++; }
return(crc);
}
unsigned int bitcal_crc(unsigned char *ptr, unsigned char len)
{ unsigned char i; unsigned int crc=0; while(len--!=0)
{
for(i=0x80; i!=0; i/=2)
{
if((crc&0x8000)!=0)
{
crc<<=1;
crc^=0x1021;
} /* 余式CRC 乘以2 再求CRC */
else crc<<=1;
if((*ptr&i)!=0) crc^=Ploy; /* 再加上本位的CRC */ }
ptr++;
}
return(crc);
}
unsigned int Bytecal_crc(unsigned char *ptr, unsigned char len)
{
unsigned int crc;
unsigned char da;
crc=0;
while(len--!=0)
{
da=(uchar) (crc/256); /* 以8 位二進(jìn)制數(shù)的形式暫存CRC 的高8 位 */
crc<<=8; /* 左移8 位，相當(dāng)于CRC 的低8 位乘以8 */
crc^=crc_tab[da^*ptr]; /* 高8 位和當(dāng)前字節(jié)相加后再查表求CRC ，再加上以前的CRC */
ptr++;
}
return(crc);
}
uchar IsCrc16(const uchar *pData,int len)
{ uint fcs;
fcs=0xffff;
while(len>0)
{
fcs = (fcs << 8)^ crc_tab[fcs^ (*pData)&0xff];
len--;
pData++;
}
return(!fcs);
}
unsigned char CRC16(unsigned char ser_data)
{ // Update the CRC for transmitted and received data using // the CCITT 16bit algorithm (X^16 + X^12 + X^5 + 1). crc = (unsigned char)(crc >> 8) | (crc << 8);
crc ^= ser_data;
crc ^= (unsigned char)(crc & 0xff) >> 4;
crc ^= (crc << 8) << 4; crc ^= ((crc & 0xff) << 4) << 1;
return 0;
}
unsigned short doCRC16( unsigned char *mstr,unsigned char len)
{
unsigned char ch;
crc = 0;
do{
ch = *mstr++;
CRC16(ch);
}while(--len);
return(crc);
}
CRC-16/CRC-32 程序代碼:
不久前寫一程序時要用到 CRC-16 ，但找來找去只在 UDDF 里找到一個 Delphi 的 CRC-32 程序代碼，而且是用查表法，雖然說查表法速度快，但 256 項 32 位數(shù)據(jù)我懷疑可能會有輸入錯誤， 讓人不是那么放心，而我又不知道這個表是怎么算出來的。后來我又在一本兩年前的筆記本里找到一段關(guān)于 CRC 的內(nèi)容， 也不知是從哪里抄來的，還好里面有一段程序代碼，是 CRC-16 的，這段程序正是產(chǎn)生 CRC 表的， 可是這區(qū)區(qū)幾行的程序（基本上與下面的 BuilderTable16 函數(shù)相同）看得我一頭霧水，直到這兩天才弄明白， 并據(jù)此推出 CRC-32 的算法，現(xiàn)將全部程序列在下面，并作一些說明以助于理解，不但要知其然，還要知其所以然嘛：
// 注意：因最高位一定為“1”，故略去
const unsigned short cnCRC_16 = 0x8005;
// CRC-16 = X16 + X15 + X2 + X0
const unsigned short cnCRC_CCITT = 0x1021;
// CRC-CCITT = X16 + X12 + X5 + X0，據(jù)說這個 16 位 CRC 多項式比上一個要好
const unsigned long cnCRC_32 = 0x04C10DB7;
// CRC-32 = X32 + X26 + X23 + X22 + X16 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X1 + X0
unsigned long Table_CRC[256]; // CRC 表
// 構(gòu)造 16 位 CRC 表
void BuildTable16( unsigned short aPoly )
{
unsigned short i, j;
unsigned short nData;
unsigned short nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned short )( i << 8 );
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0x8000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = ( unsigned long )nAccum;
}
}
// 計算 16 位 CRC 值，CRC-16 或 CRC-CCITT
unsigned short CRC_16( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned short nAccum = 0;
BuildTable16( cnCRC_16 ); // or cnCRC_CCITT
for ( i = 0; i < aSize; i++ )
nAccum = ( nAccum << 8 ) ^ ( unsigned short )Table_CRC[( nAccum >> 8 ) ^ *aData++];
return nAccum;
}
// 構(gòu)造 32 位 CRC 表
void BuildTable32( unsigned long aPoly )
{
unsigned long i, j;
unsigned long nData;
unsigned long nAccum;
for ( i = 0; i < 256; i++ )
{
nData = ( unsigned long )( i << 24 );
nAccum = 0;
for ( j = 0; j < 8; j++ )
{
if ( ( nData ^ nAccum ) & 0x80000000 )
nAccum = ( nAccum << 1 ) ^ aPoly;
else
nAccum <<= 1;
nData <<= 1;
}
Table_CRC[i] = nAccum;
}
}
// 計算 32 位 CRC-32 值
unsigned long CRC_32( unsigned char * aData, unsigned long aSize )
{
unsigned long i;
unsigned long nAccum = 0;
BuildTable32( cnCRC_32 );
for ( i = 0; i < aSize; i++ )
nAccum = ( nAccum << 8 ) ^ Table_CRC[( nAccum >> 24 ) ^ *aData++];
return nAccum;
}
說明： CRC 的計算原理如下（一個字節(jié)的簡單例子）
11011000 00000000 00000000 <- 一個字節(jié)數(shù)據(jù), 左移 16b
^10001000 00010000 1 <- CRC-CCITT 多項式, 17b
--------------------------
1010000 00010000 10 <- 中間余數(shù)
^1000100 00001000 01
-------------------------
10100 00011000 1100
^10001 00000010 0001
-----------------------
101 00011010 110100
^100 01000000 100001
---------------------
1 01011010 01010100
^1 00010000 00100001
-------------------
01001010 01110101 <- 16b CRC
仿此，可推出兩個字節(jié)數(shù)據(jù)計算如下：d 為數(shù)據(jù)，p 為項式，a 為余數(shù)
dddddddd dddddddd 00000000 00000000 <- 數(shù)據(jù) D ( D1, D0, 0, 0 )
^pppppppp pppppppp p <- 多項式 P
-----------------------------------
...
aaaaaaaa aaaaaaaa 0 <- 第一次的余數(shù) A'' ( A''1, A''0 )
^pppppppp pppppppp p
--------------------------
...
aaaaaaaa aaaaaaaa <- 結(jié)果 A ( A1, A0 )
由此與一字節(jié)的情況比較，將兩個字節(jié)分開計算如下：
先算高字節(jié)：
dddddddd 00000000 00000000 00000000 <- D1, 0, 0, 0
^pppppppp pppppppp p <- P
-----------------------------------
...
aaaaaaaa aaaaaaaa <- 高字節(jié)部分余數(shù) PHA1, PHA0
此處的部分余數(shù)與前面兩字節(jié)算法中的第一次余數(shù)有如下關(guān)系，即 A''1 = PHA1 ^ D0, A''0 = PHA0：
aaaaaaaa aaaaaaaa <- PHA1, PHA0
^dddddddd <- D0
-----------------
aaaaaaaa aaaaaaaa <- A''1, A''0
低字節(jié)的計算：
aaaaaaaa 00000000 00000000 <- A''1, 0, 0
^pppppppp pppppppp p <- P
--------------------------
...
aaaaaaaa aaaaaaaa <- 低字節(jié)部分余數(shù) PLA1, PLA0
^aaaaaaaa <- A''0 ， 即 PHA0
-----------------
aaaaaaaa aaaaaaaa <- 最后的 CRC ( A1, A0 )
總結(jié)以上內(nèi)容可得規(guī)律如下：
設(shè)部分余數(shù)函數(shù)
PA = f( d )
其中 d 為一個字節(jié)的數(shù)據(jù)（注意，除非 n = 0 ，否則就不是原始數(shù)據(jù)，見下文）
第 n 次的部分余數(shù)
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( d )
其中的
d = ( PA( n - 1 ) >> 8 ) ^ D( n )
其中的 D( n ) 才是一個字節(jié)的原始數(shù)據(jù)。
公式如下：
PA( n ) = ( PA( n - 1 ) << 8 ) ^ f( ( PA( n - 1 ) >> 8 ) ^ D( n ) )
可以注意到函數(shù) f( d ) 的參數(shù) d 為一個字節(jié)，對一個確定的多項式 P， f( d ) 的返回值
是與 d 一一對應(yīng)的，總數(shù)為 256 項，將這些數(shù)據(jù)預(yù)先算出保存在表里，f( d )就轉(zhuǎn)換為一
個查表的過程，速度也就可以大幅提高，這也就是查表法計算 CRC 的原理，在 CRC_16 和
CRC_32 兩個函數(shù)的循環(huán)中的語句便是上面那個公式。
再來看 CRC 表是如何計算出來的，即函數(shù) f( d ) 的實現(xiàn)方法。分析前面一個字節(jié)數(shù)據(jù)的
計算過程可發(fā)現(xiàn)，d 對結(jié)果的影響只表現(xiàn)為對 P 的移位異或，看計算過程中的三個 8 位
的列中只有低兩個字節(jié)的最后結(jié)果是余數(shù)，而數(shù)據(jù)所在的高 8 位列最后都被消去了，因其
中的運算均為異或，不產(chǎn)生進(jìn)位或借位，故每一位數(shù)據(jù)只影響本列的結(jié)果，即 d 并不直接
影響結(jié)果。再將前例變化一下重列如下：
11011000
--------------------------
10001000 00010000 1 // P
^ 1000100 00001000 01 // P
^ 000000 00000000 000 // 0
^ 10001 00000010 0001 // P
^ 0000 00000000 00000 // 0
^ 100 01000000 100001 // P
^ 00 00000000 0000000 // 0
^ 1 00010000 00100001 // P
-------------------
01001010 01110101
現(xiàn)在的問題就是如何根據(jù) d 來對 P 移位異或了，從上面的例子看，也可以理解為每步
移位，但根據(jù) d 決定中間余數(shù)是否與 P 異或。從前面原來的例子可以看出，決定的條
件是中間余數(shù)的最高位為0，因為 P 的最高位一定為1，即當(dāng)中間余數(shù)與 d 相應(yīng)位異或
的最高位為1時，中間余數(shù)移位就要和 P 異或，否則只需移位即可。具體做法見程序中
的 BuildTable16 和 BuildTable32 兩個函數(shù)，其方法如下例（上例的變形，注意其中
空格的移動表現(xiàn)了 d 的影響如何被排除在結(jié)果之外）：
d --------a--------
1 00000000 00000000 <- HSB = 1
0000000 000000000 <- a <<= 1
0001000 000100001 <- P, CRC-CCITT 不含最高位的 1
-----------------
1 0001000 000100001
001000 0001000010
000100 0000100001
-----------------
0 001100 0001100011 <- HSB = 0
01100 00011000110
-----------------
1 01100 00011000110 <- HSB = 1
1100 000110001100
0001 000000100001
-----------------
1 1101 000110101101 <- HSB = 0
101 0001101011010
-----------------
0 101 0001101011010 <- HSB = 1
01 00011010110100
00 01000000100001
-----------------
0 01 01011010010101 <- HSB = 0
1 010110100101010
-----------------
0 1 010110100101010 <- HSB = 1
0101101001010100
0001000000100001
-----------------
0100101001110101 <- CRC
結(jié)合這些，前面的程序就好理解了。至于 32 位 CRC 的計算與 16 相似，就不多加說明，請參考源程序。
AVR單片機(jī)CRC校驗碼的查表與直接生成
引 言：
隨著技術(shù)的不斷進(jìn)步，各種數(shù)據(jù)通信的應(yīng)用越來越廣泛。由于傳輸距離、現(xiàn)場狀況、干擾等諸多因素的影響，設(shè)備之間的通信數(shù)據(jù)常會發(fā)生一些無法預(yù)測的錯誤。為了降低錯誤所帶來的影響，一般在通信時采用數(shù)據(jù)校驗的辦法，而循環(huán)冗余碼校驗是常用的重要校驗方法之一。
AVR高速嵌入式單片機(jī)是8位RISC MCU，執(zhí)行大多數(shù)指令只需一個時鐘周期，速度快（8MHz AVR的運行速度約等于200MHz 80C51的運行速度），32個通用寄存器直接與ALU相連，消除了運算瓶頸；內(nèi)嵌可串行下載或自我編程的Flash和EPPROM，功能繁多，具有多種運行模式。
本文采用Atmel公司的Atmega128高速嵌入式單片機(jī)，依照IEEE 1999年公布的802.11無線局域網(wǎng)協(xié)議標(biāo)準(zhǔn)，采用32位循環(huán)冗余校驗碼（Cyclic Redundancy Check）實現(xiàn)無線傳輸數(shù)據(jù)時的差錯校驗。
1 CRC循環(huán)冗余校驗碼原理
1.1 數(shù)據(jù)傳輸?shù)膸袷?
根據(jù)IEEE制定的802.11無線局域網(wǎng)絡(luò)協(xié)議，在數(shù)據(jù)傳輸時都應(yīng)按照幀傳輸。這里，我們采用了信息處理系統(tǒng)－數(shù)據(jù)通信－高級數(shù)據(jù)鏈路控制規(guī)程－幀結(jié)構(gòu)，它的每個幀由下列字段組成（傳輸順序自左至右）：
地址——數(shù)據(jù)站地址字段；
控制——控制字段。
信息——信息字段；
CRC校驗位——根據(jù)前面三個字段生成的CRC校驗位。
由地址、控制、信息三個字段組成的總的字段統(tǒng)稱為數(shù)據(jù)段。
1.2 CRC校驗碼的理論生成方法
CRC校驗采用多項式編碼方法，被處理的數(shù)據(jù)塊可以看作是一個n階的二進(jìn)制多項式。這里，假定待發(fā)送的二進(jìn)制數(shù)據(jù)段為g(x)，生成多項式為 m(x)，得到的CRC校驗碼為c(x)。
CRC校驗碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)g(x)除以生成多項式m(x)，將最后的余數(shù)作為CRC校驗碼，實現(xiàn)步驟如下。
① 設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進(jìn)制多項式 g(x)，生成多項式為r階的m(x)。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m r位，對應(yīng)的二進(jìn)制多項式為G(x) 。
?、?nbsp;用生成多項式m(x)去除G(x) ，求得余數(shù)為階數(shù)是r-1的二進(jìn)制多項式c(x)。此二進(jìn)制多項式 c(x)就是g(x)經(jīng)過生成多項式m(x)編碼的CRC校驗碼。
?、?nbsp;用模2的方式減去c(x)，得到的二進(jìn)制多項式就是包含了CRC校驗碼的待發(fā)送字符串。
CRC校驗可以100%地檢測出所有奇數(shù)個隨機(jī)錯誤和長度小于等于r（r為m(x)的階數(shù)）的突發(fā)錯誤。所以，CRC的生成多項式的階數(shù)越高，誤判的概率就越小。CCITT建議：2048 Kb/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗碼生成多項式m(x)=x4 x 1 。采用16位CRC校驗，可以保證在 1014bit碼元中只含有1位未被檢測出的錯誤 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS中，使用CRC-16，其生成多項式m(x)=x16 x15 x2 1；而在CCITT推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗序列FCS中，使用CCITT-16，其生成多項式m(x)= x16 x15 x5 1。CRC-32的生成多項式m(x)=x32 x26 x23 x22 x16 x12 x11 x10 x8 x7 x5 x4 x2 x 1。CRC-32出錯的概率為CRC-16的10-5。由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計算機(jī)等領(lǐng)域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內(nèi)，都采用了CRC校驗碼進(jìn)行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進(jìn)行差錯控制。
m(x) 生成多項式的系數(shù)為0或1，但是m(x) 的首項系數(shù)為1，末項系數(shù)也必須為1。m(x) 的次數(shù)越高，其檢錯能力越強(qiáng)。
2 使用Atmega128生成32位CRC校驗碼
2.1 直接計算法生成32位CRC校驗碼
直接計算法就是依據(jù)CRC校驗碼的產(chǎn)生原理來設(shè)計程序。其優(yōu)點是模塊代碼少，修改靈活，可移植性好。這種算法簡單，容易實現(xiàn)，對任意長度生成多項式m(x) 都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用，但是如果發(fā)送的數(shù)據(jù)塊很長，這種方法就不太適合了。因為它1次只能處理1位數(shù)據(jù)，效率太低，運算量大。
計算法生成32位CRC校驗碼的流程如圖1所示。
用AVR單片機(jī)匯編語言實現(xiàn)CRC-32源程序見本刊網(wǎng)絡(luò)補充版（http://www.dpj.com.cn）。
2.2 查表法生成32位CRC校驗碼
和直接計算法相反，查表法生成32位CRC校驗碼的優(yōu)點是運算量小，速度快；缺點是可移植性較差。這種算法首先要求得到32位CRC生成表，由于1個字節(jié)有8位，所以這個表總共有256項。但是，由于AVR高速嵌入式單片機(jī)中的寄存器是以1個字節(jié)為單位的，所以在編程實現(xiàn)中，這個CRC生成表總共有1024項，分別從0~1023；每4位對應(yīng)1個32位CRC生成表的項，每一項都從高到低降冪排列。關(guān)于32位CRC生成表的程序詳見本刊網(wǎng)絡(luò)補充版（http://www.dpj.com.cn）。
查表法生成32位CRC校驗碼的流程如圖2所示。
圖2所示的流程圖中，在通過異或運算得到CRC生成表的索引時，由于AVR高速嵌入式單片機(jī)中的寄存器是以1個字節(jié)為單元的，所以在編程實現(xiàn)中應(yīng)根據(jù)所要求生成的CRC校驗碼的位數(shù)乘以相應(yīng)的系數(shù)。例如：在數(shù)據(jù)傳輸時要求32位CRC校驗碼，應(yīng)該把所得到的索引數(shù)乘以系數(shù)4，然后再從高到低依次取得32位CRC生成表單元中的內(nèi)容。
使用查表法得到32位CRC校驗碼的源程序詳見本刊網(wǎng)絡(luò)補充版（http://www.dpj.com.cn）。
3 實驗結(jié)果
為了比較所述兩種32位CRC校驗碼生成方法的特點，分別選取不同字節(jié)數(shù)的數(shù)據(jù)段，對兩種方法在不同情況下的效果進(jìn)行比較，如表1所列。
以上所有實驗結(jié)果均是在AVR Studio4仿真軟件上選用Atmel公司的Atmega128高速嵌入式單片機(jī)為實驗設(shè)備平臺，在12MHz運行速度下模擬所得。
在調(diào)用32位CRC生成表程序以得到32位CRC生成表時，耗時3968.33μs，執(zhí)行了47620個時鐘周期。從上述實驗結(jié)果可得出以下幾點結(jié)論。
?、?nbsp;如果不考慮生成32位CRC生成表的時間，例如直接把32位CRC生成表燒入到Atmega128的可編程閃速存儲器Flash中，由表1可清楚地看出，查表法的運行速度比直接計算法要快得多。因此，在類似情況下，在進(jìn)行數(shù)據(jù)傳輸要求生成32位CRC校驗碼時，應(yīng)該選擇查表法。
?、?nbsp;在某些應(yīng)用中，如果對硬件存儲器空間要求很高，并且在一定程度上對時間沒有特別高的要求時，可以采用直接計算法，以避免查表法中CRC生成表對存儲器空間的占用。
③ 雖然實驗結(jié)果對32位CRC校驗碼的兩種算法進(jìn)行了對比，但是所得到的結(jié)論也適用于8位、16位、24位CRC校驗碼。
結(jié) 語
CRC循環(huán)冗余校驗碼是一種方便、有效、快速的校驗方法，被廣泛應(yīng)用在許多實際工程中。文中所列的兩種算法——查表法和直接計算法，都可以得到CRC校驗碼；但是它們各有特點，在工程應(yīng)用中應(yīng)該根據(jù)實際需要選擇最適合的方法，以得到最優(yōu)的效果。
CRC校驗實用程序庫 - 計算機(jī)論文
在數(shù)據(jù)存儲和數(shù)據(jù)通訊領(lǐng)域，為了保證數(shù)據(jù)的正確，就不得不采用檢錯的手段。在諸多檢錯手段中，CRC是最著名的一種。CRC的全稱是循環(huán)冗余校驗，其特點是:檢錯能力極強(qiáng)，開銷小，易于用編碼器及檢測電路實現(xiàn)。從其檢錯能力來看，它所不能發(fā)現(xiàn)的錯誤的幾率僅為0.0047%以下。從性能上和開銷上考慮，均遠(yuǎn)遠(yuǎn)優(yōu)于奇偶校驗及算術(shù)和校驗等方式。因而，在數(shù)據(jù)存儲和數(shù)據(jù)通訊領(lǐng)域，CRC無處不在:著名的通訊協(xié)議X.25的FCS(幀檢錯序列)采用的是CRC-CCITT，ARJ、LHA等壓縮工具軟件采用的是CRC32，磁盤驅(qū)動器的讀寫采用了CRC16，通用的圖像存儲格式GIF、TIFF等也都用CRC作為檢錯手段。
CRC的本質(zhì)是模-2除法的余數(shù)，采用的除數(shù)不同，CRC的類型也就不一樣。通常，CRC的除數(shù)用生成多項式來表示。最常用的CRC碼的生成多項式如表1所示。
@@10A08800.GIF;表1.最常用的CRC碼及生成多項式@@
由于CRC在通訊和數(shù)據(jù)處理軟件中經(jīng)常采用，筆者在實際工作中對其算法進(jìn)行了研究和比較，總結(jié)并編寫了一個具有最高效率的CRC通用程序庫。該程序采用查表法計算CRC，在速度上優(yōu)于一般的直接模仿硬件的算法，可以應(yīng)用于通訊和數(shù)據(jù)壓縮程序。
通常的CRC算法在計算一個數(shù)據(jù)段的CRC值時，其CRC值是由求解每個數(shù)值的CRC值的和對CRC寄存器的值反復(fù)更新而得到的。這樣，求解CRC的速度較慢。通過對CRC算法的研究，我們發(fā)現(xiàn):一個8位數(shù)據(jù)加到16位累加器中去，只有累加器的高8位或低8位與數(shù)據(jù)相作用，其結(jié)果僅有256種可能的組合值。因而，我們可以用查表法來代替反復(fù)的運算，這也同樣適用于CRC32的計算。本文所提供的程序庫中，函數(shù)crchware是一般的16位CRC的算法；mk-crctbl用以在內(nèi)存中建立一個CRC數(shù)值表；crcupdate用以查表并更新CRC累加器的值；crcrevhware和crcrevupdate是反序算法的兩個函數(shù)；BuildCRCTable、CalculateBlockCRC32和UpdateCharac
terCRC32用于CRC32的計算。
/* CRC.C——CRC程序庫 */
#define CRCCCITT 0x1021
#define CCITT-REV 0x8408
#define CRC16 0x8005
#define CRC16-REV 0xA001
#define CRC32-POLYNOMIAL 0xEDB88320L
/* 以上為CRC除數(shù)的定義 */
#define NIL 0
#define crcupdate(d,a,t)*(a)=(*(a)<<8)^(t)[(*(a)>>8)^(d)];
#define crcupdate16(d,a,t)*(a)=(*(a)>>8^(t)[(*(a)^(d))0x00ff])
/* 以上兩個宏可以代替函數(shù)crcupdate和crcrevupdate */
#include
#include
#include
/* 函數(shù)crchware是傳統(tǒng)的CRC算法，其返回值即CRC值 */
unsigned short crchware(data,genpoly,accum)
unsigned short data;/* 輸入的數(shù)據(jù) */
unsigned short genpoly;/* CRC除數(shù) */
unsigned short accum;/* CRC累加器值 */
{
static int i;
data<<=8;
for(i=8;i>0;i--)
{
if((data^accum)0x8000)
accum=(accum<<1)^genpoly;
else
accum<<=1;
data<<=1;
}
return (accum);
}
/* 函數(shù)mk-crctbl利用函數(shù)crchware建立內(nèi)存中的CRC數(shù)值表 */
unsigned short *mk-crctbl(poly,crcfn);
unsigned short poly;/* CRC除數(shù)--CRC生成多項式 */
unsigned short (*crcfn)();/* 指向CRC函數(shù)(例如crchware)的指針 */
{
/* unsigned short */malloc(); */
unsigned short *crctp;
int i;
if((crctp=(unsigned short*)malloc(256*sizeof(unsigned)))==0)
return 0;
for(i=0;i<256;i++)
crctp[i]=(*crcfn)(i,poly,0);
return crctp;
}
/* 函數(shù)mk-crctbl的使用范例 */
if((crctblp=mk-crctbl(CRCCCITT,crchware))==NIL)
{
puts("insuff memory for CRC lookup table.\n");
return 1; */
/* 函數(shù)crcupdate用以用查表法計算CRC值并更新CRC累加器值 */
void crcupdate(data,accum,crctab)
unsigned short data;/* 輸入的數(shù)據(jù) */
unsigned short *accum;/* 指向CRC累加器的指針 */
unsigned short *crctab;/* 指向內(nèi)存中CRC表的指針 */
{
static short comb-val;
comb-val=(*accum>>8)^data;
*accum=(*accum<<8)^crctab[comb-val];
}
/* 函數(shù)crcrevhware是傳統(tǒng)的CRC算法的反序算法，其返回值即CRC值 */
unsigned short crcrevhware(data,genpoly,accum)
unsigned short data;
unsigned short genpoly;
unsigned short accum;
{
static int i;
data<<=1;
for(i=8;i>0;i--)
{
data>>=1;
if((data^accum)0x0001)
accum=(accum>>1)^genpoly;
else
accum>>=1;
}
return accum;
}
/* 函數(shù)crcrevupdate用以用反序查表法計算CRC值并更新CRC累加器值 */
void crcrevupdate(data,accum,crcrevtab)
unsigned short data;
unsigned short *accum;
循環(huán)冗余校驗 CRC的算法分析和程序?qū)崿F(xiàn)
摘要： 通信的目的是要把信息及時可靠地傳送給對方，因此要求一個通信系統(tǒng)傳輸消息必須可靠與快速，在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。為了解決可靠性，通信系統(tǒng)都采用了差錯控制。本文詳細(xì)介紹了循環(huán)冗余校驗CRC（Cyclic Redundancy Check）的差錯控制原理及其算法實現(xiàn)。
關(guān)鍵字 通信 循環(huán)冗余校驗 CRC-32 CRC-16 CRC-4
概述
在數(shù)字通信系統(tǒng)中可靠與快速往往是一對矛盾。若要求快速，則必然使得每個數(shù)據(jù)碼元所占地時間縮短、波形變窄、能量減少，從而在受到干擾后產(chǎn)生錯誤地可能性增加，傳送信息地可靠性下降。若是要求可靠，則使得傳送消息地速率變慢。因此，如何合理地解決可靠性也速度這一對矛盾，是正確設(shè)計一個通信系統(tǒng)地關(guān)鍵問題之一。為保證傳輸過程的正確性，需要對通信過程進(jìn)行差錯控制。差錯控制最常用的方法是自動請求重發(fā)方式（ARQ）、向前糾錯方式（FEC）和混合糾錯（HEC）。在傳輸過程誤碼率比較低時，用FEC方式比較理想。在傳輸過程誤碼率較高時，采用FEC容易出現(xiàn)“亂糾”現(xiàn)象。HEC方式則是ARQ和FEC的結(jié)合。在許多數(shù)字通信中，廣泛采用ARQ方式，此時的差錯控制只需要檢錯功能。實現(xiàn)檢錯功能的差錯控制方法很多，傳統(tǒng)的有：奇偶校驗、校驗和檢測、重復(fù)碼校驗、恒比碼校驗、行列冗余碼校驗等，這些方法都是增加數(shù)據(jù)的冗余量，將校驗碼和數(shù)據(jù)一起發(fā)送到接受端。接受端對接受到的數(shù)據(jù)進(jìn)行相同校驗，再將得到的校驗碼和接受到的校驗碼比較，如果二者一致則認(rèn)為傳輸正確。但這些方法都有各自的缺點，誤判的概率比較高。
循環(huán)冗余校驗CRC（Cyclic Redundancy Check）是由分組線性碼的分支而來，其主要應(yīng)用是二元碼組。編碼簡單且誤判概率很低，在通信系統(tǒng)中得到了廣泛的應(yīng)用。下面重點介紹了CRC校驗的原理及其 算法實現(xiàn)。
一、循環(huán)冗余校驗碼（CRC）
CRC校驗采用多項式編碼方法。被處理的數(shù)據(jù)塊可以看作是一個n階的二進(jìn)制多項式，由 。如一個8位二進(jìn)制數(shù)10110101可以表示為： 。多項式乘除法運算過程與普通代數(shù)多項式的乘除法相同。多項式的加減法運算以2為模，加減時不進(jìn)，錯位，和邏輯異或運算一致。
采用CRC校驗時，發(fā)送方和接收方用同一個生成多項式g（x）,并且g（x）的首位和最后一位的系數(shù)必須為1。CRC的處理方法是：發(fā)送方以g（x）去除t（x），得到余數(shù)作為CRC校驗碼。校驗時，以計算的校正結(jié)果是否為0為據(jù)，判斷數(shù)據(jù)幀是否出錯。
CRC校驗可以100％地檢測出所有奇數(shù)個隨機(jī)錯誤和長度小于等于k（k為g（x）的階數(shù)）的突發(fā)錯誤。所以CRC的生成多項式的階數(shù)越高，那么誤判的概率就越小。CCITT建議：2048 kbit/s的PCM基群設(shè)備采用CRC-4方案，使用的CRC校驗碼生成多項式g（x）= 。采用16位CRC校驗，可以保證在 bit碼元中只含有一位未被檢測出的錯誤 。在IBM的同步數(shù)據(jù)鏈路控制規(guī)程SDLC的幀校驗序列FCS中，使用CRC-16，其生成多項式g（x）= ；而在CCITT推薦的高級數(shù)據(jù)鏈路控制規(guī)程HDLC的幀校驗序列FCS中，使用CCITT-16，其生成多項式g（x）= 。CRC-32的生成多項式g（x）= 。CRC-32出錯的概率比CRC-16低 倍 。由于CRC-32的可靠性，把CRC-32用于重要數(shù)據(jù)傳輸十分合適，所以在通信、計算機(jī)等領(lǐng)域運用十分廣泛。在一些UART通信控制芯片（如MC6582、Intel8273和Z80-SIO）內(nèi)，都采用了CRC校驗碼進(jìn)行差錯控制；以太網(wǎng)卡芯片、MPEG解碼芯片中，也采用CRC-32進(jìn)行差錯控制。
二、CRC校驗碼的算法分析
CRC校驗碼的編碼方法是用待發(fā)送的二進(jìn)制數(shù)據(jù)t（x）除以生成多項式g（x），將最后的余數(shù)作為CRC校驗碼。其實現(xiàn)步驟如下：
（1） 設(shè)待發(fā)送的數(shù)據(jù)塊是m位的二進(jìn)制多項式t（x），生成多項式為r階的g（x）。在數(shù)據(jù)塊的末尾添加r個0，數(shù)據(jù)塊的長度增加到m+r位，對應(yīng)的二進(jìn)制多項式為 。
（2） 用生成多項式g（x）去除 ，求得余數(shù)為階數(shù)為r-1的二進(jìn)制多項式y(tǒng)（x）。此二進(jìn)制多項式y(tǒng)（x）就是t（x）經(jīng)過生成多項式g（x）編碼的CRC校驗碼。
（3） 用 以模2的方式減去y（x），得到二進(jìn)制多項式 。 就是包含了CRC校驗碼的待發(fā)送字符串。
從CRC的編碼規(guī)則可以看出，CRC編碼實際上是將代發(fā)送的m位二進(jìn)制多項式t（x）轉(zhuǎn)換成了可以被g（x）除盡的m+r位二進(jìn)制多項式 ，所以解碼時可以用接受到的數(shù)據(jù)去除g（x），如果余數(shù)位零，則表示傳輸過程沒有錯誤；如果余數(shù)不為零，則在傳輸過程中肯定存在錯誤。許多CRC的硬件解碼電路就是按這種方式進(jìn)行檢錯的。同時 可以看做是由t（x）和CRC校驗碼的組合，所以解碼時將接收到的二進(jìn)制數(shù)據(jù)去掉尾部的r位數(shù)據(jù)，得到的就是原始數(shù)據(jù)。
為了更清楚的了解CRC校驗碼的編碼過程，下面用一個簡單的例子來說明CRC校驗碼的編碼過程。由于CRC-32、CRC-16、CCITT和CRC-4的編碼過程基本一致，只有位數(shù)和生成多項式不一樣。為了敘述簡單，用一個CRC-4編碼的例子來說明CRC的編碼過程。
設(shè)待發(fā)送的數(shù)據(jù)t（x）為12位的二進(jìn)制數(shù)據(jù)100100011100；CRC-4的生成多項式為g（x）= ，階數(shù)r為4，即10011。首先在t（x）的末尾添加4個0構(gòu)成 ，數(shù)據(jù)塊就成了1001000111000000。然后用g（x）去除 ，不用管商是多少，只需要求得余數(shù)y（x）。下表為給出了除法過程。
除數(shù)次數(shù)
被除數(shù)/ g（x）/結(jié)果
余數(shù)
0
1 001000111000000
100111000000
1 0011
0 000100111000000
1
1 00111000000
1000000
1 0011
0 00001000000
2
1 000000
1100
1 0011
0 001100
從上面表中可以看出，CRC編碼實際上是一個循環(huán)移位的模2運算。對CRC-4，我們假設(shè)有一個5 bits的寄存器，通過反復(fù)的移位和進(jìn)行CRC的除法，那么最終該寄存器中的值去掉最高一位就是我們所要求的余數(shù)。所以可以將上述步驟用下面的流程描述：
//reg是一個5 bits的寄存器
把reg中的值置0.
把原始的數(shù)據(jù)后添加r個0.
While (數(shù)據(jù)未處理完)
Begin
If (reg首位是1)
reg = reg XOR 0011.
把reg中的值左移一位，讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。
End
reg的后四位就是我們所要求的余數(shù)。
這種算法簡單，容易實現(xiàn)，對任意長度生成多項式的G（x）都適用。在發(fā)送的數(shù)據(jù)不長的情況下可以使用。但是如果發(fā)送的數(shù)據(jù)塊很長的話，這種方法就不太適合了。它一次只能處理一位數(shù)據(jù)，效率太低。為了提高處理效率，可以一次處理4位、8位、16位、32位。由于處理器的結(jié)構(gòu)基本上都支持8位數(shù)據(jù)的處理，所以一次處理8位比較合適。
為了對優(yōu)化后的算法有一種直觀的了解，先將上面的算法換個角度理解一下。在上面例子中，可以將編碼過程看作如下過程：
由于最后只需要余數(shù)，所以我們只看后四位。構(gòu)造一個四位的寄存器reg，初值為0，數(shù)據(jù)依次移入reg0（reg的0位），同時reg3的數(shù)據(jù)移出reg。有上面的算法可以知道，只有當(dāng)移出的數(shù)據(jù)為1時，reg才和g（x）進(jìn)行XOR運算；移出的數(shù)據(jù)為0時，reg不與g（x）進(jìn)行XOR運算，相當(dāng)與和0000進(jìn)行XOR運算。就是說，reg和什么樣的數(shù)據(jù)進(jìn)行XOR移出的數(shù)據(jù)決定。由于只有一個bit，所以有 種選擇。上述算法可以描述如下，
//reg是一個4 bits的寄存器
初始化t[]={0011,0000}
把reg中的值置0.
把原始的數(shù)據(jù)后添加r個0.
While (數(shù)據(jù)未處理完)
Begin
把reg中的值左移一位，讀入一個新的數(shù)據(jù)并置于register的0 bit的位置。
reg = reg XOR t[移出的位]
End
上面算法是以bit為單位進(jìn)行處理的，可以將上述算法擴(kuò)展到8位，即以Byte為單位進(jìn)行處理，即CRC-32。構(gòu)造一個四個Byte的寄存器reg，初值為0x00000000，數(shù)據(jù)依次移入reg0（reg的0字節(jié)，以下類似），同時reg3的數(shù)據(jù)移出reg。用上面的算法類推可知，移出的數(shù)據(jù)字節(jié)決定reg和什么樣的數(shù)據(jù)進(jìn)行XOR。由于有8個bit，所以有 種選擇。上述算法可以描述如下：
//reg是一個4 Byte的寄存器
初始化t[]＝{…}//共有 ＝256項
把reg中的值置0.
把原始的數(shù)據(jù)后添加r/8個0字節(jié).
While (數(shù)據(jù)未處理完)
Begin
把reg中的值左移一個字節(jié)，讀入一個新的字節(jié)并置于reg的第0個byte<span sty
轉(zhuǎn)載自：http://www.yuanma.org/data/2006/1010/article_1637.htm
