Hash算法实现之MD5

2016-04-10

本文简单介绍一下MD5 HASH的底层实现原理

1. MD5简介

MD5是RSA数据安全公司开发的一种单向散列算法，具体特点是：

无论多长多随意的信息，最后都转换成一个固定长度（128bit）的散列值；
对于大量不同的信息，最后出来的散列值呈平均分布；
对于特定的一个信息，最后出来的散列值都是相同的。
已知原数据和其MD5值，想找到一个具有相同MD5值的数据（即伪造数据）是非常困难的。

2. MD5算法应用

2-1. 一致性验证

MD5典型的应用是对一段meaasge产生信息摘要（message digest），以防止被篡改，例如，平时我们在网上下载软件，而这些软件已经注入了病毒，如果不进行文件域原始发布商的一致性校验的化，很可能造成一定损失。所以平时下载的软件一般包含一个md5文件，用来验证文件的一致性

2-2. 安全访问认证

Unix系统中对用户的密码是一MD5（或其他类似算法）经过hash运算后存储在文件系统中的，在用户登陆时，将密码进行MD5 Hash运算，然后再去和文件系统中的MD5值进行比对。通过这样的步骤，系统会在不知道用户明文密码的情况下实现密码的验证工作。

3. MD5算法实现

3-1. 第一步-填充

首先对信息进行填充，使其位数对512求余的结果是448，因此填充后的信息的位长（Bites length）是N*512+448，填充的规则是在信息的后面，添加1个1和无数个0，知道满足要求为止。

3-2. 第二步-补足长度

将原数据的长度转换位64bit的数值，如果长度超过64bit，只保留最后的64bit，将该64bit数值添加到第一步的信息后面，这样就形成了一个(N+1)*512 bit的信息。

3-3. 第三步-初始化变量

用四个变量，分别位A、B、C、D，均为32bit长，初始化为：

A=(01234567)16
B=(89ABCDEF)16
C=(FEDCBA98)16
D=(76543210)16

3-4. 第四步-操作定义

首先定义四个辅助函数(其中 &-与，|-或，～-非，^-亦或，X、Y、Z均为32bit)
1
2
3
4
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))
定义四个操作(<<< s表示循环左移s位，Mj)

FF(a,b,c,d,Mj,s,ti) 表示 b+((a+F(b,c,d)+Mj+T(i))<<<s)
GG(a,b,c,d,Mj,s,ti) 表示 b+((a+G(b,c,d)+Mj+T(i))<<<s)
HH(a,b,c,d,Mj,s,ti) 表示 b+((a+H(b,c,d)+Mj+T(i))<<<s)
II(a,b,c,d,Mj,s,ti) 表示 b+((a+I(b,c,d)+Mj+T(i))<<<s)
其中T(i)(i取值1-64)等于abs(sin(i))的4294967296倍(4294967296等于2的32次方)的整数部分,i为弧度(rad)。即T(i) = 232*abs(sin(i)) (1=<i<=64)

3-5. 第五步-分組处理

总共进行4论(N+1)，对于前面得到的512(N+1) bit信息，按没512bit进行分组，分成Y1，Y2….YN+1，对于每个Yi分解长M0……M15，每32bit一组。然后进行4*(N+1)论处理。

其中:
a=A=(01234567)16、b=B=(89ABCDEF)16、c=C=(FEDCBA98)16、d=D=(76543210)16

第一轮：

a=FF(a,b,c,d,M0,7,0xd76aa478)
b=FF(d,a,b,c,M1,12,0xe8c7b756)
c=FF(c,d,a,b,M2,17,0x242070db)
d=FF(b,c,d,a,M3,22,0xc1bdceee)
a=FF(a,b,c,d,M4,7,0xf57c0faf)
b=FF(d,a,b,c,M5,12,0x4787c62a)
c=FF(c,d,a,b,M6,17,0xa8304613)
d=FF(b,c,d,a,M7,22,0xfd469501)
a=FF(a,b,c,d,M8,7,0x698098d8)
b=FF(d,a,b,c,M9,12,0x8b44f7af)
c=FF(c,d,a,b,M10,17,0xffff5bb1)
d=FF(b,c,d,a,M11,22,0x895cd7be)
a=FF(a,b,c,d,M12,7,0x6b901122)
b=FF(d,a,b,c,M13,12,0xfd987193)
c=FF(c,d,a,b,M14,17,0xa679438e)
d=FF(b,c,d,a,M15,22,0x49b40821)

第二轮：

a=GG(a,b,c,d,M1,5,0xf61e2562)
b=GG(d,a,b,c,M6,9,0xc040b340)
c=GG(c,d,a,b,M11,14,0x265e5a51)
d=GG(b,c,d,a,M0,20,0xe9b6c7aa)
a=GG(a,b,c,d,M5,5,0xd62f105d)
b=GG(d,a,b,c,M10,9,0x02441453)
c=GG(c,d,a,b,M15,14,0xd8a1e681)
d=GG(b,c,d,a,M4,20,0xe7d3fbc8)
a=GG(a,b,c,d,M9,5,0x21e1cde6)
b=GG(d,a,b,c,M14,9,0xc33707d6)
c=GG(c,d,a,b,M3,14,0xf4d50d87)
d=GG(b,c,d,a,M8,20,0x455a14ed)
a=GG(a,b,c,d,M13,5,0xa9e3e905)
b=GG(d,a,b,c,M2,9,0xfcefa3f8)
c=GG(c,d,a,b,M7,14,0x676f02d9)
d=GG(b,c,d,a,M12,20,0x8d2a4c8a)

第三轮：

a=HH(a,b,c,d,M5,4,0xfffa3942)
b=HH(d,a,b,c,M8,11,0x8771f681)
c=HH(c,d,a,b,M11,16,0x6d9d6122)
d=HH(b,c,d,a,M14,23,0xfde5380c)
a=HH(a,b,c,d,M1,4,0xa4beea44)
b=HH(d,a,b,c,M4,11,0x4bdecfa9)
c=HH(c,d,a,b,M7,16,0xf6bb4b60)
d=HH(b,c,d,a,M10,23,0xbebfbc70)
a=HH(a,b,c,d,M13,4,0x289b7ec6)
b=HH(d,a,b,c,M0,11,0xeaa127fa)
c=HH(c,d,a,b,M3,16,0xd4ef3085)
d=HH(b,c,d,a,M6,23,0x04881d05)
a=HH(a,b,c,d,M9,4,0xd9d4d039)
b=HH(d,a,b,c,M12,11,0xe6db99e5)
c=HH(c,d,a,b,M15,16,0x1fa27cf8)
d=HH(b,c,d,a,M2,23,0xc4ac5665)

第四轮：

a=II(a,b,c,d,M0,6,0xf4292244)
b=II(d,a,b,c,M7,10,0x432aff97)
c=II(c,d,a,b,M14,15,0xab9423a7)
d=II(b,c,d,a,M5,21,0xfc93a039)
a=II(a,b,c,d,M12,6,0x655b59c3)
b=II(d,a,b,c,M3,10,0x8f0ccc92)
c=II(c,d,a,b,M10,15,0xffeff47d)
d=II(b,c,d,a,M1,21,0x85845dd1)
a=II(a,b,c,d,M8,6,0x6fa87e4f)
b=II(d,a,b,c,M15,10,0xfe2ce6e0)
c=II(c,d,a,b,M6,15,0xa3014314)
d=II(b,c,d,a,M13,21,0x4e0811a1)
a=II(a,b,c,d,M4,6,0xf7537e82)
b=II(d,a,b,c,M11,10,0xbd3af235)
c=II(c,d,a,b,M2,15,0x2ad7d2bb)
d=II(b,c,d,a,M9,21,0xeb86d391)

3-6. 第六步-输出

#最后：

a = a+A
b = b+B
c = c+C
d = d+D
abcd即为最终的结果，共计128bit