密码学报 ISSN 2095-7025 CN 10-1195/TN
Journal of Cryptologic Research, 2020, 7(6): 799-811 ©《密码学报》编辑部版权所有.E-mail: *************** www.
Tel/Fax: +86-10-82789618
SM4算法快速软件实现*
*基金项目：北京市自然科学基金(4202037); CCF-腾讯科研基金(CCF-Tencent RAGR20200123)；国家重点研发计划 (2017YFB1400700)；科学研究与研究生培养共建项目(JD 100060630)；国家级大学生创新创业训练计划(201910006159, 201910006107)
Foundation: Natural Science Foundation of Beijing Municipality (4202037); CCF-Tencent Open Fund (CCF-Tencent RAGR 20200123); National Key Research and Development Program of China (2017YFB1400700); Co-Funding Project of Beijing Municipal Education Commission for Scientific Research and Graduates Training (JD 100060630); National Students 1 Innovation and Entrepreneurship Training Program (201910006159, 201910006107)
收稿日期：2019-11-13 定稿日期：2020-01-13
张觌气I 华气张习肚王肌刘建伟3
1. 北京航空航天大学软件开发环境国家重点实验室，北京100191
2. 密码科学技术国家重点实验室，北京100878
3. 北京航空航天大学空天网络安全工业与信息化部重点实验室，北京100191
4. 北京卫星信息工程研究所，北京100086
通信作者：郭华，E-mail: *************；张习勇，E-mail: ************************
摘要：SM4是对称分组密码国家标准•加解密计算效率是衡量算法实现性能的重要指标，而目前关于
SM4软件实现方法方面的研究不多.利用比特切片技术，结合支持单指令多数据(SIMD)的AVX2指令 集，本文提出了一种SM4算法的快速软件优化实现方法，使用256位的YMM 奇存器实现了 SM4算法
的256分组数据并行加解密.首先基于已有的选择函数构造了新的选择函数，之后改进了搜索算法，基于
新的选择函数和改进的搜索算法化简了 S 盒的逻辑表达式，将实现逻辑表达式所需的逻辑门电路数量
由 3000(最简与或式)降至497.在Intel Core I7-7700HQ (Kabylake) @2.80 GHz 处理器上，实现速度达到
了 2580 Mbps，同公开文献中的最好结果 1795 Mbps (Intel Core i7-5500U (Broadwell-U) @2.40 GHz)
相比，实现效率提高了 43%.基于比特切片技术的软件实现优化方法无需内存或高速缓存查表，因此该方
法可抵抗缓存-计时侧信道攻击，从而安全性得到了提升.本文提出的优化方法具有可扩展性，不仅适用于 在X86平台上借助拓展指令集AVX2实现，还可利用RISC 指令集在资源受限，安全性要求高的ARM
等嵌入式平台上实现.此外，新的选择函数和搜索算法具有通用性，可用于其它一般逻辑函数的化简.关键词：SM4算法；软件优化实现；比特切片；SIMD 技术
中图分类号：TP309.7 文献标识码：A DOI: 10.13868力ki.jcr.000407
中文引用格式：张笑从，郭华，张习勇，王闯，刘建伟.SM4算法快速软件实现[J].密码学报，2020, 7(6): 799-811.
[D0I ： 10.13868/jki.jcr.000407]
英文引用格式：ZHANG X C, GUO H, ZHANG X Y, WANG C, LIU J W. Fast software implementation of
SM4[J]. Journal of Cryptologic Research, 2020, 7(6): 799-811. [DOI: 10.13868/jki.jcr.000407]
Fast Software Implementation of SM4
ZHANG Xiao-Cong b3, GUO Hua b2, ZHANG Xi-Yong 4, WANG Chuang 1, LIU Jian-Wei 3
1. State Key Laboratory of Software Development Environment, Beihang University, Beijing 100191, China
2. State Key Laboratory of Cryptology, Beijing 100878, China
800Journal of Cryptologic Research密码学报Vol.7,No.6,Dec.2020
3. Key Laboratory of Aerospace Network Security(Ministry of Industry and Information Technology), Beihang University,Beijing100191,China
4. Beijing Institute of Satellite Information Engineering,Beijing100086,China
Corresponding author:GUO Hua,E-mail:*************;ZHANG Xi-Yong,E-mail:xiyongzhang@hotm-ail
Abstract:The SM4algoiithm is China's national standard of symmetric block cipher,and its efficiency is one of the most important features.So far,insufficient work has been done on fast software implementation of SM4algorithm.Exploiting bit-slicing technique and SIMD(single instruction multiple data)instruction set AVX2,this paper presents a fast implementation of SM4algorithm which can process256blocks in parallel via256bits YMM registers.Firstly,a new selection function is constructed based on existing ones.Then,the logic circuit generating algorithm corresponding to the selection function is improved.Furthermore,the number of gates of the S box is reduced from3000to 497.Using an Intel Core i7-7700HQ(Kabylake)@2.80GHz processor,the software performance is2580 Mbps,43%ahead of SM4's benchmark on software implementation which is1795Mbps(Intel Core i7-5500U(Broadwell-U)@2.40GHz).Bit-sliced implementation does not require to store a table in memory or in cache,hence it is immune to side channel attacks such as cache attack and timing attack. The improved method presented in this paper can be implemented on various computing platforms, which means that it is suitable to X86architecture with extended instruction set AVX2,and is also suitable to embedded systems with RISC instructions and limited resource.Note that the impr
oved selection function and the improved logic circuit generating algorithm are a generic approach,which can be used to the reduction of general logical functions.
Key words:SM4;software implementation:bit slicing;SIMD
1引言
SM4分组密码算法⑴是我国自主设计的对称分组密码，为众多信息系统提供安全、完整的数据加密方案.SM4算法的高效软件实现为我国应用在安全产品(如IPSec、VPN、SSL、TLS等)上的密码算法由国际标准替换为国家标准提供了强有力的支撑，为SM4算法广泛用于政府办公、公安、银行、税务、电力等自主可控要求高的信息系统提供了可靠的保障.目前关于SM4算法的软件优化实现方面的相关工作不多，多使用查表的方法何，但由于代替表规模相对较大，CPU在做查表操作时，表中数据在内存和cache 之间频繁对换导致查表延时较大，且不利于高效并行加/解密多组消息.此外，查表法无法抵抗缓存-计时侧信道攻击，因此在一定程度上制约了SM4的软件实现性能和安全性.
1996年Intel推出单指令多数据的SSE(Streaming SIMD Extensions)指令集后，Biham同于1997年提出一种新的对称分组密码快速软件实现方法，核心思想是将处理器视为以1比特为单位的单指令多数据处理器，随后被Matthew Kwan称为比特切片(bit slicing)⑷.比特切片方法在64位平台上实现了64组DES消息的并行加解密，将逻辑门个数从理论上需要的132个每比特输出优化到10()个每比特输岀.之后研
究者们对门函数个数进一步进行了优化，使得标准逻辑门(与、或、非、异或)和非标准逻辑门均达到了平均50+个每比特输出.2011年Roman Rusakov同又将门函数的个数降至平均44个逻辑门每比特输岀.比特切片方法可大大提高实现效率，也可用于搜索密钥，对RISC和CISC的指令集平台均适用，且具有更好的安全性.
为了提高软件实现速度，国内外许多学者尝试将采用SIMD(Single Instruction Multiple Dada，单指令多数据)技术用于密码算法的软件实现.A.Adomnicai和T.Peyrin何给出改进的比特切片方法“Fixslicing”，在ARM和RISC-V平台实现了AES.2012年Intel推出高级向量指令集(Advanced Vector Extensions,AVX)后，众多学者开始研究如何利用AVX指令集加速对称分组密码算法的实现速度，尤其是轻量级密码算法的实现速度.Seiichi Matsuda和Shiho Moriai卩】利用AVX指令集加速切片实现，给
张笑从等：SM4算法快速软件实现801
出了轻量级密码算法面向云端的实现，将SSE指令与比特切片方法结合并应用到PRESENT/Piccolo，使两者的实现吞吐量分别达到4.3cycle/byte和4.57cycle/byte.2013年，Neves和Aumasson同将AVX2指令应用到SHA-3候选算法BLAKE上并提高了其实现性能.最近，郎欢等何利用X86架构下的SIMD 指令给出了高效的SM4实现，他们釆用C语言调用AVX2指令接口方式实现，在并行查表的基础上，给出了两种不同的方法.2014年Kostas Papapagiannopoulos等人口°】将比特切片方法修改为nibble切片方法，并减少了访问内存，在AVR处理器上给出了高效实现.
此外，研究者们将比特切片方法和其它方法结合，对SM4算法进行软件实现，也取得了较好的效果. SM4算法公布不久，Fen Liu等【切破解了SM4算法S盒的结构，公布了S盒的代数表达式及具体参数值.之后，Hao Liang等问基于已破解的SM4中S盒结构，提出了基于复合域的SM4实现方法，将S 盒的有限域求逆运算变换到复合域中实现，并在FPGA上进行验证.Jingbin Zhang等问提出了SM4在复合域中的软件实现，使用X86架构普通指令实现，速率达到20Mbps.最近，A.Eldosouky和W. Saad")针对物联网应用的效率、安全需求改进了轻量级密码算法LED的比特切片方法，并在嵌入式处理器ARM Cortex-A53进行了实现验证.O.Hajihassani等1151利用比特切片方法进一步提高了高级加密算法AES的加解密吞吐率.总的来说，在国密标准SM4算法的软件优化实现方法取得了一些进展，但和其他对称加密算法如AES相比，SM4的软件优化实现仍需进一步研究.
本文利用比特切片方法，结合支持单指令多数据(SIMD)的AVX2指令集，提出了一种SM4算法的快速软件优化实现方法，使用256位的YMM寄存器实现了SM4算法的256分组数据并行加解密.该方法首先对待加密的明文消息通过SIMD版本的数据编排算法进行预处理；之后提出了一种改进的化简逻辑表达式的新方法，将实现逻辑表达式所需的逻辑门电路数量由3000降至497；最后使用反编排算法得到密文.在Intel Core i7-7700HQ(Kabylake)@2.80GHz处理器上，结合x86平台拓展指令集AVX2和上述方法对SM4算法进行软件实现，实现速度达到了2580Mbps.相比于传统的查表实现(Intel Core i7-5500U(Broadwell-U)@2.40GHz)、未优化的比特切片实现(Intel Core i7-5500U(Broadwell-U)@2.40 G
x86架构和arm架构区别Hz)、SM4软件优化实现公开文献的最佳结果[9](Intel Core i7-550()U(Broadwell-U)@2.40GHz)，新方法的实现效率分别提升了 1.8倍、2.6倍和43%.综上所述，本文主要贡献如下：
(1)提出了一种通用的对称分组密码算法的软件优化实现方法，该方法通用于所有对称加密算法的快
速软件实现.
(2)提出的基于比特切片的软件优化实现方法无需内存或高速缓存查表，因此可抵抗缓存-计时侧信
道攻击"1，从而安全性得到了提升.
(3)提出的优化方法具有较强的通用性.该方法可用于所有对称加密算法的软件优化实现，并适用于
不同的软件架构：在CISC架构平台如X86适合借助SSE、AVX2、AVX512等拓展指令集实现，在RISC架构(ARM,RISC-V)的平台可使用普通指令集实现.
(4)新的选择函数和搜索算法具有通用性，可用于一般逻辑函数的化简.
本文其余内容组织如下：第2节介绍SM4算法及AVX2指令；第3节介绍新的选择函数及基于选择函数的改进的搜索算法；第4节介绍SM4的基于比特切片和AVX指令的软件优化实现方法；第5节介绍实验结果；第6节总结全文.
2预备知识
2.1SM4简介
SM4算法釆用非平衡Feistel结构"1，分组长度和密钥长度各为128比特，解密算法与加密算法结构相同，区别在于轮密钥使用顺序相反.下面首先介绍SM4的轮函数.
设明文输入为(Xo,X“X2,X3)6(Z护)4，密文输出为(Yo,m,⑹€(Z跻丫，轮密钥为rk：6Zf2, 1=0,1,••-,31.SM4加密算法的轮函数F如图1所示.
轮函数F每次迭代的输入为(Xi,X,+l,X；+2,X<+3)，输出为(X,+l,X,+2,X;+3，尢+4)，尢+4的计算方法如下：
802Journal of Cryptologic Research 密码学报 Vol.7, No.6, Dec. 2020
X ：+4 = F(Xi, Xi+i, Xi+2, X ：+3)= X ： + T(Xi+i + Xi+2 + X+3 + rki)
其中，rk.为当前迭代的轮密钥，T 为一个Z/2 t Zf 的可逆变换.
T 为一个Zf t Z 舁的可逆变换，由非线性变换T 和线性变换L 复合而成，即T(・)= L(r(-)).
非线性变换t 由4个并行的S 盒构成.设输入为A = (ao,ai,a2,a3)€ (Z®)4，输出为B = (feo,&i,&2, &3)€ (Z 寻)4，贝！I ：
(6(), bi, &3)= r(A) = (Sbox(ao), Sbox(ai), Sbox(a2), Sbox@3))
对于每个S 盒的8位输入，前4位作为行，后4位作为列，输岀即为查表中对应行列所对应的值.S 盒
如图2所示.
D C B A 9
5926857E 13F 18O 48
O 96A A 389A E 65D B 84C 6C F F D 8851E B A 469
2O A 3497C 1B 455B C 3B 6F F 56141C 3C O 5E B
F 8C 8852C 68561E 6C 89D 56O 1O 95D D F 857
24E 7E 7O A F F O 61B C D 263A 9B B 7E O B 2129E
C 24F 143E C 3A 741O 3644F 9B 26739F 9 49E
B 45D 5E 23F 92F D 7B E 6A 3O 385
C 3
D O 31D 59
1A 388F 24A A C O 1267 73A 5A B 2255O F F D E O
B C 79B 8A.5B 5627B 72
D 4887A 178A A
E C B 7D 3O 9E 1D D 231C 8B 774 1E
F 83483746D D D 6Q
E B E O 765D C 36
F D C 9D C A 19 313F O B 2E B 5C A
C 29C F 7 69 498
D B A O 3
E 64 9C 2E 724E 528A C
F 7F A F B 55D A 24984E 9A O C 71E 6A D 27F 17D
E 951A 8O 485E 3A 397 O 7237B 4O
F E 6B B 19O
964B O 62O B A F D 1C 6F 6B C 478E 4A O D 5D A 9 8
D 29
E 461D E E 1D 8O 814 c
F C 2 2 29 3 o 7 o F 33A c o 1 F
6 5 D F 5图2 SM4代替表
Figure 2 Substitution table in SM4 algorithm
图1 SM4轮函数
Figure 1 Round function in SM4 algorithm L 是线性变换，非线性变换丁的输出是线性变换L 的输入.设输入为B t Z 沪，输出为C t Z 沪，则
C = L(B) = B + (£«2) + (£ « 10) + (£ « 18) + (£ « 24)
其中，《代表循环左移，如E «2代表循环左移2位.
2.2 SIMD 技术及AVX2指令集
SIMD (single instruction multiple data)技术可实现同一操作并行处理多组数据.目前支持SIMD
技术的处理器厂商主要有Intel. AMD 、ARM 等.目前大多数PC 及服务器采用的是Intel 处理器，而
Intel 处理器中的SSE/AVX 指令集采用的正是SIMD 技术.AVX (Advanced Vector Extensions)指令 集1181是256-bit 宽向量指令集，指令操作对象称为YMM 的256-bit SIMD 寄存器.该寄存器内容分为
2个128-bit lane. AVX 指令操作对象为lanes，该指令不支持跨越lanes 的操作.
AVX2指令集是AVX 指令集的扩展和改进，也称为Haswell New Instructions，支持跨越lanes 的操
作.AVX2 支持 8 道 32-bit 整数异或(vpxor)、移位(vpslld)，置换(vpermd)、查表(vpgatherdd)等. 2013年Inter 在22 nm Haswell 微架构处理器上正式推出AVX2指令集.表1给出了部分AVX2指令,
这些指令可用于对称分组密码的切片实现.
3构造新的选择函数及搜索算法
“选择函数” 119＞是Mattew 为比特切片方法中简化实现S 盒逻辑门电路数量而提出的一种逻辑函数 表达形式.选择函数的思想为二分法，每次分得两个子函数，直至最终分解到的子函数可以直接实现.经
研究发现，对于上述特定问题选择函数形式比其他常用的标准形式优越许多.如上所述，对于SM4算法 的S 盒，使用最简与或形式、最简或与形式、最简与或非形式等需要逻辑门数约为3000，而使用己知的
3
张笑从等：SM4算法快速软件实现803
表1相关AVX2指令总结
Table1Summary of relevant AVX2instructions
AVX2指令C/C++接口功能描述
vpshufhw_mm256_shufflehi_ep订64道64位数据重排
vpshuflw_mm256_shufflelo_ep订64道64比特数据重排
vpshufd_mm256_shu田e_epi328道32比特数据重排
vpermq_mm256_permute4x64_epi644道64比特数据重排
vpslld_mm256_slli_epi328道32比特逻辑左移
vpsrld_mm256_srli_epi328道32比特逻辑右移
vpxor_mm256_xor_si25625&比特逻辑异或
vpor_mm256_or_si256256-比特逻辑或vpgatherdd_mm256_load_si256/_mm256_store_si2568道32比特查表
vmovdqa_mm256_load_si256/_nim256_store__si256加载/存储256比特数据(要求内存对齐) vmovdqu_mm256_loadu_si256/_mm256_storeu_si256加载/存储256比特数据(不要求内存对齐)
个选择函数形式时，可将逻辑门数限制在：N sm4=12+8x(2'+22+---+28-2)=1032.使用本文提出的新的选择函数及改进的搜索算法，可进一步将逻辑门数减至497门.一般来说，使用的选择函数越多，搜索越充分，越能减少逻辑门数量.
本节首先基于已有的选择函数构造新的选择函数、之后基于新的选择函数给出改进的搜索算法，最后 介绍如何使用新的选择函数及改进的搜索算法化简S盒的逻辑表达式.
3.1选择函数简介
为化简比特切片方法中实现S盒所用的逻辑门电路数量，Mattew提出了化简逻辑门电路的算法及“选择函数”的概念.使用选择函数，DES中实现S盒的逻辑门电路数量从平均70门每比特输出被约简到平均45门每比特输岀.
设凡为8比特逻辑函数，即F o(abcdefgh)，从输入abcdefgh中任选一个比特，记为sei，给岀选择函数基本形式：
F o=(Fi and sei)or(F2and not sei)
不妨设sei为d，规定：
Fi=Fi(abcefgh),F2=F2(abcefgh)
由于Fi与F2均唯一存在，从而8比特逻辑函数被分解成7比特逻辑函数，这一过程称为利用“选择函数”的一次选择.
Mattew给出了三种“选择函数”表达式：
F。=(Fi and sei)or(J2and not sei)
令F3=Fi xor F2，局=(not F o)and sei,F5=F o xor F4，贝J
F o =(F3and sei)xor F2,F o={Fi or sei)xor F5
Mattew指出，还可使用nand、nor等非标准逻辑门构造更多选择函数.生成选择函数形式的逻辑表达式过程如下：从需要实现的逻辑函数出发，进行选择，逆向生成整个逻辑电路，直至最终得到许多2比特逻辑函数.理论上共有16种不同的2比特逻辑函数，其中有4个是平凡的(常量0,1和直接连接两个输入)，另外12个非平凡的逻辑函数可由两个输入连接12个逻辑门实现，如图3所示•每次选择时都有上述3个选择函数形式可以使用，需要逐个尝试以取得较好结果・对于DES的6比特输入4比特输出S 盒来说，先后处理4个输出，每个输出最多需要4次“选择”.处理过程中，对1个逻辑函数做“选择”前,
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论