详解SM3算法加密流程（SM3加密算法一）

1、SM3 算法简介

  SM3是中国国家密码管理局发布的消息摘要算法，首次发布于2010年，并于2016年发布了正式的国家标准GB/T 32905-2016。类似于国际上广泛应用的SHA-256算法，但有其独特的设计和实现细节。

  该算法应用于各种数据加密和验证场景，比如电子支付、身份认证、数字签名等等。比如身份认证，用户在登录自己账号时，需要输入密码，能够将设置的密码存入服务器，然后与用户输入的密码进行对比，来判断密码正确性？

  显然不能，如果服务器被攻破，那么所有用户的账号和密码不就泄露了。用户设置的密码可以经过SM3加密，然后存入服务器中。后续用户登录时输入的密码在先经过SM3加密，然后与服务器中正确的加密结果对比，来判断密码是否正确。大致流程就是这样，实际情况肯定会比这个复杂。

  SM3算法的输入可以是任意长度数据，但加密结果始终是256位（32字节）数据。SM3 是基于Merkle-Damgård构造的，采用了定制的压缩函数与消息扩展算法，具体包括以下步骤：

  1、消息填充：将输入消息填充至长度为512位的倍数。

  2、消息扩展：对填充后的消息进行扩展，形成132个字。

  3、迭代压缩：将消息分块并逐块迭代压缩，最后输出256位的加密结果。

2、SM3算法术语

  后续计算过程中出现的所有字符和术语，都会在给小节讲解，过一遍即可，后续计算过程中出现疑问在回来看即可。

  内部数据在计算过程中都采用大端存储，先运算的数据放在高字节，后运算的数据放在低字节，如下图所示。

图1 大端存储

  1个字(word) == 4字节(byte) == 32位(bit)。

  下表是计算过程中会使用到的一些符号及其含义。

表1 运算过程中使用的符号

3、SM3算法描述

  SM3密码杂凑算法的输入为长度为L(L<2的64次方)比特的消息m，经过消息填充、消息扩展、迭代压缩过程后，输出长度为256比特的加密数据。

3.1、消息填充

  假设输入数据m的长度为L比特，则首先将比特“1”添加到输入数据m的末尾，再添加k比特“0”，k是满足L+1+k≡448(mod512)的最小非负整数。然后再添加一个64比特的数据，表示输入数据m的长度。填充后的消息m’的比特长度为512的倍数。

  例如：输入数据为01100001_01100010_01100011，长度L=24，填充后的数据为：

图2 填充后的数据

  如果输入24位数据为0x616263，则经过填充后的数据如下所示：

图3 输入0x616263填充后的数据

3.2、消息扩展

  将填充后的消息m’按512比特进行分组：m’=B(0) B(1) …B(n-1)，其中n=(L+K+65)/512。如果输入数据长度小于447比特，则本次计算的m’就是B(0)，否则m’会包含多个B(i)。

  在对m’进行迭代运算之前，需要先将消息分组B(i)按以下方法扩展生成132个消息字W0，W1，…W67 ,W’0，W’1，…W’63，用于后续的压缩计算。

  扩展过程如下所示，首先将前面消息填充得到的B(i)划分为16个字（1个字等于32比特）W0，W1，…W15。

  然后通过下面的公式计算W16，…W67。

图4 W(16)~W(67)的扩展公式

  P1是一个置换函数，表达式如下所示，P1的计算结果为输入信号X异或X循环左移15位，再异或X循环左移23位。

图5 置换函数表达式

  进而分析图4的公式，W(i-16)异或W(i-9)异或W(i-3)循环左移15位得到的结果作为P1(X)函数的输入数据，P1(X)的计算结果异或W(i-13)循环左移7位，最后异或W(i-6)，得到W(i)的计算结果。

  例如需要计算W(16)，则表达式为

  W(16) = P1(W(0) 异或 W(7)异或(W(13) <<< 7) ) 异或 (W(3) <<< 7) 异或 W(10)。由于异或的符号没有找到，因此使用文字替代，后续文章可能在多个平台发布，因此上标和下标直接用括号替代。

  通过以上运算，可以得到W(0)_{W(67)，然后需要计算W’(0)} W’(63)，计算方式如下所示。

图6 W’(0)~ W’(63)的扩展方式

  上图公式里面的下标应该是打错了，应该都是i或者j，W’(i)是由W(i)异或W(i+4)得到的，计算很简单。

  上述计算得到的W0，W1，…W67 ,W’0，W’1，…W’63构成扩展后的B(i)，就可以用于后续的迭代运算了。上文的输入数据0x616263经过消息填充、消息扩展后得到的132字节如下图所示：

图7 0x616263扩展结果

3.3、迭代压缩

  迭代压缩的函数如下所示，其中CF是压缩函数，V(0)是256位压缩函数初始值，B(i)是前面消息扩展后的数据，V(n)是迭代压缩的结果。

图8 迭代压缩函数

  压缩函数的计算过程如下所示，FOR循环中的部分需要计算64次，因此被称为迭代运算。

图9 迭代运算流程

  首先把迭代函数的初始值256比特V(i)赋值给8个32比特数据ABCDEFGH，其中V(0)为固定常数0x7380166f_4914b2b9_172442d7_da8a0600_a96f30bc_163138aa_e38dee4d_b0fb0e4e。

  64次迭代内容为上图蓝色框图部分，首先（A循环左移12位+E+（T(i)循环左移（j除以32的余数）），计算结果循环左移7位得到SS1。

  其中T(i)是一个常量，具体的数值如下所示，当i小于等于15时，值为0x79cc4519，否则值为0x7a879d8a。

图10 常量函数的计算

  A循环左移12位的结果异或SS1得到SS2。

  之后计算TT1，其中FFj(X,Y,Z)函数的表达式如下所示，当j小于16时，X异或Y异或Z得到计算结果，否则X，Y，Z两两进行与运算，结果再通过或运算，得到FFj(X,Y,Z)计算结果。

图11 FFJ布尔函数

  FFj(A,B,C)计算结果加上D，再加上SS2，最后加上W’(j)得到TT1。

  在TT2的计算过程中，有一个GGj(E,F,G)的函数，对应表达式如下。当J小于16时，运算过程与FFj(X,Y,Z)一致。当J大于等于16时，（X与Y）或（X取反后与上Z）得到结果。

图12 GGj布尔函数

  GGj(E,F,G)计算结果加上H，再加上SS1，最后加上W(j)得到TT2。注意再迭代过程中W’(j)只会用来计算TT1，而W(j)用来计算TT2，同时每次迭代只会用到对应的W(j)和W’(j)，如果是在串行计算的过程中，则可以将前面的消息扩展和迭代运算同时进行流水线设计，从而加快计算过程，提高时钟频率。

  同时迭代过程并不会用到W(64)~ W(67)这几个数据，他们的作用在于生成W’(60)~ W’(63)这几个数据。

  然后中间是对A、B、C等数据的赋值过程，这部分比较简单，不再赘述。

  之后有一个P0(TT2)的函数，P0(X)对应的表达式如下所示，X异或（X循环左移9位）异或（X循环左移17位）得到计算结果。

图13 置换函数

  最终的ABCDEFGH作为本轮迭代的结果数据V(i+1)，作为下一轮迭代的初始V(i)。

  经过64轮迭代后得到这组数据的迭代结果。如果有多组B(i)，则将得到的迭代结果作为下一组数据迭代压缩过程的起始数据V(0)。

  上述整个加密过程，可以描述为下图，首先经过消息填充，把输入的任意比特数据分成很多的64字节消息组，然后每组数据通过消息扩展得到132字节数据，依次对每组数据进行迭代运算，得到最终的256比特输出结果。

图14 sm3加密概括

  上文中0x616263的部分迭代结果如下图所示：

图14 迭代中间值

  最终得到的结果如下所示：

图15 迭代结果

4、FPGA实现的思考

  在使用FPGA实现时，肯定是需要简化的，首先可以确定输入数据位宽，或者通过一个数据来指示当前输入数据的位宽，但是依旧需要确定输入数据最大位宽。

  为了简化计算，输入数据应小于等于477（512-65）比特，这样每次就只需要完成64轮迭代运算，可以快速得到结果。

图16 一次迭代完成加密的框图

  本文均参考与GB/T32905—2016，如果需要这个标准文档，在公众号后台回复“GB/T32905”（不包含引号）即可。

---

  如果对文章内容理解有疑惑或者对代码不理解，可以在评论区或者后台留言，看到后均会回复！

  如果本文对您有帮助，还请多多点赞