MD4哈希算法的消息扩展过程详解 我将为您详细讲解MD4哈希算法的消息扩展过程，这个过程是MD4算法将输入消息转换为算法内部处理块的关键步骤。 一、算法背景与基本概念 MD4是Ron Rivest于1990年设计的早期哈希算法，输出128位哈希值。虽然已被证明不安全（存在碰撞攻击），但其结构影响了后续哈希算法设计。消息扩展过程发生在 预处理阶段 ，目标是将任意长度的原始消息转换为512位的整数倍数据块。 二、完整消息扩展流程 步骤1：消息长度记录 在处理开始前，算法会记录原始消息的 位长度 （bit length），记为L。例如，消息"abc"（3字节=24位），则L=24。这个长度值将在后续填充步骤中使用。 步骤2：填充消息（核心） MD4要求输入长度必须是512位（64字节）的整数倍。填充规则如下： 添加一个"1"位 ：在原始消息末尾添加一个二进制"1"。在实际实现中，通常添加字节0x80（二进制10000000），因为消息通常按字节处理。 添加"0"位 ：在"1"位之后，添加尽可能多的"0"位，直到消息长度满足： （当前总长度 + 64） mod 512 = 0 这里的64位是为存储原始长度预留的空间。 添加原始长度 ：最后64位（8字节）以 小端序（little-endian） 存储原始消息的位长度L。如果L超过2⁶⁴-1，则只取低64位。 举例说明 ： 假设消息是"abc"（3字节）： 原始数据：01100001 01100010 01100011（ASCII表示） 第一步后：01100001 01100010 01100011 10000000（添加0x80） 需要填充"0"直到总长度（不包括最后64位）为512-64=448位 当前已有32位（3字节）+8位=40位，还需408个"0"位（51字节） 最后添加64位的小端序长度：24位=0x18，小端存储为0x18000000 00000000 三、内部块划分与子块生成 填充后的消息被划分为N个512位块：M⁽¹⁾, M⁽²⁾, ..., M⁽N⁾。 每个512位块进一步划分为16个32位 消息子块 ，记为： M₀, M₁, ..., M₁₅（每个32位） 这是 第一级扩展 ，每个Mᵢ可以直接用于MD4主循环的前16轮运算。 四、更深入的扩展（在压缩函数内部） MD4的压缩函数有3轮，每轮16步，共48步。但每轮只使用16个消息子块。消息扩展的巧妙之处在于： 第二轮 （17-32步）使用的消息顺序是： M₀, M₄, M₈, M₁₂, M₁, M₅, M₉, M₁₃, M₂, M₆, M₁₀, M₁₄, M₃, M₇, M₁₁, M₁₅ 第三轮 （33-48步）使用的消息顺序是： M₀, M₈, M₄, M₁₂, M₂, M₁₀, M₆, M₁₄, M₁, M₉, M₅, M₁₃, M₃, M₁₁, M₇, M₁₅ 注意：这只是 置换顺序 ，没有生成新数据。真正的"扩展"体现在： 每个512位块生成48个步骤的输入 但输入仍来自原始的16个32位字 通过不同的排列顺序，确保每个消息字被多次使用 五、技术细节解析 小端序的重要性 ： MD4所有操作基于小端序。例如，32位字0x12345678在内存中存储为0x78 0x56 0x34 0x12。这在处理来自网络（通常大端序）的数据时需要特别注意。 填充的确定性 ： 填充规则确保任意两个不同消息产生不同填充结果。即使两个消息只差一个"0"位，填充后的结果也会因长度字段不同而完全相异。 长度字段防碰撞 ： 最后64位的长度字段是防止某些扩展攻击的关键。如果没有它，攻击者可能构造M和M||padding使其哈希相同。 六、示例演算 假设消息为空字符串（L=0）： 添加0x80：10000000 填充"0"直到长度448位：需填充448-8=440个"0"位 添加长度0（64位全0） 最终得到一个512位块： 字节0: 0x80 字节1-55: 0x00（共55字节） 字节56-63: 0x00（8字节长度字段） 七、与后续算法的对比 MD5 ：消息扩展类似，但增加了更多的置换模式 SHA-1 ：不仅重新排序，还通过函数生成新的消息字 SHA-256 ：有专门的消息调度函数，生成64个32位字 MD4的消息扩展相对简单，这也是其弱点之一，为后来的碰撞攻击提供了便利。 通过这个过程，任意长度的消息被规范化为标准格式，确保哈希算法的确定性输出，同时增加了抗碰撞能力（尽管MD4已被攻破）。理解这个过程是分析MD4安全性及其后续改进的基础。