MD5算法
MD5信息摘要算法,一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值,用于确保信息传输完整一致。MD5算法是单向散列算法的一种。单向散列算法也称为HASH算法。
特点
- 稳定、运算速度快。
- 压缩性:输入任意长度的数据,输出长度固定(128 比特位)。
- 运算不可逆:已知运算结果的情况下,无法通过通过逆运算得到原始字符串。
- 高度离散:输入的微小变化,可导致运算结果差异巨大。
MD5算法原理:
1、数据填充
对消息进行数据填充,使消息的长度对512取模得448,设消息长度为X,即满足X mod 512=448。根据此公式得出需要填充的数据长度。
填充方法:在消息后面进行填充,填充第一位为1,其余为0。
(此时消息长度为N*512+448)
2、添加消息长度
在第一步结果之后再填充上原消息的长度,可用来进行的存储长度为64位。如果消息长度大于264,则只使用其低64位的值,即(消息长度 对 264取模)。
在此步骤进行完毕后,最终消息长度就是512的整数倍。
(此时消息长度为(N+1)*512 )
3、数据处理
首先需要用到4个常数:
四个32位变量初始化(经过研究所得,为固定值)
A = 0×01234567
B = 0×89ABCDEF
C = 0xFEDCBA98
D = 0×76543210
它们称为链接变量(chaining variable)
以上为标准的幻数的(物理顺序)
如果在程序中(小端模式)定义应该是:
A = 0x67452301
B = 0xEFCDAB89
C = 0x98BADCFE
D = 0x10325476
然后需要用到4个非线性函数
F(X,Y,Z)=(X & Y) | ((
X) & Z);Z));
G(X,Y,Z)=(X & Z) | (Y & (
H(X,Y,Z)=X ^ Y ^ Z;
I(X,Y,Z)=Y ^ (X | (~Z));
(&是与, |是或, ~是非, ^是异或)
然后是4种操作
FF(a,b,c,d,Mi,s,tj) 表示a=b+((a+(F(b,c,d)+Mi+tj)<<< s)
GG(a,b,c,d,Mi,s,tj) 表示 a=b+((a+(G(b,c,d)+Mi+tj)<<< s)
HH(a,b,c,d,Mi,s,tj) 表示 a=b+((a+(H(b,c,d)+Mi+tj)<<< s)
II(a,b,c,d,Mi,s,tj) 表示a=b+((a+(I(b,c,d)+Mi+tj)<<< s)
其中Mi表示消息的第i个子分组(从0到15,共16个),<<< s表示循环左移s位
常数tj为: 在第j步中,tj是4294967296*abs(sin(j))的整数部分,i的单位是弧度。
(4294967296是2的32次方)
亦可用 0x100000000UL * abs(sin((double)j)) 计算
x循环左移s位:
( s << x ) | ( s >> (32 - x) )
MD5运算:
由类似的64次循环构成,分成4轮,每轮16次。每轮使用FF,GG,HH,II中的一种操作;
一轮中,a,b,c,d的使用顺序轮转;
例如第一轮:
第一次计算
FF(a,b,c,d,M0,s,t1)
a = a+(F(b,c,d)+M0+t1);
a = ( s <<a ) | ( s >> (32 - a) );
a = a + b;
第二次计算
FF(b,c,d,a,M1,s,t2)
b = b+(F(c,d,a)+M1+t2);
b = ( s <<b ) | ( s >> (32 - b) );
b = b + c;
这4轮共64步是:
(初次使用的a,b,c,d为A,B,C,D的值,而Mi,s,tj根据下面的数值进行使用,可认为是常量,)
第一轮
FF(a,b,c,d,M0,7,0xd76aa478)
FF(d,a,b,c,M1,12,0xe8c7b756)
FF(c,d,a,b,M2,17,0×242070db)
FF(b,c,d,a,M3,22,0xc1bdceee)
FF(a,b,c,d,M4,7,0xf57c0faf)
FF(d,a,b,c,M5,12,0×4787c62a)
FF(c,d,a,b,M6,17,0xa8304613)
FF(b,c,d,a,M7,22,0xfd469501)
FF(a,b,c,d,M8,7,0×698098d8)
FF(d,a,b,c,M9,12,0×8b44f7af)
FF(c,d,a,b,M10,17,0xffff5bb1)
FF(b,c,d,a,M11,22,0×895cd7be)
FF(a,b,c,d,M12,7,0×6b901122)
FF(d,a,b,c,M13,12,0xfd987193)
FF(c,d,a,b,M14,17,0xa679438e)
FF(b,c,d,a,M15,22,0×49b40821)
第二轮
GG(a,b,c,d,M1,5,0xf61e2562)
GG(d,a,b,c,M6,9,0xc040b340)
GG(c,d,a,b,M11,14,0×265e5a51)
GG(b,c,d,a,M0,20,0xe9b6c7aa)
GG(a,b,c,d,M5,5,0xd62f105d)
GG(d,a,b,c,M10,9,0×02441453)
GG(c,d,a,b,M15,14,0xd8a1e681)
GG(b,c,d,a,M4,20,0xe7d3fbc8)
GG(a,b,c,d,M9,5,0×21e1cde6)
GG(d,a,b,c,M14,9,0xc33707d6)
GG(c,d,a,b,M3,14,0xf4d50d87)
GG(b,c,d,a,M8,20,0×455a14ed)
GG(a,b,c,d,M13,5,0xa9e3e905)
GG(d,a,b,c,M2,9,0xfcefa3f8)
GG(c,d,a,b,M7,14,0×676f02d9)
GG(b,c,d,a,M12,20,0×8d2a4c8a)
第三轮
HH(a,b,c,d,M5,4,0xfffa3942)
HH(d,a,b,c,M8,11,0×8771f681)
HH(c,d,a,b,M11,16,0×6d9d6122)
HH(b,c,d,a,M14,23,0xfde5380c)
HH(a,b,c,d,M1,4,0xa4beea44)
HH(d,a,b,c,M4,11,0×4bdecfa9)
HH(c,d,a,b,M7,16,0xf6bb4b60)
HH(b,c,d,a,M10,23,0xbebfbc70)
HH(a,b,c,d,M13,4,0×289b7ec6)
HH(d,a,b,c,M0,11,0xeaa127fa)
HH(c,d,a,b,M3,16,0xd4ef3085)
HH(b,c,d,a,M6,23,0×04881d05)
HH(a,b,c,d,M9,4,0xd9d4d039)
HH(d,a,b,c,M12,11,0xe6db99e5)
HH(c,d,a,b,M15,16,0×1fa27cf8)
HH(b,c,d,a,M2,23,0xc4ac5665)
第四轮
II(a,b,c,d,M0,6,0xf4292244)
II(d,a,b,c,M7,10,0×432aff97)
II(c,d,a,b,M14,15,0xab9423a7)
II(b,c,d,a,M5,21,0xfc93a039)
II(a,b,c,d,M12,6,0×655b59c3)
II(d,a,b,c,M3,10,0×8f0ccc92)
II(c,d,a,b,M10,15,0xffeff47d)
II(b,c,d,a,M1,21,0×85845dd1)
II(a,b,c,d,M8,6,0×6fa87e4f)
II(d,a,b,c,M15,10,0xfe2ce6e0)
II(c,d,a,b,M6,15,0xa3014314)
II(b,c,d,a,M13,21,0×4e0811a1)
II(a,b,c,d,M4,6,0xf7537e82)
II(d,a,b,c,M11,10,0xbd3af235)
II(c,d,a,b,M2,15,0×2ad7d2bb)
II(b,c,d,a,M9,21,0xeb86d391)
消息分以512位为一分组进行处理,每一个分组进行上述4轮共64次计算后,将A,B,C,D分别加上计算得到的a,b,c,d。当做新的A,B,C,D,并将这4个变量赋值给a,b,c,d再进行下一分组的运算。由于填充后的消息长度为(N+1)*512,则共需计算N+1个分组。计算所有数据分组后,这4个变量为最后的结果,即MD5值。
代码实现
C++:
#include<iostream>
#include<string>
using namespace std;
#define shift(x, n) (((x) << (n)) | ((x) >> (32-(n))))//右移的时候,高位一定要补零,而不是补充符号位
#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)))
#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476
//strBaye的长度
unsigned int strlength;
//A,B,C,D的临时变量
unsigned int atemp;
unsigned int btemp;
unsigned int ctemp;
unsigned int dtemp;
//常量ti unsigned int(abs(sin(i+1))*(2pow32))
const unsigned int k[]={
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};
//向左位移数
const unsigned int s[]={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};
const char str16[]="0123456789abcdef";
void mainLoop(unsigned int M[])
{
unsigned int f,g;
unsigned int a=atemp;
unsigned int b=btemp;
unsigned int c=ctemp;
unsigned int d=dtemp;
for (unsigned int i = 0; i < 64; i++)
{
if(i<16){
f=F(b,c,d);
g=i;
}else if (i<32)
{
f=G(b,c,d);
g=(5*i+1)%16;
}else if(i<48){
f=H(b,c,d);
g=(3*i+5)%16;
}else{
f=I(b,c,d);
g=(7*i)%16;
}
unsigned int tmp=d;
d=c;
c=b;
b=b+shift((a+f+k[i]+M[g]),s[i]);
a=tmp;
}
atemp=a+atemp;
btemp=b+btemp;
ctemp=c+ctemp;
dtemp=d+dtemp;
}
/*
*填充函数
*处理后应满足bits≡448(mod512),字节就是bytes≡56(mode64)
*填充方式为先加一个1,其它位补零
*最后加上64位的原来长度
*/
unsigned int* add(string str)
{
unsigned int num=((str.length()+8)/64)+1;//以512位,64个字节为一组
unsigned int *strByte=new unsigned int[num*16]; //64/4=16,所以有16个整数
strlength=num*16;
for (unsigned int i = 0; i < num*16; i++)
strByte[i]=0;
for (unsigned int i=0; i <str.length(); i++)
{
strByte[i>>2]|=(str[i])<<((i%4)*8);//一个整数存储四个字节,i>>2表示i/4 一个unsigned int对应4个字节,保存4个字符信息
}
strByte[str.length()>>2]|=0x80<<(((str.length()%4))*8);//尾部添加1 一个unsigned int保存4个字符信息,所以用128左移
/*
*添加原长度,长度指位的长度,所以要乘8,然后是小端序,所以放在倒数第二个,这里长度只用了32位
*/
strByte[num*16-2]=str.length()*8;
return strByte;
}
string changeHex(int a)
{
int b;
string str1;
string str="";
for(int i=0;i<4;i++)
{
str1="";
b=((a>>i*8)%(1<<8))&0xff; //逆序处理每个字节
for (int j = 0; j < 2; j++)
{
str1.insert(0,1,str16[b%16]);
b=b/16;
}
str+=str1;
}
return str;
}
string getMD5(string source)
{
atemp=A; //初始化
btemp=B;
ctemp=C;
dtemp=D;
unsigned int *strByte=add(source);
for(unsigned int i=0;i<strlength/16;i++)
{
unsigned int num[16];
for(unsigned int j=0;j<16;j++)
num[j]=strByte[i*16+j];
mainLoop(num);
}
return changeHex(atemp).append(changeHex(btemp)).append(changeHex(ctemp)).append(changeHex(dtemp));
}
unsigned int main()
{
string ss;
// cin>>ss;
string s=getMD5("abc");
cout<<s;
return 0;
}
JavaScript:
JavaScript 版本的实现代码,可以用于浏览器中运行和计算文本字符串的 MD5。
function md5(string) {
function md5_RotateLeft(lValue, iShiftBits) {
return (lValue << iShiftBits) | (lValue >>> (32 - iShiftBits));
}
function md5_AddUnsigned(lX, lY) {
var lX4, lY4, lX8, lY8, lResult;
lX8 = (lX & 0x80000000);
lY8 = (lY & 0x80000000);
lX4 = (lX & 0x40000000);
lY4 = (lY & 0x40000000);
lResult = (lX & 0x3FFFFFFF) + (lY & 0x3FFFFFFF);
if (lX4 & lY4) {
return (lResult ^ 0x80000000 ^ lX8 ^ lY8);
}
if (lX4 | lY4) {
if (lResult & 0x40000000) {
return (lResult ^ 0xC0000000 ^ lX8 ^ lY8);
} else {
return (lResult ^ 0x40000000 ^ lX8 ^ lY8);
}
} else {
return (lResult ^ lX8 ^ lY8);
}
}
function md5_F(x, y, z) {
return (x & y) | ((~x) & z);
}
function md5_G(x, y, z) {
return (x & z) | (y & (~z));
}
function md5_H(x, y, z) {
return (x ^ y ^ z);
}
function md5_I(x, y, z) {
return (y ^ (x | (~z)));
}
function md5_FF(a, b, c, d, x, s, ac) {
a = md5_AddUnsigned(a, md5_AddUnsigned(md5_AddUnsigned(md5_F(b, c, d), x), ac));
return md5_AddUnsigned(md5_RotateLeft(a, s), b);
};
function md5_GG(a, b, c, d, x, s, ac) {
a = md5_AddUnsigned(a, md5_AddUnsigned(md5_AddUnsigned(md5_G(b, c, d), x), ac));
return md5_AddUnsigned(md5_RotateLeft(a, s), b);
};
function md5_HH(a, b, c, d, x, s, ac) {
a = md5_AddUnsigned(a, md5_AddUnsigned(md5_AddUnsigned(md5_H(b, c, d), x), ac));
return md5_AddUnsigned(md5_RotateLeft(a, s), b);
};
function md5_II(a, b, c, d, x, s, ac) {
a = md5_AddUnsigned(a, md5_AddUnsigned(md5_AddUnsigned(md5_I(b, c, d), x), ac));
return md5_AddUnsigned(md5_RotateLeft(a, s), b);
};
function md5_ConvertToWordArray(string) {
var lWordCount;
var lMessageLength = string.length;
var lNumberOfWords_temp1 = lMessageLength + 8;
var lNumberOfWords_temp2 = (lNumberOfWords_temp1 - (lNumberOfWords_temp1 % 64)) / 64;
var lNumberOfWords = (lNumberOfWords_temp2 + 1) * 16;
var lWordArray = Array(lNumberOfWords - 1);
var lBytePosition = 0;
var lByteCount = 0;
while (lByteCount < lMessageLength) {
lWordCount = (lByteCount - (lByteCount % 4)) / 4;
lBytePosition = (lByteCount % 4) * 8;
lWordArray[lWordCount] = (lWordArray[lWordCount] | (string.charCodeAt(lByteCount) << lBytePosition));
lByteCount++;
}
lWordCount = (lByteCount - (lByteCount % 4)) / 4;
lBytePosition = (lByteCount % 4) * 8;
lWordArray[lWordCount] = lWordArray[lWordCount] | (0x80 << lBytePosition);
lWordArray[lNumberOfWords - 2] = lMessageLength << 3;
lWordArray[lNumberOfWords - 1] = lMessageLength >>> 29;
return lWordArray;
};
function md5_WordToHex(lValue) {
var WordToHexValue = "",
WordToHexValue_temp = "",
lByte, lCount;
for (lCount = 0; lCount <= 3; lCount++) {
lByte = (lValue >>> (lCount * 8)) & 255;
WordToHexValue_temp = "0" + lByte.toString(16);
WordToHexValue = WordToHexValue + WordToHexValue_temp.substr(WordToHexValue_temp.length - 2, 2);
}
return WordToHexValue;
};
function md5_Utf8Encode(string) {
string = string.replace(/\r\n/g, "\n");
var utftext = "";
for (var n = 0; n < string.length; n++) {
var c = string.charCodeAt(n);
if (c < 128) {
utftext += String.fromCharCode(c);
} else if ((c > 127) && (c < 2048)) {
utftext += String.fromCharCode((c >> 6) | 192);
utftext += String.fromCharCode((c & 63) | 128);
} else {
utftext += String.fromCharCode((c >> 12) | 224);
utftext += String.fromCharCode(((c >> 6) & 63) | 128);
utftext += String.fromCharCode((c & 63) | 128);
}
}
return utftext;
};
var x = Array();
var k, AA, BB, CC, DD, a, b, c, d;
var S11 = 7,
S12 = 12,
S13 = 17,
S14 = 22;
var S21 = 5,
S22 = 9,
S23 = 14,
S24 = 20;
var S31 = 4,
S32 = 11,
S33 = 16,
S34 = 23;
var S41 = 6,
S42 = 10,
S43 = 15,
S44 = 21;
string = md5_Utf8Encode(string);
x = md5_ConvertToWordArray(string);
a = 0x67452301;
b = 0xEFCDAB89;
c = 0x98BADCFE;
d = 0x10325476;
for (k = 0; k < x.length; k += 16) {
AA = a;
BB = b;
CC = c;
DD = d;
a = md5_FF(a, b, c, d, x[k + 0], S11, 0xD76AA478);
d = md5_FF(d, a, b, c, x[k + 1], S12, 0xE8C7B756);
c = md5_FF(c, d, a, b, x[k + 2], S13, 0x242070DB);
b = md5_FF(b, c, d, a, x[k + 3], S14, 0xC1BDCEEE);
a = md5_FF(a, b, c, d, x[k + 4], S11, 0xF57C0FAF);
d = md5_FF(d, a, b, c, x[k + 5], S12, 0x4787C62A);
c = md5_FF(c, d, a, b, x[k + 6], S13, 0xA8304613);
b = md5_FF(b, c, d, a, x[k + 7], S14, 0xFD469501);
a = md5_FF(a, b, c, d, x[k + 8], S11, 0x698098D8);
d = md5_FF(d, a, b, c, x[k + 9], S12, 0x8B44F7AF);
c = md5_FF(c, d, a, b, x[k + 10], S13, 0xFFFF5BB1);
b = md5_FF(b, c, d, a, x[k + 11], S14, 0x895CD7BE);
a = md5_FF(a, b, c, d, x[k + 12], S11, 0x6B901122);
d = md5_FF(d, a, b, c, x[k + 13], S12, 0xFD987193);
c = md5_FF(c, d, a, b, x[k + 14], S13, 0xA679438E);
b = md5_FF(b, c, d, a, x[k + 15], S14, 0x49B40821);
a = md5_GG(a, b, c, d, x[k + 1], S21, 0xF61E2562);
d = md5_GG(d, a, b, c, x[k + 6], S22, 0xC040B340);
c = md5_GG(c, d, a, b, x[k + 11], S23, 0x265E5A51);
b = md5_GG(b, c, d, a, x[k + 0], S24, 0xE9B6C7AA);
a = md5_GG(a, b, c, d, x[k + 5], S21, 0xD62F105D);
d = md5_GG(d, a, b, c, x[k + 10], S22, 0x2441453);
c = md5_GG(c, d, a, b, x[k + 15], S23, 0xD8A1E681);
b = md5_GG(b, c, d, a, x[k + 4], S24, 0xE7D3FBC8);
a = md5_GG(a, b, c, d, x[k + 9], S21, 0x21E1CDE6);
d = md5_GG(d, a, b, c, x[k + 14], S22, 0xC33707D6);
c = md5_GG(c, d, a, b, x[k + 3], S23, 0xF4D50D87);
b = md5_GG(b, c, d, a, x[k + 8], S24, 0x455A14ED);
a = md5_GG(a, b, c, d, x[k + 13], S21, 0xA9E3E905);
d = md5_GG(d, a, b, c, x[k + 2], S22, 0xFCEFA3F8);
c = md5_GG(c, d, a, b, x[k + 7], S23, 0x676F02D9);
b = md5_GG(b, c, d, a, x[k + 12], S24, 0x8D2A4C8A);
a = md5_HH(a, b, c, d, x[k + 5], S31, 0xFFFA3942);
d = md5_HH(d, a, b, c, x[k + 8], S32, 0x8771F681);
c = md5_HH(c, d, a, b, x[k + 11], S33, 0x6D9D6122);
b = md5_HH(b, c, d, a, x[k + 14], S34, 0xFDE5380C);
a = md5_HH(a, b, c, d, x[k + 1], S31, 0xA4BEEA44);
d = md5_HH(d, a, b, c, x[k + 4], S32, 0x4BDECFA9);
c = md5_HH(c, d, a, b, x[k + 7], S33, 0xF6BB4B60);
b = md5_HH(b, c, d, a, x[k + 10], S34, 0xBEBFBC70);
a = md5_HH(a, b, c, d, x[k + 13], S31, 0x289B7EC6);
d = md5_HH(d, a, b, c, x[k + 0], S32, 0xEAA127FA);
c = md5_HH(c, d, a, b, x[k + 3], S33, 0xD4EF3085);
b = md5_HH(b, c, d, a, x[k + 6], S34, 0x4881D05);
a = md5_HH(a, b, c, d, x[k + 9], S31, 0xD9D4D039);
d = md5_HH(d, a, b, c, x[k + 12], S32, 0xE6DB99E5);
c = md5_HH(c, d, a, b, x[k + 15], S33, 0x1FA27CF8);
b = md5_HH(b, c, d, a, x[k + 2], S34, 0xC4AC5665);
a = md5_II(a, b, c, d, x[k + 0], S41, 0xF4292244);
d = md5_II(d, a, b, c, x[k + 7], S42, 0x432AFF97);
c = md5_II(c, d, a, b, x[k + 14], S43, 0xAB9423A7);
b = md5_II(b, c, d, a, x[k + 5], S44, 0xFC93A039);
a = md5_II(a, b, c, d, x[k + 12], S41, 0x655B59C3);
d = md5_II(d, a, b, c, x[k + 3], S42, 0x8F0CCC92);
c = md5_II(c, d, a, b, x[k + 10], S43, 0xFFEFF47D);
b = md5_II(b, c, d, a, x[k + 1], S44, 0x85845DD1);
a = md5_II(a, b, c, d, x[k + 8], S41, 0x6FA87E4F);
d = md5_II(d, a, b, c, x[k + 15], S42, 0xFE2CE6E0);
c = md5_II(c, d, a, b, x[k + 6], S43, 0xA3014314);
b = md5_II(b, c, d, a, x[k + 13], S44, 0x4E0811A1);
a = md5_II(a, b, c, d, x[k + 4], S41, 0xF7537E82);
d = md5_II(d, a, b, c, x[k + 11], S42, 0xBD3AF235);
c = md5_II(c, d, a, b, x[k + 2], S43, 0x2AD7D2BB);
b = md5_II(b, c, d, a, x[k + 9], S44, 0xEB86D391);
a = md5_AddUnsigned(a, AA);
b = md5_AddUnsigned(b, BB);
c = md5_AddUnsigned(c, CC);
d = md5_AddUnsigned(d, DD);
}
return (md5_WordToHex(a) + md5_WordToHex(b) + md5_WordToHex(c) + md5_WordToHex(d)).toLowerCase();
}