转自MD5算法
MD5是输入不定长度信息,输出固定长度128-bits的算法。经过程序流程,生成四个32位数据,最后联合起来成为一个128-bits散列。基本方式为,求余、取余、调整长度、与链接变量进行循环运算,得出结果。
MD5的具体实现好像有所区别,起码维基百科和百度百科的就不一样。但经过验证都是正确的,而这里采用的是维基百科的方法(http://zh.wikipedia.org/wiki/MD5):
使用MD5转换数据,需要使用相关的预设数据值去执行一系列步骤。先定义几个需要使用的数据和函数,罗列如下:
A = 0x67452301;
B = 0xEFCDAB89;
C = 0x98BADCFE;
D = 0x10325476;
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);
K[ 64 ],其中K[ i ] = floor( abs(sin(i + 1)) × 2^32 );
R[ 64 ] = { 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 }
假设待转换数据为M,按如下步骤进行:
1.在M后面补1,然后补0,直到其长度模除512等于448;
2.继续在后面追加一个64bit数(小端表示),表示M的原始长度;
3.将M每512位拆分为一组,每一组进行如下操作:
A.拆分为16个32位的word(小端表示),用W[ i ]来标识;
B.将A、B、C、D分别赋值给a、b、c、d;
C.设置循环变量i,从0到63,执行如下操作:
a.若0<=i<=15,则f = F(b, c, d),g = i;
b.若16<=i<=31,则f = G(b, c, d),g = ( 5 * i + 1 ) % 16;
c.若32<=i<=47,则f = H(b, c, d),g = ( 3 * i + 5 ) % 16;
d.若48<=i<=63,则f = I(b, c, d),g = ( 7 * i ) % 16;
e. temp = d, d = c, c = b, b= leftrotate((a + f + K[i] + W[g]),R[i]) + b, a = temp;
D.A += a, B += b, C += c, D += d;
4. ABCD(各自以小端表示后级联)就是M经过MD5转换后形成的最终信息N。
在具体实现(C/C++)中,考虑到补位(bit)比较困难,一般是补字节(byte)。由于1byte=8bits,所以512bits=64bytes,448bits=56bytes,而一开始补位1就变成了补字节0x80(即128D,或者说是10000000B)。需要注意的是小端表示很重要,否则得到的结果会不正确。
下面为具体代码:
- /********************************************************
- 1.本程序只提供对字符串进行MD5加密的能力
- 2.转换过程中相关的信息输出以注释屏蔽了,如有必要可去除
- 3.学号:10389203姓名:吴嘉琪日期:2012-10-17
- *********************************************************/
- #include<cstdio>
- #include<iostream>
- #include<cmath>
- #include<string>
- #include<iomanip>
- #include<bitset>
- usingnamespacestd;
- voidMD5(strings);//对字符串s进行MD5加密
- voidappending(string&s,unsignedlonglongsize);//为原始信息补位
- inttransform(strings);//以小端规则把长度为4的字符串转换成32位(4字节)数据
- unsignedlittleEndian(unsignedn);//把n转换成小端规则表示的数据
- /*MD5需要用的相关数据*/
- unsignedA,B,C,D;
- unsignedK[64],W[16];
- unsignedR[64]={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};
- /*MD5需要用的相关函数的宏定义*/
- #defineF(x,y,z)(((x)&(y))|((~x)&(z)))
- #defineG(x,y,z)(((x)&(z))|((y)&(~z)))
- #defineH(x,y,z)((x)^(y)^(z))
- #defineI(x,y,z)((y)^((x)|(~z)))
- #defineROTATE_LEFT(x,n)(((x)<<(n))|((x)>>(32-(n))))
- intmain()
- {
- for(inti=0;i<64;i++)
- K[i]=floor(abs(sinl(i+1))*powl(2,32));
- MD5("");
- MD5("a");
- MD5("abc");
- MD5("messagedigest");
- return0;
- }
- voidMD5(strings){
- A=0x67452301,B=0xEFCDAB89,C=0x98BADCFE,D=0x10325476;
- unsignedsize=s.size();
- appending(s,size*8);
- /*每512位(64字节)拆分为一组,此为外循环*/
- for(intk=0;k<s.size()/64;k++){
- /*拆分为16个32位(4字节)的word,用W[i]来标识*/
- for(inti=0;i<16;i++)
- W[i]=transform(s.substr(64*k+4*i,4));
- //cout<<"整理为WORD之后的二进制数据: ";
- //for(inti=0;i<16;i++)
- //cout<<setw(2)<<i<<":"<<bitset<32>((int)W[i])<<endl;
- unsigneda=A,b=B,c=C,d=D,f,g,temp;
- for(inti=0;i<64;i++){
- if(i>=0&&i<=15){
- f=F(b,c,d);
- g=i;
- }
- elseif(i>=16&&i<=31){
- f=G(b,c,d);
- g=(5*i+1)%16;
- }
- elseif(i>=32&&i<=47){
- f=H(b,c,d);
- g=(3*i+5)%16;
- }
- else{
- f=I(b,c,d);
- g=(7*i)%16;
- }
- temp=d;
- d=c;
- c=b;
- b=ROTATE_LEFT((a+f+K[i]+W[g]),R[i])+b;
- a=temp;
- }
- A+=a;
- B+=b;
- C+=c;
- D+=d;
- }
- /*格式化控制输出*/
- printf("MD5("%s")=",s.substr(0,size).c_str());
- printf("%08x%08x%08x%08x ",littleEndian(A),littleEndian(B),littleEndian(C),littleEndian(D));
- }
- voidappending(string&s,unsignedlonglongsize){
- /*补位至模除512为448(56字节)*/
- s+=(char)128;
- intsign=56-s.size()%64;
- inttemp=(sign<0?64+sign:sign);
- while(temp--)
- s+=(char)0;
- /*信息尾部添加原信息长度,用64位(8字节)数据以小端规则存储*/
- char*now=(char*)&size;
- for(inti=0;i<8;i++)
- s+=*(now+i);
- //printf("检验补位完毕后的信息的二进制数据:");
- //for(inti=0;i<s.size();i++){
- //if(i%4==0)
- //printf(" ");
- //printf("%2d:",i,s[i]);
- //cout<<bitset<8>((int)s[i])<<"";
- //}
- //cout<<endl;
- }
- inttransform(strings){
- return(0xFF000000&s[3]<<24)|(0x00FF0000&s[2]<<16)
- |(0x0000FF00&s[1]<<8)|(0x000000FF&s[0]);
- }
- unsignedlittleEndian(unsignedn){
- return(0xFF000000&n<<24)|(0x00FF0000&n<<8)
- |(0x0000FF00&n>>8)|(0x000000FF&n>>24);
- }