#ant

The dreams in which I'm dying are the best I've ever had...

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个字(32byte)的整数倍。此时的数据表示为:

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


源代码下载:点击下载
在这里放上Vrcats修改的Qt版本:点击下载

posted on 2007-09-11 12:20 蚂蚁终结者 阅读(56952) 评论(121)  编辑 收藏 引用 所属分类: Encrypt

评论共2页: 1 2 

Feedback

# re: MD5算法的C++实现 2007-09-10 08:27 SmartPtr

.NET中产生HashCode用的貌似也是MD5算法???  回复  更多评论   

# re: MD5算法的C++实现 2007-09-10 09:56 Ray

其实头文件里的那些define都可以放到cpp里。
类接口也可以再简化一下。  回复  更多评论   

# re: MD5算法的C++实现 2007-09-10 11:25 蚂蚁终结者

@Ray
Thanks!
头文件的define确实该放在cpp里,是我疏忽了。
类的接口也正在优化...  回复  更多评论   

# re: MD5算法的C++实现 2007-09-10 11:45 蚂蚁终结者

@SmartPtr
Sorry!我对.Net不太熟悉呵呵  回复  更多评论   

# re: MD5算法的C++实现 2007-09-11 00:34 fanofcpp

不错的说,希望把优化的代码贴出来。  回复  更多评论   

# re: MD5算法的C++实现 2007-09-11 12:25 蚂蚁终结者

总算抽出时间修改了一下接口,只敢说比以前的好。实在想不出比较完美的,要是哪位有好的想法还望告知...
  回复  更多评论   

# re: MD5算法的C++实现 2007-09-11 13:27 Minidx全文检索

奇怪,怎么跑上面来了  回复  更多评论   

# Hi,哥们儿 2007-09-11 14:38 VrcatS

我在做一个手机的IM项目,没有合适的MD5库,试了一下你这个,哟,还真管用。于是我就顺手给你这库写了一个Qt的移植,可以直接用在Qt和Qtopia里头。在GCC4下面测过了,回头等我项目整测的时候还会测其他平台。下载点在这里HTTP://www.vrcats.com/md5.tar.gz
我的MSN:robot_liuzheng\@hotmail\.com有空交流  回复  更多评论   

# re: MD5算法的C++实现 2007-09-11 15:32 蚂蚁终结者

@VrcatS
有意思,thanks!
  回复  更多评论   

# re: MD5算法的C++实现 2007-09-12 23:46 ornaking

呵呵~~~还是受不了了~~~
辞职了~~~
看了你的帖子~~~好强啊~~~
以后多过来学习学习哈~~~  回复  更多评论   

# re: MD5算法的C++实现 2007-09-13 08:27 蚂蚁终结者

@ornaking
呵呵,共同学习  回复  更多评论   

# re: MD5算法的C++实现 2007-09-14 22:04 abc

代码在VC++ 2005上链接是发生错误!
错误 1 error LNK2019: 无法解析的外部符号 "public: class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > __thiscall MD5::toString(void)" (?toString@MD5@@QAE?AV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@XZ),该符号在函数 "void __cdecl PrintMD5(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &,class MD5 &)" (?PrintMD5@@YAXABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@AAVMD5@@@Z) 中被引用 test.obj
错误 2 error LNK2019: 无法解析的外部符号 "public: void __thiscall MD5::update(void const *,unsigned int)" (?update@MD5@@QAEXPBXI@Z),该符号在函数 "class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > __cdecl FileDigest(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)" (?FileDigest@@YA?AV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@ABV12@@Z) 中被引用 test.obj
错误 3 error LNK2019: 无法解析的外部符号 "public: __thiscall MD5::MD5(void)" (??0MD5@@QAE@XZ),该符号在函数 "class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > __cdecl FileDigest(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)" (?FileDigest@@YA?AV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@ABV12@@Z) 中被引用 test.obj
错误 4 error LNK2019: 无法解析的外部符号 "public: void __thiscall MD5::update(class std::basic_ifstream<char,struct std::char_traits<char> > &)" (?update@MD5@@QAEXAAV?$basic_ifstream@DU?$char_traits@D@std@@@std@@@Z),该符号在函数 _main 中被引用 test.obj
错误 5 error LNK2019: 无法解析的外部符号 "public: void __thiscall MD5::reset(void)" (?reset@MD5@@QAEXXZ),该符号在函数 _main 中被引用 test.obj
错误 6 error LNK2019: 无法解析的外部符号 "public: void __thiscall MD5::update(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)" (?update@MD5@@QAEXABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z),该符号在函数 _main 中被引用 test.obj
错误 7 error LNK2019: 无法解析的外部符号 "public: __thiscall MD5::MD5(class std::basic_ifstream<char,struct std::char_traits<char> > &)" (??0MD5@@QAE@AAV?$basic_ifstream@DU?$char_traits@D@std@@@std@@@Z),该符号在函数 _main 中被引用 test.obj
错误 8 error LNK2019: 无法解析的外部符号 "public: __thiscall MD5::MD5(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &)" (??0MD5@@QAE@ABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@Z),该符号在函数 _main 中被引用 test.obj
错误 9 fatal error LNK1120: 8 个无法解析的外部命令 C:\Documents and Settings\1\桌面\程设大赛\1003\Debug\1003.exe
  回复  更多评论   

# re: MD5算法的C++实现 2007-09-15 09:52 蚂蚁终结者

@abc
我最早就是在VC++ 2005上写的代码,在GCC上也测试过。
有可能你没有把md5.cpp加入工程,如果只用md5.h和test.cpp进行编译就会出现上面的8个error。
  回复  更多评论   

# re: MD5算法的C++实现 2007-09-15 14:19 abc

呵呵,这怎么可能没加?
今天重新生成了一遍莫名其妙地又好了……
感谢您的代码,我要急用所以没时间再研究md5算法,直接用您的代码构建程序后提交答案。  回复  更多评论   

# re: MD5算法的C++实现 2007-09-15 18:41 蚂蚁终结者

@abc
没问题就好。“您”字看得我好怪...  回复  更多评论   

评论共2页: 1 2 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理