This page looks best with JavaScript enabled

SHA1

 · 

SHA-1 是一種 SHA (Secure Hash Algorithm),SHA 是被美國聯邦政府所訂製的標準認證過的 Hash function,目前常被使用的有 SHA-1,像是 git 產生 commit 編號就是,檢查檔案是否完整或被竄改除了使用 md5 也常用 SHA-1,但目前有發現破解方式已經不夠安全。因此傳送機密資料已漸漸不使用 SHA-1 ,通常會選擇 SHA-2 系列,常見的像是比特幣也使用的 SHA-256 (SHA-2 的一種,輸出長度為 256),另外還有與 SHA-1、SHA-2 運算方式不同的 SHA-3 系列。

SHA-1 演算法

以下為 SHA1 演算法的過程,使用位元的角度簡介

參考資料: http://cwcserv.ucsd.edu/~billlin/classes/ECE111/SHA1-Javinen.pdf

將原始資料 (message) 後補 (append bits) 滿,直到長度變成 512 的倍數

此步驟會補上三種東西

  1. 補上一個 1
  2. 補上 k 個 0,直到目前的長度除以 512 餘 448
    目前長度: len(message)+1
    所以 k 為 (448+512-(len(message)+1)) % 512
  3. 補上原始 message 的長度,以 64 位表示,超過取低位。 (512 - 64 = 448 所以上一步以此反推)

設定初始值

hash_value = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0

初始值設定為

1
2
3
4
5
6
7
[
    [0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1],
    [1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0],
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0],
    [1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0]
]

長度為 160 bit,分成 5 組 x 32bit ,以十六進制表示: 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0。

每 512 bit 稱作一份 block,每個 block 內部執行相同動作

block_size = 512

block 內部運算

設定 block 內部 的初始值

在每個 block 開始運算時,無論現在 hash_value 為何,block 內部的初始值 都設定為 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0,放在 a, b, c, d, e 5 個變數。

生成 word 直到 80 個

word_size = 32

一個 block 有 512 bit 的資料,每 32 bit 切成一個 word,共有 16 個 word。

每個 word 長 32 bit,目前有 16 個 word,以 w[0] ~ w[15] 表示。

rounds = 80

主要運算要做 80 次,每一次都會用到一個 word,故先將 word 從 16 個變成 80 個

w[16] ~ w[79]的產生方式:

w[i] = ( w[i-3] xor w[i-8] xor w[i-14] xor w[i-16] ) leftrotate 1

運算

處理 80 次計算。每 20 次的算法稍有不同,不過計算圍繞在對 a, b, c, d, e 5 個變數做複雜計算,不斷更新他們。

計算包含以下動作:

  1. 5 個變數交換
  2. left rotation
  3. 相加
  4. or 運算
  5. and 運算
  6. xor 運算
  7. not 運算

累加 block 內部計算結果

經過 80 次的運算後 將目前的 5 個變數 a, b, c, d, e ,也就是 block 內部計算結果,加到 hash_value,然後再進行下一個 block 的計算,算完時的 hash_value 就是結果。