# MD5算法
MD5 Message-Digest Algorithm（MD5消息摘要演算法）
节选翻译自https://www.rfc-editor.org/rfc/rfc1321
# 摘要
算法将任意长度的消息作为输入，并生成 作为输入的128位“指纹”或“消息摘要”的输出。 据推测，生成两条具有相同消息摘要的消息，或生成任何具有给定预指定目标消息摘要的消息是不可能的。 MD5算法用于数字签名应用程序，其中大文件必须以安全的方式“压缩”，然后才能在公钥加密系统下使用私钥（秘密）加密，例如RSA。
MD5算法设计为在32位机器上速度相当快。此外，MD5算法不需要任何大的替换表格；该算法可以相当紧凑地编码。
MD5算法是MD4消息摘要算法的扩展。MD5比MD4略慢，但更“保守”设计。MD5的设计初衷是因为人们认为MD4可能是 被设计得用更快的速度，而不是满足现有的批判性审查；因为MD4的设计速度非常快，就成功的密码分析风险而言，它是被攻击的“边缘”。
MD5稍微退缩了一点，为了很多而放弃了一点速度最终安全的可能性更大。它包含一些各种评论员提出的建议，并包含额外的优化。MD5算法正在被置于公共领域作为标准进行审查和可能采用。
2009年，中国科学院的谢涛和冯登国仅用了220.96的碰撞算法复杂度，破解了MD5的碰撞抵抗，该攻击在普通计算机上运行只需要数秒钟[3]。2011年，RFC 6151 禁止MD5用作金钥杂凑讯息鉴别码。
# 符号描述
x_i 表示 xi下标。x_{i+1}表示xi+1。 x^i 表示 xi，指数倍。
“+”表示增加字符。X <<< s 表示左移s位。not(X)表示X的补码。X v Y表示OR运算。 X xor Y表示异或XOR运算。XY表示AND运算。
# MD5算法描述
假设一串b-bit个消息为：（b为整数，可以是0，任意长度）
m_0 m_1 ... m_{b-1}
# 1. 填充bit
首先填充消息使其长度length mod 512 = 448，这样，保证消息长度和512的整数倍差64。
填充方式为：
- 向b+1位置填充"1"。就算长度刚好是上文的长度，这也会填充。
- 接着填充"0"直到满足长度符合上文。
这样可以保证至少一个bit，最多512个bit被填充进去。
# 2. 填充长度
在消息后面添加64bit，表示b的大小（指第一步填充bit前的长度）。如果b的大小超过2^64，那么只有低64位会被使用。
这样一来，整个信息的长度就是512的整数倍了。最终，消息字节数一定是16的整数倍（32-bit，32 * 16 = 512，16bit表示一个字符）。我们设置M[0 ... N - 1]代表消息的字符。N * 16 = 消息长度。
# 3. 初始化MD buffer
初始化一个四字符的buffer（A, B, C, D），以16进制表示，低位优先。
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
# 4. 用16字符的块进行运算
首先定义四个辅助方法，每个方法输入3个32-bit字符，并且输出一个32-bit字符。
F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))
F方法的意思是：if X then Y else Z。函数F本可以用+而不是v来定义，因为XY和not(X)不会有任何一位有相同的1。有趣的事，如果X、Y、Z中的bit是独立的和正交的，那么每个F函数的输出中bit都是独立和正交的。
方法G、H、I和F相同，他们以“bit并行”的方式从X、Y和Z中计算输出。这样的方式下，如果X、Y、Z的对应bit是正交和独立的，那么每一个G、H、I函数中输出的bit都会是正交的和独立的。值得注意的是，函数H是对于输入进行按位的“xor”函数。
这一步使用64-元素表T[1 ... 64]，其元素通过正弦函数获得。T[ i ]代表第i个元素，其整数部分等于4294967296次abs(sin(i))，i代表弧度。
作如下计算：
/* Process each 16-word block. */
For i = 0 to N/16-1 do
/* Copy block i into X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* of loop on j */
/* Save A as AA, B as BB, C as CC, and D as DD. */
AA = A
BB = B
CC = C
DD = D
/* Round 1. */
/* Let [abcd k s i] denote the operation
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 7 1] [DABC 1 12 2] [CDAB 2 17 3] [BCDA 3 22 4]
[ABCD 4 7 5] [DABC 5 12 6] [CDAB 6 17 7] [BCDA 7 22 8]
[ABCD 8 7 9] [DABC 9 12 10] [CDAB 10 17 11] [BCDA 11 22 12]
[ABCD 12 7 13] [DABC 13 12 14] [CDAB 14 17 15] [BCDA 15 22 16]
/* Round 2. */
/* Let [abcd k s i] denote the operation
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 1 5 17] [DABC 6 9 18] [CDAB 11 14 19] [BCDA 0 20 20]
[ABCD 5 5 21] [DABC 10 9 22] [CDAB 15 14 23] [BCDA 4 20 24]
[ABCD 9 5 25] [DABC 14 9 26] [CDAB 3 14 27] [BCDA 8 20 28]
[ABCD 13 5 29] [DABC 2 9 30] [CDAB 7 14 31] [BCDA 12 20 32]
/* Round 3. */
/* Let [abcd k s t] denote the operation
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 5 4 33] [DABC 8 11 34] [CDAB 11 16 35] [BCDA 14 23 36]
[ABCD 1 4 37] [DABC 4 11 38] [CDAB 7 16 39] [BCDA 10 23 40]
[ABCD 13 4 41] [DABC 0 11 42] [CDAB 3 16 43] [BCDA 6 23 44]
[ABCD 9 4 45] [DABC 12 11 46] [CDAB 15 16 47] [BCDA 2 23 48]
/* Round 4. */
/* Let [abcd k s t] denote the operation
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Do the following 16 operations. */
[ABCD 0 6 49] [DABC 7 10 50] [CDAB 14 15 51] [BCDA 5 21 52]
[ABCD 12 6 53] [DABC 3 10 54] [CDAB 10 15 55] [BCDA 1 21 56]
[ABCD 8 6 57] [DABC 15 10 58] [CDAB 6 15 59] [BCDA 13 21 60]
[ABCD 4 6 61] [DABC 11 10 62] [CDAB 2 15 63] [BCDA 9 21 64]
/* Then perform the following additions. (That is increment each
of the four registers by the value it had before this block
was started.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
end /* of loop on i */
# 5. 输出
输出digest是A，B，C，D。从A的低位开始，到D的高位结束，一共128位。
# 总结和MD4，MD5的不同
以下是MD4和MD5之间的区别：
- 增加了第四轮。
- 现在，每个步骤都有一个唯一的加法常数。
- 第2轮中的函数g从(XY v XZ v YZ)改为(XZ v Y not(Z))使g不那么对称。
- 现在，每个步骤都会添加到上一步的结果中。这促进更快的“雪崩效应”。
- 第2轮访问输入词的顺序和3被更改，使这些模式彼此不那么相似。
- 每轮的shift amounts进行了优化，以产生更快的“雪崩效应”。每一轮的shifts是不同的。