﻿ SM4的快速软件实现技术
 中国科学院大学学报  2018, Vol. 35 Issue (2): 180-187 PDF
SM4的快速软件实现技术

1. 中国科学院软件研究所可信计算与信息保障实验室, 北京 100190;
2. 中国科学院大学, 北京 100190

Fast software implementation of SM4
LANG Huan1,2, ZHANG Lei1, WU Wenling1,2
1. Trusted Computing and Information Assurance Laboratory, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China;
2. University of Chinese Academy of Sciences, Beijing 100190, China
Abstract: SM4 is the national block cipher standard of China widely used in various information systems and security products.Some application environments have high demands for software implementation performance of cryptographic algorithms. Currently, SM4 software implementation is based on look-up table. Therefore, fast software implementation of SM4 algorithm has become an important research topic. This work investigates the software optimization implementation of SM4. Using SIMD technique, we present software optimization implementation of SM4, which has a significant advantage over current software implementation based on look-up table. On the Intel Core i7-6700 processor, the software performance improves by 1.38 times compared to implementation based on look-up table.
Key words: SM4     software optimization implementation     SIMD technique

SM4[1]算法即原SMS4算法，是由国家密码管理局于2006年公布的用于无线局域网产品的分组密码算法。SM4密码算法是国内官方公布的第一个商用密码算法，并于2012年3月被国家密码管理局批准为行业标准[2]。目前国内应用在安全产品(如IPSec VPN、SSL、TLS等)上的密码算法正逐步使用SM4算法取代DES[3]

1 SM4算法简介

SM4是一个分组密码算法，分组长度及主密钥长度均为128 bit。128 bit主密钥经密钥编排算法扩展为32个32-bit轮子密钥，加/解密变换均为32轮轮函数F的迭代。轮函数F的结构如图 1所示。

 Download: JPG larger image 图 1 SM4轮函数F结构图 Fig. 1 Structure of SM4 round function F

 $\begin{array}{l} {X_{i + }}{_4} = F{\rm{ }}({X_i}, {X_{i + }}{_1}, {X_{i + }}{_2}, {X_{i + }}{_3}, R{K_i}) = {X_i} \oplus \\ T{\rm{ }}({X_{i + }}{_1} \oplus {X_{i + }}{_2} \oplus {X_{i + }}{_3} \oplus R{K_i}), i = 0, 1, \cdots, 31. \end{array}$ (1)

 $B = \tau \left( A \right) = (Sbox{\rm{ }}({a_0}), Sbox{\rm{ }}({a_1}), Sbox{\rm{ }}({a_2}), Sbox{\rm{ }}({a_3})).$

 $CC = L\left( B \right) = B \oplus \left( {B \lll 2} \right) \oplus \left( {B \lll 10} \right) \oplus \left( {B \lll 18} \right) \oplus \left( {B \lll 24} \right).$
2 SM4查表实现

SM4加/解密轮函数中的T变换由非线性变换τ和线性变换L构成。将非线性变换τ的输入记为X=(x0, x1, x2, x3)∈(Z28)4，输出记为Y=(y0, y1, y2, y3)∈(Z28)4。可将非线性变换τ的操作定义如下。

 ${y_i} = Sbox{\rm{ }}\left( {{x_i}} \right), 0{\rm{ }} \le {\rm{ }}i < {\rm{ }}4.$ (2)

 $Q = L\left( B \right) = L{\rm{ }}\left( {{p_0} \ll \left( {n-1} \right){\rm{ }}m} \right) \oplus L{\rm{ }}({p_1} \ll \left( {n-2} \right){\rm{ }}m) \oplus \cdots \oplus L{\rm{ }}({p_n}{_{-1}}).$ (3)
 $\begin{array}{l} Q = T\left( X \right) = L\left( {Sbox{\rm{ }}\left( {{x_0}} \right) \ll \left( {n-1} \right){\rm{ }}m} \right) \oplus L\\ \left( {Sbox{\rm{ }}\left( {{x_1}} \right) \ll \left( {n-2} \right){\rm{ }}m} \right) \oplus \cdots \oplus L(Sbox{\rm{ }}({x_n}{_{-1}})). \end{array}$ (4)

1) 当m=8时，4个8-bit输入32-bit输出的制表操作如下：

 $\begin{array}{l} {\rm{T}}3[{d_0}] = L(Sbox{\rm{ }}({d_0}) \ll 24);\\ {\rm{T}}2[{d_1}] = L(Sbox{\rm{ }}({d_1}) \ll 16);\\ {\rm{T}}1[{d_2}] = L(Sbox{\rm{ }}({d_2}) \ll 8);\\ {\rm{T}}0[{d_3}\left] { = L\left( {Sbox{\rm{ }}\left( {{d_3}} \right)} \right);{d_i} \in } \right[0, 255], 0 \le i < 4。\end{array}$

2) 当m=16时，2个16-bit输入32-bit输出的制表操作如下：

 $\begin{array}{l} {\rm{T}}1[{d_0}] = L(Sbox{\rm{ }}\left( {{d_0} \gg 8} \right)||Sbox{\rm{ }}({d_0}\& 0{\rm{x00ff}}));\\ {\rm{T}}0[{d_1}] = L(Sbox{\rm{ }}\left( {{d_1} \gg 8} \right)||Sbox{\rm{ }}({d_1}\& 0{\rm{x00f}}f));\\ {d_i} \in \left[{0, 65535} \right], 0 \le i < 4. \end{array}$

3 SM4 SIMD技术并行实现

3.1 SIMD技术指令集概述

SIMD技术可实现同一操作并行处理多组数据。目前支持SIMD技术的处理器厂商主要有Intel、AMD、ARM等。Intel处理器中的SSE/AVX指令集及AMD处理器中的SSE/XOP指令集中的指令均采用SIMD技术。目前，大多数PC及服务器采用的是Intel处理器。下面就应用到SM4并行实现上的AVX2指令集作简要介绍。

3.1.1 AVX2指令集简介

2008年Intel宣布推出“Advanced Vector Extensions”(AVX)，引入256-bit宽向量指令集。相比于在128-bit SIMD寄存器——xmm上操作的SSE指令集，AVX指令集有如下改进：1)处理的数据量由128-bit扩展为256-bit；2)消除从内存存取数据时对内存对齐的约束；3)实现非破坏性操作，指令的操作数由2个扩展为3个，2个源操作数的计算结果存放到单独的目的操作数中。AVX指令操作对象称为ymm的256-bit SIMD寄存器(AVX指令操作也支持128-bit SIMD寄存器)，该寄存器内容分为2个128-bit lanes。AVX指令操作对象为lanes，该指令不支持跨越lanes的操作。

2011年Intel发布AVX2指令集，该指令集是对AVX的扩展和改进，AVX2指令支持跨越lanes的操作。AVX2支持8道32-bit整数异或(vpxor)、移位(vpslld)、置换(vpermd)、查表(vpgatherdd)等，这些SIMD指令可应用于SM4实现。2013年Intel在22 nm Haswell微架构处理器上正式推出AVX2指令集。

3.1.2 相关AVX2指令

vpshufb：AVX2中的vpshufb指令继承了SSE指令集中的字节置换指令pshufb。vpshufb指令需要2个xmm寄存器作为输入，如图 2中的xmm0和xmm1。目的操作数xmm0中16个字节的置换结果取决于xmm1：xmm1中每个字节低位nibble值作为“置换掩码”选取xmm0中某一位置的字节。如图 2执行指令“pshufb xmm0, xmm1”，xmm1中第9个字节0x10=16，xmm0第9个字节内容为置换前xmm0的第0个字节。当xmm1中某一字节内容大于127时，对应xmm0字节位置内容被置为0。

 Download: JPG larger image 图 2 vpshufb指令执行 Fig. 2 Execution of vpshufb instruction

3.2 SM4并行实现

3.2.1 SM4消息存储格式

n组128-bit SM4明文消息记为Pi (0 ≤ i < n, n=4, 8)。需将Pi装载到4个SIMD寄存器R0R1R2R3中。装载规则如下

 ${R_k}\left[i \right] \leftarrow {P_i}\left[k \right], 0 \le i < n, 0 \le k < 4,$

 Download: JPG larger image 图 3 SM4明文消息装载格式 Fig. 3 Plaintext message format of SM4

3.2.2 装载轮密钥

SM4轮函数中包含轮密钥层变换，因此为实现n组消息并行加/解密须将n个32-bit轮密钥装载到SIMD寄存器中。将32个轮密钥装载到SIMD寄存器有2种方式：1)每次轮变换时使用AVX2指令vpgatherdd装载到SIMD寄存器中；2)进入SM4加/解密操作前，依次将32个轮密钥存放在SIMD寄存器中。受限于Intel、AMD处理器中只有16个SIMD寄存器，本文采用第1种方式。实现装载轮密钥的代码如下。

3.2.3 轮函数T变换

SM4轮函数中的T变换操作是由非线性变换τ和线性变换L复合而成。并行实现T变换有2种策略：1)分别实现τL；2)将τL合并实现。接下来分别阐述这2种策略的实现方法。

1) 方法1

 $\begin{array}{l} S0\left[i \right] = ST\left[i \right];\\ S1\left[i \right] = ST\left[i \right] \ll 8;\\ S2\left[i \right] = ST\left[i \right] \ll 16;\\ S3\left[i \right] = ST\left[i \right] \ll 24;0 \le i < 256. \end{array}$

 $\begin{array}{l} \tau \left( R \right) = S0[R\& {\rm{0xff}}] \oplus S1\left[{\left( {R \gg 8} \right)\& {\rm{0xff}}} \right]\\ \oplus S2\left[{\left( {R \gg 16} \right)\& 0{\rm{xff}}} \right] \oplus {\rm{ }}S3\left[{R \gg 24} \right]. \end{array}$ (5)

2) 方法2

 $\begin{array}{l} S0\left[{256i + j} \right] = \left( {ST\left[i \right] \ll 8} \right) \oplus ST\left[j \right];\\ S1\left[{256i + j} \right] = \left( {\left( {ST\left[i \right] \ll 8} \right) \oplus ST\left[j \right]} \right) \ll 16;\\ 0 \le i < 256, 0 \le j < 256. \end{array}$

 $\tau \left( R \right) = S0[R\& {\rm{0xffff}}\left] { \oplus S1} \right[\left( {R \gg 16} \right)\& 0{\rm{xffff}}].$ (6)

T变换中的L包含循环移位和异或操作，一般来说，循环移位操作可通过左移、右移和异或操作实现。经研究发现，可使用字节置换指令vpshufb优化L中包含的4个循环移位操作：

1) $\lll$24：循环移位24 bit相当于循环移位3个字节位置，这样，可执行vpshufb指令实现；

2) $\lll$2：分别执行左移指令vpslld、右移指令vpsrld和异或指令vpxor即可实现；

3) $\lll$10、$\lll$18：相当于对完成$\lll$2后再次分别执行$\lll$8、$\lll$16。这样，类似于$\lll$24，$\lll$8和$\lll$16可分别执行vpshufb指令实现。

1) 8-bit输入32-bit输出查表实现

T变换制成的4个表记为T0、T1、T2、T3。这样T变换即可通过掩码、异或、移位、查表操作实现。如式(7)所示。

 $\begin{array}{l} T\left( R \right) = T0[R\& 0{\rm{xff}}] \oplus T1[\left( {R \gg 8} \right)\& 0{\rm{xff}}]\\ \oplus T2[\left( {R \gg 16} \right)\& {\rm{0xff}}\left] { \oplus T3} \right[R \gg 24]. \end{array}$ (7)

2) 16-bit输入32-bit输出查表实现

T变换制成的2个表记为T0、T1。这样T变换即可通过掩码、异或、移位、查表操作实现。如式(8)所示：

 $T\left( R \right) = T0[R\& {\rm{0xffff}}] \oplus T1[\left( {R \gg 16} \right)\& 0{\rm{xffff}}].$ (8)

3.2.4 轮函数F优化

3.3 SIMD技术并行实现与查表实现比较

4 实验结果分析

5 总结

 [1] 国家密码管理局. GM/T0002-2012. SM4分组密码算法[S]. 北京: 中国标准出版社, 2012. [2] 国家密码管理局. 国家密码管理局公告第23号[EB/OL]. (2012-02-21)[2017-01-20]. http://www.oscca.gov.cn/News/201204/News_1227.htm. [3] U. S. Department of Commerce/National Institute of Standards and Technology. Data encryption standard(DES), federal information processing standards publication[S/OL]. Gaithersburg, MD(1999)[2017-01-20]. http://csrc.nist.gov/publications/fips/fips46-3/fips46-3.pdf. [4] Daemen J, Rijmen V. The design of Rijndael:AES-the advanced encryption standard[M]. Springer Science & Business Media, 2013. [5] Gueron S. Intel advanced encryption standard (AES) new instructions set[R/OL]. Intel White Paper Rev3. 01. (2012)[2017-01-20]. https://software.intel.com/sites/default/files/article/165683/aes-wp-2012-09-22-v01.pdf. [6] Intel: advanced vector extensions programming reference[R/OL]. Intel corporation (2009)[2016-12-29]. https://software.intel.com/sites/default/files/managed/39/c5/325462-sdm-vol-1-2abcd-3abcd.pdf. [7] Seiichi M, Shiho M. Lightweight cryptography for the cloud: exploit the power of bitslice implementation[C]//Prouff E, Patrick S. CHES 2012. Berlin Heidelberg: Springer, 2012: 408-425. http://dl.acm.org/citation.cfm?id=2413347 [8] Biham E. A fast new DES implementation in software[C]//Biham E. FSE1997. Berlin Heidelberg: Springer, 1997: 260-272. http://link.springer.com/10.1007/BFb0052352 [9] Bogdanov A, Knudsen L R, Leander G, et al. PRESENT: an ultra-lightweight block cipher[C]//Paillier P, Verbauwhede I. CHES 2007. Berlin Heidelberg: Springer, 2007: 450-466. http://dl.acm.org/citation.cfm?id=1422007 [10] Shibutani K, Isobe T, Hiwatari H, et al. Piccolo: an ultra-lightweight block cipher[C]//Preneel B, Takagi T. CHES 2011. Berlin Heidelberg: Springer, 2011: 342-357. [11] Neves S, Aumasson J P. Implementing BLAKE with AVX, AVX2, and XOP[J]. IACR Cryptology ePrint Archive, 2012, 2012:275. [12] Aumasson J, Henzen L, Meier W, et al. SHA-3 proposal BLAKE[J/OL]. Submission to NIST, 2008. [2017-01-20]. http://www.131002.net/blake/. [13] Ryad B, Guo J, Victor L, et al. Implementing lightweight block ciphers on x86 architectures[C]//Lange T, Lauter K. SAC 2013. Berlin Heidelberg: Springer, 2014: 324-351. http://rd.springer.com/chapter/10.1007/978-3-662-43414-7_17