CRC

簡介

循環冗餘校驗（Cyclic redundancy check） 通稱CRC。是一種根據網絡數據包或計算機文件等數據產生簡短固定位數校驗碼的一種散列函數，主要用來檢測或校驗數據傳輸或者保存後可能出現的錯誤。生成的數字在傳輸或者存儲之前計算出來並且附加到數據後面，然後接收方進行檢驗確定數據是否發生變化。一般來説，循環冗餘校驗的值都是32位的整數。由於本函數易於用二進制的計算機硬件使用、容易進行數學分析並且尤其善於檢測傳輸通道干擾引起的錯誤，因此獲得廣泛應用

CRC與數據完整性

儘管在錯誤檢測中非常有用，CRC並不能可靠地校驗數據完整性（即數據沒有發生任何變化），這是因為CRC多項式是線性結構，可以非常容易地故意改變量據而維持CRC不變。

CRC發生碰撞的情況

與所有其它的散列函數一樣，在一定次數的碰撞測試之後CRC也會接近100%出現碰撞。CRC中每增加一個數據位，碰撞機率就會減少接近50%，如CRC-20與CRC-21相比。

  • 理論上來講，CRC64的碰撞概率大約是每18×1018個CRC碼出現一次。
  • 由於CRC的不分解多項式特性，所以經過合理設計的較少位數的CRC可能會與使用較多數據位但是設計很差的CRC的效率相媲美。在這種情況下CRC-32幾乎同CRC-40一樣優秀。

CRC是Hash嗎？

Hash是把任意長度數據往固定長度數據上的一種映射，所以基於此概念，CRC也是Hash的一種。

CRC與其它算法的區別

相同點：

  • CRC、MD5、SHA1 都是通過對數據進行計算，來生成一個校驗值，該校驗值用來校驗數據的完整性。

不同點：

  • 算法不同。CRC32採用多項式除法，MD5和SHA1使用的是替換，輪轉方法。
  • 校驗值長度不同。CRC校驗位的長度跟其多項式有關係，一般為16或32位。MD5是16字節（128位）。SHA1是20字節（160位）。
  • 校驗值稱呼不同。CRC一般叫做CRC值。MD5和SHA1一般叫做哈希值（hash）或散列值。
  • 安全性不同。MD5與SHA1的區安全性比CRC高。
  • 效率不同。CRC計算效率高。
  • 用途不同。CRC一般用作通信數據的校驗。MD5和SHA1用於安全領域。