文档章节

MD5算法的C++实现

rise-worlds
 rise-worlds
发布于 2016/06/20 13:11
字数 2074
阅读 6
收藏 0
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 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


源代码下载: 点击下载

本文转载自:http://www.cnblogs.com/flying_bat/archive/2007/09/25/905133.html

rise-worlds

rise-worlds

粉丝 2
博文 1755
码字总数 0
作品 0
深圳
程序员
私信 提问
讲讲网络模块中加解密那点儿事--AES+BASE64

这次想来讲讲网络安全通信这一块,也就是网络层封装的那一套加密、解密,编码、解码的规则,不会很深入,但会大概将这一整块的讲一讲。 之所以想写这篇,是因为,最近被抽过去帮忙做一个 C+...

请叫我大苏
2018/08/04
0
0
dlib C++ Library 18.2 发布

dlib C++ Library 18.2 主要是为了改进灵活性以及对象检测工具的简化使用。 Dlib是一个使用现代C++技术编写的跨平台的通用库,遵守Boost Software licence. 主要特点如下: 1.完善的文档:每...

oschina
2013/06/01
1K
3
讲讲网络模块里加解密那点儿事--AES+BASE64

这次想来讲讲网络安全通信这一块,也就是网络层封装的那一套加密、解密,编码、解码的规则,不会很深入,但会大概将这一整块的讲一讲。 之所以想写这篇,是因为,最近被抽过去帮忙做一个 C+...

请叫我dasu
2018/08/06
0
0
C++ STL编程轻松入门 2

1.3.3 STL和GP,GP和OOP   正如前面所提到的,在STL的背后蕴含着泛型化程序设计(GP)的思想,在这种思想里,大部分基本算法被抽象,被泛化,独立于与之对应的数据结构,用于以相同或相近的...

暖冰
2015/11/21
0
0
看完这 7 条,模拟 C++ 新功能只是一个小目标!

但是,即使你无法使用这些功能,也不一定要放弃它们的好处。至少不用放弃全部。 有一些方法可以使用代码中新功能的思路,更准确地传达你的意图。 当然,这些方法肯定不如使用新版本C++本身的...

CSDN资讯
2018/09/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

tomcat 莫名奔溃问题

Apr 24, 2019 6:18:11 PM org.apache.coyote.AbstractProtocol pause INFO: Pausing ProtocolHandler ["http-nio-8080"] Apr 24, 2019 6:18:12 PM org.apache.coyote.AbstractProtocol pause......

mellen
32分钟前
2
0
组件开发规范 class名身份识别

组件需要通过一个组件共有的class来标识这个组件,外部调用的时候,可以通过锁定这个class来方便地改变组件的css样式。 设置方式 .my-checkbox { width: 20px; height: 20px; font-...

Carbenson
40分钟前
2
0
如何在工作中快速成长?致工程师的10个简单技巧

阿里妹导读:阿里有句非常经典的土话,“今天的最好表现,是明天的最低要求。”如何挖掘潜能、发现更好的自己?今天,阿里巴巴高级无线开发专家江建明将认知升级的方法总结出来,帮助你获得快...

阿里云云栖社区
59分钟前
3
0
PHP和Redis实现在高并发下的抢购及秒杀功能

抢购、秒杀是平常很常见的场景,面试的时候面试官也经常会问到,比如问你淘宝中的抢购秒杀是怎么实现的等等。 抢购、秒杀实现很简单,但是有些问题需要解决,主要针对两个问题: 一、高并发对...

xiaogg
今天
2
0
从数据上看:谁才是漫威的绝对C位

复联4上映了!这次比美国还早了两天。当然,我还没看,不会给你们剧透,当然也不想不剧透。 这一部不仅是灭霸这一线剧情的结局,也被认为漫威第三阶段的收官之作。据说此部之后,不少影迷熟知...

crossin
今天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部