SM3 密码杂凑算法深度解析：从 Merkle-Damgård 结构到安全性证明

SM3 是我国商用密码标准中的密码杂凑算法，输出长度 256 比特，本质上是与 SHA-256 同级别的安全哈希函数。但二者在内部结构、常量设计和安全性边界上存在显著差异。本文从零拆解 SM3 的完整算法流程，结合 GM/T 0004-2012 标准原文，分析其设计思想与安全特性。

一、算法总览：输入输出与标准体系

SM3 将任意长度的消息映射为 256 比特（32 字节） 的杂凑值，适用于数字签名、消息认证码、随机数生成等场景。

标准映射

基础性质

• 抗碰撞性：找到两个不同消息产生相同哈希值的计算复杂度为 $2^{128}$（生日攻击下限）
• 抗原像性：给定哈希值 $H$，找原消息 $M$ 使 $H(M)=H$ 的复杂度为 $2^{256}$
• 雪崩效应：输入 1 比特变化导致输出约 50% 比特翻转
• 设计范式：Merkle-Damgård 迭代结构（与 SHA-256、MD5 同族）

二、消息填充：任意长度 → 512 比特分组

SM3 的填充规则与 SHA-256 一致，确保消息长度对齐到 512 比特（64 字节） 的整数倍。

填充步骤

步骤1: 附加比特 '1'（0x80）
步骤2: 填充 k 个 '0' 比特，使消息长度 ≡ 448 (mod 512)
步骤3: 附加 64 比特，表示原始消息长度的二进制（大端序）

示例：消息 "abc"

原始消息: 0x61 0x62 0x63（24 比特 = 3 字节）
填充后（64 字节 = 512 比特）:
  61 62 63 80 00 00 ... 00 00 18
  └─原始─┘ ↑  └──── 43 个 0x00 ────┘  └长度─┘
           0x80 = 1000 0000b               24 = 0x18（原始长度）

验证：消息 "abc" 的填充过程：

• 原始：3 字节 = 24 比特
• 附加 0x80（1 字节）+ 52 字节 0x00 = 53 字节
• 附加长度 8 字节 = 8 字节
• 总计：3 + 53 + 8 = 64 字节 = 512 比特 ✓

• 要求：$(3 + 1 + k + 8) \times 8 \equiv 0 \pmod{512}$
• $(12 + k) \times 8 = 512 \Rightarrow k = 52$

三、压缩函数：512 比特 → 256 比特的核心变换

SM3 的核心是压缩函数 $CF$，它将当前的 256 比特链变量 $CV^{(i)}$ 与 512 比特消息分组 $B^{(i)}$ 混合，输出新的链变量 $CV^{(i+1)}$。

$$CV^{(i+1)} = CF(CV^{(i)}, B^{(i)})$$

3.1 消息扩展（Message Expansion）

512 比特的消息分组首先被扩展为 132 个字（word，32 比特），供压缩函数使用：

步骤1: 将 512 比特分为 16 个字 W[0]..W[15]（每字 32 比特）
步骤2: 计算 W[16]..W[67]：
   for j = 16 to 67:
     W[j] = P1(W[j-16] XOR W[j-9]) XOR (W[j-3] <<< 15) XOR W[j-13]
步骤3: 并行计算 W'[0]..W'[63]：
   for j = 0 to 63:
     W'[j] = W[j] XOR W[j+4]

其中：

• <<< k 表示循环左移 k 比特
• P1(x) = x XOR (x <<< 15) XOR (x <<< 23)（置换函数）

3.2 布尔函数（Boolean Functions）

SM3 使用两个布尔函数，在不同轮次执行不同的非线性操作：

$$ FF_j(X,Y,Z) = \begin{cases} X \oplus Y \oplus Z & 0 \le j \le 15 \\ (X \wedge Y) \vee (X \wedge Z) \vee (Y \wedge Z) & 16 \le j \le 63 \end{cases} $$

$$ GG_j(X,Y,Z) = \begin{cases} X \oplus Y \oplus Z & 0 \le j \le 15 \\ (X \wedge Y) \vee (\neg X \wedge Z) & 16 \le j \le 63 \end{cases} $$

与 SHA-256 对比：

3.3 置换函数（Permutation）

SM3 使用两个置换函数实现比特级扩散：

$$ P_0(X) = X \oplus (X \lll 9) \oplus (X \lll 17) $$ $$ P_1(X) = X \oplus (X \lll 15) \oplus (X \lll 23) $$

其中 <<< k 表示 32 位字的循环左移。

置换矩阵分析：

• $P_0$ 的移位量 (9, 17) 确保相邻比特在三次 XOR 后充分混合
• $P_1$ 的移位量 (15, 23) 在消息扩展中产生长距离依赖
• 两者的循环移位距离差为 8，确保低频和高频分量均被扩散

3.4 单轮变换（64 步迭代）

压缩函数的核心是 64 步迭代，每步更新 8 个 32 比特寄存器 A-H：

初始化: A-H 取自当前链变量 CV = (A, B, C, D, E, F, G, H)

for j = 0 to 63:
    Tj = 常量（见下文）
    SS1 = ((A <<< 12) + E + (Tj <<< j)) <<< 7
    SS2 = SS1 XOR (A <<< 12)
    TT1 = FFj(A,B,C) + D + SS2 + W'[j]
    TT2 = GGj(E,F,G) + H + SS1 + W[j]
    D = C
    C = B <<< 9
    B = A
    A = TT1
    H = G
    G = F <<< 19
    F = E
    E = P0(TT2)

更新链变量:
    CV^{(i+1)} = (A,B,C,D,E,F,G,H) XOR CV^{(i)}

3.5 轮常量 Tj

每轮使用不同的常量，打破对称性：

$$ T_j = \begin{cases} \text{79cc4519} & 0 \le j \le 15 \\ \text{7a879d8a} & 16 \le j \le 63 \end{cases} $$

设计分析：

• Tj 在 0-15 轮和 16-63 轮分别取固定值，轮内通过循环移位 <<< j 产生变化
• 这种"常量 + 循环移位"的设计既保证每轮差异化，又避免了 64 个独立常量的存储开销

四、初始值（IV）与输出变换

初始向量 IV

SM3 的初始链变量为固定常量：

$$ IV = \text{7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e} $$

这是标准的"nothing-up-my-sleeve"数，通过特定数学常数导出，确保无后门。

输出变换

最终所有消息分组处理完毕后，链变量直接作为哈希输出：

$$H = CV^{(N)} = (A \parallel B \parallel C \parallel D \parallel E \parallel F \parallel G \parallel H)$$

与 MD5/SHA-1 的区别：SM3 没有额外的输出变换（如 MD5 的逆序输出），直接拼接。

五、安全性分析

5.1 抗碰撞攻击

生日攻击下限：$2^{128}$ 次运算（256 比特输出）

已知攻击结果（公开文献）：

• 截至 2024 年，SM3 完整 64 轮的抗碰撞攻击尚未公开，无实际威胁
• 已有学术研究集中在简化轮次（约 20-30 轮）的碰撞/近碰撞攻击，使用差分分析、多差分分析等技术
• 这些攻击仅针对轮次缩减版本，不影响实际部署的安全性

5.2 与 SHA-256 的安全对比

• 后 48 轮的非线性操作足以消除前 16 轮积累的差分
• 消息扩展的强扩散性
• 置换函数 $P_0$ 的有效比特混合

5.3 侧信道抵抗

SM3 的纯比特操作（XOR、AND、移位）天然抵抗时序攻击，无查表操作（不像 AES/S-box），因此无需额外防护。

六、工程实现与性能

6.1 Python 实现（gmssl）

from gmssl.sm3 import sm3_hash
from gmssl.func import bytes_to_list, list_to_bytes

def sm3_hash_bytes(data: bytes) -> bytes:
    """计算 SM3 哈希值"""
    hash_hex = sm3_hash(bytes_to_list(data))
    return bytes.fromhex(hash_hex)

# 测试向量验证
assert sm3_hash_bytes(b"abc") == bytes.fromhex(
    "66c7f0f462eeedd9d1f2d46bdc10e4e24167c4875cf2f7a2297da02b8f4ba8e0"
)

6.2 性能参考

在典型 x86-64 处理器（Intel i7-10700）上：

七、标准符合性与密评要求

7.1 密评场景中的 SM3 用途

在 GB/T 22239 等保三级和 GM/T 0054-2018 中，SM3 应用于：

• 完整性校验：数据/配置文件的杂凑保护
• 数字签名：SM2 with SM3（OID: 1.2.156.10197.1.501）
• 消息认证码：HMAC-SM3
• 随机数生成：GM/T 0005-2012 要求使用 SM3 进行随机性检测后处理

7.2 常见误用

八、总结

SM3 作为国密体系的哈希基石，其设计融合了 Merkle-Damgård 结构的成熟性和国产密码标准的自主性。理解 SM3 的内部构造（消息扩展、布尔函数、置换操作）不仅有助于正确实现，更能帮助工程师在密评场景中准确评估哈希使用的合规性。

核心要点：

• SM3 输出 256 比特，抗碰撞 $2^{128}$
• 压缩函数使用 64 轮迭代，布尔函数分前后两段设计
• 消息扩展通过 $W$ 和 $W'$ 两轮扩散实现强雪崩
• 与 SHA-256 安全性相当，但密码分析公开程度较低
• 密评场景必须使用 SM3，禁止用 SHA-256 替代

相关实践：

• SM2 with SM3 数字签名实战（即将推出）
• HMAC-SM3 消息认证码实现（即将推出）
• 国密 TLS 中的哈希算法协商

• GM/T 0004-2012《SM3 密码杂凑算法》
• GB/T 32905-2016《信息安全技术 SM3 密码杂凑算法》