MD5哈希算法的压缩函数设计
字数 2486 2025-12-06 14:01:14

MD5哈希算法的压缩函数设计

MD5（Message-Digest Algorithm 5）是一种广泛使用的密码哈希函数，可将任意长度的消息映射为128位（16字节）的哈希值。其核心是压缩函数，它将一个512位的消息分组和128位的中间状态（四个32位寄存器A、B、C、D的当前值）作为输入，并输出更新后的128位状态。下面我将循序渐进地讲解其设计细节。

1. 压缩函数的整体流程
压缩函数对每个512位消息分组执行64轮运算。每轮处理一个32位消息子块，并使用不同的常量、循环左移位数和逻辑函数。整体步骤如下：

  • 输入：128位当前状态（四个32位寄存器A、B、C、D的当前值，每个32位）、512位消息分组。
  • 处理：将消息分组划分为16个32位子块（M[0]到M[15]），并通过消息扩展生成64个32位子块（用于64轮运算）。然后，在64轮中，依次更新寄存器A、B、C、D的值。
  • 输出：压缩函数结束时，将更新后的A、B、C、D与初始状态（输入前的值）模2^32相加，作为新的128位状态。

2. 消息扩展：从16个子块到64个子块
消息分组最初划分为16个32位子块M[0…15]。在64轮中，每轮使用一个扩展后的消息子块W[t]（t从0到63），其定义如下：

  • 对于前16轮（t=0到15）：W[t] = M[t]。
  • 对于后续48轮（t=16到63）：W[t] = M[(1 + 5t) mod 16]（这是简化的表达，实际中通过循环左移和异或运算生成，但标准MD5使用特定索引规则，见下一步）。
    实际上，MD5使用固定的索引数组来选取M中的子块。对于第i轮（i从1到64），使用的消息子块索引k[i]是预先定义的，例如：
    • 第1-16轮：依次使用M[0…15]。
    • 第17-32轮：依次使用M[(1 + 5(i-17)) mod 16]等（具体公式为k[i] = (1 + 5(i-1)) mod 16 for i=17..32，但标准实现使用一个固定表，见RFC 1321）。
      为简化，你可以记住：MD5的64轮中，每轮使用一个M中的子块，但顺序是打乱的，以增加雪崩效应。

3. 四轮逻辑函数与常量
64轮分为四组，每组16轮，每组使用不同的非线性逻辑函数F、G、H、I（每个函数输入三个32位寄存器B、C、D，输出32位）：

  • 第1轮（1-16）：F(B, C, D) = (B ∧ C) ∨ (¬B ∧ D) （条件函数：如果B则C，否则D）
  • 第2轮（17-32）：G(B, C, D) = (B ∧ D) ∨ (C ∧ ¬D)
  • 第3轮（33-48）：H(B, C, D) = B ⊕ C ⊕ D （按位异或）
  • 第4轮（49-64）：I(B, C, D) = C ⊕ (B ∨ ¬D) （多数函数变种）
    此外，每轮使用一个32位常量T[i]（i从1到64），定义为T[i] = floor(2^32 * |sin(i)|)的整数部分，其中sin是正弦函数，i以弧度为单位。这提供了伪随机常数，避免规律性。

4. 单轮运算的步骤详解
以第i轮为例（i从1到64），假设当前寄存器值为A、B、C、D（每轮前更新顺序会循环右移），单轮更新一个寄存器（总是A），其他寄存器移位。具体步骤：

  1. 选择逻辑函数：根据轮数确定使用F、G、H或I，计算结果记为f。
  2. 加法1：计算 (A + f) mod 2^32。
  3. 加法2：加上消息子块W[k]（k为当前轮对应的M索引）模2^32。
  4. 加法3：加上常量T[i]模2^32。
  5. 循环左移：将结果循环左移s位（s是预定义的，每轮不同，范围在1到16之间）。
  6. 加法4：加上B模2^32，结果存入A。
  7. 寄存器循环右移：更新顺序为 (原始D, 新A, 原始B, 原始C)，但注意实际实现中，每轮后寄存器会重新标记，使A、B、C、D循环右移一位（即原B成为新A，原C成为新B，原D成为新C，原A成为新D）。
    更准确地说，标准MD5的伪代码如下（以第i轮为例）：
    a = B + ((A + f(B, C, D) + M[k] + T[i]) <<< s)
    然后更新：A = D, B = a, C = B, D = C（但注意这是循环赋值，实际代码通常用临时变量）。
    其中<<<表示循环左移，s是预定义的移位数。

5. 四组轮次的参数差异
四组轮次在逻辑函数、消息子块索引k、循环左移位数s上不同：

  • 第1-16轮：使用F函数，k = i-1（即M[0]到M[15]），s为[7,12,17,22]的循环。
  • 第17-32轮：使用G函数，k = (5i-4) mod 16（实际为固定表），s为[5,9,14,20]的循环。
  • 第33-48轮：使用H函数，k = (3i+2) mod 16（固定表），s为[4,11,16,23]的循环。
  • 第49-64轮：使用I函数，k = (7i-7) mod 16（固定表），s为[6,10,15,21]的循环。
    这些参数确保了充分的扩散和混淆。

6. 最终输出
64轮后，得到更新的A、B、C、D。然后执行以下操作：

  • A_new = (A_old + A) mod 2^32
  • B_new = (B_old + B) mod 2^32
  • C_new = (C_old + C) mod 2^32
  • D_new = (D_old + D) mod 2^32
    其中A_old、B_old、C_old、D_old是压缩函数开始前的初始状态（来自前一分组或初始向量IV）。结果A_new、B_new、C_new、D_new作为下一个分组的输入状态，或最后一个分组处理后拼接为128位哈希值。

总结：MD5压缩函数通过消息扩展、四轮非线性函数、模2^32加法和循环左移，将消息分组和当前状态混合，产生雪崩效应。尽管MD5因碰撞攻击已不适用于安全场景，但其设计体现了经典哈希压缩函数的思路。

MD5哈希算法的压缩函数设计 MD5（Message-Digest Algorithm 5）是一种广泛使用的密码哈希函数，可将任意长度的消息映射为128位（16字节）的哈希值。其核心是压缩函数，它将一个512位的消息分组和128位的中间状态（四个32位寄存器A、B、C、D的当前值）作为输入，并输出更新后的128位状态。下面我将循序渐进地讲解其设计细节。 1. 压缩函数的整体流程 压缩函数对每个512位消息分组执行64轮运算。每轮处理一个32位消息子块，并使用不同的常量、循环左移位数和逻辑函数。整体步骤如下： 输入 ：128位当前状态（四个32位寄存器A、B、C、D的当前值，每个32位）、512位消息分组。 处理 ：将消息分组划分为16个32位子块（M[ 0]到M[ 15 ]），并通过消息扩展生成64个32位子块（用于64轮运算）。然后，在64轮中，依次更新寄存器A、B、C、D的值。 输出 ：压缩函数结束时，将更新后的A、B、C、D与初始状态（输入前的值）模2^32相加，作为新的128位状态。 2. 消息扩展：从16个子块到64个子块 消息分组最初划分为16个32位子块M[ 0…15]。在64轮中，每轮使用一个扩展后的消息子块W[ t ]（t从0到63），其定义如下： 对于前16轮（t=0到15）：W[ t] = M[ t ]。 对于后续48轮（t=16到63）：W[ t] = M[ (1 + 5t) mod 16 ]（这是简化的表达，实际中通过循环左移和异或运算生成，但标准MD5使用特定索引规则，见下一步）。 实际上，MD5使用固定的索引数组来选取M中的子块。对于第i轮（i从1到64），使用的消息子块索引k[ i ]是预先定义的，例如： 第1-16轮：依次使用M[ 0…15 ]。 第17-32轮：依次使用M[ (1 + 5(i-17)) mod 16]等（具体公式为k[ i ] = (1 + 5(i-1)) mod 16 for i=17..32，但标准实现使用一个固定表，见RFC 1321）。 为简化，你可以记住：MD5的64轮中，每轮使用一个M中的子块，但顺序是打乱的，以增加雪崩效应。 3. 四轮逻辑函数与常量 64轮分为四组，每组16轮，每组使用不同的非线性逻辑函数F、G、H、I（每个函数输入三个32位寄存器B、C、D，输出32位）： 第1轮（1-16）：F(B, C, D) = (B ∧ C) ∨ (¬B ∧ D) （条件函数：如果B则C，否则D） 第2轮（17-32）：G(B, C, D) = (B ∧ D) ∨ (C ∧ ¬D) 第3轮（33-48）：H(B, C, D) = B ⊕ C ⊕ D （按位异或） 第4轮（49-64）：I(B, C, D) = C ⊕ (B ∨ ¬D) （多数函数变种） 此外，每轮使用一个32位常量T[ i]（i从1到64），定义为T[ i] = floor(2^32 * |sin(i)|)的整数部分，其中sin是正弦函数，i以弧度为单位。这提供了伪随机常数，避免规律性。 4. 单轮运算的步骤详解 以第i轮为例（i从1到64），假设当前寄存器值为A、B、C、D（每轮前更新顺序会循环右移），单轮更新一个寄存器（总是A），其他寄存器移位。具体步骤： 选择逻辑函数：根据轮数确定使用F、G、H或I，计算结果记为f。 加法1：计算 (A + f) mod 2^32。 加法2：加上消息子块W[ k ]（k为当前轮对应的M索引）模2^32。 加法3：加上常量T[ i ]模2^32。 循环左移：将结果循环左移s位（s是预定义的，每轮不同，范围在1到16之间）。 加法4：加上B模2^32，结果存入A。 寄存器循环右移：更新顺序为 (原始D, 新A, 原始B, 原始C)，但注意实际实现中，每轮后寄存器会重新标记，使A、B、C、D循环右移一位（即原B成为新A，原C成为新B，原D成为新C，原A成为新D）。 更准确地说，标准MD5的伪代码如下（以第i轮为例）： a = B + ((A + f(B, C, D) + M[ k] + T[ i]) << < s) 然后更新：A = D, B = a, C = B, D = C（但注意这是循环赋值，实际代码通常用临时变量）。 其中<< <表示循环左移，s是预定义的移位数。 5. 四组轮次的参数差异 四组轮次在逻辑函数、消息子块索引k、循环左移位数s上不同： 第1-16轮：使用F函数，k = i-1（即M[ 0]到M[ 15]），s为[ 7,12,17,22 ]的循环。 第17-32轮：使用G函数，k = (5i-4) mod 16（实际为固定表），s为[ 5,9,14,20 ]的循环。 第33-48轮：使用H函数，k = (3i+2) mod 16（固定表），s为[ 4,11,16,23 ]的循环。 第49-64轮：使用I函数，k = (7i-7) mod 16（固定表），s为[ 6,10,15,21 ]的循环。 这些参数确保了充分的扩散和混淆。 6. 最终输出 64轮后，得到更新的A、B、C、D。然后执行以下操作： A_ new = (A_ old + A) mod 2^32 B_ new = (B_ old + B) mod 2^32 C_ new = (C_ old + C) mod 2^32 D_ new = (D_ old + D) mod 2^32 其中A_ old、B_ old、C_ old、D_ old是压缩函数开始前的初始状态（来自前一分组或初始向量IV）。结果A_ new、B_ new、C_ new、D_ new作为下一个分组的输入状态，或最后一个分组处理后拼接为128位哈希值。 总结 ：MD5压缩函数通过消息扩展、四轮非线性函数、模2^32加法和循环左移，将消息分组和当前状态混合，产生雪崩效应。尽管MD5因碰撞攻击已不适用于安全场景，但其设计体现了经典哈希压缩函数的思路。