MD5(Message-Digest Algorithm 5)是一种哈希算法，哈希后的结果固定为128位的二进制数。1996年后被证实存在弱点，可以被加以破解，2004年，证实无法防止碰撞，因此MD5无法适用于安全性认证。但是在数据一致性检验还是有着广泛的用途。
MD5算法步骤
补位
- 将需要处理的数据以
512bit为单位分组 - 在最后一组的数据后追加
1位值为1的终止标志位；若追加终止位前，此组已满512bit，则终止位追加在下一组 - 判断追加终止位后，当前组的剩余位数，若剩余位不足64位，则需另起一组，并在组尾留出
64bit(留做他用)，其他未填充空位补0 - 将原始数据的长度信息(以
bit为单位)放在留出的64bit位置，若数据长度信息超过64bit，则只取长度信息的低64bit
最终，数据被加工成 N*512 bit，每组数据在处理的时候，又会被分成 32bit
的 16 个小组，每一大组数据进行一次处理，有 N 组，则进行 N 次循环。
计算
MD5基本操作：
FF(a, b, c, d, Mj, s, ti)表示a = b + ((a + (F(b, c, d) + Mj + ti) <<< s)
GG(a, b, c, d, Mj, s, ti)表示a = b + ((a + (G(b, c, d) + Mj + ti) <<< s)
HH(a, b, c, d, Mj, s, ti)表示a = b + ((a + (H(b, c, d) + Mj + ti) <<< s)
II(a, b, c, d, Mj, s, ti)表示a = b + ((a + (I(b, c, d) + Mj + ti) <<< s)
其中：
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为常数，取值参考后续完整过程 -
ti值为4294967296*abs(sin(i))的整数部分，i的单位是弧度；取值范围1 ~ 16，故可视为常数 -
Mj每个小组数据的值位32bit，需按小端方式读取
再定义一组常数，作为 a, b, c, d 的初始值。
A = 0×01234567
B = 0×89abcdef
C = 0xfedcba98
D = 0×76543210
a = A, b = B, c = C, d = D
每组内的完整过程如下
第一轮
FF(a, b, c, d, M0, 7, 0xd76aa478)
FF(d, a, b, c, M1, 12, 0xe8c7b756)
FF(c, d, a, b, M2, 17, 0×242070db)
FF(b, c, d, a, M3, 22, 0xc1bdceee)
FF(a, b, c, d, M4, 7, 0xf57c0faf)
FF(d, a, b, c, M5, 12, 0×4787c62a)
FF(c, d, a, b, M6, 17, 0xa8304613)
FF(b, c, d, a, M7, 22, 0xfd469501)
FF(a, b, c, d, M8, 7, 0×698098d8)
FF(d, a, b, c, M9, 12, 0×8b44f7af)
FF(c, d, a, b, M10,17, 0xffff5bb1)
FF(b, c, d, a, M11,22, 0×895cd7be)
FF(a, b, c, d, M12, 7, 0×6b901122)
FF(d, a, b, c, M13,12, 0xfd987193)
FF(c, d, a, b, M14,17, 0xa679438e)
FF(b, c, d, a, M15,22, 0×49b40821)
第二轮
GG(a, b, c, d, M1, 5, 0xf61e2562)
GG(d, a, b, c, M6, 9, 0xc040b340)
GG(c, d, a, b, M11,14, 0×265e5a51)
GG(b, c, d, a, M0, 20, 0xe9b6c7aa)
GG(a, b, c, d, M5, 5, 0xd62f105d)
GG(d, a, b, c, M10, 9, 0×02441453)
GG(c, d, a, b, M15,14, 0xd8a1e681)
GG(b, c, d, a, M4, 20, 0xe7d3fbc8)
GG(a, b, c, d, M9, 5, 0×21e1cde6)
GG(d, a, b, c, M14, 9, 0xc33707d6)
GG(c, d, a, b, M3, 14, 0xf4d50d87)
GG(b, c, d, a, M8, 20, 0×455a14ed)
GG(a, b, c, d, M13, 5, 0xa9e3e905)
GG(d, a, b, c, M2, 9, 0xfcefa3f8)
GG(c, d, a, b, M7, 14, 0×676f02d9)
GG(b, c, d, a, M12,20, 0×8d2a4c8a)
第三轮
HH(a, b, c, d, M5, 4, 0xfffa3942)
HH(d, a, b, c, M8, 11, 0×8771f681)
HH(c, d, a, b, M11,16, 0×6d9d6122)
HH(b, c, d, a, M14,23, 0xfde5380c)
HH(a, b, c, d, M1, 4, 0xa4beea44)
HH(d, a, b, c, M4, 11, 0×4bdecfa9)
HH(c, d, a, b, M7, 16, 0xf6bb4b60)
HH(b, c, d, a, M10,23, 0xbebfbc70)
HH(a, b, c, d, M13, 4, 0×289b7ec6)
HH(d, a, b, c, M0, 11, 0xeaa127fa)
HH(c, d, a, b, M3, 16, 0xd4ef3085)
HH(b, c, d, a, M6, 23, 0×04881d05)
HH(a, b, c, d, M9, 4, 0xd9d4d039)
HH(d, a, b, c, M12,11, 0xe6db99e5)
HH(c, d, a, b, M15,16, 0×1fa27cf8)
HH(b, c, d, a, M2, 23, 0xc4ac5665)
第四轮
II(a, b, c, d, M0, 6, 0xf4292244)
II(d, a, b, c, M7, 10, 0×432aff97)
II(c, d, a, b, M14,15, 0xab9423a7)
II(b, c, d, a, M5, 21, 0xfc93a039)
II(a, b, c, d, M12, 6, 0×655b59c3)
II(d, a, b, c, M3, 10, 0×8f0ccc92)
II(c, d, a, b, M10,15, 0xffeff47d)
II(b, c, d, a, M1, 21, 0×85845dd1)
II(a, b, c, d, M8, 6, 0×6fa87e4f)
II(d, a, b, c, M15,10, 0xfe2ce6e0)
II(c, d, a, b, M6, 15, 0xa3014314)
II(b, c, d, a, M13,21, 0×4e0811a1)
II(a, b, c, d, M4, 6, 0xf7537e82)
II(d, a, b, c, M11,10, 0xbd3af235)
II(c, d, a, b, M2, 15, 0×2ad7d2bb)
II(b, c, d, a, M9, 21, 0xeb86d391)
最后分别于四个常数相加，作为下一轮输入或作为最终结果输出
a += A
b += B
c += C
d += D
输出
在完成所有数据计算后，将 a、b、c、d 分别输出。输出的时候需要注意低位自己先输出，高位字节后输出。比如 a =0xd9b456ab，则输出 ab56b4d9，因为 0xd9b456ab 在内存中为小端存储。
举例及实现
下面以字符串 "abcde" 为例进行讲解，先看完整算法如下所示：
#include <stdio.h>
#include <string.h>
#define ROTL32(dword, n) ((dword) << (n) ^ ((dword) >> (32 - (n))))
#define F(x, y, z) ((((y) ^ (z)) & (x)) ^ (z))
#define G(x, y, z) (((x) & (z)) | ((y) & (~z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))
#define I(x, y, z) ((y) ^ ((x) | (~z)))
#define FF(a, b, c, d, x, s, ac) { \
(a) += F((b), (c), (d)) + (x) + (ac); \
(a) = ROTL32((a), (s)); \
(a) += (b); \
}
#define GG(a, b, c, d, x, s, ac) { \
(a) += G((b), (c), (d)) + (x) + (ac); \
(a) = ROTL32((a), (s)); \
(a) += (b); \
}
#define HH(a, b, c, d, x, s, ac) { \
(a) += H((b), (c), (d)) + (x) + (ac); \
(a) = ROTL32((a), (s)); \
(a) += (b); \
}
#define II(a, b, c, d, x, s, ac) { \
(a) += I((b), (c), (d)) + (x) + (ac); \
(a) = ROTL32((a), (s)); \
(a) += (b); \
}
int main(int argc, const char * argv[]) {
// "abcde"
uint32_t src[16] = {
0x64636261,
0x8065,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0,
0x00000028,
0,
};
uint32_t state[4] = {
0x67452301,
0xefcdab89,
0x98badcfe,
0x10325476
};
unsigned a, b, c, d;
a = state[0];
b = state[1];
c = state[2];
d = state[3];
const uint32_t *x = src;
FF(a, b, c, d, x[ 0], 7, 0xd76aa478);
FF(d, a, b, c, x[ 1], 12, 0xe8c7b756);
FF(c, d, a, b, x[ 2], 17, 0x242070db);
FF(b, c, d, a, x[ 3], 22, 0xc1bdceee);
FF(a, b, c, d, x[ 4], 7, 0xf57c0faf);
FF(d, a, b, c, x[ 5], 12, 0x4787c62a);
FF(c, d, a, b, x[ 6], 17, 0xa8304613);
FF(b, c, d, a, x[ 7], 22, 0xfd469501);
FF(a, b, c, d, x[ 8], 7, 0x698098d8);
FF(d, a, b, c, x[ 9], 12, 0x8b44f7af);
FF(c, d, a, b, x[10], 17, 0xffff5bb1);
FF(b, c, d, a, x[11], 22, 0x895cd7be);
FF(a, b, c, d, x[12], 7, 0x6b901122);
FF(d, a, b, c, x[13], 12, 0xfd987193);
FF(c, d, a, b, x[14], 17, 0xa679438e);
FF(b, c, d, a, x[15], 22, 0x49b40821);
GG(a, b, c, d, x[ 1], 5, 0xf61e2562);
GG(d, a, b, c, x[ 6], 9, 0xc040b340);
GG(c, d, a, b, x[11], 14, 0x265e5a51);
GG(b, c, d, a, x[ 0], 20, 0xe9b6c7aa);
GG(a, b, c, d, x[ 5], 5, 0xd62f105d);
GG(d, a, b, c, x[10], 9, 0x2441453);
GG(c, d, a, b, x[15], 14, 0xd8a1e681);
GG(b, c, d, a, x[ 4], 20, 0xe7d3fbc8);
GG(a, b, c, d, x[ 9], 5, 0x21e1cde6);
GG(d, a, b, c, x[14], 9, 0xc33707d6);
GG(c, d, a, b, x[ 3], 14, 0xf4d50d87);
GG(b, c, d, a, x[ 8], 20, 0x455a14ed);
GG(a, b, c, d, x[13], 5, 0xa9e3e905);
GG(d, a, b, c, x[ 2], 9, 0xfcefa3f8);
GG(c, d, a, b, x[ 7], 14, 0x676f02d9);
GG(b, c, d, a, x[12], 20, 0x8d2a4c8a);
HH(a, b, c, d, x[ 5], 4, 0xfffa3942);
HH(d, a, b, c, x[ 8], 11, 0x8771f681);
HH(c, d, a, b, x[11], 16, 0x6d9d6122);
HH(b, c, d, a, x[14], 23, 0xfde5380c);
HH(a, b, c, d, x[ 1], 4, 0xa4beea44);
HH(d, a, b, c, x[ 4], 11, 0x4bdecfa9);
HH(c, d, a, b, x[ 7], 16, 0xf6bb4b60);
HH(b, c, d, a, x[10], 23, 0xbebfbc70);
HH(a, b, c, d, x[13], 4, 0x289b7ec6);
HH(d, a, b, c, x[ 0], 11, 0xeaa127fa);
HH(c, d, a, b, x[ 3], 16, 0xd4ef3085);
HH(b, c, d, a, x[ 6], 23, 0x4881d05);
HH(a, b, c, d, x[ 9], 4, 0xd9d4d039);
HH(d, a, b, c, x[12], 11, 0xe6db99e5);
HH(c, d, a, b, x[15], 16, 0x1fa27cf8);
HH(b, c, d, a, x[ 2], 23, 0xc4ac5665);
II(a, b, c, d, x[ 0], 6, 0xf4292244);
II(d, a, b, c, x[ 7], 10, 0x432aff97);
II(c, d, a, b, x[14], 15, 0xab9423a7);
II(b, c, d, a, x[ 5], 21, 0xfc93a039);
II(a, b, c, d, x[12], 6, 0x655b59c3);
II(d, a, b, c, x[ 3], 10, 0x8f0ccc92);
II(c, d, a, b, x[10], 15, 0xffeff47d);
II(b, c, d, a, x[ 1], 21, 0x85845dd1);
II(a, b, c, d, x[ 8], 6, 0x6fa87e4f);
II(d, a, b, c, x[15], 10, 0xfe2ce6e0);
II(c, d, a, b, x[ 6], 15, 0xa3014314);
II(b, c, d, a, x[13], 21, 0x4e0811a1);
II(a, b, c, d, x[ 4], 6, 0xf7537e82);
II(d, a, b, c, x[11], 10, 0xbd3af235);
II(c, d, a, b, x[ 2], 15, 0x2ad7d2bb);
II(b, c, d, a, x[ 9], 21, 0xeb86d391);
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
unsigned char result1[32] ={0};
memcpy(result1, state, 32);
for (int i = 0; i < 16; i++) {
printf("%02x", result1[i]);
} // ab56b4d92b40713acc5af89985d4b786
printf("\n");
return 0;
}
对上述算法进行讲解，首先定义算法用到的宏定义 ROTL32 表示循环左移动 F，FF 为下面用到的运算。数组中的数据则为处理后的原始数据 a b c d e 的编码分别 0x61 0x62 0x63 0x64 0x65。故数组src[0] = 0x64636261，src[1] = 0x8065(65为符号e，80添加了结束位) ，0x28 位原始信息的长度。整个运算过程在内存中可表示为下图：
图1-0 "abcde" MD5的过程在内存中的表现形式
总结
此篇文章主要讲解了 MD5 的算法过程，以及代码实现，但是并没有给出通用版的实现，通用版的实现可以在上例代码中稍加修改实现。现在计算机一般都是小端存储方式，MD5 在计算的时候也使用了小端规则，如果是大端的存储方式，上述代码运行的结果并不正确，需要注意。此篇文章大部分都为我好友@gojan所写，在此表示感谢。这是一系列文章的其中一篇，你可以在这儿Encode & Decode集序找到他其他的兄弟。
