MD5 即Message-Digest Algorithm 5 (信息-摘要算法5)。MD5 使用little-endian(小端模式)，输入任意不定长度信息，以 512-bit 进行分组，生成四个32-bit 数据，最后联合输出固定 128-bit 的信息摘要。
MD5 不是足够安全的。Hans Dobbertin在1996年找到了两个不同的512-bit 块,它们 在MD5 计算下产生相同的hash 值。至今还没有真正找到两个不同的消息，它们的MD5 的hash 值相等。
MD5 算法的基本过程为：
在长度为Kbits 的原始消息数据尾部填充长度为Pbits 的标识 100…0，1< P <=512 (即至少要填充1个bit)，使得填充后的消息位 数为：(K + P) mod 512=448。注意到当K mod 512 =448时，需要P= 512。
再向上述填充好的消息尾部附加K 值的低64位 (即K mod 2^64)， 最后得到一个长度位数为K + P+ 64= 0 (mod 512) 的消息。
把填充后的消息结果分割为L个512-bit 分组：Y0, Y1, …, YL-1。分组结果也可表示成N个32-bit 字M0, M1, …, MN-1，N= L * 16。
初始化一个128-bit 的MD 缓冲区，记为CVq，表示成4个32-bit 寄存器(A, B, C,D)；CV0= IV。迭代在MD 缓冲区进行，最后一 步的128-bit 输出即为算法结果。
初始状态为:
1 2 3 4 word A: 01 23 45 67 word B: 89 ab cd ef word C: fe dc ba 98 word D: 76 54 32 10
16进制数：
1 2 3 4 int a := 0x67452301 int b := 0xEFCDAB89 int c := 0x98BADCFE int d := 0x10325476
我们首先定义了四个辅助函数，每个函数都输入三个 32 位数字并产生一个 32 位数字作为输出。
1 2 3 4 F = (B and C) or ((not B) and D) G= (D and B) or ((not D) and C) H= B xor C xor D I= C xor (B or (not D))
然后使用正弦函数构建64元素的表K:
1 2 for i from 0 to 63 K[i] = floor(232 × abs (sin(i + 1)))
计算结果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 K[ 0.. 3] := { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee } K[ 4.. 7] := { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 } K[ 8..11] := { 0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be } K[12..15] := { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 } K[16..19] := { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa } K[20..23] := { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 } K[24..27] := { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed } K[28..31] := { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a } K[32..35] := { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c } K[36..39] := { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 } K[40..43] := { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 } K[44..47] := { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 } K[48..51] := { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 } K[52..55] := { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 } K[56..59] := { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 } K[60..63] := { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }
还有偏移量 s数组:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 // rotation constants private static final int S11 = 7; private static final int S12 = 12; private static final int S13 = 17; private static final int S14 = 22; private static final int S21 = 5; private static final int S22 = 9; private static final int S23 = 14; private static final int S24 = 20; private static final int S31 = 4; private static final int S32 = 11; private static final int S33 = 16; private static final int S34 = 23; private static final int S41 = 6; private static final int S42 = 10; private static final int S43 = 15; private static final int S44 = 21;
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 // 上述填充后的消息长度为N 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 */
以 A 的低字节开始，以D的高字节结束的 ABCD 就是产出的消息摘要。
在分析MD5的碰撞概率前先介绍下生日问题：
在随机选择的一群人当中有两人的生日相同的概率。如果一个房间里有23个或23个以上的人，那么至少有两个人的生日相同的概率要大于50%；对于60或者更多的人，这种概率要大于99%。计算与此相关的概率被称为生日问题，在这个问题之后的数学理论已被用于设计著名的密码攻击方法：生日攻击。
假设有n个人在同一房间内，不考虑特殊因素，例如闰年、双胞胎，并且假设一年365日出生概率是均匀分布的。首先计算每个人的生日日期都不同的概率为：
1 (365 * 364 *... *(635-n+1)) /(365^n)
当n=23时，p(23,365)大约是0.507。
对于MD5 碰撞问题：平均而言，如果不尝试故意创建冲突，则需要对大约 2^64 个值进行哈希处理才能获得它们之间的单个冲突。如果看两个任意值，碰撞概率只有2^128。
但是已经有密码学家编写了MD5 碰撞生成器的例子 。虽然这个生成器仅仅用于构造两个文件, MD5相同但内容不同,不是从MD5值逆推出的,但是说明MD5碰撞不可靠已经足以了。(也就是说，单纯的将MD5(PassWord) 作为验证手段是不安全的。此时在工程角度来看，这正说明了加盐MD5(Password+salt)的重要作用)。
