MD5算法原理与C语言实现
blog.kurukurumi.com原创,转载请注明出处。
E-Mail : hubenchang0515@outlook.com
一、MD5算法的概念
MD5全称Message Digest Algorithm 5,译为消息摘要算法第5版,是一种广泛使用的散列(hash)算法。常用作数据加密、文件验证等用途,是一种不可逆的加密算法。
二、MD5算法的步骤
MD5算法中需要用到4个32位的标准幻数,它们分别是(MD5中所有数据均采用小端字节序):0x67452301、0xefcdab89、0x98badcfe、0x10325476。
static uint32_t magicA = 0x67452301; static uint32_t magicB = 0xefcdab89; static uint32_t magicC = 0x98badcfe; static uint32_t magicD = 0x10325476;
MD5算法将数据按512位(64字节)进行分组,在分组前需要对数据进行补齐:如果数据的总位数除以512,余数不为448,则补充一位1和多位0使余数为448。此时数据长度为 512*N + 448 位。然后用64位内存保存数据的原始长度补充到后面,数据长度为 512*(N+1) 位。补齐之后即可将数据按每组512位进行分组。每个分组再分成16个32位子分组。
MD5算法需要用到如下定义4个宏:
#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)))
MD5算法需要用到循环位左移,因此编写循环位移函数:
/* n循环左移bits位 */ uint32_t rotateLeft(uint32_t n, uint8_t bits) { return (n << bits) | (n >> (32-bits)); } /* n循环右移bits位 */ uint32_t rotateRight(uint32_t n, uint8_t bits) { return (n >> bits) | (n <<(32-bits)); }
通过上述4个宏和循环位移函数实现MD5中需要用到的4个函数(其中,Mj表示某一组数据的第j个子分组,<<<s表示循环左移s位):
FF(a,b,c,d,Mj,s,ti) 表示 a=b+((a+F(b,c,d)+Mj+ti)<<<s) GG(a,b,c,d,Mj,s,ti) 表示 a=b+((a+G(b,c,d)+Mj+ti)<<<s) HH(a,b,c,d,Mj,s,ti) 表示 a=b+((a+H(b,c,d)+Mj+ti)<<<s) II(a,b,c,d,Mj,s,ti) 表示 a=b+((a+I(b,c,d)+Mj+ti)<<<s)
实现这四个函数:
void FF(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + F(b,c,d) + Mj + ti ), s); } void GG(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + G(b,c,d) + Mj + ti ), s); } void HH(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + H(b,c,d) + Mj + ti ), s); } void II(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + I(b,c,d) + Mj + ti ), s); }
有了这四个函数之后,对每一个分组进行1次如下4轮运算:
{ /* M是当前处理的分组,M[i]是该分组的第i个子分组 */ uint32_t a = A; uint32_t b = B; uint32_t c = C; uint32_t d = D; FF(&a,b,c,d,M[0],7,0xd76aa478); FF(&d,a,b,c,M[1],12,0xe8c7b756); FF(&c,d,a,b,M[2],17,0x242070db); FF(&b,c,d,a,M[3],22,0xc1bdceee); FF(&a,b,c,d,M[4],7,0xf57c0faf); FF(&d,a,b,c,M[5],12,0x4787c62a); FF(&c,d,a,b,M[6],17,0xa8304613); FF(&b,c,d,a,M[7],22,0xfd469501); FF(&a,b,c,d,M[8],7,0x698098d8); FF(&d,a,b,c,M[9],12,0x8b44f7af); FF(&c,d,a,b,M[10],17,0xffff5bb1); FF(&b,c,d,a,M[11],22,0x895cd7be); FF(&a,b,c,d,M[12],7,0x6b901122); FF(&d,a,b,c,M[13],12,0xfd987193); FF(&c,d,a,b,M[14],17,0xa679438e); FF(&b,c,d,a,M[15],22,0x49b40821); GG(&a,b,c,d,M[1],5,0xf61e2562); GG(&d,a,b,c,M[6],9,0xc040b340); GG(&c,d,a,b,M[11],14,0x265e5a51); GG(&b,c,d,a,M[0],20,0xe9b6c7aa); GG(&a,b,c,d,M[5],5,0xd62f105d); GG(&d,a,b,c,M[10],9,0x02441453); GG(&c,d,a,b,M[15],14,0xd8a1e681); GG(&b,c,d,a,M[4],20,0xe7d3fbc8); GG(&a,b,c,d,M[9],5,0x21e1cde6); GG(&d,a,b,c,M[14],9,0xc33707d6); GG(&c,d,a,b,M[3],14,0xf4d50d87); GG(&b,c,d,a,M[8],20,0x455a14ed); GG(&a,b,c,d,M[13],5,0xa9e3e905); GG(&d,a,b,c,M[2],9,0xfcefa3f8); GG(&c,d,a,b,M[7],14,0x676f02d9); GG(&b,c,d,a,M[12],20,0x8d2a4c8a); HH(&a,b,c,d,M[5],4,0xfffa3942); HH(&d,a,b,c,M[8],11,0x8771f681); HH(&c,d,a,b,M[11],16,0x6d9d6122); HH(&b,c,d,a,M[14],23,0xfde5380c); HH(&a,b,c,d,M[1],4,0xa4beea44); HH(&d,a,b,c,M[4],11,0x4bdecfa9); HH(&c,d,a,b,M[7],16,0xf6bb4b60); HH(&b,c,d,a,M[10],23,0xbebfbc70); HH(&a,b,c,d,M[13],4,0x289b7ec6); HH(&d,a,b,c,M[0],11,0xeaa127fa); HH(&c,d,a,b,M[3],16,0xd4ef3085); HH(&b,c,d,a,M[6],23,0x04881d05); HH(&a,b,c,d,M[9],4,0xd9d4d039); HH(&d,a,b,c,M[12],11,0xe6db99e5); HH(&c,d,a,b,M[15],16,0x1fa27cf8); HH(&b,c,d,a,M[2],23,0xc4ac5665); II(&a,b,c,d,M[0],6,0xf4292244); II(&d,a,b,c,M[7],10,0x432aff97); II(&c,d,a,b,M[14],15,0xab9423a7); II(&b,c,d,a,M[5],21,0xfc93a039); II(&a,b,c,d,M[12],6,0x655b59c3); II(&d,a,b,c,M[3],10,0x8f0ccc92); II(&c,d,a,b,M[10],15,0xffeff47d); II(&b,c,d,a,M[1],21,0x85845dd1); II(&a,b,c,d,M[8],6,0x6fa87e4f); II(&d,a,b,c,M[15],10,0xfe2ce6e0); II(&c,d,a,b,M[6],15,0xa3014314); II(&b,c,d,a,M[13],21,0x4e0811a1); II(&a,b,c,d,M[4],6,0xf7537e82); II(&d,a,b,c,M[11],10,0xbd3af235); II(&c,d,a,b,M[2],15,0x2ad7d2bb); II(&b,c,d,a,M[9],21,0xeb86d391); A += a; B += b; C += c; D += d; }
在第一次运算前将A、B、C、D分别初始化为标准幻数magicA、magicB、magicC、magicD,在对每一组数据进行运算前,将a、b、c、d分别赋值为A、B、C、D,并在每一组数据运算结束时将A、B、C、D分别加上a、b、c、d。最后所得的A、B、C、D按低字节在前,高字节在后的顺序排列即为MD5值。
三、MD5实现源码
md5.h
/* blog.kurukurumi.com */ #ifndef MD5_H #define MD5_H #include <stdint.h> #include <stddef.h> typedef struct md5_t { uint8_t n[16]; }md5_t; md5_t md5(const void* data, size_t len); #endif
md5.c
/* blog.kurukurumi.com */ #include <stdlib.h> #include <string.h> #include "md5.h" static const uint32_t magicA = 0x67452301; static const uint32_t magicB = 0xefcdab89; static const uint32_t magicC = 0x98badcfe; static const uint32_t magicD = 0x10325476; uint32_t rotateLeft(uint32_t n, uint8_t bits) { bits &= 0x1f; return (n << bits) | (n >> (32-bits)); } uint32_t rotateRight(uint32_t n, uint8_t bits) { bits &= 0x1f; return (n >> bits) | (n <<(32-bits)); } #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))) /* The 4 functions of MD5 */ static void FF(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + F(b,c,d) + Mj + ti ), s); } static void GG(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + G(b,c,d) + Mj + ti ), s); } static void HH(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + H(b,c,d) + Mj + ti ), s); } static void II(uint32_t* a, uint32_t b, uint32_t c, uint32_t d, uint32_t Mj, uint8_t s, uint32_t ti) { *a = b + rotateLeft(( *a + I(b,c,d) + Mj + ti ), s); } /* fill data to able to grouping */ static void* md5Fill(const void* data, size_t* len) { size_t size = *len; size_t remainder = *len % 64; if(remainder > 56) { size = *len + 64 - remainder + 56; } else if(remainder < 56) { size = *len + 56 - remainder; } void* newData = malloc(size + 8); if(newData != NULL) { memcpy(newData, data, *len); size_t index = *len; *(uint8_t*)(newData + index) = 0x80; for( index = *len + 1; index < size; index++) { *(uint8_t*)(newData + index) = 0; } size_t bits = *len * 8; *(uint64_t*)(newData + index) = bits; //*(uint32_t*)(newData + 4) = bits; } *len = size + 8; return newData; } static uint32_t A = 0; static uint32_t B = 0; static uint32_t C = 0; static uint32_t D = 0; /* calculate the md5 value */ static void md5Calculate(const void* data, size_t len) { A = magicA; B = magicB; C = magicC; D = magicD; for(size_t i = 0; i < len / 64; i++) { uint32_t* M = (uint32_t*)(data + i * 64); uint32_t a = A; uint32_t b = B; uint32_t c = C; uint32_t d = D; FF(&a,b,c,d,M[0],7,0xd76aa478); FF(&d,a,b,c,M[1],12,0xe8c7b756); FF(&c,d,a,b,M[2],17,0x242070db); FF(&b,c,d,a,M[3],22,0xc1bdceee); FF(&a,b,c,d,M[4],7,0xf57c0faf); FF(&d,a,b,c,M[5],12,0x4787c62a); FF(&c,d,a,b,M[6],17,0xa8304613); FF(&b,c,d,a,M[7],22,0xfd469501); FF(&a,b,c,d,M[8],7,0x698098d8); FF(&d,a,b,c,M[9],12,0x8b44f7af); FF(&c,d,a,b,M[10],17,0xffff5bb1); FF(&b,c,d,a,M[11],22,0x895cd7be); FF(&a,b,c,d,M[12],7,0x6b901122); FF(&d,a,b,c,M[13],12,0xfd987193); FF(&c,d,a,b,M[14],17,0xa679438e); FF(&b,c,d,a,M[15],22,0x49b40821); GG(&a,b,c,d,M[1],5,0xf61e2562); GG(&d,a,b,c,M[6],9,0xc040b340); GG(&c,d,a,b,M[11],14,0x265e5a51); GG(&b,c,d,a,M[0],20,0xe9b6c7aa); GG(&a,b,c,d,M[5],5,0xd62f105d); GG(&d,a,b,c,M[10],9,0x02441453); GG(&c,d,a,b,M[15],14,0xd8a1e681); GG(&b,c,d,a,M[4],20,0xe7d3fbc8); GG(&a,b,c,d,M[9],5,0x21e1cde6); GG(&d,a,b,c,M[14],9,0xc33707d6); GG(&c,d,a,b,M[3],14,0xf4d50d87); GG(&b,c,d,a,M[8],20,0x455a14ed); GG(&a,b,c,d,M[13],5,0xa9e3e905); GG(&d,a,b,c,M[2],9,0xfcefa3f8); GG(&c,d,a,b,M[7],14,0x676f02d9); GG(&b,c,d,a,M[12],20,0x8d2a4c8a); HH(&a,b,c,d,M[5],4,0xfffa3942); HH(&d,a,b,c,M[8],11,0x8771f681); HH(&c,d,a,b,M[11],16,0x6d9d6122); HH(&b,c,d,a,M[14],23,0xfde5380c); HH(&a,b,c,d,M[1],4,0xa4beea44); HH(&d,a,b,c,M[4],11,0x4bdecfa9); HH(&c,d,a,b,M[7],16,0xf6bb4b60); HH(&b,c,d,a,M[10],23,0xbebfbc70); HH(&a,b,c,d,M[13],4,0x289b7ec6); HH(&d,a,b,c,M[0],11,0xeaa127fa); HH(&c,d,a,b,M[3],16,0xd4ef3085); HH(&b,c,d,a,M[6],23,0x04881d05); HH(&a,b,c,d,M[9],4,0xd9d4d039); HH(&d,a,b,c,M[12],11,0xe6db99e5); HH(&c,d,a,b,M[15],16,0x1fa27cf8); HH(&b,c,d,a,M[2],23,0xc4ac5665); II(&a,b,c,d,M[0],6,0xf4292244); II(&d,a,b,c,M[7],10,0x432aff97); II(&c,d,a,b,M[14],15,0xab9423a7); II(&b,c,d,a,M[5],21,0xfc93a039); II(&a,b,c,d,M[12],6,0x655b59c3); II(&d,a,b,c,M[3],10,0x8f0ccc92); II(&c,d,a,b,M[10],15,0xffeff47d); II(&b,c,d,a,M[1],21,0x85845dd1); II(&a,b,c,d,M[8],6,0x6fa87e4f); II(&d,a,b,c,M[15],10,0xfe2ce6e0); II(&c,d,a,b,M[6],15,0xa3014314); II(&b,c,d,a,M[13],21,0x4e0811a1); II(&a,b,c,d,M[4],6,0xf7537e82); II(&d,a,b,c,M[11],10,0xbd3af235); II(&c,d,a,b,M[2],15,0x2ad7d2bb); II(&b,c,d,a,M[9],21,0xeb86d391); A += a; B += b; C += c; D += d; } } md5_t md5(const void* data, size_t len) { size_t size = len; void* newData = md5Fill(data,&size); md5Calculate(newData,size); free(newData); md5_t md5Value; md5Value.n[0] = (uint8_t)A; md5Value.n[1] = (uint8_t)(A>>8); md5Value.n[2] = (uint8_t)(A>>16); md5Value.n[3] = (uint8_t)(A>>24); md5Value.n[4] = (uint8_t)B; md5Value.n[5] = (uint8_t)(B>>8); md5Value.n[6] = (uint8_t)(B>>16); md5Value.n[7] = (uint8_t)(B>>24); md5Value.n[8] = (uint8_t)C; md5Value.n[9] = (uint8_t)(C>>8); md5Value.n[10] = (uint8_t)(C>>16); md5Value.n[11] = (uint8_t)(C>>24); md5Value.n[12] = (uint8_t)D; md5Value.n[13] = (uint8_t)(D>>8); md5Value.n[14] = (uint8_t)(D>>16); md5Value.n[15] = (uint8_t)(D>>24); return md5Value; }
测试程序:
main.c
#include <stdio.h> #include <string.h> #include "md5.h" int main() { const char* str = "Hello World"; size_t len = strlen(str); md5_t m = md5(str,len); for(int i = 0; i < 16; i++) { printf("%02x",m.n[i]); } printf("\n"); }
得到结果为:b10a8db164e0754105b7a99be72e3fe5
注意,本文所提供的代码仅支持小端字节序的机器。
为了方便计算文件的MD5值,稍做修改后的源码:https://github.com/hubenchang0515/Cryptography
发表评论: