wen MD5算法讲解 – 劫幻
MD5分析与代码实现
一、 MD5密码算法的特点
（1） 输出总为16字节
（2） 不可逆性
（3） 高度离散性
（4） 抗碰撞性
二、 常用实例
（1） 密码保护
（2） 文件完整性校验【用于抗碰撞性高，可用于下载文件时，查看文件的md5于下载后，在检验一次md5值，如果相同，则文件没有被修改，否则文件被修改了。从而实现文件完整性校验】
（3） 数字签名
（4） 云盘秒传【有时云盘上传时，在传输大文件的情况下，并不是真正实现秒传。其实只需计算一次文件的Md5值，然后再数据库中进行寻找，如果有相同的Md5,即直接引用即可】
三、 MD5算法的过程实现如下
（1） 数据补充
MD5密码算法，需要明文的长度为N*512+448bit，即数据的长度除以512位为448bit。但总长度要是512bit。其实很好奇，最后64bit去哪了。其实最后64bit需要单独补充，作用是用来计算原始的数据长度。其次，补充的位数为1-521之间。补充的第一位为1，其次补充0.直到满足mod512的结果为448。图示如下。
（2）标准幻数
标准幻数总共为4*4=16字节，看到这个16字节，是不是感觉到很熟悉。对的，它就跟MD5输出16字节息息相关。
A = 01234567 B = 89ABCDEF
C = FEDCBA98 D = 76543210
这就是开始的标准幻数，这些就是作为循环计算的初始值用的。但需要注意的是，在程序中用的是小端字节序，也就是说高字节在前，低字节在后。即为如下所示
A = 0x67452301 B = 0xEFCDB89
C = 0x98BADCFE D = 0x10325476
(3) 加密步骤
1.原始数据分为n个512位，即n个64字节
2.然后对每个512bit，即64字节分为16个4字节的数据。
|
4字节x[0] |
4字节x[1] |
4字节x[2] |
4字节x[3] |
|
4字节x[4] |
4字节x[5] |
4字节x[6] |
4字节x[7] |
|
4字节x[8] |
4字节x[9] |
4字节x[10] |
4字节x[11] |
|
4字节x[12] |
4字节x[13] |
4字节x[14] |
4字节x[15] |
3.准备4个函数
FF（A,B,C,D, X, S,AC）；GG（A,B,C,D, X, S,AC）；
HH（A,B,C,D, X, S,AC）；II（A,B,C,D, X, S,AC）；
4个标准幻数 分组的每4字节 固定常数
通过4个函数的逻辑运算于移位运算，改变第一个标准幻数的值，对于每4个字节，4个函数分别执行16次。
FF （A,B,C,D,x[0],S11,AC）
FF (D,A,B,C,x[1],S12,AC)
……..
GG (A,B,C,D,x[0],S21,AC)
……
HH (A,B,C,D,x[0],S31,AC)
……
II (A,B,C,D,x[0],S41,AC)
……
GG (A,B,C,D,x[0],S44,AC)
这就是一轮计算，一轮计算后，改变了4个标准幻数的值。形成新的A,B,C,D。然后新的A,B,C,D于原来的A,B,C,D相加，从而形成新的标准幻数。
整个过程重复进行，知道所有的64字节处理完，得到最后的标准幻数。得到的最后的标准幻数即为MD5值。
例：
A = 0Xbfcbfgce B = 0Xc4105a80
C = 0X02599277 D = 0X5c099ee2
MD5 = cefgcbbf805a10c477925202e29e095c
一、 C++代码实现如下
1 #include<iostream>
2 #include<string>
3 using namespace std;
4 #define shift(x, n) (((x) << (n)) | ((x) >> (32-(n))))//右移的时候，高位一定要补零，而不是补充符号位
5 #define F(x, y, z) (((x) & (y)) | ((~x) & (z)))
6 #define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
7 #define H(x, y, z) ((x) ^ (y) ^ (z))
8 #define I(x, y, z) ((y) ^ ((x) | (~z)))
9 #define A 0x67452301
10 #define B 0xefcdab89
11 #define C 0x98badcfe
12 #define D 0x10325476
13 //strBaye的长度
14 unsigned int strlength;
15 //A,B,C,D的临时变量
16 unsigned int atemp;
17 unsigned int btemp;
18 unsigned int ctemp;
19 unsigned int dtemp;
20 //常量ti unsigned int(abs(sin(i+1))*(2pow32))
21 const unsigned int k[]={
22 0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,
23 0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
24 0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
25 0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
26 0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
27 0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
28 0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
29 0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
30 0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
31 0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
32 0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
33 0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
34 0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
35 //向左位移数
36 const unsigned int s[]={7,12,17,22,7,12,17,22,7,12,17,22,7,
37 12,17,22,5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
38 4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,6,10,
39 15,21,6,10,15,21,6,10,15,21,6,10,15,21};
40 const char str16[]="0123456789abcdef";
41 void mainLoop(unsigned int M[])
42 {
43 unsigned int f,g;
44 unsigned int a=atemp;
45 unsigned int b=btemp;
46 unsigned int c=ctemp;
47 unsigned int d=dtemp;
48 for (unsigned int i = 0; i < 64; i++)
49 {
50 if(i<16){
51 f=F(b,c,d);
52 g=i;
53 }else if (i<32)
54 {
55 f=G(b,c,d);
56 g=(5*i+1)%16;
57 }else if(i<48){
58 f=H(b,c,d);
59 g=(3*i+5)%16;
60 }else{
61 f=I(b,c,d);
62 g=(7*i)%16;
63 }
64 unsigned int tmp=d;
65 d=c;
66 c=b;
67 b=b+shift((a+f+k[i]+M[g]),s[i]);
68 a=tmp;
69 }
70 atemp=a+atemp;
71 btemp=b+btemp;
72 ctemp=c+ctemp;
73 dtemp=d+dtemp;
74 }
75 /*
76 *填充函数
77 *处理后应满足bits≡448(mod512),字节就是bytes≡56（mode64)
78 *填充方式为先加一个1,其它位补零
79 *最后加上64位的原来长度
80 */
81 unsigned int* add(string str)
82 {
83 unsigned int num=((str.length()+8)/64)+1;//以512位,64个字节为一组
84 unsigned int *strByte=new unsigned int[num*16]; //64/4=16,所以有16个整数
85 strlength=num*16;
86 for (unsigned int i = 0; i < num*16; i++)
87 strByte[i]=0;
88 for (unsigned int i=0; i <str.length(); i++)
89 {
90 strByte[i>>2]|=(str[i])<<((i%4)*8);//一个整数存储四个字节，i>>2表示i/4 一个unsigned int对应4个字节，保存4个字符信息
91 }
92 strByte[str.length()>>2]|=0x80<<(((str.length()%4))*8);//尾部添加1 一个unsigned int保存4个字符信息,所以用128左移
93 /*
94 *添加原长度，长度指位的长度，所以要乘8，然后是小端序，所以放在倒数第二个,这里长度只用了32位
95 */
96 strByte[num*16-2]=str.length()*8;
97 return strByte;
98 }
99 string changeHex(int a)
100 {
101 int b;
102 string str1;
103 string str="";
104 for(int i=0;i<4;i++)
105 {
106 str1="";
107 b=((a>>i*8)%(1<<8))&0xff; //逆序处理每个字节
108 for (int j = 0; j < 2; j++)
109 {
110 str1.insert(0,1,str16[b%16]);
111 b=b/16;
112 }
113 str+=str1;
114 }
115 return str;
116 }
117 string getMD5(string source)
118 {
119 atemp=A; //初始化
120 btemp=B;
121 ctemp=C;
122 dtemp=D;
123 unsigned int *strByte=add(source);
124 for(unsigned int i=0;i<strlength/16;i++)
125 {
126 unsigned int num[16];
127 for(unsigned int j=0;j<16;j++)
128 num[j]=strByte[i*16+j];
129 mainLoop(num);
130 }
131 return changeHex(atemp).append(changeHex(btemp)).append(changeHex(ctemp)).append(changeHex(dtemp));
132 }
133
134 int main()
135 {
136 string ss;
137 // cin>>ss;
138 string s=getMD5("abc");
139 cout<<s;
140 return 0;
141 }
