算法–基础–04–MD5

大家好，欢迎来到IT知识分享网。

算法–基础–04–MD5

1、什么是MD5

1.1、hash函数(散列函数/哈希函数)

把任意长度的输入 通过散列算法 变换成固定长度的输出，该输出就是散列值/哈希值。

1.2、MD5(Message-Digest Algorithm:信息-摘要算法)

1. 全称Message-Digest Algorithm(消息摘要算法)
2. 是一种hash函数，可以产生出一个128bit的散列值(大整数)，一般情况下，这个散列值是唯一的。也就是说一个字符串经过MD5后，会得到一个唯一的散列值。
3. 是一个不可逆的字符串变换算法：换句话说就是，即使你看到源程序和算法描述，也无法将一个MD5的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个。

1.3、MD5算法的不足。

随着计算机运算能力提高，找到”碰撞”是可能的。因此，在安全要求高的场合不使用MD5。

• 2004年，王小云教授证明MD5数字签名算法可以产生碰撞。
• 2007年，Marc Stevens，Arjen K. Lenstra和Benne de Weger进一步指出通过伪造软件签名，可重复性攻击MD5算法。研究者使用前缀碰撞法(chosen-prefix collision)，使程序前端包含恶意程序，利用后面的空间添上垃圾代码凑出同样的MD5 Hash值。
• 2007年，荷兰埃因霍芬技术大学科学家成功把2个可执行文件进行了MD5碰撞，使得这两个运行结果不同的程序被计算出同一个MD5。
• 2008年12月科研人员通过MD5碰撞成功生成了伪造的SSL证书，这使得在https协议中服务器可以伪造一些根CA的签名。

MD5被攻破后，在Crypto2008上， Rivest提出了MD6算法，该算法的Block size为512 bytes(MD5的Block Size是512 bits), Chaining value长度为1024 bits, 算法增加了并行 机制，适合于多核CPU。 在安全性上，Rivest宣称该算法能够抵抗截至目前已知的所有的 攻击(包括差分攻击)。

2、使用场景

2.1、MD5作用

主要用于确保信息传输完整一致

2.2、数字签名应用

对一段信息串(Message)产生所谓的指纹(fingerprint)，以防止被”篡改”。比方说，你将一段话写在一个文本文件中，并对这个文本文件产生一个MD5的值并记录在案，然后你可以传播这个文件给别人，别人如果修改了文件中的任何内容，你对这个文件重新计算MD5时就会发现和原先的MD5值不一样。如果再有一个第三方的认证机构，用MD5还可以防止文件作者的”抵赖”，这就是所谓的数字签名应用。

2.3、加密和解密应用

在很多操作系统中，用户的密码是以MD5值(或类似的其它算法)的方式保存的，用户Login的时候，系统是把用户输入的密码计算成MD5值，然后再去和系统中保存的MD5值进行比较，而系统并不”知道”用户的密码是什么。

3、原理

MD5算法的过程分为四步：填充，设置初始值，循环计算，拼接结果。

3.1、填充

3.2、设置初始值

3.2.1、4个参数

MD5有四个32位的被称作链接变量的整数参数，这是个参数我们定义为A、B、C、D其取值为：

A=0x0 B=0x89abcdef C=0xfedcba98 D=0x。 

但考虑到内存数据存储大小端的问题我们将其赋值为

A=0x B=0xefcdab89 C=0x98badcfe D=0x 

3.2.2、4个函数

MD5算法规定了四个非线性操作函数(&与，|或，~非，^异或)

F(X,Y,Z)=(X&Y)|((~X)&Z) G(X,Y,Z)=(X&Z)|(Y&(~Z)) H(X,Y,Z)=X^Y^Z I(X,Y,Z)=Y^(X|(~Z)) 

这些函数是这样设计的：如果X、Y和Z的对应位是独立和均匀的，那么结果的每一位也应是独立和均匀的。

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

FF(a, b, c, d, M[j], s, ti)表示 a = b +((a + F(b, c, d)+ Mj + ti)<<< s) GG(a, b, c, d, M[j], s, ti)表示 a = b +((a + G(b, c, d)+ Mj + ti)<<< s) HH(a, b, c, d, M[j], s, ti)表示 a = b +((a + H(b, c, d)+ Mj + ti)<<< s) II(a, b, c, d, M[j], s, ti)表示 a = b +((a + I(b, c, d)+ Mj + ti)<<< s) 

其中M[j]表示消息的第j个子分组(从0到15)，<<表示循环左移s，常数ti是*abs(sin(i))的整数部分，i取值从1到64，单位是弧度。

3.3、循环计算

定义好上述的四个计算函数后，就可以实现MD5的真正循环计算了。这个循环的循环次数为512位分组的个数。每次循环执行64次计算，上述4个函数每个16次，具体如下：

3.3.1、第一轮循环计算

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,0xdb); 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,0xa); FF(b,c,d,a,M[7],22,0xfd); FF(a,b,c,d,M[8],7,0xd8); 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,0x6b); FF(d,a,b,c,M[13],12,0xfd); FF(c,d,a,b,M[14],17,0xae); FF(b,c,d,a,M[15],22,0x49b40821); 

3.3.2、第二轮循环计算

 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,0x0); 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); 

3.3.3、第三轮循环计算

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); 

3.3.4、第四轮循环计算

II(a,b,c,d,M[0],6,0xf); 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,0xa); 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); 

3.3、拼接结果

处理完所有的512位的分组后，得到一组新的A,B,C,D的值，将这些值按ABCD的顺序级联，就得到了想要的MD5散列值。当然，输出依然要考虑内存存储的大小端问题。