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

题目描述
MD4是早期广泛使用的密码哈希函数，由Ronald Rivest于1990年设计。其核心是压缩函数，它负责将消息分组和当前状态（链接变量）混合，产生新的哈希值。本题要求详细解析MD4压缩函数的内部结构、运算步骤和设计逻辑。

解题过程

1. 预备知识：MD4概览
   MD4生成128位（16字节）哈希值。其输入消息经过填充和分块，每个消息块为512位（64字节）。压缩函数以当前链接变量（4个32位寄存器A, B, C, D）和一个512位消息块M为输入，输出更新后的链接变量。初始链接变量是固定的常量。

2. 压缩函数输入与预处理

   • 输入：
     • 链接变量 CV = (A, B, C, D)，每个为32位，初始值 IV 为：
       A = 0x67452301
       B = 0xEFCDAB89
       C = 0x98BADCFE
       D = 0x10325476
     • 消息块 M，512位，可表示为16个32位字 M[0] 到 M[15]（小端序）。
   • 处理前，将 A, B, C, D 复制到临时变量 a, b, c, d 中，即 a=A, b=B, c=C, d=D。整个压缩过程在 a, b, c, d 上进行，最后再与原始 A, B, C, D 相加。

3. 压缩函数的轮结构
   MD4压缩函数包含3轮，每轮16步，共48步。每轮使用一个不同的非线性函数 F, G, H 和一个常量表 K_i（每轮一个常量）。每轮对消息字 M[k] 的访问顺序是精心设计的排列。

   • 轮函数定义（对32位字 x, y, z 的操作）：
     • 第一轮函数 F(x, y, z) = (x ∧ y) ∨ (¬x ∧ z) // 选择函数：如果x则y，否则z
     • 第二轮函数 G(x, y, z) = (x ∧ y) ∨ (x ∧ z) ∨ (y ∧ z) // 多数函数：至少两个为真则结果为1
     • 第三轮函数 H(x, y, z) = x ⊕ y ⊕ z // 异或函数
   • 常量（十六进制，实际计算时取32位模 2^32）：
     • 第一轮常量 K1_j = 0x00000000（所有步骤）
     • 第二轮常量 K2_j = 0x5A827999
     • 第三轮常量 K3_j = 0x6ED9EBA1
   • 消息字顺序排列：每轮16步使用的消息字索引 k 不同：
     • 第一轮：k = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
     • 第二轮：k = 0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15
     • 第三轮：k = 0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15

4. 单步运算详解
   每一步对临时变量 a, b, c, d 中的三个进行非线性函数计算，然后与消息字、常量、循环左移相结合。每一步的形式为：

   a = (a + F(b, c, d) + M[k] + K_i) <<< s
   

   然后对 (a, b, c, d) 进行循环右移：即每一步后，四个寄存器的角色会轮换。具体来说，每一步的操作如下（以第 i 步为例，i 从0开始计数）：

   • 设当前寄存器状态为 (A0, B0, C0, D0)，对应 a, b, c, d。
   • 计算：T = (A0 + F(B0, C0, D0) + M[k] + K_i) mod 2^32
   • 将 T 循环左移 s 位，s 的值取决于轮数：
     • 第一轮：s = [3,7,11,19] 循环，即第0步移3位，第1步移7位，第2步移11位，第3步移19位，然后重复。
     • 第二轮：s = [3,5,9,13] 循环
     • 第三轮：s = [3,9,11,15] 循环
   • 更新寄存器：新的 a = T，同时将 (a, b, c, d) 右移一位，即新的状态为 (D0, T, B0, C0)。注意这里是右移寄存器角色，而非字循环右移。

   更清晰地说，每一步可表示为以下伪代码（设当前状态为a,b,c,d）：

   t = (a + F(b, c, d) + M[k] + K_i) mod 2^32
   t = (t <<< s)  // 循环左移s位
   (a, b, c, d) = (d, t, b, c)  // 注意赋值顺序：新的a是原来的d，新的b是t，新的c是原来的b，新的d是原来的c
   

   实际上，在常见实现中，更直观的更新方式是固定寄存器角色，每一步对不同的寄存器做运算。标准描述是：

   • 每一步更新 a：a = (a + F(b,c,d) + M[k] + K_i) <<< s
   • 然后旋转寄存器：(a, b, c, d) = (d, a, b, c) // 即a变成新b，b变成新c，c变成新d，d变成新a？注意这里容易混淆。

   准确地说，MD4的步骤是依次更新a, b, c, d，但每步后寄存器整体左移。典型实现代码结构为：

   for i in 0..15:  // 第一轮
       a = (a + F(b, c, d) + M[k1[i]]) <<< s1[i]
       (a, b, c, d) = (d, a, b, c)  // 旋转
   

   其中k1[i]是第一轮的消息字索引，s1[i]是第一轮的移位值。

5. 三轮运算完整过程
   为清晰起见，列出三轮的伪代码，使用临时变量AA, BB, CC, DD保存初始a,b,c,d。

   • 初始化：AA = a, BB = b, CC = c, DD = d
   • 第一轮（16步）：
     for i=0 to 15:
     index = i // 消息字顺序就是0..15
     shift = [3,7,11,19][i % 4] // 移位值循环
     temp = (AA + F(BB, CC, DD) + M[index]) mod 2^32
     temp = (temp <<< shift)
     (AA, BB, CC, DD) = (DD, temp, BB, CC) // 注意旋转
   • 第二轮（16步）：
     for i=0 to 15:
     index = (1 + 5*i) mod 16 // 实际上是第二轮顺序：0,4,8,12,1,5,9,13,2,6,10,14,3,7,11,15
     shift = [3,5,9,13][i % 4]
     temp = (AA + G(BB, CC, DD) + M[index] + K2) mod 2^32
     temp = (temp <<< shift)
     (AA, BB, CC, DD) = (DD, temp, BB, CC)
   • 第三轮（16步）：
     for i=0 to 15:
     index = [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15][i] // 第三轮固定顺序
     shift = [3,9,11,15][i % 4]
     temp = (AA + H(BB, CC, DD) + M[index] + K3) mod 2^32
     temp = (temp <<< shift)
     (AA, BB, CC, DD) = (DD, temp, BB, CC)

   注意：上述伪代码中，每轮使用的函数F/G/H和常量K不同。实际代码中，常将循环展开为16步显式写出。

6. 最终输出
   压缩函数完成三轮后，将临时变量与原始链接变量相加：

   A_new = (A + AA) mod 2^32
   B_new = (B + BB) mod 2^32
   C_new = (C + CC) mod 2^32
   D_new = (D + DD) mod 2^32
   

   得到的 (A_new, B_new, C_new, D_new) 作为下一个消息块的链接变量，或最后一个块的输出哈希值（按小端序输出字节）。

总结
MD4压缩函数通过三轮48步的混合，每轮使用不同的非线性函数、消息字顺序和循环左移，实现了雪崩效应。其设计简洁，但后来被发现存在严重的安全弱点（如碰撞攻击），因此已被MD5、SHA-1等替代。理解其结构有助于学习哈希函数的设计原理和密码分析基础。