SM4分组密码算法研究

SM4算法详解

  分组密码将明文数据按固定长度进行分组，并在同一密钥控制下逐组进行加密，从而将各个明文分组变换成一个个等长的密文分组。
  分组密码的设计一般基于混淆原则和扩散原则。
  混淆原则指的是将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂，使敌手即使获得了密文和明文，也无法求出密钥的任何信息，即使获得了密文和明文的统计规律，也无法求出明文的任何信息。
  扩散原则是将明文的统计规律和结构规律散射到相当长的一段统计中去。即，明文中的每一位会影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。
分组密码主要的应用场景，包括无需进行密钥交换；防止明文传输过程被窃取；数据量大，加解密速度要求快等场景。

SM4算法流程

  SM4算法主要包括异或、移位以及盒变换操作。其中密钥拓展和加/解密为两个主要模块，其流程大同小异。
  其中，移位变换是指循环左移；盒变换将8bit输入映射到8bit输出的变换，是一个固定的变换。
  下图1给出了 SM4算法的加解密（左）和密钥拓展（右）的流程图。

（1）加/解密模块
  加/解密算法由32次迭代运算和1次反序变换组成，具体步骤如下所述。
  设，明文输入为$（X_0,X_1,X_2,X_3）$，$X_i$为32 比特的数据，密文输出为$（Y_0,Y_1,Y_2,Y_3）$，轮密钥为$r{k}_i$。

  ① 当 $i=0$ 时为第一次轮变换，一直进行到 $i=31$ 结束。
  ②将 $X_{i+1},X_{i+2},X_{i+3}$ 和轮密钥$r{k}_i$ 异或得到一个 $32$ 比特的数据，作为盒变换的输入。即， $sbo{x}_{input}=X_{i+1}\oplus X_{i+2}\oplus X_{i+3}\oplus r{k}_i$，$\oplus$ 符号代表异或运算。
  ③ 将 $sbo{x}_{input}$ 拆分成 $4$个 $8$比特数据，分别进行盒变换，之后再将 $4$个 $8$比特输出合并成一个 $32$ 比特的 $sbo{x}_{output}$。
  ④ 将上一步获得的 $sbo{x}_{output}$分别循环左移 2，10，18，24 位，得到 4个 32比特的结果，记移位结果为 $y2,y10,y18,y24$。与盒变换输出 $sbo{x}_{output}$ 和$X_i$ 异或，得到 $X_{i+4}$。即， $X_{i+4}=sbo{x}_{output}\oplus y2\oplus y10\oplus y18\oplus y24\oplus X_i$。
至此完成了一轮的加/解密运算。
  ⑤将最后一轮生成的 $4$个 $32$比特数据 $X_{35}$，$X_{34}$，$X_{33}$，$X_{32}$ 合并成一个$128bit$ 的数据输出，作为最后的密文$（Y_0,Y_1,Y_2,Y_3）$输出。
(2) 密钥扩展模块
  密钥扩展与加/解密实现过程大同小异，具体实现过程如下所述。
  设，密钥输入为$(M{K}_0,M{K}_1,M{K}_2,M{K}_3)$，轮密钥输出为 K i , i ∈ { 0 , 1 , 2 , … 31 } K_i, i∈\{0,1,2,…31\} Ki​,i∈{0,1,2,…31}。

   ① 将初始密钥$(M{K}_0,M{K}_1,M{K}_2,M{K}_3)$分别异或固定参数 $(F{K}_0,F{K}_1,F{K}_2,F{K}_3)$得到用于循环的密钥$(K_0,K_1,K_2,K_3)$,即, $K_0=M{K}_0⨁F{K}_0$, $K_1=M{K}_1⨁F{K}_1$, $K_2=M{K}_2⨁F{K}_2$, $K_3=M{K}_3⨁F{K}_3$ 。
   ② 进入轮密钥$K_i$ 的生成, 当 $i=0$ 时为第一轮密钥扩展，一直进行到 i=31 结束。
   ③ 将 $K_{i+1},K_{i+2},K_{i+3}$ 和固定参数 $C{K}_i$异或得到一个 $32$ 比特的数据，作为盒变换的输入。即， $sbo{x}_{input}=K_{i+1}\oplus K_{i+2}\oplus K_{i+3}\oplus C{K}_i$。
   ④ 将 $sbo{x}_{input}$ 拆分成 $4$ 个$8$ 比特数据，分别进行盒变换，之后再将 $4$ 个 $8$比特输出合并成一个 $32$ 比特的 $sbo{x}_{output}$。
   ⑤ 将上一步获得的 $sbo{x}_{output}$分别循环左移 $13$，$23$ 位，得到 $2$个 $32$ 比特的结果，记移位结果为 $y13$, $y23$与盒变换输出 $sbo{x}_{output}$ 和 $K_i$ 异或，得到 $K_{i+4}$。即， $K_{i+4}=sbo{x}_{output}\oplus y13\oplus y23\oplus K_i$。
其中每一个$K_i$即为产生的轮密钥。

具体算法实现

  SM4算法的主体代码包括加解密模块和密钥扩展模块。以下为加解密模块具体实现代码以及注释。
（1）加/解密模块

def _do(self, text: bytes, key_r: list):text_ = [0 for _ in range(4)]# 将 128bit 转化成 4x32bitfor i in range(4):text_[i] = int.from_bytes(text[4 * i:4 * i + 4], 'big')for i in range(32):box_in = text_[1] ^ text_[2] ^ text_[3] ^ key_r[i]box_out = self._s_box(box_in)temp = text_[0] ^ box_out ^ self._rot_left(box_out, 2) ^ self._rot_left(box_out,10)temp = temp ^ self._rot_left(box_out, 18) ^ self._rot_left(box_out, 24)text_ = text_[1:] + [temp]text_ = text_[::-1]  # 结果逆序# 将 4x32bit 合并成 128bitresult = bytearray()for i in range(4):result.extend(text_[i].to_bytes(4, 'big'))return bytes(result)

（2）密钥扩展模块

def _generate_key(self, key: bytes):"""密钥生成"""key_r, key_temp = [0 for _ in range(32)], [0 for _ in range(4)]FK = [0xa3b1bac6, 0x56aa3350, 0x677d9197, 0xb27022dc]CK = [0x00070e15, 0x1c232a31, 0x383f464d, 0x545b6269, 0x70777e85, 0x8c939aa1, 0xa8afb6bd, 0xc4cbd2d9, 0xe0e7eef5, 0xfc030a11, 0x181f262d, 0x343b4249, 0x50575e65, 0x6c737a81, 0x888f969d, 0xa4abb2b9, 0xc0c7ced5, 0xdce3eaf1, 0xf8ff060d, 0x141b2229, 0x30373e45, 0x4c535a61, 0x686f767d, 0x848b9299, 0xa0a7aeb5, 0xbcc3cad1, 0xd8dfe6ed, 0xf4fb0209, 0x10171e25, 0x2c333a41, 0x484f565d, 0x646b7279]# 将 128bit 拆分成 4x32bitfor i in range(4):temp = int.from_bytes(key[4 * i:4 * i + 4], 'big')key_temp[i] = temp ^ FK[i]# 循环生成轮密钥for i in range(32):box_in = key_temp[1] ^ key_temp[2] ^ key_temp[3] ^ CK[i]box_out = self._s_box(box_in)key_r[i] = key_temp[0] ^ box_out ^ self._rot_left(box_out, 13) ^ self._rot_left(box_out, 23)key_temp = key_temp[1:] + [key_r[i]]return key_r

SM4算法性能及可靠性分析

  分组密码算法最主要的是要保证传输信息的机密性以及完整性，才能保证信息在传输过程中不被敌手窥探到。其次，随着大数据的到来，越来越多的信息在网上传播，因此算法的性能，即，执行效率显得尤为重要。与国际主流分组密码算法进行比较，可得出表1的结果。
表1. SM4与DES和AES算法比较

算法复杂性分析

  以下可以与主流国际分组密码算法DES和算法AES在空间和时间复杂度上来进行分析，比较其三种主要分组密码算法的复杂性。
(1) 空间复杂度
   DES算法需要存储$2$个IP置换矩阵，$2\times 16\times 4$；扩展置换，$6\times 8$；S盒代换，$16\times 4\times 8$；置换选择$PC1$，$7\times 8$；置换选择$PC2$, $8\times 6$。
  SM4算法需要存储S盒，大小为$2^4\times 2^4$。
AES算法需要存储$2$个S盒，大小为$2\times 2^4\times 2^4$。
  其他代码运行过程中存储的变量可忽略不计，从以上比较来看，SM4分组密码算法所需的内存空间最少，AES次之，DES则最多。
(2) 时间复杂度
  时间复杂度可以简单从计算轮数进行简单的比较，AES的计算轮数最少为$10/12/14$，DES次之，为$16$轮，SM4算法计算轮数最多，达$32$轮。
(3) 代码运行结果比较
  采用Python语言，实现三种分组密码算法（具体代码参见 python实现）。并分别使用其进行一次加密运算，比较各自运行时所占用的内存大小以及运行时间。结果如下表2所示。
表2. 占用的内存大小以及运行时间

  从表2中的运行结果来看，SM4算法运行时需要占用更多的内存，运行时间上则更快。与理论上分析的结果不一致。

安全性分析

  首先，从密钥空间上考虑，密钥空间越大，敌手可通过穷举的方法爆破密钥的可能性就越低。DES的密钥长度为64bits，AES的密钥长度为$128/192/256bits$，SM4的密钥长度为$128bits$。其中密钥长度越长，则代表密钥空间越大。AES最安全，SM4次之，最后是DES。其次，从算法特性上分析，SM4和AES均包含非线性变化，得到的密文统计特性更差，则更安全。最后，从攻击的角度分析，如，差分密码分析、线性密码分析、不可能差分分析等等，公开的评估结果表明，SM4分组密码能够抵抗目前已知的所有攻击。

参考文献

[1] 吕述望等. “SM4分组密码算法综述.” 信息安全研究 2.11(2016):13.
[2] 胡景秀等. “国密算法分析与软件性能研究.” 信息网络安全 10(2021):9.

资源下载

包括完整的AES、DES以及DES分组密码算法的python代码实现。
python代码实现