MD5算法讲解 – 劫幻

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 }
hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » MD5算法讲解 – 劫幻