CRC檢查

CRC檢查

CRC,中文名稱為循環冗餘校驗,CRC屬於密碼學一類演演算法,常用於數據校驗,一般會用來檢測程序是否被脫殼或者被修改,以達到防破解的目的。

產生機制


CRC即循環冗餘校驗碼(Cyclic Redundancy Check):是數據通信領域中最常用的一種差錯校驗碼,其特徵是信息欄位和校驗欄位的長度可以任意選定。

基本原理


目錄詳細介紹代數學的一般性演演算法生成CRC碼的基本原理:任意一個由二進位位串組成的代碼都可以和一個係數僅為‘0’和‘1’取值的多項式一一對應。例如:代碼1010111對應的多項式為x6+x4+x2+x+1,而多項式為x5+x3+x2+x+1對應的代碼101111。

運作原則


CRC碼集選擇的原則:若設碼字長度為N,信息欄位為K位,校驗欄位為R位(N=K+R),則對於CRC碼集中的任一碼字,存在且僅存在一個R次多項式g(x),使得
;
其中: m(x)為K-1次信息多項式, r(x)為R-1次校驗多項式,
g(x)稱為生成多項式
發送方通過指定的g(x)產生CRC碼字,接收方則通過該g(x)來驗證收到的CRC碼字。

生成方法


CRC校驗碼軟體生成方法:
藉助於多項式除法,其餘數為校驗欄位。
例如:信息欄位代碼為:
;對應
假設生成多項式為:g(x)=x4+x3+1;則對應g(x)的代碼為: 1
對應的代碼記為:
採用多項式除法: 得餘數為: 1010 (即校驗欄位為:1010)
發送方:發出的傳輸欄位為:
信息欄位 校驗欄位
接收方:使用相同的生成碼進行校驗:接收到的欄位/生成碼(二進位除法)
如果能夠除盡,則正確,
給出餘數(1010)的計算步驟:
除法沒有數學上的含義,而是採用計算機的模二除法,即,除數和被除數做異或運算。進行異或運算時除數和被除數最高位對齊,按位異或。
利用CRC進行檢錯的過程可簡單描述為:在發送端根據要傳送的k位二進位碼序列,以一定的規則產生一個校驗用的r位監督碼(CRC碼),附在原始信息後邊,構成一個新的二進位碼序列數共k+r位,然後發送出去。在接收端,根據信息碼和CRC碼之間所遵循的規則進行檢驗,以確定傳送中是否出錯。這個規則,在差錯控制理論中稱為“生成多項式”。