MD5算法原理

MD5消息摘要算法，属Hash算法一类。MD5算法对输入任意长度的消息进行运行，产生一个128位的消息摘要。

具体实现可参考博客

https://blog.csdn.net/sinat_27933301/article/details/79538169

和官方标准RFC1321

https://tools.ietf.org/html/rfc1321

算法实现

一些常量的定义



//定义循环右移函数

#define RPTATE_SHIFT(x, n) (((x) << (n)) | ((x) >> (32-(n))))

//定义F,G,H,I函数

#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)))

//定义寄存器word A,B,C,D

#define A 0x67452301

#define B 0xefcdab89

#define C 0x98badcfe

#define D 0x10325476

//strBaye的长度

unsigned int strlength = 0;

//A,B,C,D的临时变量

int tempA = 0, tempB = 0, tempC = 0, tempD = 0;

//定义k数组，用于压缩函数

const unsigned int k[] = {

	0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,

	0x698098d8,0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,0xa679438e,0x49b40821,

	0xf61e2562,0xc040b340,0x265e5a51,0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,

	0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,0xfcefa3f8,0x676f02d9,0x8d2a4c8a,

	0xfffa3942,0x8771f681,0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,0xbebfbc70,

	0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,

	0xf4292244,0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,0xffeff47d,0x85845dd1,

	0x6fa87e4f,0xfe2ce6e0,0xa3014314,0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391 };

//用数组存储向左位移数，方便操作

//每一行 表示一轮的左位移数 ， 根据 RFC 1321的标准参数来做

const unsigned 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进制

const char str16[] = "0123456789abcdef";

这些定义包括标准里的 A,B,C,D word， F,G,H,I函数，用于压缩参数的常量值，这些先定义下来，方便后面写程序，防止出错

MD5算法——C++实现

主要函数getMD5Code

此暗示通过传入一个字符串，返回对此字符串进行MD4处理得到的摘要字符串ik，这是一个主要的流程。

首先初始化最终的变量A，B，C，D，然后进行填充操作，进行压缩操作，最后转换为16进制哈希值。



string getMD5Code(string source) {

	//初始化

	tempA = A;

	tempB = B;

	tempC = C;

	tempD = D;

	//把string变成二进制， 同时附加填充位

	unsigned int *strByte = padding(source);

	//   对于i = 0到N / 16-1 将块i复制到X.

	//     对于j = 0到15做

	//       将X [j]设置为M [i * 16 + j]。

	//   进行压缩函数操作 

	for (int i = 0; i<strlength / 16; i++) {

		unsigned int num[16];

		for (int j = 0; j<16; j++) {

			num[j] = strByte[i * 16 + j];

		}

		MD5compress(num);

	}

	//把得到的摘要2进制变成16进制字符串输出

	return changeToHex(tempA).append(changeToHex(tempB)).append(changeToHex(tempC)).append(changeToHex(tempD));

}

填充函数padding

填充函数

处理后应满足bits≡448(mod512), 填充方式为先加一个1,其它位补零,最后加上64位的原来长度

unsigned int* padding(string str) {

	//以512位,64个字节为一组， num表示组数， 利用整数相除直接得到组数

	unsigned int num = ((str.length() + 8) / 64) + 1;

	//对于一组需要16个整数来存储 16*4=64， strByte表示此字符串的2进制表示（这里用int数组表示）

	unsigned int *strByte = new unsigned int[num * 16];

	//初始化字符串的长度（长度是16*组数）

	strlength = num * 16;

	//初始化 strByte数组

	for (unsigned int i = 0; i < num * 16; i++) {

		strByte[i] = 0;

	}

	//一个整数存储四个字节，一个unsigned int对应4个字节，保存4个字符信息

	for (unsigned int i = 0; i <str.length(); i++) {

		strByte[i / 4] |= (str[i]) << ((i % 4) * 8);

	}

	//尾部添加1 一个unsigned int保存4个字符信息,所以用128左移

	strByte[str.length() / 4] |= 0x80 << (((str.length() % 4)) * 8);

	/*

	*添加原长度，长度指位的长度，所以要乘8，然后是小端序，所以放在倒数第二个,这里长度只用了32位

	*/

	strByte[num * 16 - 2] = str.length() * 8;

	return strByte;

}

压缩函数

按照RFC 1321的标准进行一共64次压缩运算，因为每一次的参数是固定的，所以可以提前输入参数，这里我是k数组来存储这些参数

MD5算法——C++实现



//MD5 压缩函数 Hmd5

void MD5compress(unsigned int M[]) {

	int f = 0, g = 0;

	int a = tempA, b = tempB, c = tempC, d = tempD;

	/*第1轮迭代：

	*X[j] , j = 1..16.

	*第2轮迭代：

	*X[p2(j)], p2(j) = (1 + 5j) mod 16, j = 1..16.

	*第3轮迭代：

	*X[p3(j)], p3(j) = (5 + 3j) mod 16, j = 1..16.

	*第2轮迭代：

	*X[p4(j)], p4(j) = 7j mod 16, j = 1..16*/

	for (int i = 0; i < 64; i++) {

		if (i<16) {

			f = F(b, c, d);

			g = i;

		}

		else if (i<32) {

			f = G(b, c, d);

			g = (5 * i + 1) % 16;

		}

		else if (i<48) {

			f = H(b, c, d);

			g = (3 * i + 5) % 16;

		}

		else {

			f = I(b, c, d);

			g = (7 * i) % 16;

		}

		//每次循环使用相同的迭代逻辑和 4*16 次运算的预设参数表, 也就是前面的k表

		unsigned int tmp = d;

		d = c;

		c = b;

		b = b + RPTATE_SHIFT((a + f + k[i] + M[g]), s[i]);

		a = tmp;

	}

	tempA = a + tempA;

	tempB = b + tempB;

	tempC = c + tempC;

	tempD = d + tempD;

}

进制转换函数

把数字变为2进制以字符串输出

string changeToHex(int num) {

	int b;

	string tmp;

	string str = "";

	for (int i = 0; i<4; i++) {

		tmp = "";

		b = ((num >> i * 8) % (1 << 8)) & 0xff;   //逆序处理每个字节

		for (int j = 0; j < 2; j++) {

			tmp.insert(0, 1, str16[b % 16]);

			b = b / 16;

		}

		str += tmp;

	}

	return str;

}

测试函数

验证函数，通过RFC 1321给的标准输入输出来判断

MD5算法——C++实现

int main() {

	//这是 RFC 1321的标准测试输入和输出， 用来验证此MD5算法的正确性

	string input[7] = {

	        "",

	        "a",

	        "abc",

	        "message digest",

	        "abcdefghijklmnopqrstuvwxyz",

	        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789",

	        "12345678901234567890123456789012345678901234567890123456789012345678901234567890"};

    string expect[7] = {

        "d41d8cd98f00b204e9800998ecf8427e", "0cc175b9c0f1b6a831c399e269772661",

        "900150983cd24fb0d6963f7d28e17f72", "f96b697d7cb7938d525a2f31aaf161d0",

        "c3fcd3d76192e4007dfb496cca67e13b", "d174ab98d277d9f5a5611c2c9f419d9f",

        "57edf4a22be3c955ac49da2e2107b67a"};

    for (int i = 0; i < 7; i++) {

        cout << "--------------------------------" << endl;

        cout << "测试 " << i + 1 << ":" << endl;

        cout << "原消息：         " << input[i] << endl;

        cout << "MD5标准输出：    " << expect[i] << endl;

        string digest = getMD5Code(input[i]);

        cout << "MD5输出：        " << digest << endl;

    }

}

测试结果

可看到和标准输出是相同的，证明此MD5算法正确。

MD5算法——C++实现

源码传送门

https://github.com/wangjiwu/implement-MD5-in-C-

参考文档

MD5加密算法原理及实现

https://www.cnblogs.com/hjgods/p/3998570.html
The MD5 Message-Digest Algorithm

https://tools.ietf.org/html/rfc1321

秒客网