手把手做雜湊 (Hash): SHA-1 (Secure Hash Algorithm 1)

前言

這篇對於非宅宅的讀者來說會偏硬。
主要是搬移舊文的一部分，也順便更新了內容；不過篇幅比較長，就沒有放在整併一些 2021-2024 技術筆記 / snippets 中。

雜湊 (Hash) 是什麼？

Hash 就是將一個任意長度的字串轉成一串字串，而且轉換過的數字是一個固定的長度。同時還有幾項比較重要的性質：

你無法從這個數字反推回去原來的字串，換言之，是一個單向的函數。
一樣的字串轉換後一定還是一樣的數字
一個好的 hash 方法應該要降低碰撞 (Collision) 的機會，也就是說，我丟我的字串、跟你丟的字串，經過這個方法 Hash 過後，理論上要得到一樣的數字的機會極低。

舉例來說，test 經過 SHA-1 轉換後，會得到：

a94a8fe5ccb19ba61c4c0873d391e987982fbbd3

你在各個使用 SHA-1 的網站上輸入 test，都可以得到一樣結果。

如果不小心寫成 TEST，則會產生截然不同的數字：

984816fd329622876e14907634264e6f332e9fb

雜湊可以用來做什麼

這種東西乍聽之下都沒什麼用，但其實大有用處。舉凡作為資料儲存的索引、密碼儲存、證明訊息沒有被竄改過等。可以想像他有點類似製作這段字串的「指紋」的概念：同樣字串就只會產生同樣的結果。

從上面的結果可以看到，雜湊過的內容都是一段數字 (16 進位)。所以其中一種應用是，我們可以用這個方式初步對「所有字串」資料分組，任意字串丟進來的第一個數字總是 0 ~ f，根據這個數字就初步完成了所有資料的分組了，而且同樣的資料肯定會在同一組。

另一個常用的概念是儲存密碼。一般情況資料庫不能儲存 user 的密碼，否則要是被駭客攻擊流出密碼，所有 user 都會遭殃。可以想像要是在資料庫中只儲存 user 雜湊過的密碼^[1]，仍然可以完成驗證，而且就算被破解仍然無法回推正確的原始密碼。

最後是如果你有在網路上下載過東西，有些網頁會附上 sha 相關的內容，目的是讓你比對兩個雜湊值是否相同，用非常簡單的方式來檢驗你下載下來的這包東西，跟原始來源是否完全一致。

SHA-1?

常見的雜湊函數有非常多種。現在 SHA-1 已經不再安全了，不過出於好奇以及這麼方式相對其他做法來說單純一點，所以本篇挑這個紀錄運算的流程。

手把手做 Hash，步驟如下

接收一個字串、並將它轉換成二進位數字
調整一下這串數字，補上 1、補上一些 0、再補上輸入字串長度
把這一串數字切成 (Chunk) 16 組 word (每組 word 是 32 bit)
延展成 80 組 word
主要迴圈 (不同組別不同處理，混合常數打散之後合併)
再合併，最後將得到的數字轉成 16 進位輸出

Step 1: 接收字串轉成二進位

假設接收的字串是 “A Test"，共 6 個字元 (含空白)：

A (space) T e s t

對照 ASCII 上的編碼，會得到對應這些字元的 6 個數字：

65 32 84 101 115 116

然後各自轉成 8-bit 二進位數字：

01000001  00100000  01010100  01100101  01110011   01110100

於是得到一個 48 bit 的數字，第一個步驟就完成了。

Step 2: 調整一下數字

這邊會小複雜。

(1) 先補 1

把剛才得到的數字後面補上一個 ‘1’，得到 49 bit 的數字：

01000001 00100000 01010100 01100101 01110011 01110100 1
                                                      ^

(2) 再補 0

接下來是補 0，補 0 的動作比較複雜：

因為在本步驟的最後會再補上 64 bits
而目標是總共要湊成 512 bits 的整數倍

因此以目前只有 49 bits 的情況下，需要再補上：

(512 – 64 – 49) = 399 bits

因此要再補上 399 個 0 來湊成 512 bits：

0100000100100000010101000110010101110011011101001 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

如果我一開始輸入的字串有 56 字元，每個字元 8 bit，在第一步會得到 448 bit；剛才補上 1 的時候變成 449 bit，因此要補上：

(512 – 64 – 449) = -1 bit！(要湊 512 bit 居然多了 1 個 bit)

意即，目前有 449 bit 加等下補上的 64 bit 共 513 bit，因此要再加上 511 bit (-1 + 512) 變成 1024 bit，才會是 512 的整數倍。

寫成數學式的話，就是要求補上 x bit 可以使總數為 512 bit 的整數倍，x 則需要滿足：

x ≡ 448 mod 512

(3) 最後補 64 bits 的長度

第二步的最後，補上 64 bits 的「你輸入字串的『長度』」，以 A Test 來說是 6，也就是把 6 以二進位表示、用 64 bits 紀錄：

0000000000000000000000000000000000000000000000000000000000110000

最後終於得到 512 bits：

0100000100100000010101000110010101110011011101001

000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

0000000000000000000000000000000000000000000000000000000000110000

幫忙換行方便理解：這三段數字主要就是原始資料、補零、補上長度，實際操作時是黏在一起的。

Step 3: 切成 (Chunk) 16 組 word

第三步最簡單！

將剛才 512 bits 切成 16 組、每組 32 bits 的 word。

 0: 01000001001000000101010001100101
 1: 01110011011101001000000000000000
 2: 00000000000000000000000000000000
 3: 00000000000000000000000000000000
 4: 00000000000000000000000000000000
 5: 00000000000000000000000000000000
 6: 00000000000000000000000000000000
 7: 00000000000000000000000000000000
 8: 00000000000000000000000000000000
 9: 00000000000000000000000000000000
10: 00000000000000000000000000000000
11: 00000000000000000000000000000000
12: 00000000000000000000000000000000
13: 00000000000000000000000000000000
14: 00000000000000000000000000000000
15: 00000000000000000000000000110000

Step 4: 展開成 80 組 word

抱歉，簡單的部分沒了，接下來都會偏複雜。

這個步驟的目標是把 16 組資料展開成 80 組的 word。

怎麼做呢？由以下迴圈達成：

在這個步驟設定一個變數 i ，它將從 16 增長到 79，
同時第 i+1 組 (編號 i) word 會由 [i-3], [i-8], [i-14], [i-16] 分別做 XOR 再 Left Rotate 產生。

我知道沒有人看得懂，舉例來說是這樣：

根據前面的結果，我們手上只有 16 組數字
現在要製造成 80 組，肯定要用某種方式算出來
根據上面的說明，第 17 組數字就是當 i = 16 時產生的

也就是第 17 組數字會由

# 現在 i = 16

i-3     = 13
i-8     =  8
i-14    =  2
i-16    =  0

第 13, 8, 2, 0 組的數字分別做 XOR 再 Left Rotate 產生：

 0: 01000001001000000101010001100101 <-- #4
 1: 01110011011101001000000000000000
 2: 00000000000000000000000000000000 <-- #3
 3: 00000000000000000000000000000000
 4: 00000000000000000000000000000000
 5: 00000000000000000000000000000000
 6: 00000000000000000000000000000000
 7: 00000000000000000000000000000000
 8: 00000000000000000000000000000000 <-- #2
 9: 00000000000000000000000000000000
10: 00000000000000000000000000000000
11: 00000000000000000000000000000000
12: 00000000000000000000000000000000
13: 00000000000000000000000000000000 <-- #1
14: 00000000000000000000000000000000
15: 00000000000000000000000000110000

XOR

我們要的是 ((13 XOR 8) XOR 2) XOR 0

13:       00000000000000000000000000000000
 8:       00000000000000000000000000000000

# 13 XOR 8

Out:      00000000000000000000000000000000

# Now we XOR that with word number [i-14]:
 :        00000000000000000000000000000000  # 前面 Out 的結果
2:        00000000000000000000000000000000

# (13 XOR 8) XOR 2

Out:      00000000000000000000000000000000

# Now we XOR that with word number [i-16]:
 :        00000000000000000000000000000000  # 前面 Out 的結果
0:        01000001001000000101010001100101

# ((13 XOR 8) XOR 2) XOR 0

Out:      01000001001000000101010001100101 <-- XOR 最終結果

Left Rotate

將上方 XOR 最終結果向左做 Rotate 1 bit，也就是將當前最左邊的 bit 搬到最右邊；在我們的結果中，就是把現在最左邊的 0 移動到最右邊：

:      01000001001000000101010001100101
       │                               ^
       └───────────────────────────────┘
       
# Left Rotate

Out    10000010010000001010100011001010 <-- Left Rotate 最終結果

恭喜！我們得到了第 17 組數字了！

依樣畫葫蘆，進入下一個迴圈，現在 i = 17，由編號 14, 9, 3, 1 (即 [i-3], [i-8], [i-14], [i-16]) 依序做 XOR、再 Left Rotate 產生第 18 組 word (編號 17)……以此類推。

最後做到 i = 79 時，我們有以下結果：

 編號: word
 
 0: 01000001001000000101010001100101
 1: 01110011011101001000000000000000
 2: 00000000000000000000000000000000
 3: 00000000000000000000000000000000
 4: 00000000000000000000000000000000
 5: 00000000000000000000000000000000
 6: 00000000000000000000000000000000
 7: 00000000000000000000000000000000
 8: 00000000000000000000000000000000
 9: 00000000000000000000000000000000
10: 00000000000000000000000000000000
11: 00000000000000000000000000000000
12: 00000000000000000000000000000000
13: 00000000000000000000000000000000
14: 00000000000000000000000000000000
15: 00000000000000000000000000110000
16: 10000010010000001010100011001010
17: 11100110111010010000000000000000
18: 00000000000000000000000001100000
19: 00000100100000010101000110010101
20: 11001101110100100000000000000001
21: 00000000000000000000000011000000
22: 00001001000000101010001100101010
23: 10011011101001000000000001100011
24: 00000100100000010101000000010101
25: 11011111110101110100011001010101
26: 00110111010010000000000000000111
27: 00000000000000000000001100000000
28: 00100100000010101000110010101000
29: 01101110100100000000000111101110
30: 00010110100001000001000111000001
31: 10110010100011110001100111110110
32: 11010000101000111111001010100011
33: 01010110011101100000110000000010
34: 10010000001010100011001100100000
35: 10101000010001010100000111101101
36: 01101101010110000100011100000011
37: 11001010001111000110010011011010
38: 01100110100001010100011000100111
39: 00110111010010000011000110000111
40: 01010010101011011000110011010110
41: 11011110010010000001111011100001
42: 01101000010000010001110000010001
43: 00101000111100011001111110101011
44: 00000011001111011000100100010111
45: 11111100110001001100000110100110
46: 00010000101001100111010111011101
47: 10100001000110010101101011001001
48: 11011101110000010001100111100111
49: 01100001101110100100110110100110
50: 01101000010101000110010111110110
51: 00101110100100110100011011110111
52: 11010010101101011000101100101010
53: 11010011110010011110001000011010
54: 00010100001110111111001110110110
55: 00110101010110011111110100001011
56: 01101001110010001101011001110100
57: 00000110011100000111111010110101
58: 01101100111000100001101111110110
59: 00100110110111011001110100011101
60: 10001110101111000001001010101011
61: 11000101111011001100010100000111
62: 11111111000000100000010100100011
63: 11110110100011011111000110011110
64: 00110011011000101101111011000100
65: 01101100101101101110000110001111
66: 01000001000111000000100101101000
67: 11010001110010111100111001101001
68: 01001001000010010001011101110000
69: 11000100110000011010011011111100
70: 10100110011101011101110100010000
71: 00011001010110101100101010100001
72: 11100101000100110110101101110101
73: 11010100110111011011111001101111
74: 01110100001100011001010100101001
75: 10101111110100111111101000001101
76: 11011000110101010111110100101111
77: 00000111001000100000111010011001
78: 10001011100011011111100111110101
79: 10110111011010010100111100111110

Step 5. 主要迴圈

你可能想說剛剛那步已經有點複雜了，抱歉，現在這個步驟才是最複雜的步驟。

宣告常數

在進入主要迴圈之前，要先宣告五個常數：(為何是這五個常數？)

h0 = 01100111010001010010001100000001
h1 = 11101111110011011010101110001001
h2 = 10011000101110101101110011111110
h3 = 00010000001100100101010001110110
h4 = 11000011110100101110000111110000

同時，新增五個變數 A, B, C, D, E，先指派成這五個常數：

A = h0
B = h1
C = h2
D = h3
E = h4

主要迴圈

整個 SHA-1 最複雜的就是這邊了！

基於不同組的 word，每一次迴圈會做不太一樣的事情：

第 1~20 組 word (編號 0~19) 做 Function 1
第 21~40 組 word (編號 20~39) 做 Function 2
第 41~60 組 word (編號 40~59) 做 Function 3
第 61~80 組 word (編號 60~79) 做 Function 4

其中：

Function 1 做 (B AND C) OR (!B AND D) 產生 F，以及一個常數 k：

# Output of Function 1.
F = (B AND C) OR (!B AND D)
k = 01011010100000100111100110011001

Function 2 做 B XOR C XOR D 產生 f，以及一個常數 k：

# Output of Function 2.
F = B XOR C XOR D
k = 01101110110110011110101110100001

Function 3 做(B AND C) OR (B AND D) OR (C AND D)產生 f，以及一個常數 k：

# Output of Function 3.
F = (B AND C) OR (B AND D) OR (C AND D)
k = 10001111000110111011110011011100

Function 4 與 Function 2 相同，只差在常數 k ：(這些 k 是怎麼選的？)

# Output of Function 4.
F = B XOR C XOR D
k = 11001010011000101100000111010110

接著終於要用到本次迴圈的 word 了。

先宣告一個變數 temp ，它等於 (A left rotate 5) + F + E + K + (本次迴圈 word)

temp = (A left rotate 5) + F + E + K + (the current word)

我們以最後一圈第 80 組 word (編號 79) 為例，此時 temp 值是：

   A lrot 5:    00110001000100010000101101110100
+         F:    10001011110000011101111100100001
+         E:    11101001001001111110100110101011
+         K:    11001010011000101100000111010110 
+   Word 79:    10110111011010010100111100111110
 -----------------------------------------------
        Out:  1100100111110001101110010101010100

可以看到有時 temp 加總的結果可能會超過 32 bits，如果有超過的話就把前面 (最左邊) 切除 (truncate)，只留下 32 bits：

00100111110001101110010101010100

一次迴圈的最後，重新指派變數：

E = D
D = C
C = B Left Rotate 30
B = A
A = temp

如果還沒做完 80 個 word，用這次得到的 A, B, C, D, E 接著進入下一次迴圈，直到 80 個 word 都做完。

到這裡終於完成了第 5 步驟。

是不是開始覺得不如去看程式碼還比較快了解流程？

Step 6. 最後合併、輸出

終於快要結束了！

做完 80 次迴圈後會得到最終的 A, B, C, D, E，再將他們跟原始的常數 h0~h4 相加：

h0 = h0 + A
h1 = h1 + B
h2 = h2 + C
h3 = h3 + D
h4 = h4 + E

會得到：

h0 = 10001111000011000000100001010101
h1 = 10010001010101100011001111100100
h2 = 10100111110111100001100101000110
h3 = 10001011001110000111010011001000
h4 = 10010000000111011111000001000011

轉成 16 進位表示：

h0 = 10001111000011000000100001010101 = 0x 8f0c0855
h1 = 10010001010101100011001111100100 = 0x 915633e4
h2 = 10100111110111100001100101000110 = 0x a7de1946 
h3 = 10001011001110000111010011001000 = 0x 8b3874c8
h4 = 10010000000111011111000001000011 = 0x 901df043

排好，然後合併：

8f0c0855 915633e4 a7de1946 8b3874c8 901df043

# 合併
8f0c0855915633e4a7de19468b3874c8901df043

因此 A Test 經過 SHA-1 後，

就是 8f0c0855915633e4a7de19468b3874c8901df043

痛哭流涕。

補充與彩蛋

如果初始字串太長

如果在 Step 2 補 0 、補 64 bits 補到 512 bits 整數倍時，最後的總 bits 超過 512，例如 1024 bit、2048 bit，每一組 512 bit 要分別做 Step 3 ~ 5！

舉例來說，假設我輸入的字串比較長，做完 Step 2 時，得到 1024 bit，那我要將前 512 bit 切成 16 組、後 512 bit 切成另外 16 組。然後這兩組分別展開成 80 組 word (Step 4)、分別做主要迴圈 (Step 5)。

最後會得到前 512 bit 的 A1, B1, C1, D1, E1，以及後 512 bit 的 A2, B2, C2, D2, E2，此時在這一步 (Step 6) 才會合併：

h0 = h0 + A1 + A2
h1 = h1 + B1 + B2
h2 = h2 + C1 + C2
h3 = h3 + D1 + D2
h4 = h4 + E1 + E2

我想我們應該不需要更多例子了，太累了。

那些常數是如何決定的？

h0 ~ h4:

觀察 h0~h3，轉成 16 進位後可以看出 h0 到 h1 由 0123456789ABCDEF 以 big-endian 表示；如果以 little-endian 表示的話，就可以很直接地看出是 012345678 9ABCDEF。

而 h2 與 h3 則是將 h0 與 h1 依序倒過來。

至於 h4，則是 CDEF 與 3210 交叉出現。

h0 = 0110 0111 0100 0101 0010 0011 0000 0001 
   = 0x 6 7 4 5 2 3 0 1
   
h1 = 1110 1111 1100 1101 1010 1011 1000 1001 
   = 0x E F C D A B 8 9
   
h2 = 1001 1000 1011 1010 1101 1100 1111 1110 
   = 0x 9 8 B A D C F E
   
h3 = 0001 0000 0011 0010 0101 0100 0111 0110 
   = 0x 1 0 3 2 5 4 7 6
   
h4 = 1100 0011 1101 0010 1110 0001 1111 0000 
   = 0x C 3 D 2 E 1 F 0

看起來這些常數選擇的方式甚是隨意呢。

Function 1/2/3/4 中的 `k`：

其實也是其他隨意的常數：

# Function 1: 
k = 0101 1010 1000 0010 0111 1001 1001 1001 
  = 0x5A827999 
  = √2

# Function 2:
k = 0110 1110 1101 1001 1110 1011 1010 0001 
  = 0x6ED9EBA1 
  = √3

# Function 3:
k = 1000 1111 0001 1011 1011 1100 1101 1100 
  = 0x8F1BBCDC
  = √5

# Function 4:
k = 1100 1010 0110 0010 1100 0001 1101 0110
  = 0xCA62C1D6
  = √10

至於為什麼這樣選，大神說原論文也沒有特別說明；一個沿用傳統的概念。

後記

我已經忘記當初為什麼要去查整個流程了，可能出於當年的好奇心。

這次搬家過來也順便更新了一遍，現在更多抱著「不能只有我看到」的心態在更新的哈哈！如果你真的全部看完，恭喜你又變得更宅了一點。

Notes

實際上一般的雜湊也不夠安全，通常在資料庫裡面存的密碼會是做過 bcrypt 處理的結果。

Ref

https://www.metamorphosite.com/one-way-hash-encryption-sha1-data-software

前言