Skip to main content

SHA1

· 5 min read
m9H8

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

初始值設定為

[
    [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 就是結果。