概述

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

MD4由麻省理工学院教授Ronald Rivest设计于1990年,而后续被MD5所取代.

算法过程

1.数据填充

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

填充步骤如下:

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

注意:

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

2.初始化MD缓冲区

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

1
2
3
4
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程序中应该为如下程序:

1
2
3
4
#define A 0x67452301
#define B 0xefcdab89
#define C 0x98badcfe
#define D 0x10325476

3.处理分组数据

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

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

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

首先定义四个辅助函数:

1
2
3
4
5
F( X ,Y ,Z ) = ( X & Y ) | ( (~X) & Z )

G( X ,Y ,Z ) = ( X & Y ) | ( X & Z ) | ( Y & Z )

H( X ,Y ,Z ) = X ^ Y ^ Z

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

三个函数FF,GG,HH

定义如下:

1
2
3
4
5
FF(a ,b ,c ,d ,Mi ,s ): a = a + ( (a + F(b,c,d) + Mi) <<< s)

GG(a ,b ,c ,d ,Mi ,s ): a = a + ( (a + G(b,c,d) + Mj + 0x5A827999) <<< s)

HH(a ,b ,c ,d ,Mi ,s ): a = a + ( (a + H(b,c,d) + Mj + 0x6ED9EBA1) <<< s)

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

主循环

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

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

1
2
3
4
AA = A
BB = B
CC = C
DD = D

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/* ROUND 1 */
FF(A,B,C,D,M[0],3);
FF(D,A,B,C,M[1],7);
FF(C,D,A,B,M[2],11);
FF(B,C,D,A,M[3],19);

FF(A,B,C,D,M[4],3);
FF(D,A,B,C,M[5],7);
FF(C,D,A,B,M[6],11);
FF(B,C,D,A,M[7],19);

FF(A,B,C,D,M[8],3);
FF(D,A,B,C,M[9],7);
FF(C,D,A,B,M[10],11);
FF(B,C,D,A,M[11],19);

FF(A,B,C,D,M[12],3);
FF(D,A,B,C,M[13],7);
FF(C,D,A,B,M[14],11);
FF(B,C,D,A,M[15],19);
/* ROUND 2 */
GG(A,B,C,D,M[0],3);
GG(D,A,B,C,M[4],5);
GG(C,D,A,B,M[8],9);
GG(B,C,D,A,M[12],13);

GG(A,B,C,D,M[1],3);
GG(D,A,B,C,M[5],5);
GG(C,D,A,B,M[9],9);
GG(B,C,D,A,M[13],13);

GG(A,B,C,D,M[2],3);
GG(D,A,B,C,M[6],5);
GG(C,D,A,B,M[10],9);
GG(B,C,D,A,M[14],13);

GG(A,B,C,D,M[3],3);
GG(D,A,B,C,M[7],5);
GG(C,D,A,B,M[11],9);
GG(B,C,D,A,M[15],13);
/* ROUND 3 */
HH(A,B,C,D,M[0],3);
HH(D,A,B,C,M[8],9);
HH(C,D,A,B,M[4],11);
HH(B,C,D,A,M[12],15);

HH(A,B,C,D,M[2],3);
HH(D,A,B,C,M[10],9);
HH(C,D,A,B,M[6],11);
HH(B,C,D,A,M[14],15);

HH(A,B,C,D,M[1],3);
HH(D,A,B,C,M[9],9);
HH(C,D,A,B,M[5],11);
HH(B,C,D,A,M[13],15);

HH(A,B,C,D,M[3],3);
HH(D,A,B,C,M[11],9);
HH(C,D,A,B,M[7],11);
HH(B,C,D,A,M[15],15);

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

1
2
3
4
A = A + AA
B = B + BB
C = C + CC
D = D + DD

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

输出结果

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

参阅

RFC 1320: The MD4 Message-Digest Algorithm