SM3密码杂凑算法的消息扩展过程详解
字数 2202 2025-12-24 17:22:30

SM3密码杂凑算法的消息扩展过程详解

SM3是我国采用的一种密码杂凑算法（哈希函数），其输出长度为256位。它的整体结构与SHA-256类似，也采用了Merkle-Damgård结构，但其压缩函数的内部设计，特别是消息扩展过程，具有独特之处。消息扩展过程负责将每个512位的输入消息块，扩展生成132个32位字（W0~W67以及W'0~W'63），用于后续的压缩函数计算。理解这个过程是掌握SM3算法的关键。

我将循序渐进地为你讲解SM3的消息扩展过程，共分为四个主要步骤。

第一步：明确输入与目标

首先，SM3算法在填充和分组后，会将原始消息分割成若干个512位的消息块。对于每一个这样的512位消息块，我们都需要独立执行一次消息扩展。

  • 输入：一个512位的消息块，记为 B。
  • 目标：扩展生成两个数组：
    1. W 数组：包含68个32位字（W0, W1, ..., W67）。
    2. W' 数组：包含64个32位字（W'0, W1', ..., W'63）。

这些扩展字将为后续压缩函数的64轮运算提供“原料”。

第二步：消息块的初始划分

我们先将输入的512位消息块 B 视为一个由16个32位字顺序连接而成的序列。
记作：
B = (M0, M1, M2, ..., M15)
其中，每个 Mi 都是一个32位的字。

这最初的16个字，将作为我们生成扩展字序列的“种子”。

第三步：生成W数组（前68个字）

W数组的生成分为两个阶段：直接赋值和迭代扩展。

  1. 前16个字（W0 ~ W15）：
    这最简单，就是直接使用消息块划分出来的16个字。
    Wj = Mj，其中 j = 0, 1, 2, ..., 15。

  2. 后52个字（W16 ~ W67）：
    这52个字需要通过一个迭代公式计算得出。计算公式如下：
    Wj = P1( W(j-16) ⊕ W(j-9) ⊕ (W(j-3) <<< 15) ) ⊕ (W(j-13) <<< 7) ⊕ W(j-6)
    其中：

    • j 的取值范围是 16 到 67。
    • ⊕ 表示32位字的按位异或（XOR）运算。
    • <<< n 表示32位字的循环左移 n 位。
    • P1(X) 是一个线性置换函数，定义为：
      P1(X) = X ⊕ (X <<< 15) ⊕ (X <<< 23)

    让我们拆解这个公式的含义：

    • W(j-16) ⊕ W(j-9) ⊕ (W(j-3) <<< 15)：这部分组合了之前生成的、间隔不同的三个字。W(j-16) 是较早的、跨度较大的字，W(j-9) 和 W(j-3) 是较近的字。对 W(j-3) 循环左移15位是为了引入非线性扩散。
    • P1(...)：对这个组合结果应用P1函数。P1函数内部又进行了一次与自身的循环移位结果的异或，这极大地增加了比特的扩散和混淆效果，使得输出的每个比特都强烈依赖于输入的多个、不同位置的比特。
    • ⊕ (W(j-13) <<< 7) ⊕ W(j-6)：最后，再与另外两个经过不同位移处理的早期字进行异或。W(j-13)左移7位，W(j-6)不移位。这进一步将更多的历史状态混合进来，确保扩展序列具有良好的伪随机性和抗碰撞性。

    通过这个递推关系，我们可以从 W0~W15 开始，依次计算出 W16, W17, ..., W67。这个设计确保了每一个新生成的 Wj 都依赖于多个之前生成的、位置不同的字，形成了复杂的依赖网络。

第四步：生成W'数组（后64个字）

W'数组的生成规则相对简单，它由刚刚计算好的W数组直接变换而来。
计算公式为：
W'j = Wj ⊕ W(j+4)，其中 j = 0, 1, 2, ..., 63。

这里的要点是：

  • W'数组的每个字，是W数组中两个下标相差4的字的异或结果。
  • 这个操作可以看作是一种“压缩”或“二次混合”，它将68个字的W序列进一步“折叠”和“搅乱”，生成64个字的W'序列，正好对应压缩函数的64轮运算。

总结与回顾

现在，让我们回顾一下SM3消息扩展的全过程：

  1. 输入：一个512位的消息块 B。
  2. 初始划分：将 B 等分为16个32位字 M0~M15。
  3. 生成W数组：
    • 前16字：W0~W15 = M0~M15。
    • 后52字：用公式 Wj = P1( W(j-16)⊕W(j-9)⊕(W(j-3)<<<15) ) ⊕ (W(j-13)<<<7) ⊕ W(j-6) 依次计算 W16~W67。
  4. 生成W'数组：用公式 W'j = Wj ⊕ W(j+4) 计算 W'0~W'63。

最终，我们得到了 W0~W67 和 W'0~W'63 这两组扩展字。在接下来的压缩函数中，它们将作为每一轮运算的输入，与8个字的链接变量 A, B, C, D, E, F, G, H 以及固定的常量 Tj 一起，经过复杂的布尔函数和循环移位操作，不断更新链接变量，最终完成一个消息块的压缩。

SM3消息扩展过程的设计精巧之处在于，它通过递推公式和P1函数，将原始消息的512位（16字）充分“搅拌”和扩展，生成了大量具有高度扩散和混淆特性的中间字，极大地增强了算法对输入微小变化的敏感度（雪崩效应），从而奠定了其抗碰撞、抗原像攻击的密码学基础。

SM3密码杂凑算法的消息扩展过程详解 SM3是我国采用的一种密码杂凑算法（哈希函数），其输出长度为256位。它的整体结构与SHA-256类似，也采用了Merkle-Damgård结构，但其压缩函数的内部设计，特别是消息扩展过程，具有独特之处。消息扩展过程负责将每个512位的输入消息块，扩展生成132个32位字（W0~W67以及W'0~W'63），用于后续的压缩函数计算。理解这个过程是掌握SM3算法的关键。 我将循序渐进地为你讲解SM3的消息扩展过程，共分为四个主要步骤。 第一步：明确输入与目标 首先，SM3算法在填充和分组后，会将原始消息分割成若干个512位的消息块。对于 每一个 这样的512位消息块，我们都需要独立执行一次消息扩展。 输入 ：一个512位的消息块，记为 B 。 目标 ：扩展生成两个数组： W 数组：包含68个32位字（W0, W1, ..., W67）。 W' 数组：包含64个32位字（W'0, W1', ..., W'63）。 这些扩展字将为后续压缩函数的64轮运算提供“原料”。 第二步：消息块的初始划分 我们先将输入的512位消息块 B 视为一个由16个32位字顺序连接而成的序列。 记作： B = (M0, M1, M2, ..., M15) 其中，每个 Mi 都是一个32位的字。 这最初的16个字，将作为我们生成扩展字序列的“种子”。 第三步：生成W数组（前68个字） W数组的生成分为两个阶段：直接赋值和迭代扩展。 前16个字（W0 ~ W15） ： 这最简单，就是直接使用消息块划分出来的16个字。 Wj = Mj ，其中 j = 0, 1, 2, ..., 15 。 后52个字（W16 ~ W67） ： 这52个字需要通过一个迭代公式计算得出。计算公式如下： Wj = P1( W(j-16) ⊕ W(j-9) ⊕ (W(j-3) <<< 15) ) ⊕ (W(j-13) <<< 7) ⊕ W(j-6) 其中： j 的取值范围是 16 到 67 。 ⊕ 表示32位字的按位异或（XOR）运算。 <<< n 表示32位字的 循环左移 n 位。 P1(X) 是一个线性置换函数，定义为： P1(X) = X ⊕ (X <<< 15) ⊕ (X <<< 23) 让我们拆解这个公式的含义 ： W(j-16) ⊕ W(j-9) ⊕ (W(j-3) <<< 15) ：这部分组合了之前生成的、间隔不同的三个字。 W(j-16) 是较早的、跨度较大的字， W(j-9) 和 W(j-3) 是较近的字。对 W(j-3) 循环左移15位是为了引入非线性扩散。 P1(...) ：对这个组合结果应用 P1 函数。 P1 函数内部又进行了一次与自身的循环移位结果的异或，这极大地增加了比特的扩散和混淆效果，使得输出的每个比特都强烈依赖于输入的多个、不同位置的比特。 ⊕ (W(j-13) <<< 7) ⊕ W(j-6) ：最后，再与另外两个经过不同位移处理的早期字进行异或。 W(j-13) 左移7位， W(j-6) 不移位。这进一步将更多的历史状态混合进来，确保扩展序列具有良好的伪随机性和抗碰撞性。 通过这个递推关系，我们可以从 W0~W15 开始，依次计算出 W16, W17, ..., W67 。这个设计确保了每一个新生成的 Wj 都依赖于多个之前生成的、位置不同的字，形成了复杂的依赖网络。 第四步：生成W'数组（后64个字） W'数组的生成规则相对简单，它由刚刚计算好的W数组直接变换而来。 计算公式为： W'j = Wj ⊕ W(j+4) ，其中 j = 0, 1, 2, ..., 63 。 这里的要点是 ： W'数组的每个字，是W数组中两个下标相差4的字的异或结果。 这个操作可以看作是一种“压缩”或“二次混合”，它将68个字的W序列进一步“折叠”和“搅乱”，生成64个字的W'序列，正好对应压缩函数的64轮运算。 总结与回顾 现在，让我们回顾一下SM3消息扩展的全过程： 输入 ：一个512位的消息块 B 。 初始划分 ：将 B 等分为16个32位字 M0~M15 。 生成W数组 ： 前16字： W0~W15 = M0~M15 。 后52字：用公式 Wj = P1( W(j-16)⊕W(j-9)⊕(W(j-3)<<<15) ) ⊕ (W(j-13)<<<7) ⊕ W(j-6) 依次计算 W16~W67 。 生成W'数组 ：用公式 W'j = Wj ⊕ W(j+4) 计算 W'0~W'63 。 最终，我们得到了 W0~W67 和 W'0~W'63 这两组扩展字。在接下来的 压缩函数 中，它们将作为每一轮运算的输入，与8个字的链接变量 A, B, C, D, E, F, G, H 以及固定的常量 Tj 一起，经过复杂的布尔函数和循环移位操作，不断更新链接变量，最终完成一个消息块的压缩。 SM3消息扩展过程的设计精巧之处在于，它通过递推公式和P1函数，将原始消息的512位（16字）充分“搅拌”和扩展，生成了大量具有高度扩散和混淆特性的中间字，极大地增强了算法对输入微小变化的敏感度（雪崩效应），从而奠定了其抗碰撞、抗原像攻击的密码学基础。