什么是 MD5

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

至于數(shù)字 5, 則因它是從更早的 MD4 算法改進(jìn)而來(lái), 因此得名 MD5.

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

什么是信息摘要算法

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

又叫散列函數(shù).

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

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

哈希函數(shù)所返回的這個(gè)值稱為哈希值(hash value), 又稱為哈希碼(hash codes), 或直接簡(jiǎn)稱為哈希(hash).

具體例子

單純地這樣去講會(huì)比較抽象, 因此這里引入具體例子來(lái)說(shuō)明, 以 Java 為例, 可以這樣去計(jì)算 MD5:

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

注: 因?yàn)檎?jì)算的輸入是一個(gè)字節(jié)數(shù)組, 如果要計(jì)算字符串的摘要值, 則要轉(zhuǎn)成某種編碼的字節(jié)數(shù)組, 為保持一致, 應(yīng)始終顯式使用同一種編碼, 比如 utf-8.

從以上代碼中也不難看出, 一個(gè) MD5 函數(shù)的輸入和輸出都是字節(jié)數(shù)組 byte[].

而代碼中不能直接體現(xiàn)的一點(diǎn)則是: 輸入可以是任意大小的字節(jié)數(shù)組, 輸出則是固定大小的字節(jié)數(shù)組.

對(duì)于 MD5 算法而言, 這個(gè)輸出值是一個(gè)固定大小為 16 字節(jié)的數(shù)組, 然后因?yàn)槊總€(gè)字節(jié)(byte)有 8 個(gè)位(bit), 所以最終的輸出值是一個(gè) 16 × 8 = 128 位的二進(jìn)制數(shù). MD5 的值就是一個(gè) 128 位的二進(jìn)制大整數(shù).

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

這個(gè) MD5 值實(shí)際是對(duì)我的網(wǎng)站域名 xiaogd.net 作摘要的結(jié)果.

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

隨便說(shuō)一句, IPv6 的地址也是 128 bit 的, 所以也是像這般變態(tài)的長(zhǎng), 寫成 16 進(jìn)制也還是很長(zhǎng), 壓根記不住...

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

但請(qǐng)不要誤解, MD5 的值并不是一個(gè)字符串, 更不是什么字母都能出現(xiàn)在里邊的.

術(shù)語(yǔ)和符合

本文中一個(gè)“字”是32位，一個(gè)“字節(jié)”是8位。

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

 MD5算法描述

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

m_0 m_1 .. m_{b-1}

接下來(lái)的五步我們來(lái)算出它的摘要。

1、 填充

我們將輸入信息填充到長(zhǎng)度對(duì)512取余對(duì)于448。無(wú)論輸入信息的長(zhǎng)度多少，填充總是會(huì)發(fā)生的，即使本身的長(zhǎng)度就已經(jīng)滿足模512對(duì)于448的情況下。

過(guò)程如下：

在輸入信息后添加一個(gè)“1”位，其余添加“0”位使得輸入信息長(zhǎng)度滿足對(duì)512取余對(duì)于448?？偟膩?lái)說(shuō)，至少添加一位，至多添加512位。

舉個(gè)例子：66

2、 補(bǔ)充數(shù)據(jù)長(zhǎng)度

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

至此，我們的處理結(jié)果剛好是512的倍數(shù)，等效的，也是16字的倍數(shù)，我們用M[0...N-1]來(lái)表示這個(gè)結(jié)果，其中N是16的倍數(shù)。

3、 初始化MD緩沖區(qū)

用一個(gè)四字的緩沖區(qū)（A,B,C,D）來(lái)計(jì)算消息摘要，這里的A，B，C，D每一個(gè)都是一個(gè)32位的寄存器。這些寄存器的初始值如下，用16進(jìn)制表示的，低位字節(jié)優(yōu)先。

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、 處理消息

我們首先需要定義四個(gè)輔助函數(shù)。

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

對(duì)于函數(shù)F來(lái)說(shuō)，在每一位上F函數(shù)就像是一個(gè)選擇器：if X then Y else Z。

這一步需要一個(gè)64長(zhǎng)度的表格T[1...64],由sin函數(shù)構(gòu)造而成。T[i]是4294967296次運(yùn)行abs(sin(i))的結(jié)果，以此類推即可。

我們需要進(jìn)行一下處理

/* 處理原數(shù)據(jù). */ 
For i = 0 to N/16-1 do 
/* 將數(shù)據(jù)賦值給X. */ 
For j = 0 to 15 do 
Set X[j] to M[i*16+j]. 
end /* 結(jié)束對(duì)j的循環(huán) */ 
/* 把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 /* 結(jié)束對(duì)i的循環(huán) */ 

5、 輸出

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