1. Introduction
MD5算法是一種消息摘要算法(
Message Digest Algorithm)，此算法以任意長度的信息(message)作為輸入進(jìn)行計(jì)算，產(chǎn)生一個(gè)128-bit(16-byte)的指紋或報(bào)文摘要(
fingerprint or message digest)。兩個(gè)不同的message產(chǎn)生相同message digest的幾率相當(dāng)小，從一個(gè)給定的message digest逆向產(chǎn)生原始message更是困難(不過據(jù)說我國的某個(gè)教授很善于從message digest構(gòu)造message)，因此MD5算法適合用在數(shù)字簽名應(yīng)用中。MD5實(shí)現(xiàn)簡單，在32位的機(jī)器上運(yùn)行速度也相當(dāng)快，當(dāng)然實(shí)際應(yīng)用也不僅僅局限于數(shù)字簽名。
2. MD5 Algorithm Description
假設(shè)輸入信息(input message)的長度為b(bit)，我們想要產(chǎn)生它的報(bào)文摘要，在此處b為任意的非負(fù)整數(shù)：b也可能為0，也不一定為8的整數(shù)倍，且可能是任意大的長度。設(shè)該信息的比特流表示如下：
?????????
M[0] M[1] M[2] ... M[b-1]
計(jì)算此信息的報(bào)文摘要需要如下5步：
2.1 Append Padding Bits
信息計(jì)算前先要進(jìn)行位補(bǔ)位，設(shè)補(bǔ)位后信息的長度為LEN(bit)，則LEN%512 = 448(bit)，即數(shù)據(jù)擴(kuò)展至
K*512+448(bit)。即K*64+56(byte)，K為整數(shù)。補(bǔ)位操作始終要執(zhí)行，即使補(bǔ)位前信息的長度對512求余的結(jié)果是448。具體補(bǔ)位操作：補(bǔ)一個(gè)1，然后補(bǔ)0至滿足上述要求。總共最少要補(bǔ)1bit，最多補(bǔ)512bit。
2.2 Append Length
將輸入信息的原始長度b(bit)表示成一個(gè)64-bit的數(shù)字，把它添加到上一步的結(jié)果后面(在32位的機(jī)器上，這64位將用2個(gè)字來表示并且低位在前)。當(dāng)遇到b大于2^64這種極少的情況時(shí)，b的高位被截去，僅使用b的低64位。經(jīng)過上面兩步，數(shù)據(jù)就被填補(bǔ)成長度為512(bit)的倍數(shù)。也就是說，此時(shí)的數(shù)據(jù)長度是16個(gè)字(32byte)的整數(shù)倍。此時(shí)的數(shù)據(jù)表示為：
?????????
M[0 ... N-1]
其中的N是16的倍數(shù)。
2.3 Initialize MD Buffer
用一個(gè)四個(gè)字的緩沖器(A，B，C，D)來計(jì)算報(bào)文摘要，A,B,C,D分別是32位的寄存器，初始化使用的是十六進(jìn)制表示的數(shù)字，注意低字節(jié)在前：
??????? word A: 01 23 45 67
??????? word B: 89 ab cd ef
??????? word C: fe dc ba 98
??????? word D: 76 54 32 102.4 Process Message in 16-Word Blocks
首先定義4個(gè)輔助函數(shù)，每個(gè)函數(shù)的輸入是三個(gè)32位的字，輸出是一個(gè)32位的字：
??????? 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))
NOTE：not(X)代表X的按位補(bǔ)運(yùn)算，X v Y 表示X和Y的按位或運(yùn)算，X xor Y代表X和Y的按位異或運(yùn)算，XY代表X和Y的按位與運(yùn)算。
具體過程如下：
?1?/*?Process?each?16-word?block.?*/
?2????For?i?=?0?to?N/16-1?do
?3?
?4??????/*?Copy?block?i?into?X.?*/
?5??????For?j?=?0?to?15?do
?6????????Set?X[j]?to?M[i*16+j].
?7??????end?/*?of?loop?on?j?*/
?8?
?9??????/*?Save?A?as?AA,?B?as?BB,?C?as?CC,?and?D?as?DD.?*/
10??????AA?=?A
11??????BB?=?B
12??????CC?=?C
13??????DD?=?D
14?
15??????/*?Round?1.?*/
16??????/*?Let?[abcd?k?s?i]?denote?the?operation
17???????????a?=?b?+?((a?+?F(b,c,d)?+?X[k]?+?T[i])?<<<?s).?*/
18??????/*?Do?the?following?16?operations.?*/
19??????[ABCD??0??7??1]??[DABC??1?12??2]??[CDAB??2?17??3]??[BCDA??3?22??4]
20??????[ABCD??4??7??5]??[DABC??5?12??6]??[CDAB??6?17??7]??[BCDA??7?22??8]
21??????[ABCD??8??7??9]??[DABC??9?12?10]??[CDAB?10?17?11]??[BCDA?11?22?12]
22??????[ABCD?12??7?13]??[DABC?13?12?14]??[CDAB?14?17?15]??[BCDA?15?22?16]
23?
24??????/*?Round?2.?*/
25??????/*?Let?[abcd?k?s?i]?denote?the?operation
26???????????a?=?b?+?((a?+?G(b,c,d)?+?X[k]?+?T[i])?<<<?s).?*/
27??????/*?Do?the?following?16?operations.?*/
28??????[ABCD??1??5?17]??[DABC??6??9?18]??[CDAB?11?14?19]??[BCDA??0?20?20]
29??????[ABCD??5??5?21]??[DABC?10??9?22]??[CDAB?15?14?23]??[BCDA??4?20?24]
30??????[ABCD??9??5?25]??[DABC?14??9?26]??[CDAB??3?14?27]??[BCDA??8?20?28]
31??????[ABCD?13??5?29]??[DABC??2??9?30]??[CDAB??7?14?31]??[BCDA?12?20?32]
32?
33??????/*?Round?3.?*/
34??????/*?Let?[abcd?k?s?t]?denote?the?operation
35???????????a?=?b?+?((a?+?H(b,c,d)?+?X[k]?+?T[i])?<<<?s).?*/
36??????/*?Do?the?following?16?operations.?*/
37??????[ABCD??5??4?33]??[DABC??8?11?34]??[CDAB?11?16?35]??[BCDA?14?23?36]
38??????[ABCD??1??4?37]??[DABC??4?11?38]??[CDAB??7?16?39]??[BCDA?10?23?40]
39??????[ABCD?13??4?41]??[DABC??0?11?42]??[CDAB??3?16?43]??[BCDA??6?23?44]
40??????[ABCD??9??4?45]??[DABC?12?11?46]??[CDAB?15?16?47]??[BCDA??2?23?48]
41?
42??????/*?Round?4.?*/
43??????/*?Let?[abcd?k?s?t]?denote?the?operation
44???????????a?=?b?+?((a?+?I(b,c,d)?+?X[k]?+?T[i])?<<<?s).?*/
45??????/*?Do?the?following?16?operations.?*/
46??????[ABCD??0??6?49]??[DABC??7?10?50]??[CDAB?14?15?51]??[BCDA??5?21?52]
47??????[ABCD?12??6?53]??[DABC??3?10?54]??[CDAB?10?15?55]??[BCDA??1?21?56]
48??????[ABCD??8??6?57]??[DABC?15?10?58]??[CDAB??6?15?59]??[BCDA?13?21?60]
49??????[ABCD??4??6?61]??[DABC?11?10?62]??[CDAB??2?15?63]??[BCDA??9?21?64]
50?
51??????/*?Then?perform?the?following?additions.?(That?is?increment?each
52?????????of?the?four?registers?by?the?value?it?had?before?this?block
53?????????was?started.)?*/
54??????A?=?A?+?AA
55??????B?=?B?+?BB
56??????C?=?C?+?CC
57??????D?=?D?+?DD
58?
59????end?/*?of?loop?on?i?*/
2.5 Output
報(bào)文摘要的產(chǎn)生后的形式為：A，B，C，D。也就是低位字節(jié)A開始，高位字節(jié)D結(jié)束。
3. C++ Implementation
有了上面5個(gè)步驟的算法描述，用C++實(shí)現(xiàn)起來就很直接了。需要注意的是在具體實(shí)現(xiàn)的時(shí)候上述5個(gè)步驟的順序會有所變動，因?yàn)樵诖蠖鄶?shù)情況下我們都無法或很難提前計(jì)算出輸入信息的長度b(如輸入信息來自文件或網(wǎng)絡(luò))。因此在具體實(shí)現(xiàn)時(shí)
Append Padding Bits和
Append Length這兩步會放在最后面。
4. Test Suite由于實(shí)現(xiàn)代碼比較長，在這里就不貼出來了，在本文后面會提供下載。MD5類的public接口如下：
md5.h?1?class?MD5?{
?2?public:
?3?????MD5();
?4?????MD5(const?void* input,?size_t?length);
?5?????MD5(const?string& str);
?6?????MD5(ifstream?&in);
?7?????void?update(const?void* input,?size_t?length);
?8?????void?update(const?string& str);
?9?????void?update(ifstream& in);
10?????const?byte*?digest();
11?????string?toString();
12?????void?reset();
13?????...
14?};
下面簡單介紹一下具體用法：
1.計(jì)算字符串的MD5值
下面的代碼計(jì)算字符串"abc"的MD5值并用cout輸出：
1?MD5?md5;
2?md5.update("abc");
3?cout?<<?md5.toString()?<<?endl;
4?//或者更簡單點(diǎn)
5?cout?<<?MD5("abc").toString()?<<?endl;
2.計(jì)算文件的MD5值
下面的代碼計(jì)算文本文件"D:\test.txt"的MD5值并用cout輸出，如果是二進(jìn)制文件打開的時(shí)候記得要指定ios::binary模式。另外需要注意的是用來計(jì)算的文件必須存在，所以最好在計(jì)算前先判斷下ifstream的狀態(tài)。
(本來判斷ifstream是否有效不該是客戶的責(zé)任，原本想在ifstream無效時(shí)用文件名做參數(shù)拋出FileNotFoundException之類的異常，后來卻發(fā)現(xiàn)從ifstream中居然無法得到文件名...)
1?MD5?md5;
2?md5.update(ifstream("D:\\test.txt"));
3?cout?<<?md5.toString()?<<?endl;
4?//或者更簡單點(diǎn)
5?cout?<<?MD5(ifstream("D:\\test.txt")).toString()?<<?endl;
3.最基本的用法
上面的用來計(jì)算字符串和文件MD5值的接口都是為了方便才提供的，其實(shí)最基本的接口是：
void update(const void *input, size_t length);
update的另外兩個(gè)重載都是基于它來實(shí)現(xiàn)的，下面的代碼用上述接口來實(shí)現(xiàn)FileDigest函數(shù)，該函數(shù)用來計(jì)算文件的MD5值：
?1?string?FileDigest(const?string& file)?{
?2?
?3?????ifstream?in(file.c_str(),?ios::binary);
?4?????if?(!in)
?5?????????return?"";
?6?
?7?????MD5?md5;
?8?????std::streamsize?length;
?9?????char?buffer[1024];
10?????while?(!in.eof())?{
11?????????in.read(buffer,?1024);
12?????????length?=?in.gcount();
13?????????if?(length?>?0)
14?????????????md5.update(buffer,?length);
15?????}
16?????in.close();
17?????return?md5.toString();
18?}
下面看看測試代碼：
test.cpp?1?#include?"md5.h"
?2?#include?<iostream>
?3?
?4?using?namespace?std;
?5?
?6?void?PrintMD5(const?string& str,?MD5& md5)?{
?7?????cout?<<?"MD5(\""?<<?str?<<?"\")?=?"?<<?md5.toString()?<<?endl;
?8?}
?9?
10?int?main()?{
11?
12?????MD5?md5;
13?????md5.update("");
14?????PrintMD5("",?md5);
15?
16?????md5.update("a");
17?????PrintMD5("a",?md5);
18?
19?????md5.update("bc");
20?????PrintMD5("abc",?md5);
21?
22?????md5.update("defghijklmnopqrstuvwxyz");
23?????PrintMD5("abcdefghijklmnopqrstuvwxyz",?md5);
24?
25?????md5.reset();
26?????md5.update("message?digest");
27?????PrintMD5("message?digest",?md5);
28?
29?????md5.reset();
30?????md5.update(ifstream("D:\\test.txt"));
31?????PrintMD5("D:\\test.txt",?md5);
32?
33?????return?0;
34?}
測試結(jié)果：
MD5("") = d41d8cd98f00b204e9800998ecf8427e
MD5("a") = 0cc175b9c0f1b6a831c399e269772661
MD5("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5("D:\test.txt") = 7ac66c0f148de9519b8bd264312c4d64
源代碼下載：
點(diǎn)擊下載在這里放上Vrcats修改的Qt版本：
點(diǎn)擊下載