SM3 密码杂凑算法原理详解：从消息填充到压缩函数

概述

SM3 是中国国家密码管理局于 2008 年发布的密码杂凑算法，2012 年作为密码行业标准公开发布（GM/T 0004-2012），2016 年作为 GB/T 32905-2016（配套标准）的引用算法。该算法设计由中国科学院数据安全与通信保密研究中心主导。

SM3 的设计目标是对 SHA-256 提供国产替代方案，提供256-bit 的杂凑值输出，安全强度与 SHA-256 相当（128-bit 抗碰撞安全性）。SM3 适用于数字签名、消息认证码、随机数生成、密钥派生等场景。

在国际标准化方面，SM3 已通过 IETF 作为 draft-sca-cfrg-sm3-02 发布，逐步被纳入国际标准体系。

算法基本参数

Merkle-Damgård 结构

SM3 采用经典的 Merkle-Damgård 迭代结构，将任意长度的消息压缩为固定长度的杂凑值。

算法整体流程

对于长度为 $l$ 比特的消息 $M$（$l < 2^{64}$）：

• 消息填充（Padding）：将 $M$ 填充为 512-bit 的倍数
• 消息分组：将填充后的消息分为 $t$ 个 512-bit 块 $M^{(0)}, M^{(1)}, \ldots, M^{(t-1)}$
• 迭代压缩：$CV_i = CF(CV_{i-1}, M^{(i)})$，初始值 $CV_0 = IV$
• 输出截断：$H(M) = CV_t$

消息填充

填充规则与 SHA-256 类似：

• 在消息末尾附加一个 1 比特
• 填充 0 比特，直到消息长度 $\equiv 448 \pmod{512}$
• 最后 64 比特存放原始消息长度 $l$（以大端序 64-bit 整数表示）

其中 $l_{64}$ 是 $l$ 的 64-bit 大端序编码。

示例：若原始消息长度为 55 字节（440 比特），则填充 1 比特 + 7 个 0 比特（使长度为 448 比特 = 56 字节），然后附加 8 字节的长度字段，总长度 = 64 字节 = 1 个分组。

压缩函数

压缩函数 $CF$ 是 SM3 的核心，它将一个 512-bit 的消息块和一个 256-bit 的中间值压缩为一个 256-bit 的输出。

状态表示

中间变量为 8 个 32-bit 字：$A, B, C, D, E, F, G, H$，每个 32 比特，共 256 比特。

初始值 $IV$（十六进制）：

7380166f 4914b2b9 172442d7 da8a0600
a96f30bc 163138aa e38dee4b d0fb0e4e

消息扩展

每个 512-bit 的消息块 $M^{(i)}$ 被扩展为 132 个 32-bit 字 $W_0, W_1, \ldots, W_{67}, W'_0, W'_1, \ldots, W'_{63}$：

第一步：将 512-bit 消息块分为 16 个 32-bit 字 $W_0, W_1, \ldots, W_{15}$

$$M^{(i)} = W_0 \| W_1 \| \ldots \| W_{15}$$

第二步：扩展 $W_{16}$ 到 $W_{67}$

对于 $j = 16, 17, \ldots, 67$： $$W_j = P_1(W_{j-16} \oplus W_{j-9} \oplus (W_{j-3} \lll 15)) \oplus (W_{j-13} \lll 7) \oplus W_{j-6}$$

其中 $\lll$ 表示循环左移，$P_1(X) = X \oplus (X \lll 15) \oplus (X \lll 23)$

第三步：计算 $W'_0, W'_1, \ldots, W'_{63}$

对于 $j = 0, 1, \ldots, 63$： $$W'_j = W_j \oplus W_{j+4}$$

轮函数

压缩函数包含 64 轮运算，每轮更新状态变量：

对于 $j = 0, 1, \ldots, 63$：

$$SS_1 = ((A \lll 12) + E + (T_j \lll j)) \lll 7$$ $$SS_2 = SS_1 \oplus (A \lll 12)$$ $$TT_1 = FF_j(A, B, C) + D + SS_2 + W'_j$$ $$TT_2 = GG_j(E, F, G) + H + SS_1 + W_j$$ $$D = C$$ $$C = B \lll 9$$ $$B = A$$ $$A = TT_1$$ $$H = G$$ $$G = F \lll 19$$ $$F = E$$ $$E = P_0(TT_2)$$

其中：

• $T_j$ 为常量：当 $0 \leq j \leq 15$ 时 $T_j = 0x79cc4519$；当 $16 \leq j \leq 63$ 时 $T_j = 0x7a879d8a$
• $P_0(X) = X \oplus (X \lll 9) \oplus (X \lll 17)$

布尔函数

$FF_j$ 和 $GG_j$ 是轮函数中的非线性布尔函数，根据轮数 $j$ 的不同使用不同的定义：

$FF_j(X, Y, Z)$：

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

$GG_j(X, Y, Z)$：

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

设计分析：前 16 轮使用简单的异或函数（与 SHA-256 的 $Ch$ 函数类似），后 48 轮使用更复杂的布尔函数。这种设计提供了更强的扩散性和抗差分攻击能力。

常量 $T_j$

轮函数中使用的常量 $T_j$：

$$T_j = \begin{cases} \text{0x79cc4519} & 0 \leq j \leq 15 \\ \text{0x7a879d8a} & 16 \leq j \leq 63 \end{cases}$$

这些常量通过 $\sin$ 函数的小数部分生成（类似 SHA-1/SHA-256 的设计方法），确保没有后门或隐藏模式。

最终输出

64 轮运算完成后，新的中间值与旧的中间值进行异或：

$$CV_{i+1} = (A \| B \| C \| D \| E \| F \| G \| H) \oplus CV_i$$

安全性分析

抗差分攻击

SM3 的 64 轮设计提供了充分的安全边际。根据现有分析：

• 最佳差分攻击覆盖约 26 轮（低于 64 轮设计）
• 差分概率上限远低于安全阈值
• 消息扩展的双路设计（$W_j$ 和 $W'_j$）增加了差分路径的复杂性

抗碰撞攻击

SM3 提供 128-bit 的抗碰撞安全性（因为输出长度为 256 bit，生日攻击需要 $O(2^{128})$ 次运算），与 SHA-256 相当。

与 SHA-256 的结构差异

标准体系

SM3 的标准体系：

性能特征

SM3 的性能特征（基于软件实现）：

注意：以上为典型参考值，实际性能取决于 CPU 架构、实现优化和编译器选项。

参考来源

• GM/T 0004-2012 — SM3 密码杂凑算法
• GM/T 0044-2016 — SM3 密码杂凑算法 第1部分
• NIST FIPS 180-4 — Secure Hash Standard (SHA-256)
• IETF draft-sca-cfrg-sm3-02 — SM3 Hash Function
• OSCCA — 密码发展史之近现代密码

相关实践

• 如需了解 SM3 在 HMAC 中的实际应用，请参阅《SM3 国密哈希算法实战：HMAC-SM3、PBKDF2-SM3 与性能调优》
• 如需了解 SM3 在数字签名中的使用，请参阅《SM2 国密算法实战：从密钥生成到 TLS 完整部署》
• 如需了解随机数检测规范，请参阅《密码学安全随机数生成：从 /dev/urandom 到 CSPRNG 工程实践》