网站seo培训,东海县城乡建设局网站,iis添加网站建设中,湖州企业网站开发公司MD5即Message-DigestAlgorithm 5#xff08;信息-摘要算法5#xff09;#xff0c;用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一#xff08;又译摘要算法、哈希算法#xff09;#xff0c;主流编程语言普遍已有MD5实现。
1、MD5算法简介
MD5在90年代初由…MD5即Message-DigestAlgorithm 5信息-摘要算法5用于确保信息传输完整一致。是计算机广泛使用的杂凑算法之一又译摘要算法、哈希算法主流编程语言普遍已有MD5实现。
1、MD5算法简介
MD5在90年代初由MIT的计算机科学实验室和RSA Data SecurityInc发明经MD2、MD3和MD4发展而来。
MD5将任意长度的“字节串”变换成一个128bit的大整数并且它是一个不可逆的字符串变换算法换句话说就是即使你看到源程序和算法描述也无法将一个MD5的值变换回原始的字符串从数学原理上说是因为原始的字符串有无穷多个。
MD5的典型应用是对一段信息串 (Message)产生所谓的指纹 (fingerprint)以防止被“篡改”。比方说你将一段话写在一个文本文件中并对这个文本文件产生一个MD5的值并记录在案然后你可以传播这个文件给别人别人如果修改了文件中的任何内容你对这个文件重新计算MD5时就会发现。如果再有一个第三方的认证机构用MD5还可以防止文件作者的“抵赖”这就是所谓的数字签名应用。
MD5还广泛用于加密和解密技术上在很多操作系统中用户的密码是以MD5值或类似的其它算法的方式保存的用户Login的时候系统是把用户输入的密码计算成MD5值然后再去和系统中保存的MD5值进行比较而系统并不“知道”用户的密码是什么。
2、MD5算法分析
前面我们提到了MD5算法的主要应用领域那么究竟MD5算法具体是什么样的呢接下来我们就对其原理进行一些说明。
2.1、待加密信息处理
显而易见我们要对一个字符串进行MD5计算那么肯定要从这个字符串的处理入手。我们知道一个字符的长度是一个字节即8位bit的长度。MD5对待加密的字符串的处理是将一个字符串分割成每512位为一个分组形如N*512R这里的R是余下的位数。这个R分为几种情况
R0时需要补位单补上一个512位的分组因为还要加入最后64个位的字符串长度。
R448时则需要补位到448位后面添加64位的字符串长度。
R448时除了补满这一分组外还要再补上一个512位的分组后面添加64位的字符串长度。
补位的形式是先填充一个1再接无数个0直到补足512位。
2.2、MD5的链接变量及基本操作 MD5有四个32位的被称作链接变量的整数参数这是个参数我们定义为A、B、C、D其取值为A0x01234567B0x89abcdefC0xfedcba98D0x76543210。但考虑到内存数据存储大小端的问题我们将其赋值为A0x67452301B0xefcdab89C0x98badcfeD0x10325476。
同时MD5算法规定了四个非线性操作函数是与|是或~是非^是异或
F(X,Y,Z)(XY)|((~X)Z)
G(X,Y,Z)(XZ)|(Y(~Z))
H(X,Y,Z) X^Y^Z
I(X,Y,Z)Y^(X|(~Z))
这些函数是这样设计的如果X、Y和Z的对应位是独立和均匀的那么结果的每一位也应是独立和均匀的。
利用上面的四种操作生成四个重要的计算函数。首先我们声明四个中间变量a,b,c,d赋值a A, b B,c C, d D。然后定义这四个计算函数为
FF(a, b, c, d, M[j], s,ti)表示 a b ((a F(b, c, d) Mj ti) s)
GG(a, b, c, d, M[j], s,ti)表示 a b ((a G(b, c, d) Mj ti) s)
HH(a, b, c, d, M[j], s,ti)表示 a b ((a H(b, c, d) Mj ti) s)
II(a, b, c, d, M[j], s,ti)表示 a b ((a I(b, c, d) Mj ti) s)
其中M[j]表示消息的第j个子分组从0到15表示循环左移s常数ti是4294967296*abs(sin(i))的整数部分i取值从1到64单位是弧度。
2.3、循环计算
定义好上述的四个计算函数后就可以实现MD5的真正循环计算了。这个循环的循环次数为512位分组的个数。每次循环执行64不计算上述4个函数每个16次具体如下
//第一轮循环计算 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);
2.4、结果输出
处理完所有的512位的分组后得到一组新的A,B,C,D的值将这些值按ABCD的顺序级联就得到了想要的MD5散列值。当然输出依然要考虑内存存储的大小端问题。
3、MD5算法实现
根据前面分算法分析接下来我们来具体实现这一算法我们暂时不考虑字符串的分组预处理假设只有1组就是说长度不会超过448位。多组的炒作也是一样的只需要增加循环计算的次数所以我们实际从上述分析的第二步开始。
3.1、初始化操作
前面我们已经提到过了在开始MD5需要定义算法规定的数组、操作函数以及初始化4个链接变量。操作函数我们使用宏定义来实现。关于链接变量的初始化操作需要在对消息加密前操作我们定义如下的初始化函数
/*对MD5结构体进行初始化操作*/
voidMD5Start(MD5Contex *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;
}
3.2、MD5值计算
接下来我们实现MD5值得计算及结构体的更新
/*将要加密的信息传递给初始化过的MD5结构体无返回值 */
/*context初始化过了的MD5结构体 */
/*input需要加密的信息可以任意长度 */
/*inputLen指定input的长度 */
voidMD5Update(MD5Contex *context, uint8_t *input,uint32_t inputlen)
{uint32_t 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);MD5Process(context-state,context-buffer);for(i partlen;i64 inputlen;i64){MD5Process(context-state,input[i]);}index 0;}else{i 0;}memcpy(context-buffer[index],input[i],inputlen-i);
}
MD5的主体循环部分我们实现如下
/*对512bits信息(即block缓冲区)进行一次处理每次处理包括四轮 */
/*uint32_t*stateMD5结构体中的state[4]用于保存信息加密的结果 */
/*uint8_t*block欲加密的512bits信息 */
static voidMD5Process(uint32_t *state, uint8_t *block)
{uint32_t a state[0];uint32_t b state[1];uint32_t c state[2];uint32_t d state[3];uint32_t x[64];MD5Decode(x,block,64);/*第一轮计算*/FF(a, b, c, d, x[ 0],constMove[0],constTable[0][0]);FF(d, a, b, c, x[ 1],constMove[1],constTable[0][1]);FF(c, d, a, b, x[ 2],constMove[2],constTable[0][2]);FF(b, c, d, a, x[ 3],constMove[3],constTable[0][3]);FF(a, b, c, d, x[ 4],constMove[0],constTable[0][4]);FF(d, a, b, c, x[ 5],constMove[1],constTable[0][5]);FF(c, d, a, b, x[ 6],constMove[2],constTable[0][6]);FF(b, c, d, a, x[ 7],constMove[3],constTable[0][7]);FF(a, b, c, d, x[ 8], constMove[0],constTable[0][8]);FF(d, a, b, c, x[ 9],constMove[1],constTable[0][9]);FF(c, d, a, b, x[10],constMove[2],constTable[0][10]);FF(b, c, d, a, x[11],constMove[3],constTable[0][11]);FF(a, b, c, d, x[12],constMove[0],constTable[0][12]);FF(d, a, b, c, x[13],constMove[1],constTable[0][13]);FF(c, d, a, b, x[14],constMove[2],constTable[0][14]);FF(b, c, d, a, x[15],constMove[3],constTable[0][15]);/*第二轮计算*/GG(a, b, c, d, x[ 1],constMove[4],constTable[1][0]);GG(d, a, b, c, x[ 6],constMove[5],constTable[1][1]);GG(c, d, a, b, x[11],constMove[6],constTable[1][2]);GG(b, c, d, a, x[ 0],constMove[7],constTable[1][3]);GG(a, b, c, d, x[ 5],constMove[4],constTable[1][4]);GG(d, a, b, c, x[10],constMove[5],constTable[1][5]);GG(c, d, a, b, x[15],constMove[6],constTable[1][6]);GG(b, c, d, a, x[ 4],constMove[7],constTable[1][7]);GG(a, b, c, d, x[ 9],constMove[4],constTable[1][8]);GG(d, a, b, c, x[14],constMove[5],constTable[1][9]);GG(c, d, a, b, x[ 3], constMove[6],constTable[1][10]);GG(b, c, d, a, x[ 8],constMove[7],constTable[1][11]);GG(a, b, c, d, x[13],constMove[4],constTable[1][12]);GG(d, a, b, c, x[ 2],constMove[5],constTable[1][13]);GG(c, d, a, b, x[ 7],constMove[6],constTable[1][14]);GG(b, c, d, a, x[12],constMove[7],constTable[1][15]);/*第三轮计算*/HH(a, b, c, d, x[ 5],constMove[8],constTable[2][0]);HH(d, a, b, c, x[ 8],constMove[9],constTable[2][1]);HH(c, d, a, b, x[11],constMove[10],constTable[2][2]);HH(b, c, d, a, x[14],constMove[11],constTable[2][3]);HH(a, b, c, d, x[ 1],constMove[8],constTable[2][4]);HH(d, a, b, c, x[ 4],constMove[9],constTable[2][5]);HH(c, d, a, b, x[ 7],constMove[10],constTable[2][6]);HH(b, c, d, a, x[10], constMove[11],constTable[2][7]);HH(a, b, c, d, x[13],constMove[8],constTable[2][8]);HH(d, a, b, c, x[ 0],constMove[9],constTable[2][9]);HH(c, d, a, b, x[ 3],constMove[10],constTable[2][10]);HH(b, c, d, a, x[ 6],constMove[11],constTable[2][11]);HH(a, b, c, d, x[ 9],constMove[8],constTable[2][12]);HH(d, a, b, c, x[12],constMove[9],constTable[2][13]);HH(c, d, a, b, x[15],constMove[10],constTable[2][14]);HH(b, c, d, a, x[ 2],constMove[11],constTable[2][15]);/*第四轮计算*/II(a, b, c, d, x[ 0], constMove[12],constTable[3][0]);II(d, a, b, c, x[ 7],constMove[13],constTable[3][1]);II(c, d, a, b, x[14],constMove[14],constTable[3][2]);II(b, c, d, a, x[ 5],constMove[15],constTable[3][3]);II(a, b, c, d, x[12],constMove[12],constTable[3][4]);II(d, a, b, c, x[ 3],constMove[13],constTable[3][5]);II(c, d, a, b, x[10],constMove[14],constTable[3][6]);II(b, c, d, a, x[ 1],constMove[15],constTable[3][7]);II(a, b, c, d, x[ 8],constMove[12],constTable[3][8]);II(d, a, b, c, x[15],constMove[13],constTable[3][9]);II(c, d, a, b, x[ 6],constMove[14],constTable[3][10]);II(b, c, d, a, x[13],constMove[15],constTable[3][11]);II(a, b, c, d, x[ 4],constMove[12],constTable[3][12]);II(d, a, b, c, x[11], constMove[13],constTable[3][13]);II(c, d, a, b, x[ 2],constMove[14],constTable[3][14]);II(b, c, d, a, x[ 9],constMove[15],constTable[3][15]);state[0] a;state[1] b;state[2] c;state[3] d;
}
3.3、输出转换
最后我们将计算所得的MD5值进行输出格式整理时期按应有的顺序输出。
/*获得最终的MD5值无返回值 */
/*digest保存最终的加密串 */
/*context你前面初始化并填入了信息的md5结构 */
voidMD5Final(MD5Contex *context, uint8_t *digest)
{uint32_t index 0,padlen 0;uint8_t 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);
}
4、结论
MD5作为一种检验手段被广泛应用特别在用户密码保存方面因其不可逆和低碰撞的特性更是大受欢迎。我们使用自己编写的MD5算法计算一下普通的“hello world123456789”的MD5散列值 在前面我们实现了MD5算法但是我们如果仔细分析就会发现具体的实现代码是可以大幅度优化的特别是在四轮计算过程中。我们如果将FF、GG、HH、II不采用宏定义而是声明为4个函数很明显这四个函数的声明是一样的。于是利用指针和数组可将四轮计算简化为
for(i0;i4;i)
{for(j0;j4;j){pF[i](a, b, c, d, x[k[i][4*j]],constMove[4*i],constTable[i][4*j]);pF[i](d, a, b, c, x[k[i][4*j1]],constMove[4*i1],constTable[i][4*j1]);pF[i](c, d, a, b, x[k[i][4*j2]], constMove[4*i2],constTable[i][4*j2]);pF[i](b, c, d, a, x[k[i][4*j3]],constMove[4*i3],constTable[i][4*j3]);}
}
当然这一优化仅是对代码层面的简化实际的计算依然是64次所以对算法是没有影响的。
对于中文字符的MD5散列值则存在一个字符编码的问题比如对中文“中国”的编码结果
GB2312编码下的结果CF0832DEDF7457BBCBFA00BBD87B300A
UTF-8编码下的结果C13DCEABCB143ACD6C9298265D618A9F
欢迎关注
