2012年7月22日 星期日

SHA加密演算法


SHA加密演算法

SHA1演算法原理

  1 SHA1演算法簡介

  安全雜湊演算法(Secure Hash Algorithm)主要適用於數位簽章標準(Digital Signature Standard DSS)裡面定義的數位簽章演算法(Digital Signature Algorithm DSA)。對於長度小於2^64位元的消息,SHA1會產生一個160位元的消息摘要。當接收到消息的時候,這個消息摘要可以用來驗證資料的完整性。在傳輸的過程中,資料很可能會發生變化,那麼這時候就會產生不同的消息摘要。

  SHA1有如下特性:不可以從消息摘要中復原資訊;兩個不同的消息不會產生同樣的消息摘要。

  2 術語和概念

  2.1位元(Bit),位元組(Byte)和字(Word)

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

  2.2 運算子和符號

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

  X^Y = X,Y邏輯與

  X \/ Y = X,Y邏輯或

  X XOR 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. www.2cto.com

  迴圈左移位操作符Sn(X)。X是一個字,n是一個整數,0<=n<=32。Sn(X) = (X<<n)OR(X>>32-n)

  X<<n定義如下:拋棄最左邊的n位元數位,將各個位元依次向左移動n位,然後用0填補右邊的n位(最後結果還是32位)。X>>n是拋棄右邊的n位,將各個位依次向右移動n位,然後在左邊的n位填0。因此可以叫Sn(X)位迴圈移位運算

  3 SHA1演算法描述

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

  01100001 01100010 01100011

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

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

  這個位字串的長度為24。下面我們需要5個步驟來計算MD5。

  3.1 補位

  消息必須進行補位元,以使其長度在對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了,我們可以進行下一步操作。

  3.2 補長度

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

  61626380 00000000 00000000 00000000

  00000000 00000000 00000000 00000000

  00000000 00000000 00000000 00000000

  00000000 00000000 00000000 00000018

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

  3.3 使用的常量

  一系列的常量字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).

  3.4 需要使用的函數

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

  3.5 計算消息摘要

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

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

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

  為了產生消息摘要,在第4部分中定義的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 令Wt = S1(Wt-3 XOR Wt-8 XOR Wt- 14 XOR Wt-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。你也可以用相似的辦法來計算消息摘要。對消息進行補位元的演算法完全是一樣的。

轉載自《紅黑聯盟》

沒有留言:

張貼留言