047_MD5算法（数据存储加密）

2.2 MD5算法的基本原理
MD5算法以512位分组来处理输入文本，每一分组又划分为16个32位子分组。算法的输出由4个32位分组组成，将它们级联形成一个128位散列值[5]。
第1步：:填充
MD5的第1步是在原消息中增加填充位，目的是使原消息长度等于一个值，即比512的倍数少64位。例如，如果原消息长度为1000位，则要填充472位，使消息长度为1472位，因为64+1472=1536，是512的倍数(1536=512*3)。
这样，填充后，原消息的长度为448位(比512少64)，960位(比1024少64位)，1472位(比1536少64位)，等等。

图2 填充过程
填充对用一个1位和多个0位进行填充。如果消息长度已经是448，则要填充512位，使长度变成960位。因此，填充长度为1～512的值。图2显示了填充过程。
第2步：添加长度
增加填充位后，下一步要计算机消息原长，将其加进填充后的消息末尾。先计算消息长度，不包括填充位(即增加填充位前的长度)。例如，如果原消息为1000位，则填充472位，使其变成比512的倍数(1536)少64位，但长度为1000，而不是1472。
这个消息原长表示为64位值，添加到加进填充后的消息末尾，如图3所示。如果消息长度超过264位(即64位无法表示，因为消息太长)，则只用长度的低64位，即等于计算length mod 264。

【www.think58.com计算机毕业论文网】 think58 [资料来源：http://THINK58.com]

我们看到，这时消息长度为512的倍数，成为要散列的消息。

图3 添加长度
第3步：将输入分成512位的块
下面要将输入分成512位的块，如图4所示。

图4 将输入分成512块
第4步：初始化链接变量
第4步要初始化四个链接变量，分别称为A，B，C，D，它们都是32位的数字，这些链接变量的初始十六进制值如表1所示，低的字节在前面。

表1 链接变量

注意低位的字节在前面指的是Little Bndian平台上内存中字节的排列方式，而在程序中书写时，要写成：
A=0x01234567
B=Ox89abcdef
C=Oxfedcba98
D=0x76543210
第5步：处理块
初始化之后，就要开始实际算法了。这是个循环，对消息中的多个512位块运行。
5.1步：将四个链接变量复制到四个变量a，b，c，d中，使a=A，b=B，c=C，d=D，如图5所示，

图5 将四个链接变量复制到四个变量中
实际上，这个算法将a，b，c，d组合成128位寄存器(abcd)，寄存器(abcd)在实际算法运算中保存中间结果和最终结果，如图6所示。

图6 链接变量抽象视图
5.2步：将当前512位块分解为16个子块，每个子块为32位，如图7所示。

图7 将当前512块分解为16个子块
5.3步：主循环有四轮，每轮很相似。每一轮的操作，都要处理一个块中的16个子块。每一轮的输入如下：(a) 16个子块；(b)变量a，b，c，d；(c)常量t，如图8所示。

图8 每一轮处理
这四轮中的第1步进行不同处理，其他步骤是相同的。
---每一轮有16个输入子块M[0]，M[1]，…，M[15]，或表示为M[i]，其中i为1～15。我们知道，每个子块为32位。 [版权所有：http://think58.com]
---t是个常量数组，包含64个元素，每个元素为32位。我们把数组t的元素表示为t[1]，t[2]，…，t[64]，或t[i]，其中i为1～64。由于有四轮，因此每一轮用64个t值中的16个。
下面总结这四轮的迭代。每一轮输出的中间和最终结果复制到寄存器abcd中，注意，每一轮有16个寄存器。
1)首先对b, c, d作一次非线性函数运算，这个运算在四轮中不同。
2)变量a加进第1步的输出(即寄存器abcd)。
3)消息子块M[i]加进第2步的输出(即寄存器abcd)。
4)常量t[i]加进第3步输出(即寄存器abcd)。
5)第4步的输出(即寄存器abcd)循环左移s位。
6)变量b加进第5步输出(即寄存器abcd)。
7)第6步的输出成为下一步的新abcd。
图9和图10显示了MD5操作过程。

图9 MD5主循环

图10 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的对应位是独立和均匀的，那么结果的每一位也是独立和均匀的，函数F是按逐位方式操作；如果X，那么Y，否则Z，函数H是逐位奇偶操作。 think58.com [资料来源：http://THINK58.com]
设Mi表示消息的第i个子分组(从0到15)。<<<S表示循环左移S位，则四种操作为：
FF(a,b,c,d,Mi,s,ti)表示 a=b+((a+(F(b,c,d)+Mi+ti)<<<s)
GG(a,b,c,d,Mi,s,ti)表示 a=b+((a+(G(b,c,d)+Mi+ti)<<<s)
HH(a,b,c,d,Mi,s,ti)表示 a=b+((a+(H(b,c,d)+Mi+ti)<<<s)
II(a,b,c,d,Mi,s,ti)表示 a=b+((a+(I(b,c,d)+Mi+ti)<<<s)
这四轮(64步)是：
第一轮
FF(a,b,c,d,M0,7,0xd76aa478)
FF(d,a,b,c,M1,12,0xe8c7b756)
FF(c,d,a,b,M2,17,0x242070db)
FF(b,c,d,a,M3,22,0xclbdceee)
FF(a,b,c,d,M4,7, 0xf57c0faf)
FF(d,a,b,c,M5,12,0x4787c62a)
FF(c,d,a,b,M6,17,0xa8304613)
FF(b,c,d,a,M7,22, 0xfd469501)
FF(a,b,c,d,M8,7, 0x698098d8)
FF(d,a,b,c,M9,12,0x8b44f7af)
FF(c,d,a,b,M10,17,0xffff5bb1)
FF(b,c,d,a,M11,22,0x895cd7be)
FF(a,b,c,d,M12,7, 0x6b901122)
FF(d,a,b,c,M13,12,0xfd987193)
FF(c,d,a,b,M14,17,0xa679438e)
FF(b,c,d,a,M15,22,0x49b40821)
第二轮
GG(a,b,c,d,M1,5,0xf61e2562)
GG(d,a,b,c,M6,9,0xc040b340) 内容来自think58

[资料来源：http://www.THINK58.com]

GG(c,d,a,b,M11,14,0x265e5a51)
GG(b,c,d,a,M0,20,0xe9b6c7aa)
GG(a,b,c,d,M5,5,0xd62f105d)
GG(d,a,b,c,M10,9,0x02441453)
GG(c,d,a,b,M15,14,0xd8a1e681)
GG(b,c,d,a,M4,20,0xe7d3dbc8)
GG(a,b,c,d,M9,5,0x21e1cde6)
GG(d,a,b,c,M14,9,0xc33707d6)
GG(c,d,a,b,M3,14,0xf4d50d87)
GG(b,c,d,a,M8,20,0x455a14ed)
GG(a,b,c,d,M13,5,0xa9e3e905)
GG(d,a,b,c,M2,9,0xfcefa3f8)
GG(c,d,a,b,M7,14,0x676f02d9)
GG(b,c,d,a,M12,20,0x8d2a4c8a)
第三轮
HH(a,b,c,d,M5,4,0x fffa3942)
HH(d,a,b,c,M8,11,0x8771f681)
HH(c,d,a,b,M11,16,0x6d9d6122)
HH(b,c,d,a,M14,23,0xfde5380c)
HH(a,b,c,d,M1,4,0xa4beea44)
HH(d,a,b,c,M4,11,0x4dbecfa9)
HH(c,d,a,b,M7,16,0xf6bb4b60)
HH(b,c,d,a,M10,23,0xbebfbc70)
HH(a,b,c,d,M13,4,0x289b7ec6)
HH(d,a,b,c,M0,11,0xeaa127fa)
HH(c,d,a,b,M3,16,0xd4ef3085)
HH(b,c,d,a,M6,23,0x04881d05)
HH(a,b,c,d,M9,4,0xd9d4d039)
HH(d,a,b,c,M12,11,0xe6db99e5)
HH(c,d,a,b,M15,16,0x1fa27cf8) 内容来自think58
HH(b,c,d,a,M2,23,0xc4ac5665)
第四轮
II(a,b,c,d,M0,6,0xf4292244)
II(d,a,b,c,M7,10,0x432aff97)
II(c,d,a,b,M14,15,0xab9423a7)
II(b,c,d,a,M5,21,0xfc93a039)
II(a,b,c,d,M12,6,0x655b59c3)
II(d,a,b,c,M3,10,0x8f0ccc92)
II(c,d,a,b,M10,15,0xffeff47d)
II(b,c,d,a,M1,21,0x85845dd1)
II(a,b,c,d,M8,6,0x6fa87e4f)
II(d,a,b,c,M15,10,0xfe2ce6e0)
II(c,d,a,b,M6,15,0xa3014314)
II(b,c,d,a,M13,21,0x4e0811a1)
II(a,b,c,d,M4,6,0xf7537e82)
II(d,a,b,c,M11,10,0xbd3ad235)
II(c,d,a,b,M2,15,0x2ad7d2bb)
II(b,c,d,a,M9,21,0xeb86d391)
所有这些完成之后，将A，B，C，D分别加上a，b，c，d，然后用下一分组数据继续运行算法，最后MD5算法产生128位的输出是A，B，C和D的级联，其中低字节始于A，高字节终于D。至此整个MD5算法处理结束。
think58

[资料来源：THINK58.com]