md5算法原理.txt

MD5的C++源码

MD5算法的C++实现 
1. Introduction
MD5算法是一种消息摘要算法(Message Digest Algorithm)，此算法以任意长度的信息(message)作为输入进行计算，产生一个128-bit(16-byte)的指纹或报文摘要(fingerprint or message digest)。两个不同的message产生相同message digest的几率相当小，从一个给定的message digest逆向产生原始message更是困难(不过据说我国的某个教授很善于从message digest构造message)，因此MD5算法适合用在数字签名应用中。MD5实现简单，在32位的机器上运行速度也相当快，当然实际应用也不仅仅局限于数字签名。

2. MD5 Algorithm Description
假设输入信息(input message)的长度为b(bit)，我们想要产生它的报文摘要，在此处b为任意的非负整数：b也可能为0，也不一定为8的整数倍，且可能是任意大的长度。设该信息的比特流表示如下：

          M[0] M[1] M[2] ... M[b-1]

计算此信息的报文摘要需要如下5步：
2.1 Append Padding Bits
信息计算前先要进行位补位，设补位后信息的长度为LEN(bit)，则LEN%512 = 448(bit)，即数据扩展至
K*512+448(bit)。即K*64+56(byte)，K为整数。补位操作始终要执行，即使补位前信息的长度对512求余的结果是448。具体补位操作：补一个1，然后补0至满足上述要求。总共最少要补1bit，最多补512bit。

2.2 Append Length
将输入信息的原始长度b(bit)表示成一个64-bit的数字，把它添加到上一步的结果后面(在32位的机器上，这64位将用2个字来表示并且低位在前)。当遇到b大于2^64这种极少的情况时，b的高位被截去，仅使用b的低64位。经过上面两步，数据就被填补成长度为512(bit)的倍数。也就是说，此时的数据长度是16个字(32bit)的整数倍。此时的数据表示为：

          M[0 ... N-1]

其中的N是16的倍数。

2.3 Initialize MD Buffer
用一个四个字的缓冲器(A，B，C，D)来计算报文摘要，A,B,C,D分别是32位的寄存器，初始化使用的是十六进制表示的数字，注意低字节在前：

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

2.4 Process Message in 16-Word Blocks
首先定义4个辅助函数，每个函数的输入是三个32位的字，输出是一个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的按位补运算，X v Y 表示X和Y的按位或运算，X xor Y代表X和Y的按位异或运算，XY代表X和Y的按位与运算。

具体过程如下：
 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
报文摘要的产生后的形式为：A，B，C，D。也就是低位字节A开始，高位字节D结束。

3. C++ Implementation
有了上面5个步骤的算法描述，用C++实现起来就很直接了。需要注意的是在具体实现的时候上述5个步骤的顺序会有所变动，因为在大多数情况下我们都无法或很难提前计算出输入信息的长度b(如输入信息来自文件或网络)。因此在具体实现时Append Padding Bits和Append Length这两步会放在最后面。

4. Test Suite
由于实现代码比较长，在这里就不贴出来了，在本文后面会提供下载。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.计算字符串的MD5值
下面的代码计算字符串"abc"的MD5值并用cout输出：
1 MD5 md5;
2 md5.update("abc");
3 cout << md5.toString() << endl;
4 //或者更简单点
5 cout << MD5("abc").toString() << endl;
2.计算文件的MD5值
下面的代码计算文本文件"D:\test.txt"的MD5值并用cout输出，如果是二进制文件打开的时候记得要指定ios::binary模式。另外需要注意的是用来计算的文件必须存在，所以最好在计算前先判断下ifstream的状态。
(本来判断ifstream是否有效不该是客户的责任，原本想在ifstream无效时用文件名做参数抛出FileNotFoundException之类的异常，后来却发现从ifstream中居然无法得到文件名...)
1 MD5 md5;
2 md5.update(ifstream("D:\\test.txt"));
3 cout << md5.toString() << endl;
4 //或者更简单点
5 cout << MD5(ifstream("D:\\test.txt")).toString() << endl;
3.最基本的用法
上面的用来计算字符串和文件MD5值的接口都是为了方便才提供的，其实最基本的接口是：
void update(const void *input, size_t length);
update的另外两个重载都是基于它来实现的，下面的代码用上述接口来实现FileDigest函数，该函数用来计算文件的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 }
测试结果：
MD5("") = d41d8cd98f00b204e9800998ecf8427e
MD5("a") = 0cc175b9c0f1b6a831c399e269772661
MD5("abc") = 900150983cd24fb0d6963f7d28e17f72
MD5("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
MD5("message digest") = f96b697d7cb7938d525a2f31aaf161d0
MD5("D:\test.txt") = 7ac66c0f148de9519b8bd264312c4d64



首先要更正你一个概念，md5不是用于加密，而是用于数据的完整性校验的一种技术。

这是一个单向散列函数,单向的意思就是说不可逆转。你可以将源内容通过md5函数散列出一个md5校验码，这个md5校验码是唯一的，你可以作为证明源的身份标识，但是你无法通过md5校验码去还原源。
Src ---> md5 --->md5Code
但是 md5Code --->某算法 ---> Src 是不可能的（至少目前，未来的10年内是如此）

同样的内容经过md5算法总是得到相同的md5校验码。

之所以给人以md5是用于加密的这种假象，是因为该技术应用于很多密码校验和文件完整性校验过程中。

如你的password用明文输入，经过md5以后形成一个32字节的 md5校验码，保存在服务器上。服务器的管理员可以看到你的32字节的md5校验码，但是因为没有办法通过md5校验码还原成原密码，因此该密码的保存（实际上是保存的密码的一个唯一标识）是安全的。
校验的时候，你输入你的密码，经过md5以后形成一个新的32字节的md5校验码，服务器比较新的校验码和旧的校验码就可以判断你是否输入了正确的密码。在整个认证和鉴权的过程中，服务器只和你的密码生成以后的md5校验码打交道，而避免了和密码直接打交道。

其次用得非常多的是文件的完整性校验。
我们都经常从FTP站点上下载文件，在Internet不可信任的环境中，存在很多的不安全因素。如果你下载的session被人截获，并在下载的文件中插入危险代码，使得当你下载完毕运行程序的时候植入木马或者病毒或者其他非安全的代码。要验证文件的完整性，FTP server一般将整个文件夹打成包，如iso文件，然后同时给出md5校验码。当你下在该iso文件，在刻盘之前，运行md5程序产生一个md5校验码，如果和FTP Server上的校验码一样，就可以证明：在文件传输的过程中没有产生错误和任何修改。如果你信赖该FTP Server，那么你就可以放心使用该文件或资源。



MD5算法说明 

一、补位 
二、补数据长度 
三、初始化MD5参数 
四、处理位操作函数 
五、主要变换过程 
六、输出结果 


补位： 
MD5算法先对输入的数据进行补位，使得数据位长度LEN对512求余的结果是448。即数据扩展至K*512+448位。即K*64+56个字节，K为整数。 
具体补位操作：补一个1，然后补0至满足上述要求。 
补数据长度： 
用一个64位的数字表示数据的原始长度B，把B用两个32位数表示。这时，数 
据就被填补成长度为512位的倍数。 
初始化MD5参数： 
四个32位整数 (A,B,C,D) 用来计算信息摘要，初始化使用的是十六进制表 
示的数字 
A=0X01234567 
B=0X89abcdef 
C=0Xfedcba98 
D=0X76543210 

处理位操作函数： 
X，Y，Z为32位整数。 
F(X,Y,Z) = X&Y|NOT(X)&Z 
G(X,Y,Z) = X&Z|Y?(Z) 
H(X,Y,Z) = X xor Y xor Z 
I(X,Y,Z) = Y xor (X|not(Z)) 

主要变换过程： 
使用常数组T[1 ... 64]， T[i]为32位整数用16进制表示，数据用16个32位 
的整数数组M[]表示。 
具体过程如下： 

/* 处理数据原文 */ 
For i = 0 to N/16-1 do 

/*每一次，把数据原文存放在16个元素的数组X中. */ 
For j = 0 to 15 do 
Set X[j] to M[i*16+j]. 
end /结束对J的循环 

/* Save A as AA, B as BB, C as CC, and D as DD. 
*/ 
AA = A 
BB = B 
CC = C 
DD = D 

/* 第1轮*/ 
/* 以 [abcd k s i]表示如下操作 
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */ 

/* Do the following 16 operations. */ 
[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]