MD5算法原理以及实现

MD5算法

MD5（单向散列算法） 的全称是Message-Digest Algorithm 5（信息-摘要算法）

MD5的功能:

输入任意长度的信息，经过处理，输出位128位的信息；不同的输入可以得到不同的结果(唯一性)

根据128位输出结果反推出输入信息是及其困难的(不可逆)

• 散列函数

散列函数是一种将输入数据映射到固定大小的散列值的函数。它通过对输入数据进行计算，生成一个唯一的散列值，用于快速查找或验证数据的完整性。

散列函数的特点和要求

1. 均匀分布:散列函数将输入数据均匀地分布在散列值的范围内，以避免碰撞(即多个不同的数据得到相同散列值)的发生–不过无法完全避免
2. 碰撞概率最小化

• memcpy

复制字符串，原理自查。

memcpy(需要赋值的char [],被复制的char1 []的起始位置，被复制的数据多少)；

C 库函数 – memcpy() | 菜鸟教程

大致过程

填充该数据

示例输入 message ,将其加上64bit 然后补充至512的 K倍。最后的64bit是表示的

就像这样。

然后每一个512bit进行HMD5的操作

接下来我们只需知道HMD5是什么操作就行了

这里的IV是初始的数据，128Bit是固定的

初始化缓冲区

算法实验128bit的缓冲区存放中间结果和最终哈希，128bit 可以看做四组32-bit字所占的Bit位。$Buffer_A,Buffer_B,Buffer_C,Buffer_D$. 每个缓冲区都以小端的方式存储数据. 将 4 块 Buffer 组合起来记为链接向量 CVi。

循环哈希

调用$H_{MD5}(mi,CVi)$数对魅族消息分组进行哈希计算

由上图可知，哈希函数计算分为4大步，每一大步又有16小伦次。，共进行64次运算。我们将512bit的M存储在uint_32 X[16]这个数组中。得到的128bit与之前的相加就行了。

每一轮轮函数

每轮进行16次计算，每次计算用特定方式调用T和X中的数据，详情看代码

CLS 表示循环左位移。

详情见代码，四轮每一个函数有区别的详情见代码

#include <iostream>
#include <string>
#include <stdint.h> // for uint* type
#include <limits.h> // for CHAR_BIT

using namespace std;

const uint32_t T[64] = {
	0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee, 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501,
	0x698098d8, 0x8b44f7af, 0xffff5bb1, 0x895cd7be, 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821,
	0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aa, 0xd62f105d, 0x2441453, 0xd8a1e681, 0xe7d3fbc8,
	0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed, 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a,
	0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c, 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70,
	0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x4881d05, 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665,
	0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039, 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1,
	0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1, 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391};

const unsigned int SHIFT[4][4]{
	{7, 12, 17, 22},
	{5, 9, 14, 20},
	{4, 11, 16, 23},
	{6, 10, 15, 21}};
//控制每一轮移位
const uint8_t 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 padmes(string message, uint8_t *mes1) {
    uint64_t mesL=message.length();
    uint64_t bitmesL=mesL*CHAR_BIT;
    int block =(bitmesL+64)/512+1;//计算填充后的数据量是512的block倍
    memcpy(mes1, message.c_str(), mesL);//将原数据拷贝到mes1中
for( int i =mesL;i<(block*64-8);i++){
	mes1[i]=PADDING[i-mesL];
}
    memcpy(mes1+(block*64-8), &bitmesL, 8);//存储长度数据

}


uint32_t Left_Rotate(uint32_t x, unsigned int n) {
	n&=31;
	return (x << n) | (x >> (32-n));
}
uint32_t FF(int i ,uint32_t b, uint32_t c, uint32_t d) {
	switch (i)
	{
		case 0:
			return (b & c) | (~b & d);
		case 1:
			return (b & d) | (c & (~d));
		case 2:
			return b ^ c ^ d;
		case 3:
			return c ^ (b | (~d));
	}
	return 0;
}
unsigned int Subs(int round_i,int i){
	switch ( round_i){
		case 0:
			return i;
		case 1:
			return (5*i+1)%16;
		case 2:
			return (3*i+5)%16;
		case 3:
			return (7*i)%16;
		
	}
	return 0;//控制输入的X[i]的位置
	}
void Round_F(int Round_i,uint32_t buffer[4],const uint32_t X[16]) {
	for (int i =0;i<16;i++){
		buffer[0]+=FF(Round_i,buffer[1],buffer[2],buffer[3]);
		buffer[0]+=X[Subs(Round_i,i)];
		buffer[0]+=T[i+Round_i*16];
		buffer[0]=Left_Rotate(buffer[0],SHIFT[Round_i][i%4]);
		buffer[0]+=buffer[1];
		uint32_t temp=buffer[3];
		buffer[3]=buffer[2];
		buffer[2]=buffer[1];
		buffer[1]=buffer[0];
		buffer[0]=temp;
		}
		return ;
	}
void oneMD5(uint32_t chain_vetor[4],const uint32_t X[16]) {
	uint32_t buffer[4];
	for (int i =0;i<4;i++){
		buffer[i]=chain_vetor[i];
	}//chain_vetor[4]代表初始的128bit数据是固定的
	for (int i =0;i<4;i++){
		Round_F(i,buffer,X);//完整的一次进行四次不同的操作，每次16轮。
	}
	for (int i =0;i<4;i++){
		chain_vetor[i]+=buffer[i];
	}
}/**/
__uint128_t MD5(string message){
	uint64_t mesL=message.length();
	uint64_t bitmesL=mesL*CHAR_BIT;
	uint64_t block =(bitmesL+64)/512+1;//计算填充后的数据量是512的block倍
	uint8_t mes1[block*64];//填充后的数据
	uint32_t chain_vetor[4]={0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476};//初始的128bit数据是固定的
	padmes(message, mes1);//填充数据
	uint32_t *X=new uint32_t[16];//每次进行512bit的操作
	for (int i =0;i<block;i++){
		memcpy(X,mes1+64*i,64);//每次512bit的操作
		oneMD5(chain_vetor,X);//进行一次hash操作
	}
	__uint128_t md5 = 0;
	for (int i = 0; i < 4; i++)
		md5 += (__uint128_t)chain_vetor[i] << (i * 32);

	delete[] X;
	return md5;
}
void MD5_Print(__uint128_t in)
{
	unsigned char *ptr = (unsigned char *)&in;
	for (int i = 0; i < 16; i++)
		printf("%02x", ptr[i]);
}

int main(){
	
	
	
	cout << "----------------- MD5 -----------------\n";
	cout << "-----------------------\n";
	string str;
	while (1)
	{
		cout << "text: ";
		getline(cin, str);
		__uint128_t md5 = MD5(str);

		cout << "result: ";
		MD5_Print(md5);
		if(str == "Please_let_me_go~") break;
		cout << "\n-----------------------\n";
	}

	return 0;
}