概述

MD5是一种广泛引用的密码散列函数,用于为任意长度的数据产生一个固定长128bits(16 bytes)的散列值,来确保信息传输的一致性.

MD5于1992年公开，用以取代MD4算法.

算法过程

1.数据填充

MD5和MD4的数据填充相同.

MD5可以对任意长度的数据进行散列,在算法之前需要对数据进行填充,使其位长度(bits)对512(64 bytes)求余的结果为448(56 bytes).即最后需要空出64bits(8 bytes),这8字节用于填充长度信息,因此最终结果对齐到512bits.

填充步骤如下:

在原始信息的末尾填充一个1和若干个0,直到满足上述求余结果.
在第1步结果的后面附加一个64bits长度的数据(其值为原始信息的长度信息,单位为bit),如果长度信息超过64bits,则取低64位.

注意:

填充数据应该使用小端序进行处理,包括原始数据和64bits的长度信息.
最终的结果是512bits对齐的,即每个分组为512bits.
后续说的1字(1-word)代表4字节,即32-bits.

2.初始化MD缓冲区

MD5使用4个缓冲区,命名为A,B,C,D.每个缓冲区均为32bits,以小端序储存:

word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10

由于以小端序存储,因此在C程序中应该为如下程序:

#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476

3.处理分组数据

每521bits(即64-bytes/16-words)数据为一组,每个分组单独进行处理.

注意:仍然以小端序进行处理.

四个辅助非线性函数F,G,H,I

首先定义四个辅助函数:

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) )

其中,F为"如果X则Y,否则Z; H为"诸位异或"或称之为"奇偶校验".

四个函数FF,GG,HH,II

定义如下:

FF(a ,b ,c ,d ,Mj ,s ,ti ): a = b + ( (a + F(b,c,d) + Mj + ti) <<< s)

GG(a ,b ,c ,d ,Mj ,s ,ti ): a = b + ( (a + G(b,c,d) + Mj + ti) <<< s)

HH(a ,b ,c ,d ,Mj ,s ,ti ): a = b + ( (a + H(b,c,d) + Mj + ti) <<< s)

II(a ,b ,c ,d ,Mj ,s ,ti ): a = b + ( (a + I(b,c,d) + Mj + ti) <<< s)

其中,<<<代表循环左移.

表T

如下是后面要用到的T表:

static const uint32_t 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  
};

主循环

该步骤使用一个有64个元素的表T[0...63],该表的每个元素T[i]的值为 $sin(i)*(2^{32})$ 的整数部分. 即T[i] = int(sin(i) * pow(2,32)),可以硬编码进程序,表如前所述.

将每个分组(512-bits/64bytes)分为16个子分组(4-bytes),即M[0...15]

首先需要将四个缓冲区A,B,C,D复制到另外的四个位置AA,BB,CC,DD:

AA = A
BB = B
CC = C
DD = D

注意在第一个分组处理之前,A,B,C,D已被初始化.

主循环处理每个16-WORDs的分组,共有四个轮次(ROUND),每个轮次都很相似,执行四轮操作:

/* ROUND 1 */
FF(A,B,C,D,M[0],7,T[1]);
FF(D,A,B,C,M[1],12,T[2]);
FF(C,D,A,B,M[2],17,T[3]);
FF(B,C,D,A,M[3],22,T[4]);

FF(A,B,C,D,M[4],7,T[5]);
FF(D,A,B,C,M[5],12,T[6]);
FF(C,D,A,B,M[6],17,T[7]);
FF(B,C,D,A,M[7],22,T[8]);

FF(A,B,C,D,M[8],7,T[9]);
FF(D,A,B,C,M[9],12,T[10]);
FF(C,D,A,B,M[10],17,T[11]);
FF(B,C,D,A,M[11],22,T[12]);

FF(A,B,C,D,M[12],7,T[13]);
FF(D,A,B,C,M[13],12,T[14]);
FF(C,D,A,B,M[14],17,T[15]);
FF(B,C,D,A,M[15],22,T[16]);

/* ROUND 2 */
GG(A,B,C,D,M[1],5,T[17]);
GG(D,A,B,C,M[6],9,T[18]);
GG(C,D,A,B,M[11],14,T[19]);
GG(B,C,D,A,M[0],20,T[20]);

GG(A,B,C,D,M[5],5,T[21]);
GG(D,A,B,C,M[10],9,T[22]);
GG(C,D,A,B,M[15],14,T[23]);
GG(B,C,D,A,M[4],20,T[24]);

GG(A,B,C,D,M[9],5,T[25]);
GG(D,A,B,C,M[14],9,T[26]);
GG(C,D,A,B,M[3],14,T[27]);
GG(B,C,D,A,M[8],20,T[28]);

GG(A,B,C,D,M[13],5,T[29]);
GG(D,A,B,C,M[2],9,T[30]);
GG(C,D,A,B,M[7],14,T[31]);
GG(B,C,D,A,M[12],20,T[32]);

/* ROUND 3 */
HH(A,B,C,D,M[5],4,T[33]);
HH(D,A,B,C,M[8],11,T[34]);
HH(C,D,A,B,M[11],16,T[35]);
HH(B,C,D,A,M[14],23,T[36]);

HH(A,B,C,D,M[1],4,T[37]);
HH(D,A,B,C,M[4],11,T[38]);
HH(C,D,A,B,M[7],16,T[39]);
HH(B,C,D,A,M[10],23,T[40]);

HH(A,B,C,D,M[13],4,T[41]);
HH(D,A,B,C,M[0],11,T[42]);
HH(C,D,A,B,M[3],16,T[43]);
HH(B,C,D,A,M[6],23,T[44]);

HH(A,B,C,D,M[9],4,T[45]);
HH(D,A,B,C,M[12],11,T[46]);
HH(C,D,A,B,M[15],16,T[47]);
HH(B,C,D,A,M[2],23,T[48]);

/* ROUND 4 */
II(A,B,C,D,M[0],6,T[49]);
II(D,A,B,C,M[7],10,T[50]);
II(C,D,A,B,M[14],15,T[51]);
II(B,C,D,A,M[5],21,T[52]);

II(A,B,C,D,M[12],6,T[53]);
II(D,A,B,C,M[3],10,T[54]);
II(C,D,A,B,M[10],15,T[55]);
II(B,C,D,A,M[1],21,T[56]);

II(A,B,C,D,M[8],6,T[57]);
II(D,A,B,C,M[15],10,T[58]);
II(C,D,A,B,M[6],15,T[59]);
II(B,C,D,A,M[13],21,T[60]);

II(A,B,C,D,M[4],6,T[61]);
II(D,A,B,C,M[11],10,T[62]);
II(C,D,A,B,M[2],15,T[63]);
II(B,C,D,A,M[9],21,T[64]);

然后,四个缓冲区(寄存器): A,B,C,D增加其原来的值:

A = A + AA
B = B + BB
C = C + CC
D = D + DD

到此,一轮主循环结束,如此逐个使用每个16-WORDs分组执行以上算法.

输出结果

最终输出的结果即为四个缓冲区的值A,B,C,D的级联,共128-bits,一般将其转换为16进制表示.
注意: 输出时,从A的低字节开始,到D的高字节结束,即小端序.(?)

参阅

RFC 1321 - The MD5 Message-Digest Algorithm