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

 

4-4 SHA-1 演算法

內容:

4-4-1 SHA-1 演算法

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

  • 可以輸入不定長度的訊息,但不可以超過 264 個位元。經過附加位元後必須是 512 位元的整數倍,但還餘有 448 個位元。填補方式與 MD5 一樣,需加入 64 位元的長度欄位。

  • 附加位元後的訊息,以 512 位元為單位,分割成若干個區塊;雖然,演算區塊的長度為 512 個位元;但每一區塊經過擴充字元,填入 32 位元的 W[t] 紀錄器,計有 80 個紀錄器(t =0, 1, 2, …, 79)。

  • 每個步驟計算與最後運算的結果,皆得到 160 個位元的雜湊值。

  • SHA-1 區塊之間的演算程序和 MD5 一樣,如圖 5-3 所示。

  • 利用 5 32 位元的暫存器(ABCD E,來儲存演算中的 160 位元的雜湊值。

  • 演算步驟共有 4 個回合,每回合執行 20 次,共計 80 次的運算。

  • 每回合含一個基本邏輯函數,計有 4 個邏輯函數(f1f2f3 f4);並於每回合加入一個固定常數(K1~4,或稱為『鹽』)。

  • 每個步驟於演算基本邏輯函數時,會輸入相對應的常數(K1~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 進位表示)

A67 45 23 01

BEF CD AB 89

C98 BA DC FE

D10 32 54 76

E C3 D2 E1 F0

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

4-4-3 輸入常數

每一運算回合都會分別給一個固定常數(類似『鹽』的功能),四個回合共有四個常數(K1~4);如以步驟來計算,共有 80 個步驟(t),每個步驟的常數如下:(以 16 進位表示)

回合

步驟編號

輸入常數

取值方式 (整數)

第一回合

0 t 19

K1 = 5A82799

[230× 2]

第二回合

20 t 39

K2 = 6ED9EBA1

[230× 3]

第三回合

40 t 59

K3 = 8F1BBCDC

[230× 5]

第四回合

60 t 79

K4 = CA62C1D6

[230× 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] = S1(W[t-16] W[t-14] W[t-8] W[t-3]), t =16, 17, …, 79

譬如:

W[16] = S1(W[0] W[2] W[8] W[13])

W[17] = S1(W[1] W[3] W[9] W[14])

…….,

W[79] = S1(W[63] W[65] W[71] W[76])

其中 S1 表示向左迴旋一個位元的意思。由此可見,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。其功能是將上一步驟所計算的結果(CVq),再重複計算一次,得到本次的計算結果(CVq+1);演算當中會加入參數 k1~4 與訊息小區塊 W[t];總共計算了 80 次,其中又分為 4 個回合。SHA-1 壓縮函數的功能如圖 4-8 所示,運算過程如下:(以 5 個暫存器 ABCDE 為計算對象)

A = E + f1-4(B, C, D) + S5(A) + W[t] + K1-4

B = A

C = S30(B)

D = C

E = D

4-8 SHA-1 壓縮函數的功能圖

其中,Sn(A) 表示將暫存器 A 向左迴旋 n 位元的意思;『+』表示取 232 同餘(mod 232)的加法。第一回合(0 t 19)會輸入常數 k1;第二回合(20 t 39)會輸入常數 k2;依此類推,第四回合輸入參數為 k4

SHA-1 設計了 4 個基本邏輯函數(f1~4),分別使用於每一回合的計算中。各個基本邏輯函數與使用時機如下:

回合

步驟編號

基本邏輯函數

簡式

1

0 t 19

BC+D

2

20 t 39

BCD

3

40 t 59

BC+BD+CD

4

60 t 79

BCD

其中,ANDORNOT XOR 分別以     符號表示。

 

主講人:粘添壽博士

 

資訊與網路安全技術