国密之 sm4 分组密码算法
目录
SM4分组密码算法,原名SMS4,国家密码管理局于2012年3月21日发布,相关标准为“GM/T 0002-2012《SM4分组密码算法》(原SMS4分组密码算法)”。它是一种分组对称加密算法,分组长度和密钥长度均为 128bit
,加密算法与密码扩展算法均采用 32 轮
非线性迭代结构, Sbox 为固定的 8bit
输入 8bit
输出的置换。 数据加/解密的算法结构相同,只是轮密钥的使用顺序相反,解密轮密钥是加密轮密钥的逆序。
SBox
在密码学中,Sbox(Substitution-box,替换盒)是对称密钥加密算法执行替换计算的基本结构。SBox接受一个特定位数的输入,通过查表将其转换为特定位数的输出。SM4 给定的 SBox 如下:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | A | B | C | D | E | F | |
0 | D6 | 90 | E9 | FE | CC | E1 | 3D | B7 | 16 | B6 | 14 | C2 | 28 | FB | 2C | 05 |
1 | 2B | 67 | 9A | 76 | 2A | BE | 04 | C3 | AA | 44 | 13 | 26 | 49 | 86 | 06 | 99 |
2 | 9C | 42 | 50 | F4 | 91 | EF | 98 | 7A | 33 | 54 | 0B | 43 | ED | CF | AC | 62 |
3 | E4 | B3 | 1C | A9 | C9 | 08 | E8 | 95 | 80 | DF | 94 | FA | 75 | 8F | 3F | A6 |
4 | 47 | 07 | A7 | FC | F3 | 73 | 17 | BA | 83 | 59 | 3C | 19 | E6 | 85 | 4F | A8 |
5 | 68 | 6B | 81 | B2 | 71 | 64 | DA | 8B | F8 | EB | 0F | 4B | 70 | 56 | 9D | 35 |
6 | 1E | 24 | 0E | 5E | 63 | 58 | D1 | A2 | 25 | 22 | 7C | 3B | 01 | 21 | 78 | 87 |
7 | D4 | 00 | 46 | 57 | 9F | D3 | 27 | 52 | 4C | 36 | 02 | E7 | A0 | C4 | C8 | 9E |
8 | EA | BF | 8A | D2 | 40 | C7 | 38 | B5 | A3 | F7 | F2 | CE | F9 | 61 | 15 | A1 |
9 | E0 | AE | 5D | A4 | 9B | 34 | 1A | 55 | AD | 93 | 32 | 30 | F5 | 8C | B1 | E3 |
A | 1D | F6 | E2 | 2E | 82 | 66 | CA | 60 | C0 | 29 | 23 | AB | 0D | 53 | 4E | 6F |
B | D5 | DB | 37 | 45 | DE | FD | 8E | 2F | 03 | FF | 6A | 72 | 6D | 6C | 5B | 51 |
C | 8D | 1B | AF | 92 | BB | DD | BC | 7F | 11 | D9 | 5C | 41 | 1F | 10 | 5A | D8 |
D | 0A | C1 | 31 | 88 | A5 | CD | 7B | BD | 2D | 74 | D0 | 12 | B8 | E5 | B4 | B0 |
E | 89 | 69 | 97 | 4A | 0C | 96 | 77 | 7E | 65 | B9 | F1 | 09 | C5 | 6E | C6 | 84 |
F | 18 | F0 | 7D | EC | 3A | DC | 4D | 20 | 79 | EE | 5F | 3E | D7 | CB | 39 | 48 |
例如,对于输入 EF
, 通过查表输出为 第 E
行,第 F
列,84
合成置换 $T$
$T$ 置换是一个可逆变换, 由非线性变换 $\tau$ 与线性变换 $L$ 构成,$T(x) = L(\tau(x))$
非线性变换 $\tau$
设输入为 $A=[a_0,a_1,a_2,a_3]$, $A$ 为 32bit, $a_i$ 为 8bit 数据, 则 $\tau(A) = [SBox(a_0),SBox(a_1),SBox(a_2),SBox(a_3)]$
线性变换 $L$
设输入为 $B$ ,为 32bit 数据,则 $L(B) = B \oplus (B \llless 2) \oplus (B \lll {10}) \oplus (B \lll {18}) \oplus (B \lll {24})$
密钥
SM4 的加密密钥长度为 128bit (16位),轮密钥为32个 32bit 自然数构成,轮密钥由加密密钥生成。
密钥扩展
- 设加密密钥为 $MK=[MK_0,MK_1,MK_2,MK_3]$, 轮密钥为 $RK=[rk_0, rk_1, ... , rk_{31}]$
- 设有 $K$, 令 $K_i = MK_i \oplus FK_i , i \in \{0,1,2,3\}$, 其中 $FK_i$ 为常量: $FK_0 = $0xA3B1BAC6, $FK_1=$0x56AA3350, $FK_2=$0x677D9197, $FK_3$=0xB27022DC
- 设 $B$ 为 32bit 数据,则有线性变换 $L^{'}, T^{'}$ , $L^{'}(B) = B \oplus (B \lll {13}) \oplus (B \lll {23}), T^{'}(x) = L^{'}(\tau(x))$ , $\tau$ 见前一节
- 设有常量数组 $CK = [CK_0, CK_1, ... ,CK_{32}]$ , 设 $ck_{i,j}$ 为 $CK_i$ 的第 $j$ 字节,其中 $0 \le i \le 31,0 \le j \le 3$ ,即 $CK_i = [ck_{i,0},ck_{i,1},ck_{i,2},ck_{i,3},]$ ,则 $ck_{i,j} = ((4i +j) \times 7) \% 256$ 。则可计算出 $CK$ 具体值:$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]。
由 1~4, 则有,轮密钥 $RK = [rk_0, rk_1, ... , rk31]$, 其中 $rk_i = K_{(m+4)\%5} = K_{m\%5} \oplus T^{'}(K_{(m+1)\%5} \oplus K_{(m+2)\%5} \oplus K_{(m+3)\%5} \oplus CK_i), 0 \le i \le 32$
算法描述
轮函数 $F$
设明文输入为 $X = [X_0, X_1, X_2, X_3]$ ,其中 $X$ 为 32bit,轮密钥为 $rk, rc \in RK$, 则轮函数 $F(X_0, X_1, X_2, X_3, rk) = X_0 \oplus T(X_1 \oplus X_2 \oplus X_2 \oplus rk)$
加密算法
sm4 的加密算法由 32 次迭代运算与 1 次反序变换 $R$ 组成。
设明文输入为 $X = [X_0, X_1, X_2, X_3]$ ,其中 $X$ 为 32bit,轮密钥为 $rk, rk \in RK$ ,输出密文为 $Y=[Y_0,Y_1,Y_2,Y_3]$, 则加密算法的运算过程如下:
1. 32 次迭代: $X_{i+4} = F(X_i,X_{i+1},X_{i+2},X_{i+3},rki), 0 \le i \le 31$
2. 1 次反序变换: $[Y_0,Y_1,Y_2,Y_3] = R(X_{32},X_{33},X_{34},X_{35}) = [X_{35},X_{34},X_{33},X_{32}]$
解密运算
除了轮密钥的使用顺序不同外,SM4 解密算法与加密算法的结构完全相同。解密时轮密钥的使用顺序为 $RK=[rk_{31},rk_{30},...,rk_0]$