MD5的概述

1.簡介

MD5訊息摘要演算法是Ron Rivest開發的。MD5實際上根源於一系列訊息的摘要演算法。原先的訊息摘要演算法稱爲MD，很快進入下一版MD2，但很脆弱。因此，Ron Rivest開始開發MD3，結果失敗了。後來，開發了MD4，但其結果還是很不理想，因此最終推出了MD5。
MD5速度很快，產生128位元訊息摘要。經過初始處理後，輸入文字變成512位元塊，進一步分爲16個32位元塊。這個演算法的輸出是4個32位元塊構成的集合，形成128位元訊息摘要。

2.MD5工作原理

2.1填充
MD5的第一步實在初始訊息中增加填充位，目的使初始訊息長度等於一個值，即比512位元的倍數少64位元。例如，如果初始訊息長度爲1000位，則要填充472位，使訊息長度爲1472位，因爲1472+64=1536，是512的倍數。
這樣，填充後，初始訊息的長度爲448位元（比512少64位元）、960位元（比1024少64位元）、1472位（比1536少64位元），等等。
填充對用一個1位和多個0位。注意，填充總是要進行的，即使訊息長度已經是比512的倍數少64。因此，如果訊息長度已經是448位元，則要填充512位元，是長度變成960位元，因此，填充長度爲1~ 512位元的值。
2.2新增長度
新增填充位後，下一步要計算訊息原長，將其加進填充後的訊息末尾。其工作流程如下：先計算訊息長度，不包括填充位（即增加填充位前的長度）。例如，如果初始訊息爲1000位，則填充472位，使其變成比512的倍數少64位元，但長度爲1000，而不是1472。
這個訊息原長表示爲64位元值，新增到加進填充後的訊息末尾，如下圖所示：

這是訊息的長度爲512位元的倍數。注意，如果訊息長度超過$2^{64}$位，即64位元無法表示，因爲訊息太長，則只用長度的低64位元，即等於計算length mod $2^{64}$。
2.3 將輸入分成512位元的塊
下面 下麪要將輸入分成512位元的塊，如下圖所示：

2.4 初始鏈接變數
這一步要初始化4個鏈接變數，分別稱爲A、B、C、D，都是32位元數位。這些鏈接變數都是初始十六進制值，如下表所示：

鏈接變數	十六進制值
A	01 23 45 67
B	89 AB CD EF
C	FE DC BA 98
D	76 54 32 10

2.5 處理塊
初始化之後，就要開始實際的演算法，這是一個回圈，對訊息中的多個512位元塊執行。其步驟如下：
第一步：將4個鏈接變數複製到4個變數a、b、c、d中，使a=A、b=B、c=C、d=D。實際上，這個演算法將a、b、c、d組合成128位元暫存器（abcd），暫存器（abcd）在實際演算法運算中儲存中間結果和最終結果，如下圖所示：

第二步：將當前的512位元塊分解爲16個子塊，每個子塊爲32位元。
第三步：這時有4輪，每一輪處理一個塊的16位元，每一輪的輸入如下：（a）16個子塊；（b）變數a、b、c、d；（c）常數t，如下圖所示：

這4輪的第一步進行不同處理（即處理P處理bcd），其他步驟是相同的。每一輪有16個輸入子塊M[0]，M[1]，…，M[15]，或表示爲M[i]，其中i位0~ 15，每個子塊爲32位元。t是個常數陣列，包含64個元素，每個元素32位元。把陣列t的元素表示爲t[1]，t[2]，…，t[64]，或t[k]，其中k爲1~64，由於有四輪，因此每一輪使用t值中的16個。
下面 下麪總結這四輪的迭代，每一輪的輸出的中間和最終結果複製到暫存器abcd中，注意，每一輪有16個暫存器。
（1）處理P首先處理b、c、d。這個處理P在四輪中不同。
（2）變數a加進處理P的輸出（即暫存器abcd）。
（3）訊息子塊M[i]加進第2步輸出（即暫存器abcd）。
（4）常數t[k]加進第3步輸出（即暫存器abcd）。
（5）第4步的輸出（即暫存器abcd內容）回圈左移S位（S值不斷改變）。
（6）變數b加進第5步輸出（即暫存器abcd）。
（7）第6步輸出成爲下一步的新abcd。
下圖顯示了MD5的操作過程：

可以用數學方法表示MD5操作過程：
$a=b+((a+Process P(b,c,d)+M[i]+t[k])<<<S)$
其中，a、b、c、d爲鏈接變數；Process P（P處理）爲非線性運算；M[i]表示訊息的第i個分組；t[k]爲常數；<<<S表示回圈左移S位。
2.6 處理P簡介
處理P在4輪中是不同的。簡單地說，處理P就是a、b、c、d的基本布爾運算，如下表所示：

輪次	處理P
1	(b AND c) OR ((NOT b) AND (b))
3	b XOR c XOR d
2	(b AND d) OR (c AND (NOT d))
4	c XOR (b OR (NOT d))

注：每一輪只有P處理不同，所有其他步驟都是相同的，因此每一輪中替換處理P的實際細節，其餘保持不變。
2.7 四輪運算
下表顯示了4輪的迭代運算：

迭代	a	b	c	d	M	s	t
1	a	b	c	d	M[0]	7	t[1]
2	d	a	b	c	M[1]	12	t[2]
3	c	d	a	b	M[2]	17	t[3]
4	b	c	d	a	M[3]	22	t[4]
5	a	b	c	d	M[4]	7	t[5]
6	d	a	b	c	M[5]	12	t[6]
7	c	d	a	b	M[6]	17	t[7]
8	b	c	d	a	M[7]	22	t[8]
9	a	b	c	d	M[8]	7	t[9]
10	d	a	b	c	M[9]	12	t[10]
11	c	d	a	b	M[10]	17	t[11]
12	b	c	d	a	M[11]	22	t[12]
13	a	b	c	d	M[12]	7	t[13]
14	d	a	b	c	M[13]	12	t[14]
15	c	d	a	b	M[14]	17	t[15]
16	b	c	d	a	M[15]	22	t[16]

迭代	a	b	c	d	M	s	t
1	a	b	c	d	M[1]	5	t[17]
2	d	a	b	c	M[6]	9	t[18]
3	c	d	a	b	M11]	14	t[9]
4	b	c	d	a	M[0]	20	t[20]
5	a	b	c	d	M[5]	5	t[21]
6	d	a	b	c	M[10]	9	t[22]
7	c	d	a	b	M[15]	14	t[23]
8	b	c	d	a	M[4]	20	t[24]
9	a	b	c	d	M[9]	5	t[25]
10	d	a	b	c	M[14]	9	t[26]
11	c	d	a	b	M[3]	14	t[27]
12	b	c	d	a	M[8]	20	t[28]
13	a	b	c	d	M[13]	5	t[29]
14	d	a	b	c	M[2]	9	t[30]
15	c	d	a	b	M[7]	14	t[31]
16	b	c	d	a	M[2]	20	t[32]

迭代	a	b	c	d	M	s	t
1	a	b	c	d	M[5]	4	t[33]
2	d	a	b	c	M[8]	11	t[34]
3	c	d	a	b	M11]	16	t[35]
4	b	c	d	a	M[14]	23	t[36]
5	a	b	c	d	M[1]	4	t[37]
6	d	a	b	c	M[4]	11	t[38]
7	c	d	a	b	M[7]	16	t[39]
8	b	c	d	a	M[10]	23	t[40]
9	a	b	c	d	M[13]	4	t[41]
10	d	a	b	c	M[0]	11	t[42]
11	c	d	a	b	M[3]	16	t[43]
12	b	c	d	a	M[6]	23	t[44]
13	a	b	c	d	M[9]	4	t[45]
14	d	a	b	c	M[12]	11	t[46]
15	c	d	a	b	M[15]	16	t[47]
16	b	c	d	a	M[2]	23	t[48]

迭代	a	b	c	d	M	s	t
1	a	b	c	d	M[0]	6	t[49]
2	d	a	b	c	M[7]	10	t[50]
3	c	d	a	b	M[14]	15	t[51]
4	b	c	d	a	M[5]	21	t[52]
5	a	b	c	d	M[12]	6	t[53]
6	d	a	b	c	M[3]	10	t[54]
7	c	d	a	b	M[10]	15	t[55]
8	b	c	d	a	M[1]	21	t[56]
9	a	b	c	d	M[8]	6	t[57]
10	d	a	b	c	M[15]	10	t[58]
11	c	d	a	b	M[16]	15	t[59]
12	b	c	d	a	M[13]	21	t[60]
13	a	b	c	d	M[4]	6	t[61]
14	d	a	b	c	M[11]	10	t[62]
15	c	d	a	b	M[2]	15	t[63]
16	b	c	d	a	M[9]	21	t[64]

其中t的取值如下表所示：

t[i]	值	t[i]	值	t[i]	值	t[i]	值
t[1]	D76AA478	t[17]	F61E2562	t[33]	FFFA3942	t[49]	F4292244
t[2]	E8C7B756	t[18]	C040B340	t[34]	8771F681	t[50]	432AFF97
t[3]	242070DB	t[19]	265E5A51	t[35]	699D6122	t[51]	AB9423A7
t[4]	C1BDCEEE	t[20]	E9B6C7AA	t[36]	FDE5380C	t[52]	FC93A039
t[5]	F57C0FAF	t[21]	D62F105D	t[37]	A4BEEA44	t[53]	655B59C3
t[6]	4787C62A	t[22]	02441453	t[38]	4BDECFA9	t[54]	8F0CCC92
t[7]	A8304613	t[23]	D8A1E681	t[39]	F6BB4B60	t[55]	FFEFF47D
t[8]	FD469501	t[24]	E7D3FBC8	t[40]	BEBFBC70	t[56]	85845DD1
t[9]	698098D8	t[25]	21E1CDE6	t[41]	289B7EC6	t[57]	6FA87E4F
t[10]	8B44F7AF	t[26]	F4D50D87	t[42]	EAA127FA	t[58]	FE2CE6E0
t[11]	FFFF5BB1	t[27]	F4D50D87	t[43]	D4EF3085	t[59]	A3014314
t[12]	895CD7BE	t[28]	455A14ED	t[44]	04881D05	t[60]	4E0811A1
t[13]	6B901122	t[29]	A9E3E905	t[45]	D9D4D039	t[61]	F7537E82
t[14]	FD987193	t[30]	FCEFA3F8	t[46]	E6DB99E5	t[62]	BD3AF235
t[15]	A679438E	t[31]	676F02D9	t[47]	1FA27CF8	t[63]	2AD7D2BB
t[16]	49B40821	t[32]	8D2A4C8A	t[48]	C4AC5665	t[64]	BE86D391

3.MD5與MD4

下表表示了MD5和MD4的關鍵差別：

特性	MD4	MD5
輪數	3	4
常數t的使用	所有迭代中相同	所有迭代中不同
第2輪的處理P	(b AND d) OR (b AND d) OR (c AND d)	(b AND d) OR (c AND (NOT d))，更隨機

此外，第2輪和第3輪存取子塊的順序也發生了改變，引入了更大的隨機性。