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
« 全排列
|
守护进程Daemon»
发表评论：