SM4

SM4(原名SMS4)是中華人民共和國政府采用的一种分组密码标准,由国家密码管理局于2012年3月21日发布[。2016年8月,成为中国国家密码标准(GB/T 32907-2016。在商用密码体系中,SM4主要用于数据加密,其算法公开,分组长度与密钥长度均为128bit,加密算法与密钥扩展算法都采用32轮非线性迭代结构,S盒为固定的8比特输入8比特输出。

概述

SM4 是一种对称分组密码算法,分组长度为 128 bit,密钥长度为 128 bit,。加密算法 与密钥扩展算法均采用非线性迭代结构,共进行 32 轮迭代。数据解密和数据加密的算法结构相同, 只是轮密钥的使用顺序相反,解密轮密钥是加密轮密钥的逆序。广泛用于国密体系、金融、政务、通信安全等领域

整体架构

设输入明文被表示为四个 32 比特字

\[ (X_0,X_1,X_2,X_3) \]

则 SM4 在每一轮中都会利用当前的轮密钥 rk_i 和已有的 4 个状态字,生成一个新的 32 比特字。其基本迭代关系为

\[ X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i),\qquad i=0,1,\dots,31 \]

其中轮函数 F 定义为

\[ F(X_0,X_1,X_2,X_3,rk)=X_0\oplus T(X_1\oplus X_2\oplus X_3\oplus rk) \]

这里的 T 是 SM4 的核心合成变换,它由非线性变换和线性变换复合而成,因此每一轮都同时具备“混淆”和“扩散”的作用。

SM4 的每一轮都可以看成:先将后三个状态字与轮密钥进行异或混合,再经过合成变换 T 处理,最后与最前面的状态字异或,得到新的状态字。这样经过 32 轮迭代之后,算法得到

\[ (X_{32},X_{33},X_{34},X_{35}) \]

随后再经过一次反序变换,输出最终密文

\[ (Y_0,Y_1,Y_2,Y_3)=(X_{35},X_{34},X_{33},X_{32}) \]

也就是说,SM4 的最终输出并不是按照自然顺序直接拼接,而是要将最后四个字逆序排列后再作为密文输出。

因此,从整体架构上看,SM4 可以概括为:以 128 比特分组为输入,以 128 比特密钥生成 32 个轮密钥,通过 32 轮迭代轮函数不断更新状态,最后经过反序变换输出密文。

明文处理

在 SM4 中,输入的明文分组长度固定为 128 比特。为了便于后续迭代运算将整个 128 比特明文按顺序划分为 4 个 32 比特字。标准中将“字”定义为长度为 32 比特的组,因此 SM4 的初始输入状态通常记为

\[ (X_0,X_1,X_2,X_3) \]

其中每个 X_i 都是一个 32 比特字。

也就是说,如果将一组 128 比特明文记作

\[ M \]

那么在进入加密过程之前,首先要完成的工作就是把它拆分成四个连续的 32 比特部分,分别作为算法的初始输入字:

\[ M \longrightarrow (X_0,X_1,X_2,X_3) \]

后续 32 轮加密迭代,都是在这四个字的基础上不断生成新的状态字,并逐步完成从明文到密文的变换。

这说明 SM4 从一开始就是“4 个 32 位字”为基本处理对象来组织内部状态的。

密钥处理

在 SM4 中,密钥长度固定为 128 比特。与明文处理方式类似,为了便于后续的密钥扩展运算,算法会先将 128 比特主密钥按顺序划分为 4 个 32 比特字。设主密钥记为

\[ MK=(MK_0,MK_1,MK_2,MK_3) \]

其中每个 MK_i 都是一个 32 比特字。

也就是说,如果将输入密钥记作

\[ K \]

那么在进入密钥扩展算法之前,首先需要将其拆分为四个连续的 32 比特部分:

\[ K \longrightarrow (MK_0,MK_1,MK_2,MK_3) \]

不过,这四个字并不会直接用于生成轮密钥,而是要先与系统参数 FK 进行一次异或运算,得到密钥扩展的初始状态:

\[ (K_0,K_1,K_2,K_3)=(MK_0\oplus FK_0,\;MK_1\oplus FK_1,\;MK_2\oplus FK_2,\;MK_3\oplus FK_3) \]

其中

\[ FK=(FK_0,FK_1,FK_2,FK_3) \]

FK是 SM4 规定的系统参数,用于初始化密钥扩展过程。

FK₀ = 0xA3B1BAC6

FK₁ = 0x56AA3350

FK₂ = 0x677D9197

FK₃ = 0xB27022DC

在得到初始状态 (K_0,K_1,K_2,K_3) 之后,SM4 会继续进行 32 轮密钥扩展。第 i 轮轮密钥的生成公式为

\[ rk_i=K_{i+4}=K_i\oplus T'(K_{i+1}\oplus K_{i+2}\oplus K_{i+3}\oplus CK_i),\qquad i=0,1,\dots,31 \]

也就是说,每一轮都会先将后面三个字 K_{i+1},K_{i+2},K_{i+3} 与固定参数 CK_i 进行异或,然后经过变换 T’ 处理,最后再与前面的 K_i 异或,得到新的字 K_{i+4}。而这个新生成的 K_{i+4},就是当前轮使用的轮密钥 rk_i。

CK

换句话说,轮密钥并不是一次性全部算出来的,而是按轮递推生成的:

  • 第 0 轮:
\[ rk_0=K_4=K_0\oplus T'(K_1\oplus K_2\oplus K_3\oplus CK_0) \]
  • 第 1 轮:
\[ rk_1=K_5=K_1\oplus T'(K_2\oplus K_3\oplus K_4\oplus CK_1) \]
  • 第 2 轮:
\[ rk_2=K_6=K_2\oplus T'(K_3\oplus K_4\oplus K_5\oplus CK_2) \]

依此类推,直到生成第 31 轮轮密钥

\[ rk_{31}=K_{35} \]

因此,SM4 的轮密钥序列

\[ (rk_0,rk_1,\dots,rk_{31}) \]

本质上就是由初始的 (K_0,K_1,K_2,K_3) 通过上述递推公式不断向前展开得到的。也就是说,真正参与每一轮加密运算的 rk_i,都是主密钥经过初始化、再经过 32 轮递推扩展后得到的结果。

轮函数F

在 SM4 中,真正推动整个加密过程不断向前迭代的核心,就是轮函数 F。经过明文处理后,算法已经将输入表示为 4 个 32 比特字

\[ (X_0,X_1,X_2,X_3) \]

之后每一轮的任务,就是在当前 4 个状态字和轮密钥的基础上,计算出一个新的 32 比特字,并将其加入到后续状态中。轮函数 F 定义为

\[ F(X_0,X_1,X_2,X_3,rk)=X_0\oplus T(X_1\oplus X_2\oplus X_3\oplus rk) \]

其中,rk 表示当前轮使用的轮密钥,T 表示一个合成置换,它由后续要介绍的非线性变换和线性变换共同构成。也就是说,轮函数 F 并不是简单地对输入做一次异或,而是先将后三个状态字与轮密钥混合,再经过变换 T 处理,最后再与最前面的状态字 X_0异或,得到当前轮的输出。

如果把这个过程拆开来看,那么轮函数 F 的计算逻辑可以概括为以下几步。首先,先计算后三个状态字与轮密钥的异或结果:

\[ A=X_1\oplus X_2\oplus X_3\oplus rk \]

然后,将这个中间结果输入到合成置换 T 中:

\[ B=T(A) \]

最后,再将其与最前面的状态字 X_0 进行异或,得到轮函数输出:

\[ F(X_0,X_1,X_2,X_3,rk)=X_0\oplus B \]

因此,从结构上看,SM4 的轮函数可以理解为一种“反馈式”更新机制:它并不是同时修改 4 个状态字,而是利用当前的 4 个字计算出一个新的字,并将这个新字接到状态序列后面。也正因为如此,SM4 的整体迭代关系被写成

\[ X_{i+4}=F(X_i,X_{i+1},X_{i+2},X_{i+3},rk_i),\qquad i=0,1,\dots,31 \]

也就是说,第 i 轮并不会直接覆盖原来的 X_i,X_{i+1},X_{i+2},X_{i+3},而是在它们的基础上生成新的 X_{i+4},从而推动整个状态不断向前演化。

合成置换T

SM4 中的合成置换 T 定义为

\[ T(\cdot)=L(\tau(\cdot)) \]

其中,τ 表示非线性变换,L 表示线性变换。也就是说,T 先通过τ ( S 盒完成字节代换),再通过线性变换实现扩散,是 SM4 轮函数中的核心变换。

非线性变换τ

在合成置换 T 中,第一步就是非线性变换 。它的作用是对输入的 32 比特字进行字节级替换,从而为 SM4 提供最关键的非线性来源。( 其实就是个和AES的sbox查表替换一样)

设输入为一个 32 比特字

\[ A=(a_0,a_1,a_2,a_3)\in (Z_2^8)^4 \]

其中 a_0,a_1,a_2,a_3 分别表示 A 的 4 个字节。经过非线性变换 后,输出记为

\[ B=(b_0,b_1,b_2,b_3) \]

其变换关系为

\[ (b_0,b_1,b_2,b_3)=\tau(A)=(Sbox(a_0),Sbox(a_1),Sbox(a_2),Sbox(a_3)) \]

也就是说,τ 的本质就是将输入字中的每一个字节分别送入 SM4 规定的 S 盒,得到对应的新字节,再重新拼接成一个新的 32 比特字。

\[ b_i=Sbox(a_i),\qquad i=0,1,2,3 \]

因此,非线性变换τ 可以理解为一种逐字节替换操作:它保持字节数不变,但会根据 S 盒查表规则,把每个输入字节替换成另一个输出字节。

SM4-Sbox.png

若输入字节为 EF,则应在 S 盒表中查找第 E 行、第 F 列,对应得到的输出为 84,即

\[ Sbox(\mathrm{EF})=\mathrm{84} \]

线性变换 L

在线性变换 完成字节代换之后,SM4 还需要进一步将这种非线性效果扩散到更多比特位置上,这一步就是线性变换 L。设 τ 的输出为一个 32 比特字 B,则线性变换 L 定义为

\[ L(B)=B\oplus(B\lll2)\oplus(B\lll10)\oplus(B\lll18)\oplus(B\lll24) \]
\[ 其中,\lll i 表示将 32 比特字循环左移 i 位 \]

也就是说,L 会将输入字 B 本身与其循环左移 2 位、10 位、18 位和 24 位后的结果分别进行异或,从而得到新的 32 比特输出。这样一来,输入中某一位的变化就会通过移位和异或传播到输出的多个位置,从而增强算法的扩散能力。

随后,轮函数会将这个结果再与当前最前面的状态字进行异或,从而生成新的状态字,并作为下一轮迭代的一部分继续参与运算。也就是说,SM4 并不是只进行一次这样的变换,而是不断重复这一过程:每一轮都利用当前的 4 个状态字和对应的轮密钥,生成一个新的状态字,再推动整个状态向前更新。

经过 32 轮迭代之后,算法最终得到

\[ (X_{32},X_{33},X_{34},X_{35}) \]

不过,这 4 个字并不会按当前顺序直接输出,而是还需要经过一次反序变换,重新排列为

\[ (Y_0,Y_1,Y_2,Y_3)=(X_{35},X_{34},X_{33},X_{32}) \]

这样得到的结果,才是 SM4 的最终密文

总结

SM4 是一种 128 比特分组、128 比特密钥 的对称分组密码算法,共进行 32 轮迭代。在加密开始时,算法首先将 128 比特明文划分为 4 个 32 比特字

\[ (X_0,X_1,X_2,X_3) \]

同时,将 128 比特主密钥划分为 4 个 32 比特字,并经过初始化和密钥扩展生成 32 个轮密钥

\[ (rk_0,rk_1,\dots,rk_{31}) \]

供后续每一轮加密使用。

在每一轮中,SM4 都会先将后三个状态字与当前轮密钥进行异或,再送入合成置换 T。其中T 先通过非线性变换τ 完成 S 盒替换,再通过线性变换 L实现扩散,最后再与最前面的状态字异或,生成新的状态字。其轮函数可表示为

\[ X_{i+4}=X_i\oplus T(X_{i+1}\oplus X_{i+2}\oplus X_{i+3}\oplus rk_i),\qquad i=0,1,\dots,31 \]

也就是说,SM4 正是通过这样的轮函数迭代,不断将明文状态推进到新的状态。

当 32 轮运算全部结束后,算法得到

\[ (X_{32},X_{33},X_{34},X_{35}) \]

最后再经过一次反序变换,输出密文

\[ (Y_0,Y_1,Y_2,Y_3)=(X_{35},X_{34},X_{33},X_{32}) \]

因此,从整体上看,SM4 的加密过程可以概括为:明文分组、密钥扩展、32 轮轮函数迭代,以及最终的反序输出。

封面来自XilmO