MD5(HASH算法）

MD5

简介

将任意长度的"字符串"变为一个固定长度为128 bit的摘要值（hash值）。

算法

1、待加密信息处理

MD5将待加密的消息分割成每512bit为一个分组，得到：
$$N\ast 512+R$$
这里的R是剩余的位数。分为三种情况：

1、R = 0时，需要单独补上一个512 bit的分组，如图：
$$\underset{512bit}{\underbrace{1\underset{447bit}{\underbrace{000000...}}\underset{64bit}{\underbrace{输入消息的长度的二进制}}}}$$
2、R < 448时，则需要补位到448 bit，再在其后面添加64 bit消息长度的二进制。
$$\underset{448-R}{\underbrace{10000...}}\underset{64bit}{\underbrace{输入消息的长度的二进制}}$$

3、R >= 448时，除了补满这一个分组外，还需要再补一个512 bit的分组，如图：
$$\underset{512-R}{\underbrace{100...}}\underset{512bit}{\underbrace{\underset{448bit}{\underbrace{000...}}\underset{64bit}{\underbrace{输入消息的长度的二进制}}}}$$

2、MD5的链接变量及基本操作

MD5有四个32位的被称为链接变量的整数参数，这四个参数定义为A、B、C、D，其取值为：A=0x01234567，B=0x89abcdef，C=0xfedcba98，D=0x76543210。（每一个变量给出的数值是高字节存于内存低地址，低字节存于内存高地址，即大端字节序。在程序中变量A、B、C、D的值分别为0x67452301，0xEFCDAB89，0x98BADCFE，0x10325476）。

同时，MD5算法规定了四个非线性操作函数（& 是“与”，| 是“或”，~ 是“非”，^是“异或”）：

F(a,b,c) =(a&b)|((~a)&c)

G(a,b,c) =(a&c)|(b&(~c))

H(a,b,c) =a^b^c

I(a,b,c)=b^(a|(~c))

利用上面的四种操作，可以生成四个计算函数。首先声明四个中间变量a，b，c，d，赋值为：a = A，b = B，c = C，d = D；然后定义四个计算函数为：

FF(a, b, c, d, M[j], s, t_i)表示 a = b + ((a + F(b, c, d) + M[j] + t_i) <<< s)

GG(a, b, c, d, M[j], s, t_i)表示 a = b + ((a + G(b, c, d) + M[j] + t_i) <<< s)

HH(a, b, c, d, M[j], s, t_i)表示 a = b + ((a + H(b, c, d) + M[j] + t_i) <<< s)

II(a, b, c, d, M[j], s, t_i)表示 a = b + ((a + I(b, c, d) + M[j] + t_i) <<< s)
其中，M[j]为消息的第j个子分组(从0到15)，就是一组512位分组进来后，再按32位进行分组存储到M[j]中，<<<表示循环左移s位，常数t_i是4294967296*abs(sin(i))的整数部分，i取值从0到63。
循环左移的位数s定义为：

int[] s = 
{ 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 };

常数t_i从0~63定义为一个数组：

//常量t_i unsigned int(abs(sin(i+1))*(2pow32))
int[] k = {
    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 };

3、循环计算

定义好上述的四个计算函数后，就可以实现MD5的真正循环计算了。每次进入一个512位的分组，循环执行FF、GG、HH、II四种操作，每种操作执行16次，具体如下：当第一组512位的分组进来后：

​ //第一轮循环计算(i = 0~15,M[j]的j = i)

​ FF(a,b,c,d,M[0],7,0xd76aa478);

​ FF(d,a,b,c,M[1],12,0xe8c7b756);

​ FF(c,d,a,b,M[2],17,0x242070db);

​ FF(b,c,d,a,M[3],22,0xc1bdceee);

​ FF(a,b,c,d,M[4],7,0xf57c0faf);

​ FF(d,a,b,c,M[5],12,0x4787c62a);

​ FF(c,d,a,b,M[6],17,0xa8304613);

​ FF(b,c,d,a,M[7],22,0xfd469501) ;

​ FF(a,b,c,d,M[8],7,0x698098d8) ;

​ FF(d,a,b,c,M[9],12,0x8b44f7af) ;

​ FF(c,d,a,b,M[10],17,0xffff5bb1) ;

​ FF(b,c,d,a,M[11],22,0x895cd7be) ;

​ FF(a,b,c,d,M[12],7,0x6b901122) ;

​ FF(d,a,b,c,M[13],12,0xfd987193) ;

​ FF(c,d,a,b,M[14],17,0xa679438e) ;

​ FF(b,c,d,a,M[15],22,0x49b40821);

​ //第二轮循环计算(i =16~31，M[j]的j=(5 * i + 1) % 16)

​ GG(a,b,c,d,M[1],5,0xf61e2562);

​ GG(d,a,b,c,M[6],9,0xc040b340);

​ GG(c,d,a,b,M[11],14,0x265e5a51);

​ GG(b,c,d,a,M[0],20,0xe9b6c7aa) ;

​ GG(a,b,c,d,M[5],5,0xd62f105d) ;

​ GG(d,a,b,c,M[10],9,0x02441453) ;

​ GG(c,d,a,b,M[15],14,0xd8a1e681);

​ GG(b,c,d,a,M[4],20,0xe7d3fbc8) ;

​ GG(a,b,c,d,M[9],5,0x21e1cde6) ;

​ GG(d,a,b,c,M[14],9,0xc33707d6) ;

​ GG(c,d,a,b,M[3],14,0xf4d50d87) ;

​ GG(b,c,d,a,M[8],20,0x455a14ed);

​ GG(a,b,c,d,M[13],5,0xa9e3e905);

​ GG(d,a,b,c,M[2],9,0xfcefa3f8) ;

​ GG(c,d,a,b,M[7],14,0x676f02d9) ;

​ GG(b,c,d,a,M[12],20,0x8d2a4c8a);

​ //第三轮循环计算(i =32~47,M[j]的j=(3 * i + 5) % 16)

​ HH(a,b,c,d,M[5],4,0xfffa3942);

​ HH(d,a,b,c,M[8],11,0x8771f681);

​ HH(c,d,a,b,M[11],16,0x6d9d6122);

​ HH(b,c,d,a,M[14],23,0xfde5380c) ;

​ HH(a,b,c,d,M[1],4,0xa4beea44) ;

​ HH(d,a,b,c,M[4],11,0x4bdecfa9) ;

​ HH(c,d,a,b,M[7],16,0xf6bb4b60) ;

​ HH(b,c,d,a,M[10],23,0xbebfbc70);

​ HH(a,b,c,d,M[13],4,0x289b7ec6);

​ HH(d,a,b,c,M[0],11,0xeaa127fa);

​ HH(c,d,a,b,M[3],16,0xd4ef3085);

​ HH(b,c,d,a,M[6],23,0x04881d05);

​ HH(a,b,c,d,M[9],4,0xd9d4d039);

​ HH(d,a,b,c,M[12],11,0xe6db99e5);

​ HH(c,d,a,b,M[15],16,0x1fa27cf8) ;

​ HH(b,c,d,a,M[2],23,0xc4ac5665);

​ //第四轮循环计算(i = 48~63,M[j]的j=(7 * i) % 16)

​ II(a,b,c,d,M[0],6,0xf4292244) ;

​ II(d,a,b,c,M[7],10,0x432aff97) ;

​ II(c,d,a,b,M[14],15,0xab9423a7);

​ II(b,c,d,a,M[5],21,0xfc93a039) ;

​ II(a,b,c,d,M[12],6,0x655b59c3) ;

​ II(d,a,b,c,M[3],10,0x8f0ccc92) ;

​ II(c,d,a,b,M[10],15,0xffeff47d);

​ II(b,c,d,a,M[1],21,0x85845dd1) ;

​ II(a,b,c,d,M[8],6,0x6fa87e4f) ;

​ II(d,a,b,c,M[15],10,0xfe2ce6e0);

​ II(c,d,a,b,M[6],15,0xa3014314) ;

​ II(b,c,d,a,M[13],21,0x4e0811a1);

​ II(a,b,c,d,M[4],6,0xf7537e82) ;

​ II(d,a,b,c,M[11],10,0xbd3af235);

​ II(c,d,a,b,M[2],15,0x2ad7d2bb);

​ II(b,c,d,a,M[9],21,0xeb86d391);

4、结果

上述64步执行完成后，得到的a、b、c、d与第二组512位分组一起，再次执行相同的64步操作，又得到了新的a、b、c、d与第三组512位分组一起执行64步操作……，得到了新的a、b、c、d与最后一组512位分组一起执行64步操作，得到的新的a、b、c、d顺序级联，就是消息的128位hash值。