MD5 算法流程

先通过下面的命令对 md5算法有个感性的认识：

$ md5sum /tmp/1.txt 
1dc792fcaf345a07b10248a387cc2718  /tmp/1.txt

$ md5sum // 从键盘输入，ctrl-d 结束输入
hello, world!
910c8bc73110b0cd1bc5d2bcae782511  -
1
2
3
4
5
6

从上面可以看到，一个文件或一段数据的 md5值是一个字符串，这个字符串一共有 32个字符，每个字符都是一个十六进制字符。因此，如果每 8个字符一组的话，可以分为 4组。同时，每 8个字符可以看成一个 4字节整数的十六进制表示。所以，md5值是 4个 4字节整数的十六进制表示。

有了这样的认识，可能大概已经猜到，md5其实是通过某种运算将任意长度的数据转换为 4个 4字节整数。
这 4个 4字节整数在 md5里面叫作链接变量（或者叫作状态），可以用 A, B, C, D表示，在初始时，这 4个变量的取值是：

A = 0x01234567
B = 0x89abcdef
C = 0xfedcba98
D = 0x76543210
1
2
3
4

现在先暂停一下，来关注数据长度的问题。 按照要求，md5算法是以 64字节分组为单位来处理输入文本的，因此当数据长度不是 64字节整数倍的时候，需要在数据的末尾进行填充，使其长度为 64字节的整数倍。填充的方法是先在数据的末尾添加一个 bit的 1，再接若干个 bit的 0，然后再附加上一个 64 bit的数，这个数的取值是填充前数据的长度。

至此，在经过填充（如果需要填充的话）后，md5算法处理的数据长度一定是 64字节的整数倍。接下来，就进入了算法的主循环，循环的次数是数据中 64字节分组的数目。

在每次循环之前，需要将 A, B, C，D这 4个变量复制到另外的 4个变量中，即：A到 a、B到 b、C到 c、D到 d，在每次循环中，计算操作是在a，b，c，d这 4个变量上进行的，计算完后还需要将 a，b，c，d加回到原来的A，Ｂ，Ｃ，Ｄ上，以便进行下一次循环，由此可见 md5算法是存在较长的数据依赖的，不太好用向量进行优化。

每次循环有 4轮计算，每一轮进行 16次运算，这里的运算比较复杂，后面用宏定义进行表示。

具体来说，每次循环有 64次运算，第一轮包含第 1到 16次运算，使用的宏是 FF()，第二轮包含第 17到 32次运算，使用的宏是 GG()，第三轮包含第 33到 48次运算，使用的宏是 HH()，第四轮包含第 49到 64次运算，使用的宏是 II()。

这 4个宏的定义分别是：
1)FF()：

FF(a, b, c, d, Mj, s, ti) 表示 a = b + ((a + F(b, c, d) +Mj + ti) <<< s)
1

其中

F(X, Y, Z) = (X & Y) | ((~X) & Z)
1

2)GG()：

GG(a, b, c, d, Mj, s, ti) 表示 a = b + ((a + G(b, c, d) +Mj + ti) <<< s)
1

其中

G(X, Y, Z) = (X & Z) | (Y & (~Z))
1

3)HH：

HH(a, b, c, d, Mj, s, ti) 表示 a = b + ((a + H(b, c, d) +Mj + ti) <<< s)
1

其中

H(X, Y, Z) = X ^ Y ^ Z
1

4)II()：

II(a, b, c, d, Mj, s, ti) 表示 a = b + ((a + I(b, c, d) +Mj + ti) <<< s)
1

其中

I(X, Y, Z) = Y ^ (X | (~Z))
1

上述宏定义中的 a，b，c，d之前已提到，这里不再解释，Mj是 64字节分组中第 j个 4字节整数（ 0<=j<=15），ti是常量，<<<是循环左移， s也是常量。

下面具体罗列出这 64次运算的表达式，其中 x[j]为数据分组的第 j个 4字节整数：

// 第一轮
  FF (a, b, c, d, x[ 0], 7, 0xd76aa478); /* 1 */
  FF (d, a, b, c, x[ 1], 12, 0xe8c7b756); /* 2 */
  FF (c, d, a, b, x[ 2], 17, 0x242070db); /* 3 */
  FF (b, c, d, a, x[ 3], 22, 0xc1bdceee); /* 4 */
  FF (a, b, c, d, x[ 4], 7, 0xf57c0faf); /* 5 */
  FF (d, a, b, c, x[ 5], 12, 0x4787c62a); /* 6 */
  FF (c, d, a, b, x[ 6], 17, 0xa8304613); /* 7 */
  FF (b, c, d, a, x[ 7], 22, 0xfd469501); /* 8 */
  FF (a, b, c, d, x[ 8], 7, 0x698098d8); /* 9 */
  FF (d, a, b, c, x[ 9], 12, 0x8b44f7af); /* 10 */
  FF (c, d, a, b, x[10], 17, 0xffff5bb1); /* 11 */
  FF (b, c, d, a, x[11], 22, 0x895cd7be); /* 12 */
  FF (a, b, c, d, x[12], 7, 0x6b901122); /* 13 */
  FF (d, a, b, c, x[13], 12, 0xfd987193); /* 14 */
  FF (c, d, a, b, x[14], 17, 0xa679438e); /* 15 */
  FF (b, c, d, a, x[15], 22, 0x49b40821); /* 16 */

// 第二轮
GG (a, b, c, d, x[ 1], 5, 0xf61e2562); /* 17 */
  GG (d, a, b, c, x[ 6], 9, 0xc040b340); /* 18 */
  GG (c, d, a, b, x[11], 14, 0x265e5a51); /* 19 */
  GG (b, c, d, a, x[ 0], 20, 0xe9b6c7aa); /* 20 */
  GG (a, b, c, d, x[ 5], 5, 0xd62f105d); /* 21 */
  GG (d, a, b, c, x[10], 9,  0x2441453); /* 22 */
  GG (c, d, a, b, x[15], 14, 0xd8a1e681); /* 23 */
  GG (b, c, d, a, x[ 4], 20, 0xe7d3fbc8); /* 24 */
  GG (a, b, c, d, x[ 9], 5, 0x21e1cde6); /* 25 */
  GG (d, a, b, c, x[14], 9, 0xc33707d6); /* 26 */
  GG (c, d, a, b, x[ 3], 14, 0xf4d50d87); /* 27 */
  GG (b, c, d, a, x[ 8], 20, 0x455a14ed); /* 28 */
  GG (a, b, c, d, x[13], 5, 0xa9e3e905); /* 29 */
  GG (d, a, b, c, x[ 2], 9, 0xfcefa3f8); /* 30 */
  GG (c, d, a, b, x[ 7], 14, 0x676f02d9); /* 31 */
  GG (b, c, d, a, x[12], 20, 0x8d2a4c8a); /* 32 */

// 第三轮
HH (a, b, c, d, x[ 5], 4, 0xfffa3942); /* 33 */
  HH (d, a, b, c, x[ 8], 11, 0x8771f681); /* 34 */
  HH (c, d, a, b, x[11], 16, 0x6d9d6122); /* 35 */
  HH (b, c, d, a, x[14], 23, 0xfde5380c); /* 36 */
  HH (a, b, c, d, x[ 1], 4, 0xa4beea44); /* 37 */
  HH (d, a, b, c, x[ 4], 11, 0x4bdecfa9); /* 38 */
  HH (c, d, a, b, x[ 7], 16, 0xf6bb4b60); /* 39 */
  HH (b, c, d, a, x[10], 23, 0xbebfbc70); /* 40 */
  HH (a, b, c, d, x[13], 4, 0x289b7ec6); /* 41 */
  HH (d, a, b, c, x[ 0], 11, 0xeaa127fa); /* 42 */
  HH (c, d, a, b, x[ 3], 16, 0xd4ef3085); /* 43 */
  HH (b, c, d, a, x[ 6], 23,  0x4881d05); /* 44 */
  HH (a, b, c, d, x[ 9], 4, 0xd9d4d039); /* 45 */
  HH (d, a, b, c, x[12], 11, 0xe6db99e5); /* 46 */
  HH (c, d, a, b, x[15], 16, 0x1fa27cf8); /* 47 */
  HH (b, c, d, a, x[ 2], 23, 0xc4ac5665); /* 48 */
  
// 第四轮
II (a, b, c, d, x[ 0], 6, 0xf4292244); /* 49 */
  II (d, a, b, c, x[ 7], 10, 0x432aff97); /* 50 */
  II (c, d, a, b, x[14], 15, 0xab9423a7); /* 51 */
  II (b, c, d, a, x[ 5], 21, 0xfc93a039); /* 52 */
  II (a, b, c, d, x[12], 6, 0x655b59c3); /* 53 */
  II (d, a, b, c, x[ 3], 10, 0x8f0ccc92); /* 54 */
  II (c, d, a, b, x[10], 15, 0xffeff47d); /* 55 */
  II (b, c, d, a, x[ 1], 21, 0x85845dd1); /* 56 */
  II (a, b, c, d, x[ 8], 6, 0x6fa87e4f); /* 57 */
  II (d, a, b, c, x[15], 10, 0xfe2ce6e0); /* 58 */
  II (c, d, a, b, x[ 6], 15, 0xa3014314); /* 59 */
  II (b, c, d, a, x[13], 21, 0x4e0811a1); /* 60 */
  II (a, b, c, d, x[ 4], 6, 0xf7537e82); /* 61 */
  II (d, a, b, c, x[11], 10, 0xbd3af235); /* 62 */
  II (c, d, a, b, x[ 2], 15, 0x2ad7d2bb); /* 63 */
  II (b, c, d, a, x[ 9], 21, 0xeb86d391); /* 64 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

在每次循环中，当执行完上述 64次运算后，还要将最后得到的 a, b, c, d分别加回到原来的 A, B, C, D中，即：

  A += a;
  B += b;
  C += c;
  D += d;
1
2
3
4

这样在经过一次循环后，A， B， C，D都被更新了，然后进行下一次循环，直到处理完所有的 64字节分组。

最后的输出是 A、B、C、D这 4个 4字节变量的十六进制，也即数据的 md5值，但值得注意的是输出的字符串是 A，B， C， D这 4个变量的小端序 16进制表示。

参考资料：
1.md5算法的 RFC：rfc1321