來自http://m.shnenglu.com/ant/archive/2007/09/11/31886.html
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至滿足上述要求?？偣沧钌僖a(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è)步驟的順序會(huì)有所變動(dòng)，因?yàn)樵诖蠖鄶?shù)情況下我們都無法或很難提前計(jì)算出輸入信息的長度b(如輸入信息來自文件或網(wǎng)絡(luò))。因此在具體實(shí)現(xiàn)時(shí)
Append Padding Bits和
Append Length這兩步會(huì)放在最后面。
4. Test Suite由于實(shí)現(xiàn)代碼比較長，在這里就不貼出來了，在本文后面會(huì)提供下載。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