SHA1摘要演算法詳解:[1]演算法詳解?

SHA1(安全雜湊演算法Secure Hash Algorithm)摘要加密演算法主要適用於數字簽名標準裡面定義的數字簽名演算法。對於長度小於2^64位的訊息,SHA1會產生一個160位的訊息摘要,由於SHA1演算法的雪崩效應(改變一位訊息資料會使輸出值大幅度變動)與不可逆性,可用於驗證資料完整性與訊息驗證。

方法/步驟

1.術語解釋:SHA1演算法需要用到一系列的位運算,以下介紹位運算的符號表示:

XOR 異或 A XOR B

OR 或 A OR B

AND 與 A AND B

NOT 非 NOT A

<< 左移 A>>n(n為常數,下同)

>> 右移 A<

另外這裡還需要用到一種較為複雜的位運算,我們稱之為迴圈左移:

Sn(X)= (X< >32-n) 迴圈左移

例如,1001迴圈左移1位: S1(1001)=0011

即將資料左移1位,然後用左邊溢位的位去填補右邊需要補充的位。

2.資料前期處理:當我們得到一個訊息資訊,需要對其進行一系列的處理,主要有補位、補長度及分塊。

1)補位:令我們得到的訊息為字串"bob",我們先以字元為單位將其轉換為十六進位制Ascii碼的排列。b--62,o--6f,b--62。即現在的訊息資訊為626f62。再將其轉換為二進位制排列,可得:01100010 01101111 01100010。可見,這是一個長度為24位的資料。現在進行補位操作,首先在我們的資料後加上一個1。得到:01100010 01101111 01100010 1。目前的長度L=25,計算長度L對512的取餘運算,及X=L%512,若X不等於448,就在資料末尾加上一個0,一直迴圈到X=448為止。此時資料的長度應為512的n倍加上448,即L'=512*n+448。補位結束。

2)補長度與分塊:現在我們得到一個長度L為512*n+448位的二進位制字串,我們在這個二進位制字串的末尾新增上一個長度為64位的二進位制字串,用來表示原訊息資料的長度,如上文中的"bob"長度為24位,其二進位制表示:

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00011000

如此,我們最終得到一個長度L''=512*n(即長度為512的倍數)的二進位制字串。最後,我們判斷這個二進位制字串的長度是否大於512位(即n是否為1)。若大於512位,我們則需要將其分割為長度為512位的多個字串,這裡用M[i](M[0],M[1]……)表示。若不大於,則直接用M0儲存。到此,補長度與分塊結束。

3.演算法需要的各常量的值及函式表示式:

1)常量:

Kt = 0x5A827999 (0 <= t <= 19)

Kt = 0x6ED9EBA1 (20 <= t <= 39)

Kt = 0x8F1BBCDC (40 <= t <= 59)

Kt = 0xCA62C1D6 (60 <= t <= 79)

2)函式表示式:

ft(B,C,D) = (B AND C) OR ((NOT B) AND D) ( 0 <= t <= 19)

ft(B,C,D) = B XOR C XOR D (20 <= t <= 39)

ft(B,C,D) = (B AND C) OR (B AND D) OR (C AND D) (40 <= t <= 59)

ft(B,C,D) = B XOR C XOR D (60 <= t <= 79).

4.演算法:

1)緩衝區:

處理上述的二進位制字串需要一些緩衝區,下面我們詳細列出各緩衝區的規格:

a.32位的緩衝區5個:A,B,C,D,E

b.32位的緩衝區80個:W[0]~W[79]

c.32位的緩衝區5個:H[0]~H[4]

d.32位的緩衝區1個:TEMP

首先我們將緩衝區H[]進行初始化賦值:

H[0]=0x67452301

H[1]=0xEFCDAB89

H[2]=0x98BADCFE

H[3]=0x10325476

H[4]=0xC3D2E1F0

2)針對每個M[i]進行迴圈:

a.將M[i]從左到右分割為16個32位的字串,轉換為uint型的數值分別儲存在緩衝區W[0]~W[15]中。

b.對於W[16]~W[79],我們進行如下迴圈:

W[i] = S1(W[i-3] XOR W[i-8] XOR W[i- 14] XOR W[i-16])

至此,我們的W[]緩衝區已經全部賦值完畢。

c.對緩衝區A,B,C,D,E分別進行賦值:

A=H[0]

B=H[1]

C=H[2]

D=H[3]

E=H[4]

d.對於W[0]~W[79],我們再進行如下迴圈:

TEMP = S5(A) + ft(B,C,D) + E + W[i] + K[i]

E=D

D=C

C=S30(B)

B=A

A=TEMP

e.我們再對緩衝區H[]進行操作:

H[0]=H[0]+A

H[1]=H[1]+B

H[2]=H[2]+C

H[3]=H[3]+D

H[4]=H[4]+E

3)如此完成每一個M[i]的迴圈後,最終得到的訊息摘要為:

H[0] H[1] H[2] H[3] H[4]

此處緩衝區H[]中的數值全部轉換為16進位制數用字串形式表示,以上述格式排列即為我們最終計算出的訊息摘要。

訊息, 演算法, 長度, 摘要,
相關問題答案