SHA1

SHA1

安全哈希算法(Secure Hash Algorithm)主要適用於數字簽名標準 (Digital Signature Standard DSS)裡面定義的數字簽名算法(Digital Signature Algorithm DSA)。對於長度小於2^64位的訊息,SHA1會產生一個160位的訊息摘要。當接收到訊息的時候,這個訊息摘要可以用來驗證數據的完整性。在傳輸的過程中,數據很可能會發生變化,那么這時候就會產生不同的訊息摘要。 SHA1有如下特性:不可以從訊息摘要中復原信息;兩個不同的訊息不會產生同樣的訊息摘要,(但會有1x10 ^ 48分之一的機率出現相同的訊息摘要,一般使用時忽略)。

基本信息

術語和概念

位,位元組和字

SHA1始終把訊息當成一個位(bit)字元串來處理。本文中,一個字(Word)是32位,而一個位元組(Byte)是8位。比如,字元串“abc”可以被轉換成一個位字元串:01100001 01100010 01100011。它也可以被表示成16進制字元串: 0x616263.

運算符和符號

下面的邏輯運算符都被運用於“字”(Word)

X & Y = X, Y邏輯與

X | Y = X, Y邏輯或

X ^ Y= X, Y邏輯異或

~X = X邏輯取反

X+Y定義如下:

字 X 和 Y 代表兩個整數 x 和y, 其中 0 <= x < 2^32 且 0 <= y < 2^32. 令整數z = (x + y) mod 2^32. 這時候 0 <= z < 2^32. 將z轉換成字Z, 那么就是 Z = X + Y.

邏輯左移位(循環移位)操作符Sn(X):

X是一個字,n是一個整數,0<=n<=32。

Sn(X) = (X<<n)OR(X>>32-n)

SHA1算法描述

在SHA1算法中,我們必須把原始訊息(字元串,檔案等)轉換成位字元串。SHA1算法只接受位作為輸入。假設我們對字元串“abc”產生訊息摘要。首先,我們將它轉換成位字元串如下:

01100001 01100010 01100011

―――――――――――――

‘a’=97 ‘b’=98 ‘c’=99

這個位字元串的長度為24。下面我們需要5個步驟來計算訊息摘要MAC。

補位

訊息必須進行補位,以使其長度在對512取模以後的餘數是448。也就是說,(補位後的訊息長度)%512 = 448。即使長度已經滿足對512取模後餘數是448,補位也必須要進行。

補位是這樣進行的:先補一個1,然後再補0,直到長度滿足對512取模後餘數是448。總而言之,補位是至少補一位,最多補512位。還是以前面的“abc”為例顯示補位的過程。

原始信息: 01100001 01100010 01100011

補位第一步:01100001 01100010 01100011 1

首先補一個“1”

補位第二步:01100001 01100010 01100011 10…..0

然後補423個“0”

我們可以把最後補位完成後的數據用16進制寫成下面的樣子

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000

經過以上的處理之後,數據的長度是448了,我們可以進行下一步操作。

補長度

所謂的補長度是將原始數據的長度補到已經進行了補位操作的訊息後面。通常用一個64位的數據來表示原始訊息的長度。如果訊息長度不大於2^64,那么第一個字就是0。在進行了補長度的操作以後,整個訊息就變成下面這樣了(16進制格式)

61626380 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000000

00000000 00000000 00000000 00000018

如果原始的訊息經過補位後長度超過了512,我們需要將它補成512的倍數。然後我們把整個訊息分成一個一個512位的數據塊,分別處理每一個數據塊,從而得到訊息摘要。

使用的常量

一系列的常量字K(0), K(1), ... , K(79),如果以16進制給出。它們如下:

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

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

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

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

使用的函式

在SHA1中我們需要一系列的函式。每個函式ft (0 <= t <= 79)都操作32位字B,C,D並且產生32位字作為輸出。ft(B,C,D)可以如下定義

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).

計算訊息摘要

必須使用進行了補位和補長度後的訊息來計算訊息摘要。計算需要兩個緩衝區,每個都由5個32位的字組成,還需要一個80個32位字的緩衝區。第一個5個字的緩衝區被標識為A,B,C,D,E。第二個5個字的緩衝區被標識為H0, H1, H2, H3, H4

。80個字的緩衝區被標識為W0, W1,..., W79

另外還需要一個一個字的TEMP緩衝區。

為了產生訊息摘要,在第3.2部分中定義的512位(16個字)的數據塊M1, M2,..., Mn

會依次進行處理,處理每個數據塊Mi 包含80個步驟。

在處理所有數據塊之前,緩衝區{Hi} 被初始化為下面的值(16進制)

H0 = 0x67452301

H1 = 0xEFCDAB89

H2 = 0x98BADCFE

H3 = 0x10325476

H4 = 0xC3D2E1F0.

現在開始處理M1, M2, ... , Mn。為了處理 Mi,需要進行下面的步驟

(1). 將 Mi 分成 16 個字 W0, W1, ... , W15, W0 是最左邊的字

(2). 對於 t = 16 到 79 令

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

(3). 令 A = H0, B = H1, C = H2, D = H3, E = H4.

(4) 對於 t = 0 到 79,執行下面的循環

TEMP = S5(A) + ft(B,C,D) + E + Wt + Kt;

E = D; D = C; C = S30(B); B = A; A = TEMP;

(5). 令 H0 = H0 + A, H1 = H1 + B, H2 = H2 + C, H3 = H3 + D, H4 = H4 + E.

在處理完所有的 Mn, 後,訊息摘要是一個160位的字元串,以下面的順序標識

H0 H1 H2 H3 H4.

對於SHA256,SHA384,SHA512。你也可以用相似的辦法來計算訊息摘要。對訊息進行補位的算法完全是一樣的。

SHA1在許多安全協定中廣為使用,包括TLS和SSL、PGP、SSH、S/MIME和IPsec,曾被視為是MD5(更早之前被廣為使用的散列函式)的後繼者。

相關詞條

相關搜尋

熱門詞條

聯絡我們