淺析CRC32加密算法
cc CRC全稱為Cyclic Redundancy Check，又叫循環(huán)冗余校驗。CRC是目前使用中最老的一種校驗算法，它是由W. Wesley Peterson在1961年發(fā)表的論文中提出，CRC是種根據(jù)網(wǎng)絡(luò)數(shù)據(jù)封包或電腦檔案等數(shù)據(jù)產(chǎn)生簡短固定位數(shù)校驗碼的一種散列函數(shù)（HASH，把任意長度的輸入通過散列算法，最終變換成固定長度的摘要輸出，其結(jié)果就是散列值，按照HASH算法，HASH具有單向性，不可逆性），主要用來檢測或校驗數(shù)據(jù)傳輸或者保存后可能出現(xiàn)的錯誤。生成的數(shù)字在傳輸或者儲存之前計算出來并且附加到數(shù)據(jù)后面，然后接收方進行檢驗確定數(shù)據(jù)是否發(fā)生變化。一般來說，循環(huán)冗余校驗的值都是32位的整數(shù)。由于本函數(shù)易于用二進制的電腦硬件使用、容易進行數(shù)學(xué)分析并且尤其善于檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應(yīng)用。
一、基本原理
CRC檢驗原理實際上就是在一個p位二進制數(shù)據(jù)序列之后附加一個r位二進制檢驗碼(序列)，從而構(gòu)成一個總長為n＝p＋r位的二進制序列；附加在數(shù)據(jù)序列之后的這個檢驗碼與數(shù)據(jù)序列的內(nèi)容之間存在著某種特定的關(guān)系。如果因干擾等原因使數(shù)據(jù)序列中的某一位或某些位發(fā)生錯誤，這種特定關(guān)系就會被破壞。因此，通過檢查這一關(guān)系，就可以實現(xiàn)對數(shù)據(jù)正確性的檢驗。
二、幾個基本概念
1、幀檢驗序列FCS（Frame Check Sequence）：為了進行差錯檢驗而添加的冗余碼。
2、多項式模2運行：實際上是按位異或(Exclusive OR)運算，即相同為0，相異為1，也就是不考慮進位、借位的二進制加減運算。如：10011011 + 11001010 = 01010001。
3、生成多項式（generator polynomial）：當(dāng)進行CRC檢驗時，發(fā)送方與接收方需要事先約定一個除數(shù)，即生成多項式，一般記作G（x）。生成多項式的最高位與最低位必須是1。常用的CRC碼的生成多項式有：
CRC8=X8+X5+X4+1
CRC-CCITT=X16+X12+X5+1
CRC16=X16+X15+X5+1
CRC12=X12+X11+X3+X2+1
CRC32=X32+X26+X23+X22+X16+X12+X11+X10+X8+X7+X5+X4+X2+X1+1
每一個生成多項式都可以與一個代碼相對應(yīng)，如CRC8對應(yīng)代碼：100110001。
三、CRC檢驗碼的計算
設(shè)信息字段為K位，校驗字段為R位，則碼字長度為N(N=K+R)。設(shè)雙方事先約定了一個R次多項式g(x)，則CRC碼：
V(x)=A(x)g(x)=xRm(x)+r(x)
其中: m(x)為K次信息多項式， r(x)為R-1次校驗多項式。
這里r(x)對應(yīng)的代碼即為冗余碼，加在原信息字段后即形成CRC碼。
r(x)的計算方法為：在K位信息字段的后面添加R個0，再除以g(x)對應(yīng)的代碼序列，得到的余數(shù)即為r(x)對應(yīng)的代碼(應(yīng)為R－1位；若不足，而在高位補0)。
四、錯誤檢測
當(dāng)接收方收到數(shù)據(jù)后，用收到的數(shù)據(jù)對P（事先約定的）進行模2除法，若余數(shù)為0，則認為數(shù)據(jù)傳輸無差錯；若余數(shù)不為0，則認為數(shù)據(jù)傳輸出現(xiàn)了錯誤，由于不知道錯誤發(fā)生在什么地方，因而不能進行自動糾正，一般的做法是丟棄接收的數(shù)據(jù)。
五、幾點說明：
1、CRC是一種常用的檢錯碼，并不能用于自動糾錯。
2、只要經(jīng)過嚴格的挑選，并使用位數(shù)足夠多的除數(shù) P，那么出現(xiàn)檢測不到的差錯的概率就很小很小。
3、僅用循環(huán)冗余檢驗 CRC 差錯檢測技術(shù)只能做到無差錯接受（只是非常近似的認為是無差錯的），并不能保證可靠傳輸。
CRC32有如下幾個特征：
1. 一張靜態(tài)的CRC32表或者動態(tài)生成一張CRC32的表，表的元素個數(shù)為256，元素大小為4字節(jié)
2. 在計算CRC32時，會進行查表操作，然后異或上一次CRC32的結(jié)果右移8位
3. 最終生成8字節(jié)CRC32值
