【CRYPTO】MD5算法详解

前言

MD5是一种哈希算法,用来保证信息的完整性。
就一段信息对应一个哈希值,且不能通过哈希值推出这段信息,而且还需要保证不存在任意两段不相同的信息对应同一个哈希值。
不过MD5算法算出来的值也就16byte(即128bit),肯定存在相同的,找到另一个所花时间长短而已。

填充信息

我们要对一个字符串进行MD5计算,那么肯定要从这个字符串的处理入手。
我们知道一个字符的长度是1个byte,即8bit的长度。
MD5对待加密的字符串的处理是将一个字符串分割成每512bit为一个分组,形如N*512+R,这里的R是余下的位数。这个R分为几种情况:

  • R=0时,需要补位,单补上一个512bit的分组,因为还要加入最后64个位的字符串长度。
  • R<448时,则需要补位到448位,后面添加64位的字符串长度。
  • R>448时,除了补满这一分组外,还要再补上一个512位的分组后面添加64位的原字符串长度。

补位的形式是先填充一个1,再接无数个0,直到补足512位。

举例:
消息内容为“HUANG”,就能得到以下内容

48 55 41 4E 47 80 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
00 00 00 00 00 00 00 00 [28 00 00 00 00 00 00 00]低位在左边

最后面这里有个0x28,数8个字节,就是0x0000000000000028,刚刚好是十进制的40,消息的内容是5个byte,也就是40bit
还要注意到这里是小端字节序存储

数据说明

MD5有四个32位的被称作链接变量的整数参数,这是个参数我们定义为A、B、C、D其取值为

A=0x01234567
B=0x89ABCDEF
C=0xFEDCBA89
D0x76543210

但考虑到内存数据存储大小端的问题我们将其赋值为

A=0x67452301;
B=0xEFCDAB89;
C=0x98BADCFE;
D=0x10325476;

以及一些所需要的数据

DWORDmd5::A=0x67452301;
DWORDmd5::B=0xEFCDAB89;
DWORDmd5::C=0x98BADCFE;
DWORDmd5::D=0x10325476;
DWORDmd5::T[64]={
    0xD76AA478,0xE8C7B756,0x242070DB,0xC1BDCEEE,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
    };
DWORDmd5::s[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
};
DWORDmd5::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
};

信息处理

经过信息填充后,填充后的信息长度肯定是512bit(64byte)的倍数,也就是说每512bit(64byte)为1段可以分成n段(n大于等于1),对于每一段信息(512bit,64byte)又划分成16小段(每段32bit,4个byte,用M表示)
同时MD5算法规定了四个非线性操作函数( & 是与,| 是或,~ 是非,^ 是异或):

//操作函数
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))
//运算函数
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)

对于每种函数都会执行64次
执行顺序是:
先执行16次FF,再执行16次GG,再执行16次HH,最后执行16次II
可以把这个4种函数各执行16次看作一次周期,那么这样的周期有4个,可以简单理解为:

for(i=0;i<4;i++)FF(16)GG(16),HH(16),II(16);//括号内为执行次数

以下为具体的函数说明

DWORD md5::F(DWORD X,DWORD Y,DWORD Z){
    return(X&Y)|((~X)&Z);
}
DWORD md5::G(DWORD X,DWORD Y,DWORD Z){
    return(X&Z)|(Y&(~Z));
}
DWORD md5::H(DWORD X,DWORD Y,DWORD Z){
    returnX^Y^Z;
}
DWORD md5::I(DWORD X,DWORD Y,DWORD Z){
    returnY^(X|(~Z));
}
void md5::FF(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp=F(b,c,d)+a+mj+ti;
    temp=(temp<<s)|(temp>>(32-s));
    a=b+temp;
}
void md5::GG(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp=G(b,c,d)+a+mj+ti;
    temp=(temp<<s)|(temp>>(32-s));
    a=b+temp;
}
void md5::HH(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp=H(b,c,d)+a+mj+ti;
    temp=(temp<<s)|(temp>>(32-s));
    a=b+temp;
}
void md5::II(DWORD &a,DWORD &b,DWORD &c,DWORD &d,DWORD mj,DWORD s,DWORD ti){
    DWORD temp=I(b,c,d)+a+mj+ti;
    temp=(temp<<s)|(temp>>(32-s));
    a=b+temp;
}

参数说明

A,B,C,D 4个参数对应的值是周期变化的,周期长度为4,所以有

for(int j=0;j<16;j+=4){ //每次增加4
    FF(A,B,C,D,M[m[j]],s[j],T[j]);
    FF(D,A,B,C,M[m[j+1]],s[j+1],T[j+1]);
    FF(C,D,A,B,M[m[j+2]],s[j+2],T[j+2]);
    FF(B,C,D,A,M[m[j+3]],s[j+3],T[j+3]);
}
//GG、HH、II也类似,每种函数执行16次(1轮4次,4轮16次)后再执行下一种函数
for(int j=0;j<16;j+=4){
    GG(A,B,C,D,M[m[j]],s[j],T[j]);
    GG(D,A,B,C,M[m[j+1]],s[j+1],T[j+1]);
    GG(C,D,A,B,M[m[j+2]],s[j+2],T[j+2]);
    GG(B,C,D,A,M[m[j+3]],s[j+3],T[j+3]);
}
  • M是上面每一段的16个小段了,其中m[j]表示每次函数处理的小段都不同,按照一定的顺序来处理每个小段,其中的顺序就在m中保存了。
  • s是循环左移的位数,也有一定顺序。
  • T是常数,共64个,意味着64次的函数调用都是用不同的数值
  • 对于第一段消息(前512bit(64个byte))传入的a,b,c,d的值是上面的ABCD,4个有规律的值(初始值)。
  • 第一段消息处理完后(即4个函数各执行了16次之后),得到新的a,b,c,d的值,将它们分别加上原来a,b,c,d的值(即计算前的值),作为下一段消息(第2个512bit(64个byte))的初始a,b,c,d的值。

当每段消息(512bit,64byte)都处理完之后,得到的a,b,c,d的值
按照地址的顺序从低到高(内存大小端影响)打印对应的值,就是所求的MD5值。

16位和32位MD5的区别

MD5加密后的位数一般为两种,16位与32位。
16位实际上是从32位字符串中,取中间的第9位到第24位的部分

参考文献

发布者

正汰

永远是这样,山前面是山,天空上面是天空,道路前面还是道路,迷茫之后还有迷茫。

发表回复

您的电子邮箱地址不会被公开。