什么是 MD5

MD5 是一種算法, MD5 中的 MD 代表 Message Digest, 也即信息摘要.

至于數字 5, 則因它是從更早的 MD4 算法改進而來, 因此得名 MD5.

所以 MD5 即是信息摘要算法第五版.

什么是信息摘要算法

那什么又是信息摘要算法呢? 它本質上就是一個哈希函數(hash function).

又叫散列函數.

那什么又是哈希函數呢? 它是指這樣一種函數: 它能把任意大小的數據映射(map)為一個固定大小的值.

A hash function is any function that can be used to map data of arbitrary size to fixed-size values.

哈希函數所返回的這個值稱為哈希值(hash value), 又稱為哈希碼(hash codes), 或直接簡稱為哈希(hash).

具體例子

單純地這樣去講會比較抽象, 因此這里引入具體例子來說明, 以 Java 為例, 可以這樣去計算 MD5:

public void rawMd5() throws NoSuchAlgorithmException { 
    byte[] bytes = "hello".getBytes(StandardCharsets.UTF_8); 
    MessageDigest md = MessageDigest.getInstance("MD5"); 
    byte[] md5 = md.digest(bytes); 
} 

注: 因為摘要計算的輸入是一個字節數組, 如果要計算字符串的摘要值, 則要轉成某種編碼的字節數組, 為保持一致, 應始終顯式使用同一種編碼, 比如 utf-8.

從以上代碼中也不難看出, 一個 MD5 函數的輸入和輸出都是字節數組 byte[].

而代碼中不能直接體現的一點則是: 輸入可以是任意大小的字節數組, 輸出則是固定大小的字節數組.

對于 MD5 算法而言, 這個輸出值是一個固定大小為 16 字節的數組, 然后因為每個字節(byte)有 8 個位(bit), 所以最終的輸出值是一個 16 × 8 = 128 位的二進制數. MD5 的值就是一個 128 位的二進制大整數.

比如下面就是一個具體的 MD5 的值, 以原始的 128 位二進制形式表示: 10001000100100011001000111110000100011111000000111010010110010101100010111101010000110011011110000111011111101111101100110111110

這個 MD5 值實際是對我的網站域名 xiaogd.net 作摘要的結果.

這個值的二進制形式實在是長得不要不要的, 所以一般會轉換為十六進制形式, 共 16 組具體為: 88 91 91 f0 8f 81 d2 ca c5 ea 19 bc 3b f7 d9 be. 依然還是很長, 但比二進制好多了.

隨便說一句, IPv6 的地址也是 128 bit 的, 所以也是像這般變態的長, 寫成 16 進制也還是很長, 壓根記不住...

最后通常還會去掉空格寫成一個緊湊的 32 個字符的字符串的形式: 889191f08f81d2cac5ea19bc3bf7d9be, 也即是我們最常見到的 MD5 值的形式.

但請不要誤解, MD5 的值并不是一個字符串, 更不是什么字母都能出現在里邊的.

術語和符合

本文中一個“字”是32位，一個“字節”是8位。

我們定義x_i代表“x減去I".如果減數是一個表達式，則用括號括住，如：x_{i+1}。同樣我們用^代表求冪，這樣x^i則代表x的i次冪。“+”代表“字”之間的相加，X<<< s代表X左移s位，not(X)表示對X進行按位補運算，X v Y表示按位或。X xor Y表示按位異或，XY表示按位與。

 MD5算法描述

我們假設有一個b位長的信息作為輸入，然后我們算出他的摘要信息。b是一個非負整數，b有可能是0，不需要一定是8的倍數，可能會非常得大。我們將輸入信息描繪如下：

m_0 m_1 .. m_{b-1}

接下來的五步我們來算出它的摘要。

1、 填充

我們將輸入信息填充到長度對512取余對于448。無論輸入信息的長度多少，填充總是會發生的，即使本身的長度就已經滿足模512對于448的情況下。

過程如下：

在輸入信息后添加一個“1”位，其余添加“0”位使得輸入信息長度滿足對512取余對于448。總的來說，至少添加一位，至多添加512位。

舉個例子：66

2、 補充數據長度

將輸入信息b用64位表示并添加到填充的數據之后，如果b大于2^64的話，則只取低64位。

至此，我們的處理結果剛好是512的倍數，等效的，也是16字的倍數，我們用M[0...N-1]來表示這個結果，其中N是16的倍數。

3、 初始化MD緩沖區

用一個四字的緩沖區（A,B,C,D）來計算消息摘要，這里的A，B，C，D每一個都是一個32位的寄存器。這些寄存器的初始值如下，用16進制表示的，低位字節優先。

word A: 01 23 45 67 
word B: 89 ab dc ed 
word C: fe dc ba 98 
word D: 76 54 32 10 

4、 處理消息

我們首先需要定義四個輔助函數。

F(X,Y,Z) = XY v not(X) Z 
G(X,Y,Z) = XZ v Y not(Z) 
H(X,Y,Z) = X xor Y xor Z 
I(X,Y,Z) = Y xor (X v not(Z)) 

對于函數F來說，在每一位上F函數就像是一個選擇器：if X then Y else Z。

這一步需要一個64長度的表格T[1...64],由sin函數構造而成。T[i]是4294967296次運行abs(sin(i))的結果，以此類推即可。

我們需要進行一下處理

/* 處理原數據. */ 
For i = 0 to N/16-1 do 
/* 將數據賦值給X. */ 
For j = 0 to 15 do 
Set X[j] to M[i*16+j]. 
end /* 結束對j的循環 */ 
/* 把A保存位AA B保存為BB C保存為CC D保存位DD */ 
AA = A 
BB = B 
CC = C 
DD = D 
/* 第一輪操作 */ 
/* [abcd k s i] 表示如下操作 
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */ 
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4] 
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8] 
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12] 
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16] 
/* 第二輪操作 */ 
/* [abcd k s i] 表示如下操作 
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */ 
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20] 
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24] 
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28] 
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32] 
/* 第三輪操作 */ 
/* [abcd k s t] 表示如下操作 
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */ 
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36] 
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40] 
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44] 
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48] 
/* 第四輪操作 */ 
/* [abcd k s t] 表示如下操作 
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */ 
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52] 
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56] 
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60] 
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64] 
A = A + AA 
B = B + BB 
C = C + CC 
D = D + DD 
end /* 結束對i的循環 */ 

5、 輸出

上一步輸出最終的結果A，B，C，D。我們從A的低位字節開，到D的高位字節結束，每一個都是32位，最終拼接的結果就是4*32 = 128位，這就是MD5結算的結果。