MD5（Message Digest Algorithm 5）
MD5（Message Digest Algorithm 5）是一种广泛使用的哈希函数，最初由罗纳德·李维斯特（Ronald Rivest）在1991年设计，旨在生成数据的128位（16字节）哈希值。MD5的主要作用是通过将任意长度的数据输入转换为固定长度的哈希值，来验证数据的完整性。
MD5的特点
- 输入长度不限：MD5可以接受任意长度的输入。
- 输出固定：无论输入数据长度如何，MD5都会生成128位的哈希值。
- 速度快：MD5的计算速度较快，在计算资源有限的情况下广泛应用。
- 广泛应用：MD5曾经广泛用于文件校验、数字签名、消息验证、密码存储等领域。
MD5的工作原理
MD5算法主要分为以下几个步骤：
-
填充消息：在原始消息的末尾填充一个1比特的“1”，然后再填充若干个“0”，使得填充后的消息长度恰好为64比特的倍数。最后在消息末尾附加一个64比特的数，表示原始消息的长度。
-
初始化MD缓冲区：MD5算法使用四个32位寄存器（A、B、C、D）作为缓冲区，分别初始化为特定的常量。
-
处理每个512比特块：将消息分成512比特的块，然后对每个块进行四轮复杂的位操作，每轮包括16个步骤。每一步使用逻辑函数和非线性函数，逐步将消息块混合到A、B、C、D寄存器中。
-
生成哈希值：处理完所有消息块后，将A、B、C、D的最终值连接起来，生成128位的哈希值。
安全性问题
尽管MD5曾经被广泛应用，但随着时间的推移，研究人员发现了其在安全性上的重大缺陷：
- 碰撞攻击：MD5存在严重的碰撞攻击漏洞，即不同的输入可能产生相同的哈希值。2004年，研究人员首次成功展示了如何生成MD5碰撞。
- 预映像攻击：虽然MD5的预映像攻击难度较高，但理论上仍然存在一定的风险。
C语言实现
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <stdint.h>
// MD5算法使用的四个常量初始化向量#define F(x, y, z) ((x & y) | (~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 ROTATE_LEFT(x, n) ((x << n) | (x >> (32 - n)))
#define FF(a, b, c, d, x, s, ac) { \ a += F(b, c, d) + x + (uint32_t)ac; \ a = ROTATE_LEFT(a, s); \ a += b; \}
#define GG(a, b, c, d, x, s, ac) { \ a += G(b, c, d) + x + (uint32_t)ac; \ a = ROTATE_LEFT(a, s); \ a += b; \}
#define HH(a, b, c, d, x, s, ac) { \ a += H(b, c, d) + x + (uint32_t)ac; \ a = ROTATE_LEFT(a, s); \ a += b; \}
#define II(a, b, c, d, x, s, ac) { \ a += I(b, c, d) + x + (uint32_t)ac; \ a = ROTATE_LEFT(a, s); \ a += b; \}
typedef struct { uint32_t state[4]; // ABCD四个状态变量 uint32_t count[2]; // 用来记录位数的计数器 uint8_t buffer[64]; // 输入缓冲区} MD5_CTX;
void MD5_Init(MD5_CTX *context);void MD5_Update(MD5_CTX *context, uint8_t *input, uint32_t inputLen);void MD5_Final(uint8_t digest[16], MD5_CTX *context);void MD5_Transform(uint32_t state[4], uint8_t block[64]);void Encode(uint8_t *output, uint32_t *input, uint32_t len);void Decode(uint32_t *output, uint8_t *input, uint32_t len);void MD5_memcpy(uint8_t *output, uint8_t *input, uint32_t len);void MD5_memset(uint8_t *output, int value, uint32_t len);
uint8_t PADDING[64] = { 0x80, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
// 初始化MD5上下文void MD5_Init(MD5_CTX *context) { context->count[0] = context->count[1] = 0; context->state[0] = 0x67452301; context->state[1] = 0xEFCDAB89; context->state[2] = 0x98BADCFE; context->state[3] = 0x10325476;}
// MD5主循环void MD5_Update(MD5_CTX *context, uint8_t *input, uint32_t inputLen) { uint32_t i, index, partLen;
index = (uint32_t)((context->count[0] >> 3) & 0x3F);
if ((context->count[0] += (inputLen << 3)) < (inputLen << 3)) { context->count[1]++; } context->count[1] += (inputLen >> 29);
partLen = 64 - index;
if (inputLen >= partLen) { MD5_memcpy(&context->buffer[index], input, partLen); MD5_Transform(context->state, context->buffer);
for (i = partLen; i + 63 < inputLen; i += 64) { MD5_Transform(context->state, &input[i]); }
index = 0; } else { i = 0; }
MD5_memcpy(&context->buffer[index], &input[i], inputLen - i);}
// 最终MD5哈希结果void MD5_Final(uint8_t digest[16], MD5_CTX *context) { uint8_t bits[8]; uint32_t index, padLen;
Encode(bits, context->count, 8);
index = (uint32_t)((context->count[0] >> 3) & 0x3F); padLen = (index < 56) ? (56 - index) : (120 - index); MD5_Update(context, PADDING, padLen); MD5_Update(context, bits, 8);
Encode(digest, context->state, 16);
MD5_memset((uint8_t*)context, 0, sizeof(*context));}
// MD5基本变换操作void MD5_Transform(uint32_t state[4], uint8_t block[64]) { uint32_t a = state[0], b = state[1], c = state[2], d = state[3]; uint32_t x[16];
Decode(x, block, 64);
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, 0x02441453); 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, 0x04881d05); 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;
MD5_memset((uint8_t*)x, 0, sizeof(x));}
// 编码，将32位整数转换为字节序列void Encode(uint8_t *output, uint32_t *input, uint32_t len) { uint32_t i, j; for (i = 0, j = 0; j < len; i++, j += 4) { output[j] = (uint8_t)(input[i] & 0xff); output[j + 1] = (uint8_t)((input[i] >> 8) & 0xff); output[j + 2] = (uint8_t)((input[i] >> 16) & 0xff); output[j + 3] = (uint8_t)((input[i] >> 24) & 0xff); }}
// 解码，将字节序列转换为32位整数void Decode(uint32_t *output, uint8_t *input, uint32_t len) { uint32_t i, j; for (i = 0, j = 0; j < len; i++, j += 4) { output[i] = ((uint32_t)input[j]) | (((uint32_t)input[j + 1]) << 8) | (((uint32_t)input[j + 2]) << 16) | (((uint32_t)input[j + 3]) << 24); }}
// 内存拷贝void MD5_memcpy(uint8_t *output, uint8_t *input, uint32_t len) { uint32_t i; for (i = 0; i < len; i++) { output[i] = input[i]; }}
// 内存设置void MD5_memset(uint8_t *output, int value, uint32_t len) { uint32_t i; for (i = 0; i < len; i++) { output[i] = (uint8_t)value; }}
// 打印哈希值void MD5_Print(uint8_t digest[16]) { for (int i = 0; i < 16; i++) { printf("%02x", digest[i]); } printf("\n");}
int main(int argc, char *argv[]) { MD5_CTX context; uint8_t digest[16]; uint8_t *string = (uint8_t *)"hello world";
MD5_Init(&context); MD5_Update(&context, string, strlen((char *)string)); MD5_Final(digest, &context);
printf("MD5 (\"%s\") = ", string); MD5_Print(digest);
return 0;}