跳到主要内容

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

我们首先假设有一个 b 位的消息作为输入, 并希望找到其消息摘要. 这里 b 是任意非负整数; b 可以为零, 不必是八的倍数, 并且可以任意大. 我们将消息的位写成如下形式:

m_0 m_1 ... m_{b-1}

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

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

消息被"填充 (padded)"(扩展), 使其长度 (以位为单位) 与 448 模 512 同余. 也就是说, 消息被扩展, 使其比 512 位的倍数少 64 位. 即使消息的长度已经与 448 模 512 同余, 也始终执行填充.

填充执行如下: 向消息追加一个 "1" 位, 然后追加 "0" 位, 使填充后消息的位长度与 448 模 512 同余. 总共追加至少一位, 最多 512 位.

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

将 b 的 64 位表示 (填充位添加之前的消息长度) 追加到上一步的结果中. 在 b 大于 2^64 的极少情况下, 只使用 b 的低 64 位. (这些位作为两个 32 位字追加, 低位字在前, 符合前面的约定.)

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

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

使用四字缓冲区 (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 Step 4. Process Message in 16-Word Blocks (步骤4. 以16字块处理消息)​

我们首先定义四个辅助函数, 每个函数以三个 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 Step 5. Output (步骤5. 输出)​

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

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

最后于 更新