MD5消息摘要算法学习

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