MD5算法的C++实现.doc

MD5算法的C+实现数理学院 信息与计算科学 赵峰 20074390115一、MD5算法概述1.MD5算法简介：MD5算法是一种消息摘要算法，此算法以任意长度的信息作为输入进行计算，产生一个128-bit的指纹或报文摘要。两个不同的信息产生相同信息摘要的几率相当小，从一个给定的信息摘要逆向产生原始信息更是困难，因此MD5算法适合用在数字签名应用中。2.MD5算法的用途：防止被篡改防止直接看到明文防止抵赖（数字签名）3.MD5算法的描述：对MD5算法简要的叙述可以为：MD5以512位分组来处理输入的信息，且每一分组又被划分为16个32位子分组，经过了一系列的处理后，算法的输出由四个32位分组组成，将这四个32位分组级联后将生成一个128位散列值。第一步、填充：如果输入信息的长度(bit)对512求余的结果不等于448，就需要填充使得对512求余的结果等于448。填充的方法是填充一个1和n个0。填充完后，信息的长度就为N*512+448(bit)。第二步、记录信息长度：用64位来存储填充前信息长度。这64位加在第一步结果的后面，这样信息长度就变为N*512+448+64=(N+1)*512位。第三步、装入标准的幻数（四个整数）：标准的幻数（物理顺序）是（A=(01234567)16，B=(89ABCDEF)16，C=(FEDCBA98)16，D=(76543210)16）。如果在程序中定义应该是（A=0X67452301L，B=0XEFCDAB89L，C=0X98BADCFEL，D=0X10325476L）。第四步、四轮循环运算：循环的次数是分组的个数（N+1）。1） 将每一512字节细分成16个小组，每个小组64位（8个字节）。2） 先认识四个线性函数(&是与,|是或,是非,是异或)。 F(X,Y,Z)=(X&Y)|(X)&Z) G(X,Y,Z)=(X&Z)|(Y&(Z)H(X,Y,Z)=XYZI(X,Y,Z)=Y(X|(Z)3）设Mj表示消息的第j个子分组（从0到15），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)4)四轮运算 第一轮 a=FF(a,b,c,d,M0,7,0xd76aa478)b=FF(d,a,b,c,M1,12,0xe8c7b756)c=FF(c,d,a,b,M2,17,0x242070db)d=FF(b,c,d,a,M3,22,0xc1bdceee)a=FF(a,b,c,d,M4,7,0xf57c0faf)b=FF(d,a,b,c,M5,12,0x4787c62a)c=FF(c,d,a,b,M6,17,0xa8304613)d=FF(b,c,d,a,M7,22,0xfd469501)a=FF(a,b,c,d,M8,7,0x698098d8)b=FF(d,a,b,c,M9,12,0x8b44f7af)c=FF(c,d,a,b,M10,17,0xffff5bb1)d=FF(b,c,d,a,M11,22,0x895cd7be)a=FF(a,b,c,d,M12,7,0x6b901122)b=FF(d,a,b,c,M13,12,0xfd987193)c=FF(c,d,a,b,M14,17,0xa679438e)d=FF(b,c,d,a,M15,22,0x49b40821)第二轮 a=GG(a,b,c,d,M1,5,0xf61e2562)b=GG(d,a,b,c,M6,9,0xc040b340)c=GG(c,d,a,b,M11,14,0x265e5a51)d=GG(b,c,d,a,M0,20,0xe9b6c7aa)a=GG(a,b,c,d,M5,5,0xd62f105d)b=GG(d,a,b,c,M10,9,0x02441453)c=GG(c,d,a,b,M15,14,0xd8a1e681)d=GG(b,c,d,a,M4,20,0xe7d3fbc8)a=GG(a,b,c,d,M9,5,0x21e1cde6)b=GG(d,a,b,c,M14,9,0xc33707d6)c=GG(c,d,a,b,M3,14,0xf4d50d87)d=GG(b,c,d,a,M8,20,0x455a14ed)a=GG(a,b,c,d,M13,5,0xa9e3e905)b=GG(d,a,b,c,M2,9,0xfcefa3f8)c=GG(c,d,a,b,M7,14,0x676f02d9)d=GG(b,c,d,a,M12,20,0x8d2a4c8a)第三轮 a=HH(a,b,c,d,M5,4,0xfffa3942)b=HH(d,a,b,c,M8,11,0x8771f681)c=HH(c,d,a,b,M11,16,0x6d9d6122) d=HH(b,c,d,a,M14,23,0xfde5380c)a=HH(a,b,c,d,M1,4,0xa4beea44)b=HH(d,a,b,c,M4,11,0x4bdecfa9)c=HH(c,d,a,b,M7,16,0xf6bb4b60)d=HH(b,c,d,a,M10,23,0xbebfbc70)a=HH(a,b,c,d,M13,4,0x289b7ec6)b=HH(d,a,b,c,M0,11,0xeaa127fa)c=HH(c,d,a,b,M3,16,0xd4ef3085)d=HH(b,c,d,a,M6,23,0x04881d05)a=HH(a,b,c,d,M9,4,0xd9d4d039)b=HH(d,a,b,c,M12,11,0xe6db99e5)c=HH(c,d,a,b,M15,16,0x1fa27cf8)d=HH(b,c,d,a,M2,23,0xc4ac5665)第四轮 a=II(a,b,c,d,M0,6,0xf4292244)c=II(c,d,a,b,M14,15,0xab9423a7)d=II(b,c,d,a,M5,21,0xfc93a039)a=II(a,b,c,d,M12,6,0x655b59c3)b=II(d,a,b,c,M3,10,0x8f0ccc92)c=II(c,d,a,b,M10,15,0xffeff47d)d=II(b,c,d,a,M1,21,0x85845dd1)a=II(a,b,c,d,M8,6,0x6fa87e4f)b=II(d,a,b,c,M15,10,0xfe2ce6e0)c=II(c,d,a,b,M6,15,0xa3014314)d=II(b,c,d,a,M13,21,0x4e0811a1)a=II(a,b,c,d,M4,6,0xf7537e82)b=II(d,a,b,c,M11,10,0xbd3af235)c=II(c,d,a,b,M2,15,0x2ad7d2bb)d=II(b,c,d,a,M9,21,0xeb86d391)5）每轮循环后，将A，B，C，D分别加上a，b，c，d，然后进入下一循环。5.MD5算法的安全性MD5相对MD4所作的改进：1. 增加了第四轮；2. 每一步均有唯一的加法常数；3. 为减弱第二轮中函数G的对称性从(X&Y)|(X&Z)|(Y&Z)变为(X&Z)|(Y&(Z)；4. 第一步加上了上一步的结果，这将引起更快的雪崩效应；5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似；6. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。二、MD5算法的C+程序1MD5算法程序库#define UINT4 unsigned int/* F, G, H and I are basic MD5 functions. */#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)/* ROTATE_LEFT rotates x left n bits. */#define ROTATE_LEFT(x, n) (x) (32-(n)/* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4.Rotation is separate from addition to prevent recomputation. */#define FF(a, b, c, d, x, s, ac) (a) += F (b), (c), (d) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT (a), (s); (a) += (b); #define GG(a, b, c, d, x, s, ac) (a) += G (b), (c), (d) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT (a), (s); (a) += (b); #define HH(a, b, c, d, x, s, ac) (a) += H (b), (c), (d) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT (a), (s); (a) += (b); #define II(a, b, c, d, x, s, ac) (a) += I (b), (c), (d) + (x) + (UINT4)(ac); (a) = ROTATE_LEFT (a), (s); (a) += (b); / Constants for MD5 Transform routine.#define S11 7#define S12 12#define S13 17#define S14 22#define S21 5#define S22 9#define S23 14#define S24 20#define S31 4#define S32 11#define S33 16#define S34 23#define S41 6#define S42 10#define S43 15#define S44 21/=#include #include #include md5.h/MD5摘要MD5VAL md5(char * str, unsigned int size)if(size=0)size=strlen(str);unsigned int m=size%64;unsigned int lm=size-m; /数据整块长度unsigned int ln; /数据补位后长度if(m56)ln=lm+64;elseln=lm+128;char * strw=new charln;unsigned int i;/复制原字串到缓冲区strwfor(i=0;isize;i+)strwi=stri;/补位strwi+=0x80;for(i;iln-8;i+)strwi=0x00;/补长度unsigned int * x=(unsigned int *)(strw+i);*(x+)=size29;/初始化MD5参数MD5VAL val=0x67452301,0xefcdab89,0x98badcfe,0x10325476;unsigned int &a=val.a, &b=val.b, &c=val.c, &d=val.d;unsigned int aa,bb,cc,dd;for(i=0;iln;i+=64)x=(unsigned int *)(strw+i);/ Save the valuesaa=a; bb=b; cc=c; dd=d;/ Round 1FF (a, b, c, d, x 0, S11, 0xd76aa478); /* 1 */FF (d, a, b, c, x 1, S12, 0xe8c7b756); /* 2 */FF (c, d, a, b, x 2, S13, 0x242070db); /* 3 */FF (b, c, d, a, x 3, S14, 0xc1bdceee); /* 4 */FF (a, b, c, d, x 4, S11, 0xf57c0faf); /* 5 */FF (d, a, b, c, x 5, S12, 0x4787c62a); /* 6 */FF (c, d, a, b, x 6, S13, 0xa8304613); /* 7 */FF (b, c, d, a, x 7, S14, 0xfd469501); /* 8 */FF (a, b, c, d, x 8, S11, 0x698098d8); /* 9 */FF (d, a, b, c, x 9, S12, 0x8b44f7af); /* 10 */FF (c, d, a, b, x10, S13, 0xffff5bb1); /* 11 */FF (b, c, d, a, x11, S14, 0x895cd7be); /* 12 */FF (a, b, c, d, x12, S11, 0x6b901122); /* 13 */FF (d, a, b, c, x13, S12, 0xfd987193); /* 14 */FF (c, d, a, b, x14, S13, 0xa679438e); /* 15 */FF (b, c, d, a, x15, S14, 0x49b40821); /* 16 */ Round 2GG (a, b, c, d, x 1, S21, 0xf61e2562); /* 17 */GG (d, a, b, c, x 6, S22, 0xc040b340); /* 18 */GG (c, d, a, b, x11, S23, 0x265e5a51); /* 19 */GG (b, c, d, a, x 0, S24, 0xe9b6c7aa); /* 20 */GG (a, b, c, d, x 5, S21, 0xd62f105d); /* 21 */GG (d, a, b, c, x10, S22, 0x2441453); /* 22 */GG (c, d, a, b, x15, S23, 0xd8a1e681); /* 23 */GG (b, c, d, a, x 4, S24, 0xe7d3fbc8); /* 24 */GG (a, b, c, d, x 9, S21, 0x21e1cde6); /* 25 */GG (d, a, b, c, x14, S22, 0xc33707d6); /* 26 */GG (c, d, a, b, x 3, S23, 0xf4d50d87); /* 27 */GG (b, c, d, a, x 8, S24, 0x455a14ed); /* 28 */GG (a, b, c, d, x13, S21, 0xa9e3e905); /* 29 */GG (d, a, b, c, x 2, S22, 0xfcefa3f8); /* 30 */GG (c, d, a, b, x 7, S23, 0x676f02d9); /* 31 */GG (b, c, d, a, x12, S24, 0x8d2a4c8a); /* 32 */ Round 3HH (a, b, c, d, x 5, S31, 0xfffa3942); /* 33 */HH (d, a, b, c, x 8, S32, 0x8771f681); /* 34 */HH (c, d, a, b, x11, S33, 0x6d9d6122); /* 35 */HH (b, c, d, a, x14, S34, 0xfde5380c); /* 36 */HH (a, b, c, d, x 1, S31, 0xa4beea44); /* 37 */HH (d, a, b, c, x 4, S32, 0x4bdecfa9); /* 38 */HH (c, d, a, b, x 7, S33, 0xf6bb4b60); /* 39 */HH (b, c, d, a, x10, S34, 0xbebfbc70); /* 40 */HH (a, b, c, d, x13, S31, 0x289b7ec6); /* 41 */HH (d, a, b, c, x 0, S32, 0xeaa127fa); /* 42 */HH (c, d, a, b, x 3, S33, 0xd4ef3085); /* 43 */HH (b, c, d, a, x 6, S34, 0x4881d05); /* 44 */HH (a, b, c, d, x 9, S31, 0xd9d4d039); /* 45 */HH (d, a, b, c, x12, S32, 0xe6db99e5); /* 46 */HH (c, d, a, b, x15, S33, 0x1fa27cf8); /* 47 */HH (b, c, d, a, x 2, S34, 0xc4ac5665); /* 48 */ Round 4 */II (a, b, c, d, x 0, S41, 0xf4292244); /* 49 */II (d, a, b, c, x 7, S42, 0x432aff97); /* 50 */II (c, d, a, b, x14, S43, 0xab9423a7); /* 51 */II (b, c, d, a, x 5, S44, 0xfc93a039); /* 52 */II (a, b, c, d, x12, S41, 0x655b59c3); /* 53 */II (d, a, b, c, x 3, S42, 0x8f0ccc92); /* 54 */II (c, d, a, b, x10, S43, 0xffeff47d); /* 55 */II (b, c, d, a, x 1, S44, 0x85845dd1); /* 56 */II (a, b, c, d, x 8, S41, 0x6fa87e4f); /* 57 */II (d, a, b, c, x15, S42, 0xfe2ce6e0); /* 58 */II (c, d, a, b, x 6, S43, 0xa3014314); /* 59 */II (b, c, d, a, x13, S44, 0x4e0811a1); /* 60 */II (a, b, c, d, x 4, S41, 0xf7537e82); /* 61 */II (d, a, b, c, x11, S42, 0xbd3af235); /* 62 */II (c, d, a, b, x 2, S43, 0x2ad7d2bb); /* 63 */II (b, c, d, a, x 9, S44, 0xeb86d391); /* 64 */ Add the original valuesa+=aa;b+=bb;c+=cc;d+=dd;delete strw;return val;#define BUFFER_SIZE 4096 /必须是64的倍数static char * Buffer=NULL;/MD5文件摘要MD5VAL md5File(FILE * fpin)if(!Buffer)Buffer=new charBUFFER_SIZE+64;char * buf=Buffer;MD5VAL val=0x67452301,0xefcdab89,0x98badcfe,0x10325476;unsigned int &a=val.a, &b=val.b, &c=val.c, &d=val.d;unsigned int aa,bb,cc,dd;unsigned int i,j,count,co;unsigned int * x;i=0;docount=fread(buf,1,BUFFER_SIZE,fpin);i+=count;if(count=BUFFER_SIZE)co=BUFFER_SIZE;elsej=count;bufj+=0x80;for(j;j%64!=56;j+)bufj=0x00;*(unsigned int *)(buf+j)=i29; j+=4;co=j;for(j=0;jco;j+=64)x=(unsigned int *)(buf+j);/ Save the valuesaa=a; bb=b; cc=c; dd=d;/ Round 1FF (a, b, c, d, x 0, S11, 0xd76aa478); /* 1 */FF (d, a, b, c, x 1, S12, 0xe8c7b756); /* 2 */FF (c, d, a, b, x 2, S13, 0x242070db); /* 3 */FF (b, c, d, a, x 3, S14, 0xc1bdceee); /* 4 */FF (a, b, c, d, x 4, S11, 0xf57c0faf); /* 5 */FF (d, a, b, c, x 5, S12, 0x4787c62a); /* 6 */FF (c, d, a, b, x 6, S13, 0xa8304613); /* 7 */FF (b, c, d, a, x 7, S14, 0xfd469501); /* 8 */FF (a, b, c, d, x 8, S11, 0x698098d8); /* 9 */FF (d, a, b, c, x 9, S12, 0x8b44f7af); /* 10 */FF (c, d, a, b, x10, S13, 0xffff5bb1); /* 11 */FF (b, c, d, a, x11, S14, 0x895cd7be); /* 12 */FF (a, b, c, d, x12, S11, 0x6b901122); /* 13 */FF (d, a, b, c, x13, S12, 0xfd987193); /* 14 */FF (c, d, a, b, x14, S13, 0xa679438e); /* 15 */FF (b, c, d, a, x15, S14, 0x49b40821); /* 16 */ Round 2GG (a, b, c, d, x 1, S21, 0xf61e2562); /* 17 */GG (d, a, b, c, x 6, S22, 0xc040b340); /* 18 */GG (c, d, a, b, x11, S23, 0x265e5a51); /* 19 */GG (b, c, d, a, x 0, S24, 0xe9b6c7aa); /* 20 */GG (a, b, c, d, x 5, S21, 0xd62f105d); /* 21 */GG (d, a, b, c, x10, S22, 0x2441453); /* 22 */GG (c, d, a, b, x15, S23, 0xd8a1e681); /* 23 */GG (b, c, d, a, x 4, S24, 0xe7d3fbc8); /* 24 */GG (a, b, c, d, x 9, S21, 0x21e1cde6); /* 25 */GG (d, a, b, c, x14, S22, 0xc33707d6); /* 26 */GG (c, d, a, b, x 3, S23, 0xf4d50d87); /* 27 */GG (b, c, d, a, x 8, S24, 0x455a14ed); /* 28 */GG (a, b, c, d, x13, S21, 0xa9e3e905); /* 29 */GG (d, a, b, c, x 2, S22, 0xfcefa3f8); /* 30 */GG (c, d, a, b, x 7, S23, 0x676f02d9); /* 31 */GG (b, c, d, a, x12, S24, 0x8d2a4c8a); /* 32 */ Round 3HH (a, b, c, d, x 5, S31, 0xfffa3942); /* 33 */HH (d, a, b, c, x 8, S32, 0x8771f681); /* 34 */HH (c, d, a, b, x11, S33, 0x6d9d6122); /* 35 */HH (b, c, d, a, x14, S34, 0xfde5380c); /* 36 */HH (a, b, c, d, x 1, S31, 0xa4beea44); /* 37 */HH (d, a, b, c, x 4, S32, 0x4bdecfa9); /* 38 */HH (c, d, a, b, x 7, S33, 0xf6bb4b60); /* 39 */HH (b, c, d, a, x10, S34, 0xbebfbc70); /* 40 */HH (a, b, c, d, x13, S31, 0x289b7ec6); /* 41 */HH (d, a, b, c, x 0, S32, 0xeaa127fa); /* 42 */HH (c, d, a, b, x 3, S33, 0xd4ef3085); /* 43 */HH (b, c, d, a, x 6, S34, 0x4881d05); /* 44 */HH (a, b, c, d, x 9, S31, 0xd9d4d039); /* 45 */HH (d, a, b, c, x12, S32, 0xe6db99e5); /* 46 */HH (c, d, a, b, x15, S33, 0x1fa27cf8); /* 47 */HH (b, c, d, a, x 2, S34, 0xc4ac5665); /* 48 */ Round 4 */II (a, b, c, d, x 0, S41, 0xf4292244); /* 49 */II (d, a, b, c, x 7, S42, 0x432aff97); /* 50 */II (c, d, a, b, x14, S43, 0xab9423a7); /* 51 */II (b, c, d, a, x 5, S44, 0xfc93a039); /* 52 */II (a, b, c, d, x12, S41, 0x655b59c3); /* 53 */II (d, a, b, c, x 3, S42, 0x8f0ccc92); /* 54 */II (c, d, a, b, x10, S43, 0xffeff47d); /* 55 */II (b, c, d, a, x 1, S44, 0x85845dd1); /* 56 */II (a, b, c, d, x 8, S41, 0x6fa87e4f); /*