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