MD5算法详解

0x00 前言

MD5是一种哈希算法，用来保证信息的完整性。
就一段信息对应一个哈希值，且不能通过哈希值推出这段信息，而且还需要保证不存在任意两段不相同的信息对应同一个哈希值。不过MD5算法算出来的值也就16个字节（16*8=128，即128位），肯定存在相同的，找到另一个所花时间长短而已。

0x01 填充信息

在计算机中，数据存储都是二进制存储的，所以任意一个文件都是些二进制。
每个文件（消息）的大小（长短）都不一样，所以在计算MD5值之前，要将这些文件（消息）用特定内容填充到指定的情况为止。（这里的大小长度是指字节数）

填充的过程如下：
1.先判断文件（消息）的大小（长度） mod 512 == 448 mod 512 ，就是大小（长度）对512求余等于448。（这里的512、448是“位”为单位，转成“字节”就是64、56，即mod 64 == 56 mod 64）

2.如果大小（长度）满足 mod 512 == 448 mod 512，就在文件（消息）的末尾处添加64位（8字节）的值，值的内容是原消息的长度（以位为单位）

3.如果大小（长度）不满足要求，就执行以下操作：
（1）填充1个1
（2）填充0，直到满足满足过程的第一步。
注意：这里是以位为单位，假如是以字节为单位，第一个填充的是0x80（1000 0000），然后就填0x0
举例：消息内容为“gnubd”，就能得到以下内容

67 6E 62 75 64 80 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 28 00 00 00 00 00 00 00 

注意到最后面这里有个0x28，数8个字节，就是0x0000000000000028，刚刚好是十进制的40，消息的内容是5个字节，也就是40位，还要注意到这里是小端字节序存储

0x02 数据说明

填充信息满足要求后就要开始计算MD5值了，首先先把需要的东西先列出来：

DWORD md5::A = 0x67452301;
DWORD md5::B = 0xEFCDAB89;
DWORD md5::C = 0x98BADCFE;
DWORD md5::D = 0x10325476;

DWORD md5::T[64] = {
    0xD76AA478,0xE8C7B756,0x242070DB,0xC1BDCEEE,0xF57C0FAF,0x4787C62A,0xA8304613,0xFD469501,
    0x698098D8,0x8B44F7AF,0xFFFF5BB1,0x895CD7BE,0x6B901122,0xFD987193,0xA679438E,0x49B40821,
    0xF61E2562,0xC040B340,0x265E5A51,0xE9B6C7AA,0xD62F105D,0x02441453,0xD8A1E681,0xE7D3FBC8,
    0x21E1CDE6,0xC33707D6,0xF4D50D87,0x455A14ED,0xA9E3E905,0xFCEFA3F8,0x676F02D9,0x8D2A4C8A,
    0xFFFA3942,0x8771F681,0x6D9D6122,0xFDE5380C,0xA4BEEA44,0x4BDECFA9,0xF6BB4B60,0xBEBFBC70,
    0x289B7EC6,0xEAA127FA,0xD4EF3085,0x04881D05,0xD9D4D039,0xE6DB99E5,0x1FA27CF8,0xC4AC5665,
    0xF4292244,0x432AFF97,0xAB9423A7,0xFC93A039,0x655B59C3,0x8F0CCC92,0xFFEFF47D,0x85845DD1,
    0x6FA87E4F,0xFE2CE6E0,0xA3014314,0x4E0811A1,0xF7537E82,0xBD3AF235,0x2AD7D2BB,0xEB86D391
    };

DWORD md5::s[64]={
    7,12,17,22,7,12,17,22,7,12,17,22,7,12,17,22,
    5,9,14,20,5,9,14,20,5,9,14,20,5,9,14,20,
    4,11,16,23,4,11,16,23,4,11,16,23,4,11,16,23,
    6,10,15,21,6,10,15,21,6,10,15,21,6,10,15,21
};

DWORD md5::m[64]={
    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
    1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12,
    5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2,
    0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9
};

看上去很复杂，其实不是。
首先前4个数值A、B、C、D，它们原本的值是这样的：

A = 0x01234567
B = 0x89ABCDEF
C = 0xFEDCBA89
D = 0x76543210

为了保证ABCD4个值在内存中的显示情况为上面情况，所以要调整数字的位置，故实际情况是：

A = 0x67452301;
B = 0xEFCDAB89;
C = 0x98BADCFE;
D = 0x10325476;

0x03 处理信息

经过信息填充后，填充后的信息长度肯定是512位（64字节）的倍数，也就是说每512位（64字节）为1段可以分成n段，（n大于等于1），对于每一段信息（512位，64字节）又划分成16小段（每段32位，4个字节，用M表示）

对于每一段信息，都会经过下列的运算处理，共4种函数
FF(a,b,c,d,mj,s,ti)
GG(a,b,c,d,mj,s,ti)
HH(a,b,c,d,mj,s,ti)
II(a,b,c,d,mj,s,ti)

对于每种函数，都会执行16次，共执行64次。
函数的内容分别是：

void md5::FF(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp = F(b,c,d) + a + mj + ti;
    temp = (temp<<s)|(temp>>(32-s));
    a = b + temp; 
}

void md5::GG(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp = G(b,c,d) + a + mj + ti;
    temp = (temp<<s)|(temp>>(32-s));
    a = b + temp; 
}

void md5::HH(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp = H(b,c,d) + a + mj + ti;
    temp = (temp<<s)|(temp>>(32-s));
    a = b + temp; 
}

void md5::II(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp = I(b,c,d) + a + mj + ti;
    temp = (temp<<s)|(temp>>(32-s));
    a = b + temp; 
}

其中，F，G，H，I分别是：

DWORD md5::F(DWORD X,DWORD Y,DWORD Z){
    return (X&Y)|((~X)&Z);
}

DWORD md5::G(DWORD X,DWORD Y,DWORD Z){
    return (X&Z)|(Y&(~Z));
}

DWORD md5::H(DWORD X,DWORD Y,DWORD Z){
    return X^Y^Z;
}

DWORD md5::I(DWORD X,DWORD Y,DWORD Z){
    return Y^(X|(~Z));
}

接下来是参数说明，由于每个函数的参数具有相同的意义，所以只说一个就行了。
a，b，c，d 4个参数对应的值是周期变化的，周期长度为4，所以是：

FF(A,B,C,D,M[m[j]],s[j],T[j]);
FF(D,A,B,C,M[m[j+1]],s[j+1],T[j+1]);
FF(C,D,A,B,M[m[j+2]],s[j+2],T[j+2]);
FF(B,C,D,A,M[m[j+3]],s[j+3],T[j+3]);

M是上面每一段的16个小段了，其中m[j]表示每次函数处理的小段都不同，按照一定的顺序来处理每个小段，其中的顺序就在m中保存了。
s是循环左移的位数，也有一定顺序。
T是常数，共64个，意味着64次的函数调用都是用不同的数值
对于第一段消息（前512位（64个字节））传入的a，b，c，d的值是上面的ABCD4个有规律的值。
第一段消息处理完后（即4个函数各执行了16次之后），得到新的a，b，c，d的值，将它们分别加上原来a，b，c，d的值（即计算前的值），作为下一段消息（第2个512位（64个字节））的初始a，b，c，d的值。

当每段消息（512位，64个字节）都处理完之后，得到的a，b，c，d的值，按照地址的顺序从低到高打印对应的值，就是所求的MD5值。