密码学MD5详解及C语⾔实现
MD5算法详解及实现
基本信息
Message Digest Algorithm MD5(中⽂名为消息摘要算法第五版)为计算机安全领域⼴泛使⽤的⼀种散列函数，⽤以提供消息的完整性保护。该算法的⽂件号为RFC 1321(R.Rivest,MIT Laboratory for Computer Science and RSA Data Security Inc. April 1992)。
MD5即Message-Digest Algorithm 5(信息-摘要算法5)，⽤于确保信息传输完整⼀致。是计算机⼴泛使⽤的杂凑算法之⼀(⼜译摘要算法、哈希算法)，主流编程语⾔普遍已有MD5实现。将数据(如汉字)运算为另⼀固定长度值，是杂凑算法的基础原理，MD5的前⾝有MD2、MD3和MD4。
MD5算法具有以下特点:
1、压缩性：任意长度的数据，算出的MD5值长度都是固定的。
2、容易计算：从原数据计算出MD5值很容易。
3、抗修改性：对原数据进⾏任何改动，哪怕只修改1个字节，所得到的MD5值都有很⼤区别。
4、强抗碰撞：已知原数据和其MD5值，想到⼀个具有相同MD5值的数据(即伪造数据)是⾮常困难的。
MD5的作⽤是让⼤容量信息在⽤数字签名软件签署私⼈密钥前被"压缩"成⼀种保密的格式(就是把⼀个任意长度的字节串变换成⼀定长的⼗六进制数字串)。除了MD5以外，其中⽐较有名的还有sha-1、RIPEMD以及Haval等。
以上信息收集于: .
原理
MD5算法简要的叙述可以为:
MD5以512位分组来处理输⼊的信息，且每⼀分组⼜被划分为16个32位⼦分组，经过了⼀系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将⽣成⼀个128位散列值。
具体步骤：
1.填充
在MD5算法中，⾸先需要对信息进⾏填充，使其位长对512求余的结果等于448，并且填充必须进⾏，即使其位长对512求余的结果等于448。因此，信息的位长(Bits Length)将被扩展⾄N*512+448 位（N⼤于等于0）
应该怎么填呢？
1. 信息后⾯添加⼀个1和n个0 （直到满⾜N*512+448 位 ，N⼤于等于0）
2. 结果后⾯附加⼀个以64位⼆进制（即01串）表⽰的填充前信息长度(单位为Bit)，如果⼆进制表⽰的填充前信息长度超过64位，则取
低64位。
经过这两步的处理，信息的位长=N*512+448+64=(N+1)*512，即长度恰好是512的整数倍，从⽽可以形成512位的多个分组。
2.初始化变量
初始的128位值为初试链接变量，这些参数⽤于第⼀轮的运算，分别为:
A=0x01234567，B=0x89ABCDEF，C=0xFEDCBA98，D=0x76543210。
(每⼀个变量给出的数值是⾼字节存于内存低地址，低字节存于内存⾼地址，在程序中变量分别为·：
A=0x67452301，B=0xEFCDAB89，
C= 0x98BADCFE，D =0x10325476)
3. 处理分组数据
每⼀分组的算法流程如下:
第⼀分组需要将上⾯四个链接变量复制到另外四个变量中:A到a，B到b，C到c，D到d。从第⼆分组开始的变量为上⼀分组的运算结果，即A = a， B = b， C = c， D = d。
主循环有四轮，每轮循环都很相似。第⼀轮进⾏16次操作。每次操作对a、b、c和d中的其中三个作⼀次⾮线性函数运算，然后将所得结果加上第四个变量，⽂本的⼀个⼦分组和⼀个常数。再将所得结果向左环移⼀个不定的数，并加上a、b、c或d中之⼀。最后⽤该结果取代a、b、c或d中之⼀。
以下是每次操作中⽤到的四个⾮线性函数(每轮⼀个)。
F( X ,Y ,Z ) = ( X & Y ) | ( (~X) & Z )
G( X ,Y ,Z ) = ( X & Z ) | ( Y & (~Z) )
H( X ,Y ,Z ) =X ^ Y ^ Z
I( X ,Y ,Z ) =Y ^ ( X | (~Z) )
(&是与(And)，|是或(Or)，~是⾮(Not)，^是异或(Xor))
这四个函数的说明：如果X、Y和Z的对应位是独⽴和均匀的，那么结果的每⼀位也应是独⽴和均匀的。
F是⼀个逐位运算的函数。即，如果X，那么Y，否则Z。函数H是逐位奇偶操作符。
假设Mj表⽰消息的第j个⼦分组(从0到15)，常数ti是4294967296*abs( sin(i) )的整数部分，i 取值从1到64，单位是弧度。(4294967296=2)
现定义:
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)
然后进⾏主循环，主循环有四轮， 每⼀轮由16次操作组成，共64次。
FF、GG、HH、II四种具体操作可以参考密码学教材及下⾯的代码，不再赘述。
所有这些步骤进⾏完之后，将A、B、C、D分别加上AA、BB、CC、DD，然后⽤下⼀块数据继续进⾏算法。
4.输出
最后的输出是A、B、C、D的级联。
实现“加密”代码
#include <memory.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct
{
unsigned int count[2];
unsigned int state[4];
unsigned char buffer[64];
}MD5_CTX;
#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 +=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 MD5Init(MD5_CTX*context);
void MD5Update(MD5_CTX*context,unsigned char *input,unsigned int inputlen); void MD5Final(MD5_CTX*context,unsigned char digest[16]);
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])
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);/* 1 */
FF(d, a, b, c, x[1],12,0xe8c7b756);/* 2 */
FF(c, d, a, b, x[2],17,0x242070db);/* 3 */
FF(b, c, d, a, x[3],22,0xc1bdceee);/* 4 */
FF(a, b, c, d, x[4],7,0xf57c0faf);/* 5 */
FF(d, a, b, c, x[5],12,0x4787c62a);/* 6 */
FF(c, d, a, b, x[6],17,0xa8304613);/* 7 */
FF(b, c, d, a, x[7],22,0xfd469501);/* 8 */
FF(a, b, c, d, x[8],7,0x698098d8);/* 9 */
FF(d, a, b, c, x[9],12,0x8b44f7af);/* 10 */
FF(c, d, a, b, x[10],17,0xffff5bb1);/* 11 */
FF(b, c, d, a, x[11],22,0x895cd7be);/* 12 */
FF(a, b, c, d, x[12],7,0x6b901122);/* 13 */
FF(d, a, b, c, x[13],12,0xfd987193);/* 14 */
FF(c, d, a, b, x[14],17,0xa679438e);/* 15 */
FF(b, c, d, a, x[15],22,0x49b40821);/* 16 */
/
* Round 2 */
GG(a, b, c, d, x[1],5,0xf61e2562);/* 17 */
GG(d, a, b, c, x[6],9,0xc040b340);/* 18 */
GG(c, d, a, b, x[11],14,0x265e5a51);/* 19 */
GG(b, c, d, a, x[0],20,0xe9b6c7aa);/* 20 */
GG(a, b, c, d, x[5],5,0xd62f105d);/* 21 */
GG(a, b, c, d, x[5],5,0xd62f105d);/* 21 */
GG(d, a, b, c, x[10],9,0x2441453);/* 22 */
GG(c, d, a, b, x[15],14,0xd8a1e681);/* 23 */
GG(b, c, d, a, x[4],20,0xe7d3fbc8);/* 24 */
GG(a, b, c, d, x[9],5,0x21e1cde6);/* 25 */
GG(d, a, b, c, x[14],9,0xc33707d6);/* 26 */
GG(c, d, a, b, x[3],14,0xf4d50d87);/* 27 */
GG(b, c, d, a, x[8],20,0x455a14ed);/* 28 */
GG(a, b, c, d, x[13],5,0xa9e3e905);/* 29 */
GG(d, a, b, c, x[2],9,0xfcefa3f8);/* 30 */
GG(c, d, a, b, x[7],14,0x676f02d9);/* 31 */
GG(b, c, d, a, x[12],20,0x8d2a4c8a);/* 32 */
/* Round 3 */
HH(a, b, c, d, x[5],4,0xfffa3942);/* 33 */
HH(d, a, b, c, x[8],11,0x8771f681);/* 34 */
HH(c, d, a, b, x[11],16,0x6d9d6122);/* 35 */
HH(b, c, d, a, x[14],23,0xfde5380c);/* 36 */
HH(a, b, c, d, x[1],4,0xa4beea44);/* 37 */
HH(d, a, b, c, x[4],11,0x4bdecfa9);/* 38 */
HH(c, d, a, b, x[7],16,0xf6bb4b60);/* 39 */
HH(b, c, d, a, x[10],23,0xbebfbc70);/* 40 */
HH(a, b, c, d, x[13],4,0x289b7ec6);/* 41 */
HH(d, a, b, c, x[0],11,0xeaa127fa);/* 42 */
HH(c, d, a, b, x[3],16,0xd4ef3085);/* 43 */
HH(b, c, d, a, x[6],23,0x4881d05);/* 44 */
HH(a, b, c, d, x[9],4,0xd9d4d039);/* 45 */
HH(d, a, b, c, x[12],11,0xe6db99e5);/* 46 */
HH(c, d, a, b, x[15],16,0x1fa27cf8);/* 47 */
HH(b, c, d, a, x[2],23,0xc4ac5665);/* 48 */
/* Round 4 */
II(a, b, c, d, x[0],6,0xf4292244);/* 49 */
II(d, a, b, c, x[7],10,0x432aff97);/* 50 */
II(c, d, a, b, x[14],15,0xab9423a7);/* 51 */
II(b, c, d, a, x[5],21,0xfc93a039);/* 52 */
II(a, b, c, d, x[12],6,0x655b59c3);/* 53 */
II(d, a, b, c, x[3],10,0x8f0ccc92);/* 54 */
II(c, d, a, b, x[10],15,0xffeff47d);/* 55 */
II(b, c, d, a, x[1],21,0x85845dd1);/* 56 */
II(a, b, c, d, x[8],6,0x6fa87e4f);/* 57 */
II(d, a, b, c, x[15],10,0xfe2ce6e0);/* 58 */
II(c, d, a, b, x[6],15,0xa3014314);/* 59 */
II(b, c, d, a, x[13],21,0x4e0811a1);/* 60 */
II(a, b, c, d, x[4],6,0xf7537e82);/* 61 */
II(d, a, b, c, x[11],10,0xbd3af235);/* 62 */
II(c, d, a, b, x[2],15,0x2ad7d2bb);/* 63 */明解c语言
II(b, c, d, a, x[9],21,0xeb86d391);/* 64 */
state[0]+= a;
state[1]+= b;
state[2]+= c;
state[3]+= d;
}
int main(int argc, char *argv[])
{
int i;
unsigned char encrypt[100];
unsigned char decrypt[16];
printf("请输⼊明⽂：\n");
scanf("%s",encrypt);
MD5_CTX md5;
MD5Init(&md5);
MD5Update(&md5,encrypt,strlen((char *)encrypt));
MD5Final(&md5,decrypt);
printf("明⽂是:\n%s\n---------------------\n对应的密⽂是:\n",encrypt);

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。