hsiung.博格 ERP軟體

MD5訊息摘要演算法

MD5這個訊息摘要(message-digest)演算法(RFC1321)，是Ron River在MIT所發展出來的(Ron River就是公開鑰匙加密演算法RSA[Rivest-Shamir-Adleman]裡面的「R」)。一直到幾年前(當暴力攻擊法與密碼破解等議題升溫時)，MD5還是最多人使用的安全雜湊函數。

MD5 的原理

這個演算法的輸入是一個任意長度的訊息，其輸出則是一個128位元的訊息摘要。輸入的訊息會被分成好機個512位元的區段來處理。

圖2所顯示的是產生訊息摘要的整個處理流程。這個流程採用了圖1的一般性架構。整個處理程序是由下列步驟所組成的：

步驟一：加上附加位元(padding bits)。在訊息之後附加一些位元，使得其位元長度在取512的同餘之後會等於448(訊息長度= 448 mod 512)。換言之，附加過後的訊息長度，會比512位元的倍數少64位元。我們一定要在訊息尾端附加位元，即使訊息本身的長度就已經符合我們的需求。例如，如果訊息長度剛好是448個位元，那麼我們就要在尾端加上512個位元，使其最後的長度為960個位元。因此。我們附加的位元可以從1到512。

附加的方式是：先加一個1，然後再用0補到所需的長度。

步驟二：加上長度。我們會將訊息的原始長度(以位元為單位)(換言之，在步驟一之前的長度)表示成一段64位元的資料，然後將這段資料附加在步驟一所產生的訊息末端(以最低位元為優先)。如果訊息的原始長度大於2⁶⁴的話，那麼我們只取訊息長度的最低64個位元。這樣一來，這個欄位的內容就是原始訊息長度取2⁶⁴的同餘。

經過前兩個步驟之後，訊息的長度就會變成512位元的整數倍。在圖2中，加長之後的訊息會被表示成一連串512位元的區段Y0,Y1,…YL-1，所以加長之後的訊息總長度就變成 L x 512個位元。我們也可以說，訊息長度是16個32位元字元的整數倍，我們設M[0…N-1]為訊息內的字元，這裡的N是16的倍數。因此我們可得N=L x 16。

步驟三：設定MD暫存區(MD buffer)的初值。我們會使用一個128位元的暫存區，來儲存這個雜湊函數的中間值，以及最後的結果。我們可以使用4個32位元的暫存器(A、B、C、D)來表示這個暫存區。這4個暫存器的初始值設定如下(以十六進位來表示)：

                                        A=67452301

                                        B=EFCDAB89

                                        C=98BADCFE

                                        D=10325476

這些值是以「以較低位元為結尾(little-endian)」的格式來儲存，在這種格式下，一個字元中最低的位元組，所佔據的是低位的位元組位置。就32位元的字串來說，這些初始值(以十六進位來表示)會如下所示：

                                        字元A：01 23 45 67

                                        字元B：89 AB CD EF

                                        字元C：FE DC BA 98

                                        字元D：76 54 32 10

步驟四：處理訊息中所有的512位元(16個字元)區段。這個演算法的核心部份，是由「四個回合」所組成的壓縮模組；這個模組在圖2中被標示成HMD5，其運作原理顯示在圖3中，這四個回合的結構都差不多，但是每個回合都用了一個不同的基本邏輯函數，這些邏輯函數在這個規格中分別被標示成F、G、H以及I。

每個回合的輸入，是我們正要處理的512位元區段(Yq)，與128位元的暫存區ABCD；這4個回合會分別更新這個暫存區的內容。此處有一個利用正弦函數所建立的具有64個項目的表格T[1…64]，每個回合都會用到這個表格的四分之一。我們用符號T[i]來表示T的第i個項目，其值等於2³² x abs(sin(i))的整數部份，此處的i表示弧度(radians)。因為abs(sin(i))是一個介於0到1之間的數，所以T中的每個項目都可以用32個字元來表示。這個表格提供了一組「隨機化」的32位元樣式，它們被用來消除輸入區段的規律性。表格1b就是T的內容。

這四個回合的輸出，會跟第一個回合的輸入(CVq)加在一起，所產生的結果就是CV_q+1。相加的方式是：暫存區中的四個字元，與CVq中相對應的字元相加(字元間彼此獨立相加)，並且要取2³²的同餘。

步驟五：輸出。當所有的L個512位元的區段都處理過之後，第L個階段所產生的輸出，就是我們所要的128位元的訊息摘要。

我們可以將MD5的行為歸納如下：

 CV₀         =  IV

CV_q+1        =  SUM₃₂[CV_q,RF_I(Y_q,RF_G(Y_q,RF_F(Y_q,CV_q))))]

  MD     =  CV_L-1

MD5的壓縮函數

讓我們更仔細地來看看，在每個回合中是如何處理一個512位元的區段。每個回合會用一連串16個步驟來處理暫存區ABCD。每一個步驟都具有下列的形式

a ← b+((a+g(b,c,d)+X[k]+T[i]<<< s)

其中

圖4所顯示的是一個步驟的運作方式。(a,b,c,d)這4個字元的順序，會在每一個步驟中向右輪轉一個字元。

每個回合都會用到一個基本邏輯函數。每個基本函數都需要三個32位元的輸入字元，然後會產生一個32位元的輸出字元。每個函數都會執行一組位元的邏輯運算；換言之，輸出的第n個位元，是由三個輸入的第n個位元所產生的。這些函數可以歸納如下：

(AND, OR, NOT, XOR)這4個邏輯運算分別被表示成(,,,)。函數F是一個條件函數：If b then c else d。同樣地，G如下列所示：If d then b else c。函數H會產生一個同位位元(parity bit)。表格1a是這4個函數的真值表。

圖5：MD5的基本更新演算法(RFC 1321)

圖5改編自RFC 1321，它定義了前述的步驟四的演算法。X[0…15]這個32位元字元的陣列所記錄的是，目前正要被處理的512位元輸入區段。在每個回合中，每個字元X[i](共有16個)都會被用到一次(16個步驟各用到一個)；每個回合使用這些字元的順序都不一樣。在第一個回合中，我們按照原來的順序來使用這些字元，第二個回合到第四個合的字元重排方式定義如下：

                        p₂(i)         = (1 + 5i) mod 16

                        p₃(i)         = (5 + 3i) mod 16

                        p₄(i)         = 7i mod 16

表格T中的每個32位元字元(共有64個)，都會在某個回合中的某個步驟被用到一次。請注意，在每個步驟中，暫存區ABCD中只有一個位元組會被改變。因此，在每個回合內，暫存區中的每個位元組都會被改變4次。而最後一次改變則會產生這個區段的最後輸出。最後，請注意每個回合之間的左移輪轉距離都不同。這種種的複雜措施，都是為了避免產生「碰撞(collisions)」(就是兩個不同的512位元區段，產生相同的輸出結果)。