MD5(Message Digest Algorithm 5)是一种广泛使用的哈希函数,它用于生成128位的哈希值(也称为消息摘要)。MD5主要用于确保信息的完整性,即可以通过对数据生成的哈希值来验证数据是否被篡改。尽管MD5在过去被广泛应用,但由于它在安全性上的漏洞,现代加密中已逐渐被更安全的算法(如SHA-256)所取代。
MD5是一种哈希函数算法,哈希函数是一种用于消息认证的一种方式。消息认证是一种确定完整性并进行认证的技术。
消息认证
为了防止消息背篡改,发布消息的部门会在发布消息的同时发布该消息的哈希值,哈希值就是通过哈希函数计算计算出来的值。
哈希函数
- 函数的输入是任意长。
- 函数的输出是固定长。
- 单向不可逆。
整体流程
算法输入为任意长的消息,然后将这段任意长的消息分为512比特(64字节)长度的分组,给定一个128比特的初始化变量,然后每个被分成512比特的分组数据会分别经过一个HMD5压缩函数的运算,最终结果会生成128比特(16字节)的消息摘要(哈希值)。
算法处理过程
补位
信息计算前先要进行位补位,设补位后信息的长度为LEN(bit),则LEN%512 = 448(bit),即数据扩展至 K * 512 + 448(bit)。即K * 64+56(byte),K为整数。补位操作始终要执行,即使补位前信息的长度对512求余的结果是448。具体补位操作:补一个1,然后补0至满足上述要求。总共最少要补1bit,最多补512bit。
尾部追加信息长度
将输入信息的原始长度b(bit)表示成一个64-bit的数字,把它添加到上一步的结果后面(在32位的机器上,这64位将用2个字来表示并且低位在前)。当遇到b大于2^64这种极少的情况时,b的高位被截去,仅使用b的低64位。经过上面两步,数据就被填补成长度为512(bit)的倍数。也就是说,此时的数据长度是16个字(32byte)的整数倍。此时的数据表示为: M[0 … N-1] 其中的N是16的倍数。
初始化缓冲区
用一个四个字的缓冲器(A,B,C,D)来计算报文摘要,A,B,C,D分别是32位的寄存器,初始化使用的是十六进制表示的数字,注意低字节在前: word A: 01 23 45 67 word B: 89 ab cd ef word C: fe dc ba 98 word D: 76 54 32 10
以分组为单位迭代处理
对每个512位的数据块进行4轮加密处理,每轮使用不同的非线性函数和常数表。
非线性函数
MD5的每一轮处理使用了不同的非线性函数,这些函数的输入是B、C、D三个变量。以下是每轮使用的非线性函数(x, y, z是32位数):
- 第一轮:F(B, C, D) = (B & C) | (~B & D)
逻辑操作:选择B和C相同的位,或者选择B为0时的D位。 - 第二轮:G(B, C, D) = (B & D) | (C & ~D)
逻辑操作:选择B和D相同的位,或者选择C的位,D为0时。 - 第三轮:H(B, C, D) = B ⊕ C ⊕ D
逻辑操作:对B、C、D执行按位异或操作。 - 第四轮:I(B, C, D) = C ⊕ (B | ~D)
逻辑操作:对C执行按位异或,B或非D。
常数表
每轮中使用的常数表(称为T表)是由正弦函数的整数部分生成的64个常数 ,这些常数确保每一轮的操作是独立且混淆原始输入的。
每轮的操作
每轮都会对A、B、C、D进行64次操作,这些操作包括:
选择一个子块M:将512位的数据块分成16个32位的子块M0,M1,M2,,...,M15
。
计算临时变量K:使用当前轮的非线性函数,结合当前的A、B、C、D值、消息块和一个常量表中的值(这些常数是MD5的设计者精心选取的,来源于正弦函数的值)。
循环左移S:将计算出的临时结果进行循环左移,然后与B相加。
输出更新
每次64次操作完成后,A、B、C、D的值会更新,并累加到上一轮的结果中。最终,这些值组合在一起,形成最后的128位哈希值。
代码实现
md5.h
#ifndef MD5_H
#define MD5_Htypedef struct
{unsigned int count[2];unsigned int state[4];unsigned char buffer[64];
}MD5_CTX;void MD5Init(MD5_CTX* context);
void MD5Update(MD5_CTX* context, unsigned char* input, unsigned int inputlen);
void MD5Final(MD5_CTX* context, unsigned char digest[16]);#endif
md5.c
#include <string.h>
#include "md5.h"#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 + ac; \a = ROTATE_LEFT(a,s); \a += b; \}
#define GG(a,b,c,d,x,s,ac) \{ \a += G(b,c,d) + x + ac; \a = ROTATE_LEFT(a,s); \a += b; \}
#define HH(a,b,c,d,x,s,ac) \{ \a += H(b,c,d) + x + ac; \a = ROTATE_LEFT(a,s); \a += b; \}
#define II(a,b,c,d,x,s,ac) \{ \a += I(b,c,d) + x + ac; \a = ROTATE_LEFT(a,s); \a += b; \}void MD5Transform(unsigned int state[4], unsigned char block[64]);
void MD5Encode(unsigned char* output, unsigned int* input, unsigned int len);
void MD5Decode(unsigned int* output, unsigned char* input, unsigned int len);unsigned char PADDING[] = {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
};void MD5Init(MD5_CTX* context) {context->count[0] = 0;context->count[1] = 0;context->state[0] = 0x67452301;context->state[1] = 0xEFCDAB89;context->state[2] = 0x98BADCFE;context->state[3] = 0x10325476;
}
void MD5Update(MD5_CTX* context, unsigned char* input, unsigned int inputlen)
{unsigned int i = 0, index = 0, partlen = 0;index = (context->count[0] >> 3) & 0x3F;partlen = 64 - index;context->count[0] += inputlen << 3;if (context->count[0] < (inputlen << 3)) {context->count[1]++;}context->count[1] += inputlen >> 29;if (inputlen >= partlen) {memcpy(&context->buffer[index], input, partlen);MD5Transform(context->state, context->buffer);for (i = partlen; i + 64 <= inputlen; i += 64) {MD5Transform(context->state, &input[i]);}index = 0;}else {i = 0;}memcpy(&context->buffer[index], &input[i], inputlen - i);
}void MD5Final(MD5_CTX* context, unsigned char digest[16]) {unsigned int index = 0, padlen = 0;unsigned char bits[8];index = (context->count[0] >> 3) & 0x3F;padlen = (index < 56) ? (56 - index) : (120 - index);MD5Encode(bits, context->count, 8);MD5Update(context, PADDING, padlen);MD5Update(context, bits, 8);MD5Encode(digest, context->state, 16);
}
void MD5Encode(unsigned char* output, unsigned int* input, unsigned int len) {unsigned int i = 0, j = 0;while (j < len) {output[j] = input[i] & 0xFF;output[j + 1] = (input[i] >> 8) & 0xFF;output[j + 2] = (input[i] >> 16) & 0xFF;output[j + 3] = (input[i] >> 24) & 0xFF;i++;j += 4;}
}
void MD5Decode(unsigned int* output, unsigned char* input, unsigned int len) {unsigned int i = 0, j = 0;while (j < len) {output[i] = (input[j]) | (input[j + 1] << 8) | (input[j + 2] << 16) | (input[j + 3] << 24);i++;j += 4;}
}
void MD5Transform(unsigned int state[4], unsigned char block[64]) {unsigned int a = state[0];unsigned int b = state[1];unsigned int c = state[2];unsigned int d = state[3];unsigned int x[64];MD5Decode(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, 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;
}
main.c
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "md5.h" // 包含你的 MD5 实现int main() {MD5_CTX* context = (MD5_CTX*)malloc(sizeof(MD5_CTX));memset(context, 0, sizeof(context));if (context == NULL) {printf("Memory allocation failed.\n");return 1; // 分配失败,返回错误码}unsigned char digest[16];char input[] = "Bileton";int i;// 初始化 MD5 上下文MD5Init(context);// 更新 MD5 上下文,处理输入数据MD5Update(context, (unsigned char*)input, strlen(input));// 生成最终的 MD5 哈希值MD5Final(context, digest);// 打印 MD5 哈希值,格式化为 16 进制字符串printf("MD5(\"%s\") = ", input);for (i = 0; i < 16; i++) {printf("%02x", digest[i]); //MD5("Bileton") = 1483ab1f77ea828faa5f78514d2765c1}printf("\n");free(context);return 0;
}
github项目地址:https://github.com/talent518/md5/blob/master/md5.c
代码分析
MD5Update()
void MD5Update(MD5_CTX* context, unsigned char* input, unsigned int inputlen)
{unsigned int i = 0, index = 0, partlen = 0;// 计算当前 context->buffer 中已有数据的字节偏移量,即输入数据应该存储到缓冲区中的位置。// 右移三位相当于除以8,得到字节数,然后 & 0x3F 取模确保index处于0-63的范围。index = (context->count[0] >> 3) & 0x3F;// 当前块剩余空间大小partlen = 64 - index;// 将输入数据长度转换为比特,并累加到 context->count[0] 中。context->count[0] += inputlen << 3;// 如果 context->count[0] 发生了溢出(即新值变小了),说明输入的数据长度超过了 2^32 比特。if (context->count[0] < (inputlen << 3)) {// 高位部分记录溢出context->count[1]++;}// 将输入数据长度(字节数)的高位部分加到 count[1] 中。context->count[1] += inputlen >> 29;// 数据输入长度大于或等于分组长度if (inputlen >= partlen) {// 把数据copy到缓冲区memcpy(&context->buffer[index], input, partlen);// 进行轮加密MD5Transform(context->state, context->buffer);for (i = partlen; i + 64 <= inputlen; i += 64) {MD5Transform(context->state, &input[i]);}index = 0;}else {i = 0;}// 最后,将输入中剩余的部分(不足 64 字节)复制到 buffer 中,以便在下一次调用时继续处理。memcpy(&context->buffer[index], &input[i], inputlen - i);
}
总结
场景:数据长度小于 448 位(56 字节)。
假设输入数据长度为 N 字节,并且 N < 56。
第一步:调用 MD5Update
- 数据输入:假设输入的数据长度是 N 字节,N < 56。例如,输入数据是 20 字节。
- MD5 缓存处理:MD5Update 会把这 N 字节的数据填充到 context->buffer 中。由于 N 小于 56 字节,所以这次调用并不会触发 MD5Transform 计算,只是把数据暂存到 buffer 中。
- 效果:此时,buffer 中的内容为 20 字节的数据,buffer 的剩余空间是 64 - 20 = 44 字节。
第二步:调用 MD5Final 进行填充和处理
MD5Final 负责在数据的末尾进行填充,使数据长度变为 512 位(64 字节)的整数倍,以满足 MD5 的分块运算要求。
填充过程(这里要经过两次MD5Update):
- 添加 1 位:在数据末尾加上一个 1 位(0x80 表示)。这会占用 1 字节,并用零填充剩余的位。
- 补零到 448 位:在 1 位之后继续填充 0 直到达到 448 位(56 字节)。对于我们假设的 20 字节输入,填充后 buffer 里有 20(原始数据) + 1(0x80) + 35(0 值填充) = 56 字节。
- 附加原始数据长度:在 buffer 的末尾添加 8 字节,表示原始数据长度的二进制表示(单位是比特)。如果原始数据是 N 字节,则这里附加 N * 8 位的表示。这个长度信息用于表示数据的实际大小。
MD5Transform:
在填充和附加长度信息后,buffer 的总长度变为 64 字节(512 位),刚好满足 MD5Transform 的要求。
调用 MD5Transform 对填充后的 64 字节块进行 MD5 计算,更新 context->state,即内部的 MD5 状态。
Java调用MD5
我用Android写了一个按钮,按钮的功能是对一个指定的字符串生成其MAC(消息认证码),利用Toast把消息验证码输出。
Button Java_md5 = findViewById(R.id.java_md5);Java_md5.setOnClickListener(new View.OnClickListener() {@RequiresApi(api = Build.VERSION_CODES.UPSIDE_DOWN_CAKE)@Overridepublic void onClick(View v) {try {MessageDigest md = MessageDigest.getInstance("MD5");byte[] digest = md.digest("Bileton".getBytes());String md5 = bytesToHex(digest);Toast.makeText(MainActivity.this,md5,Toast.LENGTH_SHORT).show();} catch (NoSuchAlgorithmException e) {throw new RuntimeException(e);}}});
字节数组转换为字符串
public String bytesToHex(byte[] data){final char[] HEX_DIGITS = "0123456789abcdef".toCharArray();char[] result = new char[data.length*2];int c = 0;for(byte b:data){result[c++] = HEX_DIGITS[ (b>>4) & 0xf]; //保留高位result[c++] = HEX_DIGITS[b & 0xf]; //保留低位}return new String(result);}
效果如下
Python调用MD5
import hashlib# 要加密的字符串
md5_str = "Bileton"
# 创建md5对象
md5 = hashlib.md5()
# 更新要加密的数据,参数要是字节类型
md5.update(md5_str.encode('UTF-8'))
# 获取加密后的数据,以16进制表示
md5_hash = md5.hexdigest()
print(md5_str,"的哈希值为:",md5_hash)>>> Bileton 的哈希值为: 1483ab1f77ea828faa5f78514d2765c1