SM3 密码杂凑算法原理
SM3 密码杂凑算法
SHA-256 是常用的哈希算法,输入长度小于 2^64 bit
的消息,输出为 256 bit
的杂凑值,分组大小为 512 bit
,字长定义为 32 bit
;
SM3 算法在 SHA-256 的基础上进行改良,输入长度小于 2^64 bit
的消息,输出为 256 bit
的杂凑值。分组大小为 512 bit
,字长定义为 32bit
;
SM3 和 SHA-256 对比:

SM3 算法步骤
SM3 算法主要分为以下几个部分:
- 消息填充
- 消息扩展
- 迭代压缩
- 生成杂凑值
输出为 256 bit 杂凑值,即 32 byte
设消息 m 的长度为 l
,索引从 0 开始编号
常量与函数
符号约定
ABCDEFGH:8 个字寄存器(串联)
$ B^{(i)} $:第 i 个消息分组
CF:压缩函数
$ FF_j $:布尔函数,随 j 的变化取不同的表达式
$ GG_j $:布尔函数,随 j 的变化取不同的表达式
IV:初始值,用于确定压缩函数寄存器的初态
$ P_0 $:压缩函数中的置换函数
$ P_1 $:消息扩展中的置换函数
$ T_j $:常量,随 j 的变化取不同的值
$ m $:消息
$ m’ $:填充后的消息
$ \wedge $:32 比特与运算
$ \vee $:32 比特或运算
$ \oplus $:32 比特异或运算
$ \lnot $:32 比特非运算
$ + $:$ mod 2^{32} $ 算数加运算
$ \lll k $:循环左移 k 比特运算
$ \leftarrow $:左向赋值运算符
初始值 IV
$$ IV = 7380166f 4914b2b9 172442d7 da8a0600 a96f30bc 163138aa e38dee4d b0fb0e4e $$
常量
$$
T_j =
\begin{cases}
79cc4519 & {0 \leq j \leq 15} \newline
7a879d8a & {16 \leq j \leq 63}
\end{cases}
$$
布尔函数
$$
FF_j(X, Y, Z) =
\begin{cases}
X \oplus Y \oplus Z & {0 \leq j \leq 15} \newline
(X \wedge Y) \vee (X \wedge Z) \vee (Y \wedge Z) & {16 \leq j \leq 63}
\end{cases}
$$
$$
GG_j(X, Y, Z) =
\begin{cases}
X \oplus Y \oplus Z & {0 \leq j \leq 15} \newline
(X \wedge Y) \vee (\lnot X \wedge Z) & {16 \leq j \leq 63}
\end{cases}
$$
X,Y,Z 为字。
置换函数
$$
P_0(X) = X \oplus (X \lll 9) \oplus (X \lll 17) \newline
P_1(X) = X \oplus (X \lll 15) \oplus (X \lll 23)
$$
X 为字。
消息填充
首先在消息 m 的末尾添加一个比特 1
;
然后再添加 k 个比特 0
;
k 满足 l + 1 + k ≡ 448(mod 512)
,字节表示为 (448(mod 512))/8 = 56(mod 64)
最后添加长度 l
的二进制比特表示,以大端序存放;
数据的高位字节存储在地址的低端

填充后的消息 m’ 的长度为 512 bit 的倍数。

消息扩展
将填充后的消息 m’ 按照 512 bit 分组
n = (l + k + 65) / 512
$$ m’ = B^{(0)}B^{(1)}…B^{(n-1)} $$
对消息分组 $ B^{(i)} $ 进行扩展,生成 132 个字:
$$
W_0, W_1, …, W_{67}, W_0’, W_1’, …, W_{63}’
$$
具体过程如下:
首先将消息分组 $ B^{(i)} $ 划分为 16 个字 $ W_0, W_1, …, W_{15} $ ,记为 $ W_j $
递推生成剩余的 $ W_j $ ,共计 68 个字
$$
\begin{align}
& FOR \quad j=16 \quad TO \quad 67 \newline
& \qquad W_j \leftarrow 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} \newline
& ENDFOR
\end{align}
$$递推生成 $ W_j’ $ ,共计 64 个字
$$
\begin{align}
& FOR \quad j=0 \quad TO \quad 63 \newline
& \qquad W_j’ = W_j \oplus W_{j+4} \newline
& ENDFOR
\end{align}
$$
迭代压缩

迭代过程
$$
\begin{align}
& FOR \quad i=0 \quad TO \quad n-1 \newline
& \qquad V^{(i+1)} = CF(V^{(i)}, B^{(i)}) \newline
& ENDFOR
\end{align}
$$
- CF 是压缩函数
- $ V^{(0)} $ 为 256 比特初始值 IV
- $ B^{(i)} $ 为填充后的消息分组
- 迭代压缩的结果为 $ V^{(n)} $ ,即最终的杂凑值
压缩函数
- A, B, C, D, E, F, G, H 为字寄存器
- SS1, SS2, TT1, TT2 为中间变量
- $ V^{i+1} = CF(V^{(i)}, B^{(i)}) , 0 \leq i \leq n-1 $
压缩函数过程如下:
$$
\begin{align}
& ABCDEFGH \leftarrow V^{(i)} \newline
\newline
& FOR \quad j=0 \quad TO \quad 63 \newline
& \qquad SS1 \leftarrow ((A \lll 12) + E + (T_j \lll j)) \lll 7 \newline
& \qquad SS2 \leftarrow SS1 \oplus ((A \lll 12) \newline
& \qquad TT1 \leftarrow FF_j(A, B, C) + D + SS2 + W_j’ \newline
& \qquad TT2 \leftarrow GG_j(E, F, G) + H + SS1 + W_j \newline
& \qquad D \leftarrow C \newline
& \qquad C \leftarrow B \lll 9 \newline
& \qquad B \leftarrow A \newline
& \qquad A \leftarrow TT1 \newline
& \qquad H \leftarrow G \newline
& \qquad G \leftarrow F \lll 19 \newline
& \qquad F \leftarrow E \newline
& \qquad E \leftarrow P_0(TT2) \newline
& ENDFOR \newline
\newline
& V^{(i+1)} \leftarrow ABCDEFGH \oplus V^{(i)}
\end{align}
$$
生成杂凑值
$$ ABCDEFGH \leftarrow V^{(n)} $$
输出 256 bit 杂凑值 y = ABCDEFGH
总结
SM3 算法流程简洁明了,可以直接按步骤实现。已有支持国密SM2/SM3/SM4/SM9/ZUC/SSL的密码工具箱 The GmSSL Project ,提供不同语言的 API 接口;学习 Golang 的过程中找到开源实现 基于Go语言的国密SM2/SM3/SM4加密算法库 ,研读了一段时间,现在才回头梳理总结(老懒熊了xd