SHA-1 演算法

資訊與網路安全技術：第四章雜湊與亂數演算法上一頁 下一頁

4-4 SHA-1 演算法

內容：

4-4-1 SHA-1 演算法

4-4-2 暫存器起始值

4-4-3 輸入常數

4-4-4 訊息擴充

4-4-5 壓縮函數

4-4-1 SHA-1 演算法

『安全雜湊演算法』（Secure Hash Algorithm, SHA）是美國 NIST 所制定的標準，於 1993 年與 1995 年分別發表 FIPS PUB 180 與 FIPS PUB 180-1，目前都通稱後面的版本為 SHA-1。SHA 是以 MD4 為基礎發展出來的，其設計方式與 MD5 非常相似。首先我們列出 SHA-1 的特性，再來推演它的演算法，特性如下：

可以輸入不定長度的訊息，但不可以超過 2⁶⁴ 個位元。經過附加位元後必須是 512 位元的整數倍，但還餘有 448 個位元。填補方式與 MD5 一樣，需加入 64 位元的長度欄位。
附加位元後的訊息，以 512 位元為單位，分割成若干個區塊；雖然，演算區塊的長度為 512 個位元；但每一區塊經過擴充字元，填入 32 位元的 W[t] 紀錄器，計有 80 個紀錄器（t =0, 1, 2, …, 79）。
每個步驟計算與最後運算的結果，皆得到 160 個位元的雜湊值。
SHA-1 區塊之間的演算程序和 MD5 一樣，如圖 5-3 所示。
利用 5 個 32 位元的暫存器（A、B、C、D 與 E），來儲存演算中的 160 位元的雜湊值。
演算步驟共有 4 個回合，每回合執行 20 次，共計 80 次的運算。
每回合含一個基本邏輯函數，計有 4 個邏輯函數（f₁、f₂、f₃ 與 f₄）；並於每回合加入一個固定常數（K_1~4，或稱為『鹽』）。
每個步驟於演算基本邏輯函數時，會輸入相對應的常數（K_1~4）與訊息區段（W[t], t = 0, 1, 2, …, 79）。

SHA-1 演算法亦屬區塊運算方式，但較特殊的地方，是將512 個位元區塊擴充成 80 個 32 個位元的小區塊，每個執行步驟輸入一個小區塊。圖 4-7 為 SHA-1 演算法的功能圖，以下將說明它的運作程序。

圖 4-7 SHA-1 演算法的功能圖

4-4-2 暫存器起始值

共計有 5 個 32 位元的暫存器，還未輸入計算之前，給予的起始值如下：（以 16 進位表示）

A：67 45 23 01

B：EF CD AB 89

C：98 BA DC FE

D：10 32 54 76

E ：C3 D2 E1 F0

前面 4 個暫存器與 MD5 相同，但 SHA-1 是採用『較高位元結尾』（Big-endian）的格式儲存（不同於 MD5）。

4-4-3 輸入常數

每一運算回合都會分別給一個固定常數（類似『鹽』的功能），四個回合共有四個常數（K_1~4）；如以步驟來計算，共有 80 個步驟（t），每個步驟的常數如下：（以 16 進位表示）

回合	步驟編號	輸入常數	取值方式 (整數)
第一回合	0 ≦ t ≦ 19	K₁ = 5A82799	[2³⁰× 2]
第二回合	20 ≦ t ≦ 39	K₂ = 6ED9EBA1	[2³⁰× 3]
第三回合	40 ≦ t ≦ 59	K₃ = 8F1BBCDC	[2³⁰× 5]
第四回合	60 ≦ t ≦ 79	K₄ = CA62C1D6	[2³⁰× 10]

4-4-4 訊息擴充

為了打亂訊息內資料的關聯性、或訊息的格式，SHA-1 採用了訊息擴充的方法，將訊息（512 個位元）擴充成 80 個 32 位元的小區塊（W[k], k=0, 1, …, 79）。其方法是，首先將訊息以每 32 位元為單位，分割為 16 個小區塊，分別存入 W[0]、W[1]、…、W[15] 之中，而第 16 個以後的小區塊，分別以下面公式計算填入：

W[t] = S¹(W[t-16] ⊕ W[t-14] ⊕ W[t-8] ⊕ W[t-3]), t =16, 17, …, 79

譬如：

W[16] = S¹(W[0] ⊕ W[2] ⊕ W[8] ⊕ W[13])

W[17] = S¹(W[1] ⊕ W[3] ⊕ W[9] ⊕ W[14])

…….,

W[79] = S¹(W[63] ⊕ W[65] ⊕ W[71] ⊕ W[76])

其中 S¹ 表示向左迴旋一個位元的意思。由此可見，SHA-1 的訊息擴充方法是，前面 16 個小區塊是由原訊息分割得來；而第 16 個小區塊以後，是由前面某4 個小區塊之間執行 XOR 運算之後，再向左迴旋一個位元。如此說來，應該可以完全攪碎訊息的關聯性。

SHA-1 演算法中，每執行一個步驟（共計 80 個步驟），便輸入一個訊息的小區塊。譬如，第一個步驟（t=0），則輸入 W[0]；第二個步驟（t=1），則輸入 W[1]；依此類推，到了第 80 個步驟，剛好使用完最後的小區塊 W[79]。

4-4-5 壓縮函數

接下來介紹 SHA-1 的重頭戲：『壓縮函數』（Compression Function）。其功能是將上一步驟所計算的結果（CV_q），再重複計算一次，得到本次的計算結果（CV_q+1）；演算當中會加入參數 k_1~4 與訊息小區塊 W[t]；總共計算了 80 次，其中又分為 4 個回合。SHA-1 壓縮函數的功能如圖 4-8 所示，運算過程如下：（以 5 個暫存器 A、B、C、D、E 為計算對象）