引言
MD5（Message-Digest Algorithm 5）是由Ron Rivest于1991年设计的经典密码学哈希函数，可将任意长度的输入消息压缩为128位的固定长度摘要。尽管MD5已不再推荐用于安全敏感场景（因其存在碰撞漏洞），但作为计算机科学史上的里程碑算法，其位运算技巧、轮函数设计与压缩迭代结构至今仍是学习密码学和哈希算法的绝佳范例。本文将用Java从零实现完整的MD5算法，详解每一步的数学原理与位级操作。
核心算法一：消息填充（Padding）
MD5要求输入消息的长度（比特数）满足 $length \equiv 448 \pmod{512}$，即填充后的消息长度比512的倍数少64位。填充规则：
- 在消息末尾追加一个
1比特 - 追加若干个
0比特，使长度满足上述同余式 - 最后追加64位的原始消息长度（低字节序）
/**
* MD5消息填充器
*/
class MD5Padder {
/**
* 对输入字节数组进行MD5标准填充
* @param input 原始消息
* @return 填充后的字节数组（长度是64的倍数）
*/
public static byte[] pad(byte[] input) {
long originalLengthBits = (long) input.length * 8;
// 计算需要填充的零字节数
// 总填充后长度 = 原始长度 + 1 + 零填充 + 8（长度字段）
// 需满足：(originalLength + 1 + zeroPadding + 8) % 64 == 0
int paddingLength = 64 - (input.length % 64);
if (paddingLength < 9) paddingLength += 64; // 确保有足够空间放1+长度
byte[] padded = new byte[input.length + paddingLength];
System.arraycopy(input, 0, padded, 0, input.length);
// 第1位填充为 0x80（即二进制 10000000）
padded[input.length] = (byte) 0x80;
// 零填充已在数组初始化时自动完成
// 最后8字节填充原始消息长度（低字节序 Little-Endian）
for (int i = 0; i < 8; i++) {
padded[padded.length - 8 + i] =
(byte) (originalLengthBits >>> (i * 8));
}
return padded;
}
}
核心算法二：初始化向量与辅助函数
MD5使用4个32位寄存器（A, B, C, D）存储中间哈希状态，以及4个非线性轮函数。
四个非线性函数（每轮使用一个）
| 轮次 | 函数 | 公式 | 逻辑含义 |
|---|---|---|---|
| 1 | F | $F(X,Y,Z) = (X \land Y) \lor (\lnot X \land Z)$ | 条件选择：X为真选Y，否则选Z |
| 2 | G | $G(X,Y,Z) = (X \land Z) \lor (Y \land \lnot Z)$ | 条件选择：Z为真选X，否则选Y |
| 3 | H | $H(X,Y,Z) = X \oplus Y \oplus Z$ | 奇偶校验：三者异或 |
| 4 | I | $I(X,Y,Z) = Y \oplus (X \lor \lnot Z)$ | 非条件选择 |
常量表 T
$T[i] = \lfloor 2^{32} \cdot |\sin(i + 1)| \rfloor$，即 $2^{32}$ 乘以正弦函数绝对值的整数部分，$i$ 从0到63。
/**
* MD5核心常量与辅助函数
*/
class MD5Constants {
// 初始化向量（低字节序）
public static final int A0 = 0x67452301;
public static final int B0 = 0xEFCDAB89;
public static final int C0 = 0x98BADCFE;
public static final int D0 = 0x10325476;
// T表：2^32 * |sin(i+1)|
public static final int[] T = new int[64];
static {
for (int i = 0; i < 64; i++) {
T[i] = (int) (long) (Math.abs(Math.sin(i + 1)) * (1L << 32));
}
}
// 每轮左循环移位的位数
public static final int[] S = {
7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22,
5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20,
4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21
};
// 每轮使用的消息字索引（对16个字的消息块的置换）
public static final int[] X_INDEX = {
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15,
1, 6, 11, 0, 5, 10, 15, 4, 9, 14, 3, 8, 13, 2, 7, 12,
5, 8, 11, 14, 1, 4, 7, 10, 13, 0, 3, 6, 9, 12, 15, 2,
0, 7, 14, 5, 12, 3, 10, 1, 8, 15, 6, 13, 4, 11, 2, 9
};
// 四个非线性函数
public static int F(int x, int y, int z) { return (x & y) | (~x & z); }
public static int G(int x, int y, int z) { return (x & z) | (y & ~z); }
public static int H(int x, int y, int z) { return x ^ y ^ z; }
public static int I(int x, int y, int z) { return y ^ (x | ~z); }
}
核心算法三：64步压缩轮函数
MD5对每512位（64字节）的消息块执行64步压缩运算，每步更新4个寄存器中的一个。
单步运算公式（以更新A为例）：
$$A = B + \text{leftrotate}((A + f(B, C, D) + X[k] + T[i]), s)$$
其中：
– $f$ 为当前轮次的非线性函数（F/G/H/I）
– $X[k]$ 为消息块的第 $k$ 个32位字
– $T[i]$ 为常量表第 $i$ 项
– $s$ 为左循环移位数
– $\text{leftrotate}$ 为32位左循环移位
/**
* MD5压缩函数核心实现
*/
class MD5Compressor {
/**
* 32位左循环移位
*/
private static int leftRotate(int value, int bits) {
return (value << bits) | (value >>> (32 - bits));
}
/**
* 处理单个512位消息块
* @param block 64字节消息块
* @param state 当前哈希状态 [A, B, C, D]
*/
public static void processBlock(byte[] block, int[] state) {
// 将64字节解析为16个32位整数（低字节序）
int[] X = new int[16];
for (int i = 0; i < 16; i++) {
X[i] = (block[i * 4] & 0xFF) |
((block[i * 4 + 1] & 0xFF) << 8) |
((block[i * 4 + 2] & 0xFF) << 16) |
((block[i * 4 + 3] & 0xFF) << 24);
}
int a = state[0], b = state[1], c = state[2], d = state[3];
// 64步压缩（4轮 × 16步）
for (int i = 0; i < 64; i++) {
int f, g;
if (i < 16) {
f = MD5Constants.F(b, c, d);
g = i;
} else if (i < 32) {
f = MD5Constants.G(b, c, d);
g = (5 * i + 1) % 16;
} else if (i < 48) {
f = MD5Constants.H(b, c, d);
g = (3 * i + 5) % 16;
} else {
f = MD5Constants.I(b, c, d);
g = (7 * i) % 16;
}
int temp = d;
d = c;
c = b;
b = b + leftRotate(a + f + X[g] + MD5Constants.T[i],
MD5Constants.S[i]);
a = temp;
}
// 将本轮结果累加到状态（模 $2^{32}$ 加法）
state[0] += a;
state[1] += b;
state[2] += c;
state[3] += d;
}
}
完整MD5哈希实现
/**
* 完整的MD5哈希算法实现
*/
public class MD5Hash {
/**
* 计算字节数组的MD5摘要
* @param input 输入消息
* @return 16字节（128位）摘要
*/
public static byte[] digest(byte[] input) {
// 1. 消息填充
byte[] padded = MD5Padder.pad(input);
// 2. 初始化状态
int[] state = {
MD5Constants.A0,
MD5Constants.B0,
MD5Constants.C0,
MD5Constants.D0
};
// 3. 逐块处理
for (int i = 0; i < padded.length; i += 64) {
byte[] block = new byte[64];
System.arraycopy(padded, i, block, 0, 64);
MD5Compressor.processBlock(block, state);
}
// 4. 输出128位摘要（低字节序）
byte[] digest = new byte[16];
for (int i = 0; i < 4; i++) {
digest[i * 4] = (byte) state[i];
digest[i * 4 + 1] = (byte) (state[i] >>> 8);
digest[i * 4 + 2] = (byte) (state[i] >>> 16);
digest[i * 4 + 3] = (byte) (state[i] >>> 24);
}
return digest;
}
/**
* 计算字符串的MD5摘要，返回32位十六进制字符串
*/
public static String hash(String input) {
byte[] digest = digest(input.getBytes());
StringBuilder sb = new StringBuilder(32);
for (byte b : digest) {
sb.append(String.format("%02x", b & 0xFF));
}
return sb.toString();
}
/**
* 验证测试向量
*/
public static void main(String[] args) {
// RFC 1321 标准测试向量
String[][] testVectors = {
{"", "d41d8cd98f00b204e9800998ecf8427e"},
{"a", "0cc175b9c0f1b6a831c399e269772661"},
{"abc", "900150983cd24fb0d6963f7d28e17f72"},
{"message digest", "f96b697d7cb7938d525a2f31aaf161d0"},
{"abcdefghijklmnopqrstuvwxyz",
"c3fcd3d76192e4007dfb496cca67e13b"},
{"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",
"d174ab98d277d9f5a5611c2c9f419d9f"},
{"12345678901234567890123456789012345678901234567890" +
"123456789012345678901234567890",
"57edf4a22be3c955ac49da2e2107b67a"}
};
System.out.println("MD5 测试向量验证：");
boolean allPass = true;
for (String[] tv : testVectors) {
String result = hash(tv[0]);
boolean pass = result.equals(tv[1]);
allPass &= pass;
System.out.println((pass ? "✓" : "✗") + " \"" +
(tv[0].length() > 30 ? tv[0].substring(0, 30) + "..." : tv[0]) +
"\" => " + result);
}
System.out.println("\n" + (allPass ? "全部通过！" : "存在失败用例"));
}
}
核心算法四：算法结构解析
Merkle-Damgård结构
MD5采用经典的Merkle-Damgård迭代结构：
- 消息填充：将输入填充为512位的整数倍
- 初始化向量：设定4个32位初始寄存器值
- 迭代压缩：每512位消息块触发一轮64步压缩函数
- 级联输出：最终寄存器值即为128位摘要
雪崩效应（Avalanche Effect）
MD5的设计目标之一是雪崩效应：输入的微小变化（如1比特翻转）应导致输出摘要约50%的比特位发生变化。这是通过以下机制实现的：
- 非线性轮函数（F/G/H/I）混淆输入比特
- 模 $2^{32}$ 加法产生进位传播
- 循环左移使高比特位影响低比特位，反之亦然
- 64步迭代使单比特影响扩散到整个状态
/**
* 雪崩效应演示：对比仅差1比特的两个输入的MD5输出
*/
class AvalancheDemo {
public static void main(String[] args) {
String s1 = "Hello World";
String s2 = "Hello Xorld"; // 第6字符 W(0x57) -> X(0x58)，差1比特
String h1 = MD5Hash.hash(s1);
String h2 = MD5Hash.hash(s2);
System.out.println("输入1: " + s1 + " => " + h1);
System.out.println("输入2: " + s2 + " => " + h2);
// 计算汉明距离
int diffBits = 0;
for (int i = 0; i < h1.length(); i++) {
int n1 = Integer.parseInt(h1.substring(i, i+1), 16);
int n2 = Integer.parseInt(h2.substring(i, i+1), 16);
diffBits += Integer.bitCount(n1 ^ n2);
}
System.out.println("输出汉明距离: " + diffBits + "/128 比特");
}
}
算法复杂度分析
| 操作 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 消息填充 | $O(n)$ | $O(n)$ | n为输入字节数，填充后长度 ≈ n + 64 |
| 单块压缩 | $O(1)$ | $O(1)$ | 固定64步，每步常数时间位运算 |
| 整体哈希 | $O(n)$ | $O(1)$ | 每64字节输入触发常数时间压缩 |
| 雪崩测试 | $O(n)$ | $O(1)$ | 两次哈希的额外开销 |
安全性说明与扩展
MD5的已知弱点
- 碰撞攻击：2004年，王小云团队首次在合理时间内找到MD5碰撞；2008年出现可构造的恶意碰撞（如伪造CA证书）
- 前缀碰撞：可保持前缀相同的情况下构造碰撞消息对
- 推荐替代：SHA-256、SHA-3、BLAKE2等更安全的哈希函数
学习价值
尽管MD5已不再安全，其设计思想仍具重要意义：
– Feistel-like轮结构：非线性函数+线性混合的经典范式
– 常量设计：$\sin$函数取整提供”无偏”伪随机常量
– 消息扩展：Merkle-Damgård结构影响了一代哈希函数设计
扩展实现
/**
* 扩展：基于MD5结构的HMAC-MD5消息认证码
*/
class HMAC_MD5 {
private static final int BLOCK_SIZE = 64; // 512 bits = 64 bytes
public static byte[] hmac(byte[] key, byte[] message) {
// 密钥填充/截断至块大小
byte[] k = new byte[BLOCK_SIZE];
if (key.length > BLOCK_SIZE) {
key = MD5Hash.digest(key);
}
System.arraycopy(key, 0, k, 0, key.length);
// ipad = 0x36重复, opad = 0x5C重复
byte[] ipad = new byte[BLOCK_SIZE];
byte[] opad = new byte[BLOCK_SIZE];
for (int i = 0; i < BLOCK_SIZE; i++) {
ipad[i] = (byte) (k[i] ^ 0x36);
opad[i] = (byte) (k[i] ^ 0x5C);
}
// HMAC = MD5(opad || MD5(ipad || message))
byte[] inner = concat(ipad, message);
byte[] innerHash = MD5Hash.digest(inner);
byte[] outer = concat(opad, innerHash);
return MD5Hash.digest(outer);
}
private static byte[] concat(byte[] a, byte[] b) {
byte[] result = new byte[a.length + b.length];
System.arraycopy(a, 0, result, 0, a.length);
System.arraycopy(b, 0, result, a.length, b.length);
return result;
}
}
总结
本文完整实现了MD5消息摘要算法，核心知识点包括：
– 消息填充机制：通过 0x80 + 零填充 + 长度字段，将任意输入对齐到512位块边界
– 四组非线性轮函数（F/G/H/I）：提供混淆层，实现雪崩效应
– 64步压缩迭代：每步使用消息字、正弦常量和循环移位更新状态
– Merkle-Damgård结构：将变长输入压缩为固定128位输出的迭代范式
完整代码通过RFC 1321全部7组测试向量验证，可直接用于教学演示、校验和计算等场景。对于安全敏感应用，请使用SHA-256或更新一代的哈希算法。
