iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 22
0
Security

無趣的密碼學,有趣的加密!系列 第 22

[Day 22] 022 - 雜湊 - Hash(番外)

雜湊 - Hash(番外) - CRC

接下來我想要來聊聊跟密碼學來說不是很相關,但我卻很想跟大家聊聊的一個校驗用的碼。

CRC原稱為:Cyclic redundancy check。

Hash來說都是把資料混亂化,以方便比對資料完整等,CRC也提供類似的功能,但CRC跟其他Hash來說更偏向『簡單』的比對。

而CRC是線性的變化,因此很簡單的可以偽造,一般是用來檢查錯誤的,『並不是』用來處理數據完整的。

簡單的CRC-1就是『奇偶校驗位』,雖然準度不精確但能檢查傳輸中奇數位元的loss(遺失)。

如果說那這樣不是依靠其他的Hash就可以代替,但CRC因為很簡單,能在接收訊息時就開始計算,很迅速地先排除傳輸出現的問題。

這樣就能減少資源的開銷,先排除錯誤。

那哪些協定用過CRC呢?

這問題很好,不如說很多大家都不知道,我簡單列一些重要的:

  • USB傳輸協定
  • Bus傳輸協定
  • Bluetooth(藍牙)傳輸協定
  • 乙太網路傳輸協定

也就是說其實很多很多協定都利用了CRC,等等我們會來說說CRC的算法和擴充。

那我們廢話不多說,來說說吧。


CRC 算法

CRC的算法其實不難懂,其實就是做『二進制除法』的動作。

利用多項式來表示如:x^5+x^3+x^1+1這樣的多項式來表示為鑰匙。

x^5+x^3+x^1+1 -> 101011(鑰匙)

然後在原資料中補『多項式的最高次方個0』。

假如資料為:10110110
補0後:10110110 00000

然後去做二進制除法(XOR):

除數:101011
被除數:1011011000000

開始除法:

    101101 1000000
    101011 0000000(做XOR)
    
    高位元做XOR後 ↓
    000110 1000000

位移高位元為0的值,變成如下:

除數:101011
被除數:1101000000

在做一次直到長度小於除數

除法第2次:
    110100 0000
    101011 0000(做XOR)

    高位元做XOR後 ↓
    011111 0000
 
    ------------

    111110 000
    101011 000(做XOR)

    高位元做XOR後 ↓

    010101 000

    ------------

    101010 00
    101011 00(做XOR)

    高位元做XOR後 ↓
    000001 00(長度短於除數101011)

我們得到了100這著二進制,然後把他加回補過0的資料裡。

原資料:10110110
補0後資料:10110110 00000
二進制除法完後的餘數:100
加入餘數資料:10110110 00100

最終資料:1011011000100

驗證的方法也很簡單,拿去把最終資料再做一次二進制除法,得到0就是正確。
要是不為0,資料表示有損毀或竄改。

這就是CRC的算法啦,接著大家可以去看WiKi的列表循環冗餘校驗

這邊有很多的多項式,可以嘗試做做看。


CRC 結論

到了這邊應該都能看得出來,如果要偽造的話很簡單。

但CRC同時也很快速,來確認資料是否傳輸正常。

所以CRC一直以來都是用來實體層傳輸的檢查碼。

而CRC跟密碼學的關係不是很重要就是了,但我覺得也算是密碼學的分支之一。

正確來說應該是編碼理論的範圍了。

所以這一篇也算是番外,希望大家能知道有這樣的東西,同時也能幫助大家處理一些除了密碼學之外的傳輸用Hash。

下一章是附錄,很精彩不要錯過~


作者的話

對不起這篇很水,剛爬完5天的山下來,太累了。

這邊寫稿還要看一堆訊息,一個不小心股票還沒注意到跌了蠻多的,從原本能賺1000元變成了10元……

好……不提傷心事,接下來希望能把文章水準提升回水平上。

CRC本來還想說說變體跟程式上的寫法,在WiKi上面有寫,就是『逆向使用』這件事。

我這邊就提出來,大家看一下WiKi來完整知識鍊。

希望明天能把文章寫的更好,也謝謝大家的觀看。


參考資料

循環冗餘校驗


上一篇
[Day 21] 021 - 雜湊 - Hash(三)
下一篇
[Day 23] 023 - 雜湊 - Hash(附錄)(密碼Hash,分享,非細節)(附:後端資訊安全常識)
系列文
無趣的密碼學,有趣的加密!30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言