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

前言

本篇移轉自之前寫在 medium 的文章。
環境：
- Python 3.7
- Windows 10

Hash (雜湊) 是什麼？

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

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

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

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

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

→ 984816fd329622876e14907634264e6f332e9fb3

Hash 可以用來幹嘛？

舉凡作為資料儲存的索引、密碼儲存、證明訊息沒有被竄改過等等。

手把手做 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’，得到 49 bit 的數字：

01000001 00100000 01010100 01100101 01110011 01110100 1
                                                      ^

再補 0

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

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

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

(512 – 64 – 49) = 399 bit

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

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

最後補 64 bit

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

0000000000000000000000000000000000000000000000000000000000110000

最後終於得到 512 bit：

0100000100100000010101000110010101110011011101001 000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000110000

Step 3: 切成 (Chunk) 16 組 word

第三步相對簡單，將 512 bit 切成 16 組、每組 32 bit 的 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 組 word (0~~15)，如何展開成 80 組 (0~~79)？

由以下迴圈達成。

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

XOR

因此在得到第 17 組 word 之前，先第 13, 8, 2, 0 組 word 依序 XOR 。

 # first loop, i = 16

 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:       00000000000000000000000000000000
8:        00000000000000000000000000000000

# 13 XOR 8

Out:      00000000000000000000000000000000

# Now we XOR that with word number [i-14]:
:         00000000000000000000000000000000
2:        00000000000000000000000000000000

# (13 XOR 8) XOR 2

Out:      00000000000000000000000000000000

# Now we XOR that with word number [i-16]:
:         00000000000000000000000000000000
0:        01000001001000000101010001100101

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

Out:      01000001001000000101010001100101 <-- XOR 最終結果

Left Rotate

將上方的結果向左做 Rotate 1 bit，也就是將當前最左邊的 bit 搬到最右邊。

:      01000001001000000101010001100101

# Left Rotate

Out    10000010010000001010100011001010 <-- Left Rotate 最終結果

此時得到的結果就是第 17 組 word (編號 16)。

# first loop, i = 16

 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 組 word

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

最後當 i 做到 79，即有 80 組 word (編號 0~79)：

 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

主要迴圈

接下來這步稍微複雜一些。

基於不同組的 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) 為例，此時值是：

A lrot 5:                         00110001000100010000101101110100
F:                                10001011110000011101111100100001
A lrot 5 + F
Out:                             110111100110100101110101010010101

A lrot 5 + F:                    110111100110100101110101010010101
E:                                11101001001001111110100110101011
A lrot 5 + F + E
Out:                            1010100101111110101101010001000000

A lrot 5 + F + E:               1010100101111110101101010001000000
K:                                11001010011000101100000111010110
A lrot 5 + F + E + K
Out:                           11101110000010111011001011000010110

A lrot 5 + F + E + K:          11101110000010111011001011000010110
Word 79:                          10110111011010010100111100111110
A lrot 5 + F + E + K + Word 79
Out:                          <strong>100000100111110001101110010101010100</strong>

此時 temp 的值就是：

temp = 100000100111110001101110010101010100

你會發現目前的 temp 有 36 bit，而且每一輪可能長短不一。

所以做完上述步驟，要把最後得到的 temp 切除 (truncate) 前面，直到只有 32 bit。

32-bit temp =   00100111110001101110010101010100

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

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

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

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

合併後就得到 “ 8f0c0855915633e4a7de19468b3874c8901df043”

8f0c0855 915633e4 a7de1946 8b3874c8 901df043
    --> 8f0c0855915633e4a7de19468b3874c8901df043

因此 “A Test” 經過 SHA-1 後，

就是 ” 8f0c0855915633e4a7de19468b3874c8901df043”

注意！

如果在 Step 2 補 0 、補 64 bit 補到 512 bit 整數倍時，最後的總 bit 超過 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，則是奇數 1357 與偶數 0246 交叉出現。

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 1 0 3 2 5 4 7 6

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

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

Source Code:

如果可以的話，去下載專門做 binary 邏輯處理的 module，可能會更快一點。這兩個函數是之前為了練習而寫的，然後直接拿來用：

產 2 補數 : b()
把二進位轉成數字: to_num()

所以有些地方可能會有些多餘，例如說 b() 函數考慮了負數，事實上 SHA-1 用不到；或是導致一些邏輯計算 (XOR/AND/OR/NOT) 都必須持續在數字跟字串之間轉換；如果能直接用一些 Module 可能會更有效率、也比較簡潔。

參考程式碼：

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137


# Left rotate
def lrot(byte_string, offset):
    for i in range(offset):
        byte_string = byte_string[1:]+byte_string[0]
    return byte_string

# Transfer num to binary (string), e.g "00101011"
def b(num, bits=8):
    if -num > 2**(bits-1) or num > 2**(bits-1) - 1:
        return format(num, "b")[-bits:]

    maximum = 2 ** bits - 1
    if num < 0:
        n = format((-num - 1) ^ maximum, "b")
        if bits - len(n) > 0:
            return "1"*(bits - len(n)) + n
        else:
            return n

    else:
        n = format(num, "b")
        if bits - len(n) > 0:
            return "0"*(bits - len(n)) + n
        else:
            return n

# Transfer binary to num.
def to_num(input_bits):
    return int(input_bits, 2)



# Get a whole dict of words
def first_part_to_80_words(string):
    chunked_dict = {}
    s = ""
    for i in string:
        s += b(ord(i))  # String to ASCII.
    org_len = len(s)  # Original length of input string
    s += "1"  # Append '1'.
    amount = (512 * ((len(s) // 512) + 1) - (len(s) - 448)) % 512  # Append some zero's to make s congruent to 448 % 512.
    s += "0" * amount
    s += b(org_len, bits=64)  # Append Original length of input string in 64-bit.
    for x in range(len(s)//512):  # One chunk deal with up to 512 bit.
        chunked_dict[x] = {}
        for y in range(16):
            chunked_dict[x][y] = s[0:32]  # Store words (32-bit).
            s = s[32:]

    
    for i in chunked_dict.keys():  # Extend to 80 words.
        ini = 16
        for j in range(ini, 80):
            # d[i-3], d[i-8], d[i-14], d[i-16]
            xor_res = to_num(chunked_dict[i][j-3]) ^ to_num(chunked_dict[i][j-8])
            xor_res = xor_res ^ to_num(chunked_dict[i][j-14])
            xor_res = xor_res ^ to_num(chunked_dict[i][j-16])
            new_bits = b(xor_res, bits=32)
            new_bits = new_bits[1:] + new_bits[0]
            chunked_dict[i][j] = new_bits
    return chunked_dict


# Main loop
def hash_sha1(string):
    def function_1(x, y, z):
        f = b((x & y) | (~x & z), 32)
        k = "01011010100000100111100110011001"
        return f, k

    def function_2(x, y, z):
        f = b((x ^ y) ^ z, 32)
        k = "01101110110110011110101110100001"
        return f, k

    def function_3(x, y, z):
        f = b((x & y) | (x & z) | (y & z), 32)
        k = "10001111000110111011110011011100"
        return f, k

    def function_4(x, y, z):
        f = b((x ^ y) ^ z, 32)
        k = "11001010011000101100000111010110"
        return f, k

    print(string)
    h0 = "01100111010001010010001100000001"
    h1 = "11101111110011011010101110001001"
    h2 = "10011000101110101101110011111110"
    h3 = "00010000001100100101010001110110"
    h4 = "11000011110100101110000111110000"


    byte_dict = first_part_to_80_words(string)
    for key in byte_dict.keys():
        A = h0
        B = h1
        C = h2
        D = h3
        E = h4

        for i in range(80):
            if i < 20:
                F, K = function_1(to_num(B), to_num(C), to_num(D))
            elif i < 40:
                F, K = function_2(to_num(B), to_num(C), to_num(D))
            elif i < 60:
                F, K = function_3(to_num(B), to_num(C), to_num(D))
            elif i < 80:
                F, K = function_4(to_num(B), to_num(C), to_num(D))

            temp = to_num(lrot(A, 5)) + to_num(F) + to_num(E) + to_num(K) + to_num(byte_dict[key][i])
            temp = b(temp, 32)

            E = D
            D = C
            C = lrot(B, 30)
            B = A
            A = temp

        h0 = b((to_num(h0) + to_num(A)), 32)
        h1 = b((to_num(h1) + to_num(B)), 32)
        h2 = b((to_num(h2) + to_num(C)), 32)
        h3 = b((to_num(h3) + to_num(D)), 32)
        h4 = b((to_num(h4) + to_num(E)), 32)

    s0 = hex(int(h0, 2))[2:]
    s1 = hex(int(h1, 2))[2:]
    s2 = hex(int(h2, 2))[2:]
    s3 = hex(int(h3, 2))[2:]
    s4 = hex(int(h4, 2))[2:]
    print(" --> ", end="")
    print(s0 + s1 + s2 + s3 + s4)
    return s0 + s1 + s2 + s3 + s4


hash_sha1("TEST")