国密算法系列之杂凑算法SM3

杂凑算法，也称哈希算法，在信息安全领域中用于计算消息的摘要，校验消息的完整性。
国际标准的常用哈希算法有消息摘要算法MD5, 安全哈希算法SHA系列等。
本文介绍国家密码管理局发布的杂凑算法标准SM3，详见国家密码管理局官方网站.

SM3算法图解

整体流程

SM3算法整体流程如下：

可以看到，整个流程包括消息填充、分块、迭代压缩3个步骤。
其中，输入为长度l$l$(l<264$l<2^{64}$)的消息x$x$，输出为256-bit的杂凑值y$y$，B0,B1,...Bn−1$B_0,B_1,...B_{n-1}$为填充后消息的分块(共n个块)，消息块大小为512-bit，CF$CF$为压缩函数，V0,V1,...Vn$V_0,V_1,...V_n$为各消息块迭代压缩结果，大小为256-bit，最终得到的消息杂凑值为y=Vn$y=V_n$。

压缩函数CF

压缩函数可表示为：
Vi+1=CF(Vi,Bi)，i=0,...n−1,V0=IV$V_{i+1}=CF(V_i,B_i)，i=0,...n-1,V_0=IV$
IV=7380166f4914b2b9172442d7da8a0600a96f30bc163138aae38dee4db0fb0e4e$IV=7380166f4914b2b9172442d7da8a0600a96f30bc163138aae38dee4db0fb0e4e$

假设压缩函数处理第Bi$B_i$个消息块，其流程如下：

其中，ABCDEFGH为字寄存器，长度为32-bit，j为迭代轮数，TT1,TT2为中间值字寄存器；
可以看出压缩函数共有64轮迭代，ABCDEFGH寄存器值初始化为前一个消息块Bi−1$B_{i-1}$的压缩结果Vi$V_i$。

块消息扩展

块消息扩展是指将Bi$B_i$扩展为132个字：W0,W1,...W67,W′0,W′1,...W′63$W_0,W_1,...W_{67},W_0^{\prime },W_1^{\prime },...W_{63}^{\prime }$,过程如下：

W0,...W15$W_0,...W_{15}$ : 块切分为16个字；
W17,...W67$W_{17},...W_{67}$ : Wj←P1(Wj−16⊕Wj−16⊕(Wj−3<<<15))⊕(Wj−13<<<7)⊕Wj−13$W_j\leftarrow P_1(W_{j-16}\oplus W_{j-16}\oplus (W_{j-3}<<<15))\oplus (W_{j-13}<<<7)\oplus W_{j-13}$；
W′0,...W′63$W_0^{\prime },...W_{63}^{\prime }$ : W′j←Wj⊕Wj+4$W_j^{\prime }\leftarrow W_j\oplus W_{j+4}$

其中，P1(X)=X⊕(X<<<15)⊕(X<<<23)$P_1(X)=X\oplus (X<<<15)\oplus (X<<<23)$, <<<$<<<$指循环位左移。

计算中间值TT1,TT2

中间计算过程如下图所示：

其中，

X,Y,Z$X,Y,Z$为字，∧$\wedge$为与运算，∨$\vee$为或运算，¬$\mathrm{\neg }$为非运算，⊕$\oplus$为异或运算。

更新ABCDEFGH

在计算的TT1,TT2中间之后，依次更新各个寄存器如下：

其中，P0(X)=X⊕(X<<<9)⊕(X<<<17)$P_0(X)=X\oplus (X<<<9)\oplus (X<<<17)$。

---