密码学MD5的实现
MD5的实现是很坑的，我学的这本教材上写的MD5算法写的很简单，很多细节都没有说清楚，如果不注意的话，在实现md5的时候会走很多弯路。
第一个坑点：就是MD强化，俗称填充。消息的初始化处理时，需要使得消息的比特长度时512的整数倍。书上是说在消息m的二进制表示之后先填入一个1，然后再添加若干个0（不超过511个0），是的消息的比特长度是512的整数倍少64比特，最后在最低的64比特位填入消息m的比特长度的二进制表示。那么这就有一个疑问了，消息m的比特长度二进制表示如果无法填满64比特该咋办？一般大家都会想着直接在前面补0就好，是的，确实是在前面补0，但是有讲究。这个二进制表示只占高32位，不足的在前面补0，低32位直接补0即可。
第二个坑点：如果有同学想用unsigned int存储消息块并进行那64轮计算的话， 一定要记得存储的顺序问题，因为怎么平时看到的数字都是大端序，比方说一个4字节的的unsigned int，每四位用一个16进制表示的话可以分为12345678这8个16进制位，这是咱们一般认为的大端序，但计算机存储是小端序，也就是说一个数字存储进去正确的表示应该是78563412。这样存储进去在进行运算才会得到正确结果。
另外，MD5对汉字的杂凑值计算是使用UTF-8编码的，所以下面示例代码在计算汉字编码是结果是不正确的，因为它使用的是GBK编码。
#include <bits/stdc++.h>
#define MAX_LEN 51200
#define u_int unsigned int
//初始向量A,B,C,D
const u_int AAA = 0x67452301;//"00000001001000110100010101100111"
const u_int BBB = 0xefcdab89;//"10001001101010111100110111101111"
const u_int CCC = 0x98badcfe;//"11111110110111001011101010011000"
const u_int DDD = 0x10325476;//"01110110010101000011001000010000"
u_int cl[] = {0xd76aa478,0xe8c7b756,0x242070db,0xc1bdceee,//64***作中的常量
0xf57c0faf,0x4787c62a,0xa8304613,0xfd469501,0x698098d8,
0x8b44f7af,0xffff5bb1,0x895cd7be,0x6b901122,0xfd987193,
0xa679438e,0x49b40821,0xf61e2562,0xc040b340,0x265e5a51,
0xe9b6c7aa,0xd62f105d,0x02441453,0xd8a1e681,0xe7d3fbc8,
0x21e1cde6,0xc33707d6,0xf4d50d87,0x455a14ed,0xa9e3e905,
0xfcefa3f8,0x676f02d9,0x8d2a4c8a,0xfffa3942,0x8771f681,
0x6d9d6122,0xfde5380c,0xa4beea44,0x4bdecfa9,0xf6bb4b60,
0xbebfbc70,0x289b7ec6,0xeaa127fa,0xd4ef3085,0x04881d05,
0xd9d4d039,0xe6db99e5,0x1fa27cf8,0xc4ac5665,0xf4292244,
0x432aff97,0xab9423a7,0xfc93a039,0x655b59c3,0x8f0ccc92,
0xffeff47d,0x85845dd1,0x6fa87e4f,0xfe2ce6e0,0xa3014314,
0x4e0811a1,0xf7537e82,0xbd3af235,0x2ad7d2bb,0xeb86d391};
u_int pos[] = {7,12,17,22,7,12,17,22,7,12,17,22,7,//64***作中的移位距离
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};
u_int M[16];//主循环中的更小的消息块，即512比特的块分成16个32比特的小块
u_int m[64] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,
1,6,11,0,5,10,15,4,9,14,3,8,13,2,7,12,
5,8,11,14,1,4,7,10,13,0,3,6,9,12,15,2,
0,7,14,5,12,3,10,1,8,15,6,13,4,11,2,9};
u_int yiwei(u_int a , u_int s)
{//循环移位,a向左循环左移s位
return (a<<s)|(a>>(32-s));
}
u_int F(const u_int x ,const u_int y ,const u_int z)
{//F函数
return (x&y)|((~x)&z);
}
u_int G(const u_int x ,const u_int y ,const u_int z)
{//G函数
return (x&z)|(y&(~z));
}
u_int H(const u_int x ,const u_int y ,const u_int z)
{//H函数
return x^y^z;
}
u_int I(const u_int x ,const u_int y ,const u_int z)
{//I函数
return y^(x|(~z));
}
//填充一个1和若干个0，即md强化
void tianchong(char *s , u_int *len)
{
char lb[66];
//将未填充前的len转换为二进制存储在lb数组中
_itoa(*len ,lb ,2);
u_int t = *len/512 + 1;
if((t*512 - *len) < 65)
t++;
u_int bound = t*512 - 64;
s[*len] = '1';//先填个1
//再填若干个0
int i;
for(i = *len+1 ; i < bound ; i++)
s[i] = '0';
s[i] = '\0';
*len = t*512;//填充后的长度
u_int Len = strlen(lb);
char ll[66];
Len = 32-Len;
for(u_int i = 0; i < Len ; i++ )
ll[i] = '0';
for(u_int i = Len ,j = 0; lb[j]; i++,j++)
ll[i] = lb[j];
for(u_int i = 32; i < 64; i++)
ll[i] = '0';
ll[64] = '\0';
strcat(s , ll);
}
//算出32比特的子块M[i]
void sub_str(const char *s ,bool flag)
{
int p = 0;
for(u_int i = 0 ,j = 0 ; i < 512 ; i+=32 ,j++,p++)
{
char ss[33];
int l = 0;
if(flag && p>=14)
{
for(int m = 0 ; m < 32; m++)
ss[m] = s[i+m];
}else {
for(int m = 24 ; m < 32; l++,m++)
ss[l] = s[i+m];
for(int m = 16 ; m < 24; m++,l++)
ss[l] = s[i+m];
for(int m = 8 ; m < 16; m++,l++)
ss[l] = s[i+m];
for(int m = 0 ; m < 8; m++,l++)
ss[l] = s[i+m];}
ss[32] = '\0';
u_int t = 1 ,sum = 0;
for(int k = 31 ; k >= 0 ; k--)
{
if(ss[k] == '1')
sum += t;
t = t*2;
}
M[j] = sum;
}
}
//每个字节倒序，原先12345678，现在78563412
u_int changeHex(u_int a)
{
u_int b(0);
b = b|(a<<24);
b = b|((a&0xff00)<<8);
b = b|((a&0xff0000)>>8);
b = b|((a&0xff000000)>>24);
return b;
}
//将字符的ascall码转换为八位二进制
void transfor(const char *p , char *s)
{
char buff[100];
int j = 0;
for(int i = 0 ; p[i] ; i++)
{
itoa(p[i] ,buff ,2);
//printf("%c:%d:%s\n" ,p[i],p[i],buff);
int len = strlen(buff);
len = len>8 ? 0 : (8-len);
while(len--)
s[j++] = '0';
for(int k = 0 ; buff[k] ; k++)
s[j++] = buff[k];
}
s[j] = '\0';
}
int main()
{
char S[MAX_LEN];
u_int len;
while(~scanf("%s" ,S)){
char s[MAX_LEN*8];
transfor(S,s);//将字符的ascall码转换为八位二进制
//printf("字符对应的二进制：%s\n" ,s);
len = strlen(s);
//printf("len=%d\n" ,len);
//先填充
tianchong(s ,&len);//对s进行填充
//printf("填充后\nlen=%d\ns=%s\n" ,len ,s);
//主循环
u_int AA=AAA ,BB=BBB ,CC=CCC ,DD=DDD;
u_int A =AAA ,B =BBB ,C =CCC ,D =DDD;
for(int i = 0 ; s[i] ; i+=512)
{
s[i+512]=='\0' ? sub_str(&s[i] ,true) : sub_str(&s[i] ,false);
//for(int i = 0 ; i < 16 ; i++)
// printf("%d\n" ,M[i]);
A=AA ,B=BB ,C=CC ,D=DD;
for(u_int j = 0 ; j < 16 ; j++)
{
int t = j*4;
if(j < 4)
{
A = B+(yiwei((A+F(B,C,D)+M[m[t]]+cl[t]),pos[t]));
D = A+(yiwei((D+F(A,B,C)+M[m[t+1]]+cl[t+1]),pos[t+1]));
C = D+(yiwei((C+F(D,A,B)+M[m[t+2]]+cl[t+2]),pos[t+2]));
B = C+(yiwei((B+F(C,D,A)+M[m[t+3]]+cl[t+3]),pos[t+3]));
}else if(j>=4 && j<8){
A = B+(yiwei((A+G(B,C,D)+M[m[t]]+cl[t]),pos[t]));
D = A+(yiwei((D+G(A,B,C)+M[m[t+1]]+cl[t+1]),pos[t+1]));
C = D+(yiwei((C+G(D,A,B)+M[m[t+2]]+cl[t+2]),pos[t+2]));
B = C+(yiwei((B+G(C,D,A)+M[m[t+3]]+cl[t+3]),pos[t+3]));
}else if(j>=8 && j<12){
A = B+(yiwei((A+H(B,C,D)+M[m[t]]+cl[t]),pos[t]));
D = A+(yiwei((D+H(A,B,C)+M[m[t+1]]+cl[t+1]),pos[t+1]));
C = D+(yiwei((C+H(D,A,B)+M[m[t+2]]+cl[t+2]),pos[t+2]));
B = C+(yiwei((B+H(C,D,A)+M[m[t+3]]+cl[t+3]),pos[t+3]));
}else if(j>=12 && j<16){
A = B+(yiwei((A+I(B,C,D)+M[m[t]]+cl[t]),pos[t]));
D = A+(yiwei((D+I(A,B,C)+M[m[t+1]]+cl[t+1]),pos[t+1]));
C = D+(yiwei((C+I(D,A,B)+M[m[t+2]]+cl[t+2]),pos[t+2]));
B = C+(yiwei((B+I(C,D,A)+M[m[t+3]]+cl[t+3]),pos[t+3]));
}
//printf("%4x%4x%4x%4x\n" ,A ,B ,C ,D);
}
AA = A+AA;
BB = B+BB;
CC = C+CC;
DD = D+DD;
}
printf("MD5杂凑值：%4x%4x%4x%4x\n\n" ,changeHex(AA) ,changeHex(BB),changeHex(CC) ,changeHex(DD));}
return 0;
}
得物app公司福利 402人发布
