數(shù)據(jù)校驗(yàn)是計(jì)算機(jī)發(fā)展至今的至關(guān)重要的部分。但是它一般作為底層、后臺(tái)或者內(nèi)置模塊出現(xiàn)，因而即使對(duì)于多數(shù)成天在計(jì)算機(jī)網(wǎng)絡(luò)里飄蕩的人來也說并不十分了解。前段時(shí)間由于特殊原因深入學(xué)習(xí)了一下MD5，后面接著學(xué)習(xí)了SHA-1和CRC32,我發(fā)覺網(wǎng)絡(luò)上的資料并不多，尤其是中文的資料大概就那么兩三個(gè)版本。小奀在這里根據(jù)我的學(xué)習(xí)體會(huì)整體的淺談（掃盲級(jí)/入門初級(jí)）一下這幾種在目前主要使用的數(shù)據(jù)校驗(yàn)算法，不當(dāng)之處請(qǐng)高人指正。
當(dāng)前最常用的三個(gè)數(shù)據(jù)校驗(yàn)算法CRC、MD5和SHA-1當(dāng)中，強(qiáng)度（這個(gè)強(qiáng)度是相對(duì)于被破解的困難程度來說的）以CRC最弱，而SHA-1最強(qiáng)。其實(shí)三個(gè)算法的原理和實(shí)現(xiàn)都很簡(jiǎn)單（CRC優(yōu)化的算法可能比較費(fèi)解），下面依次講起，并對(duì)各算法的當(dāng)前破解情況進(jìn)行了介紹，在相應(yīng)之處列有比較詳細(xì)的參考文檔。
CRC
CRC是什么？CRC的全稱是Cyclic Redundancy Checksum，即“循環(huán)冗余校驗(yàn)碼”。簡(jiǎn)單的說它是一種利用二進(jìn)制的多項(xiàng)式除法來取得數(shù)據(jù)的校驗(yàn)和的方法。
CRC有什么用？目前主要使用在哪些地方？一如其名，CRC對(duì)數(shù)據(jù)的處理結(jié)果是取得一個(gè)校驗(yàn)碼，在數(shù)據(jù)傳輸?shù)那昂蠓謩e計(jì)算一次，然后進(jìn)行比較就可以發(fā)現(xiàn)是否有錯(cuò)誤發(fā)生。打一個(gè)不是很恰當(dāng)?shù)谋确剑愠塑嚽皺z查了一下錢包，里面有N張RMB，下車的時(shí)候你再檢查一次，如果不是N張RMB的話你就會(huì)應(yīng)該意識(shí)到出問題了（不過這種情況下一般是會(huì)減少吧），但如果還是N張RMB的時(shí)候是否能保證沒有出問題了呢——很不幸，不一定，有可能被人家換了幾張小額的給你，或者換了假幣給你，這就類似于后邊要講到的“CRC碰撞”。CRC廣泛應(yīng)用于以太網(wǎng)的數(shù)據(jù)包檢查，PNG，以及我們常用的壓縮軟件（PKZIP， Zlib，WinRAR……）等。
CRC原理是什么？原理其實(shí)非常簡(jiǎn)單，就是二進(jìn)制的多項(xiàng)式除法。在后面的參考文檔里有不厭其煩的描述，當(dāng)需要更詳細(xì)的講解時(shí)建議你參考這些列出的文檔。在這里我只簡(jiǎn)單的說說我在學(xué)習(xí)過程中覺得比較重要的幾點(diǎn)：
1.這個(gè)二進(jìn)制除法的沒有優(yōu)化的偽代碼大概可以這樣寫（設(shè)除數(shù)有P個(gè)bits）：
{
任命余數(shù)r = 被除數(shù)的前(P-1)位;
while(被除數(shù)還有剩余bit沒有補(bǔ)入到r中)
{
補(bǔ)入一個(gè)bit到r中;
r = 補(bǔ)位后的r作為被除數(shù) 除以 除數(shù) 所得的余數(shù);
}
哈哈，這回完了吧。就是你了，拿起小r就可以跑了;
}
看看吧，是不是覺得很熟悉？的確，跟我們年輕時(shí)學(xué)過的一模一樣。
2.二進(jìn)制的多項(xiàng)式除法這個(gè)東東跟我們小學(xué)學(xué)過的普通的十進(jìn)制運(yùn)算沒有多大差別，簡(jiǎn)單的來說就是不考慮進(jìn)位退位就可以了，記住這個(gè)很重要。那么不夠減的時(shí)候怎么辦呢？直接把本來是0的位看作2就可以了。
3.二進(jìn)制的多項(xiàng)式除法運(yùn)算中，對(duì)于有T個(gè)bit位的被除數(shù)除以有P個(gè)bit位的除數(shù)，應(yīng)該除多少次才能得到余數(shù)呢？如果除數(shù)的高位為1時(shí)，應(yīng)該做(T +1-P)次運(yùn)算（如果T+1<P，那么為0次）。有的人可能會(huì)反駁說CRC的實(shí)作代碼中是（T-P）次，其實(shí)問題在于那里使用的除數(shù)是把最高位去掉了的。
4.關(guān)于除數(shù)多項(xiàng)式Poly（以下簡(jiǎn)稱Poly）。我曾經(jīng)看過一篇中文文檔中說，“不要問我為什么Poly的最高位和最低位都是 1，因?yàn)檫@是規(guī)定”。規(guī)定當(dāng)然是規(guī)定，但是做出這種規(guī)定也應(yīng)當(dāng)是有原因的吧？根據(jù)我的個(gè)人理解（當(dāng)然，也許這是錯(cuò)誤的理解），首先最高位必須為1，這個(gè) bit位在英文文檔中稱為"Active" bit，為什么呢？如果Poly最高位不是1那么除法無法進(jìn)行下去而得到有我們所需要的位數(shù)的余數(shù)（當(dāng)Poly最高位為0而被除數(shù)高位為1時(shí)無法抵消）。而低位為什么也必須為1呢？在有的使用場(chǎng)合是把CRC的Poly和被除數(shù)都做了反射之后再進(jìn)行的，這種情況下低位反射成了高位，基于前面同樣的理由，所以必須保持最低位也為1。
5.關(guān)于查表算法，查表法的主要目的是提高運(yùn)算速度。下面以最常用的CRC32為例。查表法的方案也不同，最長采用的是按照字節(jié)（8位）生成碼表。這里對(duì)應(yīng)前面所述的最原始的除法方案進(jìn)行講述，即沒有反射，并把字節(jié)中的高位作為被除數(shù)的高位。
對(duì)于喜歡證明結(jié)論的人，或者可以按照如下的思路進(jìn)行：
在進(jìn)行除法的過程中，當(dāng)寄存器移出一個(gè)字節(jié)的時(shí)候，最終對(duì)余數(shù)的影響相當(dāng)于其后的四個(gè)字節(jié)異或上某一個(gè)值（設(shè)這個(gè)值為y），設(shè)移出值為x時(shí)對(duì)應(yīng)的y為f (x)，那么這個(gè)f映射是一個(gè)雙射，這很容易證明。因?yàn)檫@個(gè)映射是一系列異或操作的疊加，而異或運(yùn)算滿足交換律和結(jié)合律。那么當(dāng)y后面的四個(gè)字節(jié)全為0 時(shí)，可以推出余數(shù)值為：r = y^0 = f(x)^0 = f(x)。利用這個(gè)關(guān)系，對(duì)每個(gè)x值算出對(duì)應(yīng)的r，并記錄在以x值為下標(biāo)的數(shù)組中，就得到了f映射在x定義域上的所有值。而這個(gè)數(shù)組就是查表法所使用的碼表。
顯然，這個(gè)f映射是提高效率的關(guān)鍵，它相當(dāng)于有“預(yù)見性”的進(jìn)行一個(gè)字節(jié)的除法運(yùn)算。當(dāng)然也很容易想到可以有其他位數(shù)的查表算法，比如16位、32位等。而且如果你了解了以上的算法，你應(yīng)該可以想到兩點(diǎn)（以16位為例）：前面256個(gè)元素和8位的應(yīng)該完全一致；16位的碼表可以通過類似的按照位進(jìn)行運(yùn)算的方法得到，同樣也可以對(duì)8位的已經(jīng)運(yùn)算出的碼表進(jìn)行運(yùn)算得到，把一個(gè)字節(jié)看成一個(gè)“位”就行。
CRC的碰撞是什么東東？怎么產(chǎn)生的？CRC“碰撞”實(shí)際上是不同的源數(shù)據(jù)可能對(duì)應(yīng)同一個(gè)CRC值的沖突現(xiàn)象。根據(jù)前面的討論，可以把CRC看成一個(gè)從無限定義域映射到2的 32次方空間的一個(gè)單向函數(shù)，很明顯這個(gè)映射是“多對(duì)一”的。這種現(xiàn)象類似于中國目前的男女比率失調(diào)狀況，根據(jù)某甲某乙們預(yù)計(jì)的結(jié)果，到2020年，中國會(huì)有幾千萬的男光棍出現(xiàn)——為啥乜？其實(shí)簡(jiǎn)單的說就是供映射的目標(biāo)空間不夠大，在這種情況下如果保證每個(gè)人都不做光棍的話，那么除了從外國（當(dāng)然也可以是外星球）大力引進(jìn)適齡女子外，就只能多男共事一妻了^_^（各位兄弟們，你今天汗了嗎？）。
CRC被破解了么？是的。實(shí)際上要從CRC結(jié)果逆向找回?cái)?shù)據(jù)源幾乎是不可行的，因?yàn)檫@是個(gè)一對(duì)多的映射，因此所謂的“破解”一般指找到一個(gè)產(chǎn)生相同CRC結(jié)果的數(shù)據(jù)，但無法判斷這個(gè)找到的數(shù)據(jù)和源數(shù)據(jù)的異同（除非有上下文等信息）。CRC是一個(gè)相對(duì)簡(jiǎn)單的數(shù)據(jù)校驗(yàn)算法，從理論上我們得知只要提供比映射的目標(biāo)空間的值的個(gè)數(shù)（CRC32是2的32次方個(gè)）更多的互不相同的源數(shù)據(jù)時(shí)，就一定會(huì)出現(xiàn)CRC碰撞。實(shí)際上破解CRC是有規(guī)可循的，看雪論壇上有一篇文章做了理論推導(dǎo)并提供了程序下載，有興趣的請(qǐng)參考后面列出的參考文檔。
CRC 參考文檔
1. CRC圣經(jīng)（注：這是我所找到的一份最全的英文文檔，很多其他的英文文檔以及幾乎目前的所有中文文檔都是這份文檔的衍生品，我稱其為“CRC圣經(jīng)”實(shí)在是一點(diǎn)都不為過）
2. CSDN文章（這是CSDN上選自http://blog.csdn.net/chensheng913/ 的文章，基本上是CRC圣經(jīng)的節(jié)選翻譯＋讀書筆記）
3. 老羅的繽紛天地：原理篇＋實(shí)踐篇（注：老羅其實(shí)沒有老，文章非常好:-)，這里另外還有匯編代碼）
4. RFC3309 中的講述
5. PNG中用到的CRC的實(shí)作代碼
6. Koders上的實(shí)作代碼（注：在此MHASH模塊中包含了CRC和本文中另外所提到的MD5和SHA-1，非常值得一看）
7. 看雪論壇上的破解文章
源地址未知。