Skip to main content

3. MD5 算法描述 (MD5 Algorithm Description)

我们首先假设我们有一个 b 位的消息作为输入,并且我们希望找到它的消息摘要。这里 b 是一个任意的非负整数,b 可以为零,它不需要是 8 的倍数,并且它可以任意大。我们假设消息的位按如下方式写下:

m_0 m_1 ... m_{b-1}

执行以下五个步骤来计算消息的消息摘要。

3.1 步骤 1. 追加填充位 (Step 1. Append Padding Bits)​

消息被"填充"(扩展),使其长度(以位为单位)对 512 取模后等于 448。也就是说,消息被扩展,使其恰好比 512 位的倍数少 64 位。填充总是要执行的,即使消息的长度已经对 512 取模后等于 448。

填充的执行方式如下:首先向消息追加一个"1"位,然后追加"0"位,使得填充后消息的位长度对 512 取模后等于 448。总共至少追加 1 位,最多追加 512 位。

3.2 步骤 2. 追加长度 (Step 2. Append Length)​

将 b 的 64 位表示(添加填充位之前消息的长度)追加到前一步骤的结果中。在不太可能的情况下,如果 b 大于 2^64,则仅使用 b 的低 64 位。(这些位作为两个 32 位字追加,并按照前面的约定先追加低位字。)

此时,得到的消息(在用位和 b 填充之后)的长度是 512 位的精确倍数。等价地,该消息的长度是 16 个(32 位)字的精确倍数。令 M[0 ... N-1] 表示得到的消息的字,其中 N 是 16 的倍数。

3.3 步骤 3. 初始化 MD 缓冲区 (Step 3. Initialize MD Buffer)​

使用一个四字缓冲区 (A,B,C,D) 来计算消息摘要。这里 A、B、C、D 各自是一个 32 位寄存器。这些寄存器被初始化为以下十六进制值(低位字节在前):

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

3.4 步骤 4. 以 16 字块处理消息 (Step 4. Process Message in 16-Word Blocks)​

我们首先定义四个辅助函数,每个函数接受三个 32 位字作为输入,并产生一个 32 位字作为输出。

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

在每个位位置上,F 充当条件运算:如果 X 则 Y 否则 Z。函数 F 本可以使用 + 而不是 v 来定义,因为 XY 和 not(X)Z 永远不会在同一位位置上都有 1。值得注意的是,如果 X、Y 和 Z 的位是独立且无偏的,则 F(X,Y,Z) 的每一位都将是独立且无偏的。

函数 G、H 和 I 与函数 F 类似,它们以"按位并行"的方式从 X、Y 和 Z 的位产生输出,使得如果 X、Y 和 Z 的相应位是独立且无偏的,则 G(X,Y,Z)、H(X,Y,Z) 和 I(X,Y,Z) 的每一位都将是独立且无偏的。注意,函数 H 是其输入的按位"xor"或"奇偶校验"函数。

此步骤使用从正弦函数构造的 64 元素表 T[1 ... 64]。令 T[i] 表示表的第 i 个元素,它等于 4294967296 乘以 abs(sin(i)) 的整数部分,其中 i 以弧度为单位。表的元素在附录中给出。

执行以下操作:

/* 处理每个 16 字块。 */
For i = 0 to N/16-1 do

  /* 将块 i 复制到 X 中。 */
  For j = 0 to 15 do
    Set X[j] to M[i*16+j].
  end /* of loop on j */

  /* 将 A 保存为 AA,B 保存为 BB,C 保存为 CC,D 保存为 DD。 */
  AA = A
  BB = B
  CC = C
  DD = D

  /* 第 1 轮。 */
  /* 令 [abcd k s i] 表示操作
       a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s)。 */
  /* 执行以下 16 个操作。 */
  [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
  [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
  [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
  [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

  /* 第 2 轮。 */
  /* 令 [abcd k s i] 表示操作
       a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)。 */
  /* 执行以下 16 个操作。 */
  [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
  [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
  [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
  [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]

  /* 第 3 轮。 */
  /* 令 [abcd k s t] 表示操作
       a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)。 */
  /* 执行以下 16 个操作。 */
  [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
  [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
  [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
  [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]

  /* 第 4 轮。 */
  /* 令 [abcd k s t] 表示操作
       a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)。 */
  /* 执行以下 16 个操作。 */
  [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
  [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
  [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
  [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]

  /* 然后执行以下加法。(即用该块开始之前的值递增四个寄存器中的每一个。) */
  A = A + AA
  B = B + BB
  C = C + CC
  D = D + DD

end /* of loop on i */

3.5 步骤 5. 输出 (Step 5. Output)​

作为输出产生的消息摘要是 A、B、C、D。也就是说,我们从 A 的低位字节开始,以 D 的高位字节结束。

这就完成了 MD5 的描述。附录中给出了 C 语言的参考实现。

Last updated on