一种基于复合域的国密SM4算法快速软件实现方法_陈晨.pdf

密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):289305密码学报编辑部版权所有.E-mail:http:/Tel/Fax:[phone]一种基于复合域的国密 SM4 算法快速软件实现方法*陈 晨1,2,郭 华1,2,王 闯3,刘源灏1,刘建伟11.北京航空航天大学 空天网络安全工业和信息化部重点实验室,北京 1001912.密码科学技术国家重点实验室,北京 1008783.国防科技大学 计算机学院,长沙 410073通信作者:郭华,E-mail:摘要:成为 ISO/IEC 国际标准算法后,SM4 的性能受到更多关注.目前针对 SM4 算法实现效率提升的方法主要集中在缩短 S 盒的运算时间,其中采用复合域实现的方法大都基于 AES 算法实现的复合域,而在 GF(24)2)上鲜有针对 SM4 算法软件实现的复合域被提出.本文首次在 GF(24)2)上找到了一个针对 SM4 算法 S 盒软件实现的复合域,给出一种基于复合域的 SM4 算法快速软件实现方法,使用穷举搜索和数学分析优化了算法 S 盒的复合域数学构造,构建了同构映射矩阵及其最小化目标函数,仅使用 175个门函数就完成了 S 盒运算,平均每个输出比特占用 22 个门函数.基于比特切片技术,利用扩展指令集AVX2 实现了 SM4 算法 256 组消息的并行化加密.每字节加解密平均耗时仅 6.5 个时钟周期.对硬件依赖程度低,经测试在 Intel i5、Intel i7 和 AMD R7 环境下均能显著提升 SM4 算法的计算效率,对有相似S 盒结构的密码算法快速软件实现具有重要的参考价值.关键词:SM4 算法;S 盒;复合域;比特切片;AVX2 扩展指令集中图分类号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000594中文引用格式:陈晨,郭华,王闯,刘源灏,刘建伟.一种基于复合域的国密 SM4 算法快速软件实现方法J.密码学报,2023,10(2):289305.DOI:10.13868/ki.jcr.000594英文引用格式:CHEN C,GUO H,WANG C,LIU Y H,LIU J W.A fast software implementationof SM4 based on composite fieldsJ.Journal of Cryptologic Research,2023,10(2):289305.DOI:10.13868/ki.jcr.000594A Fast Software Implementation of SM4 Based on Composite FieldsCHEN Chen1,2,GUO Hua1,2,WANG Chuang3,LIU Yuan-Hao1,LIU Jian-Wei11.Key Laboratory of Aerospace Network Security(Ministry of Industry and Information Technology),Beihang University,Beijing 100191,China2.State Key Laboratory of Cryptology,Beijing 100878,China3.School of Computer Science,National University of Defense Technology,Changsha 410073,ChinaCorresponding author:GUO Hua,E-mail:Abstract:Since becoming an ISO/IEC international standard,the efficiency of SM4 has attracted*基金项目:北京市自然科学基金(4202037);国家自然科学基金(61972018)Foundation:Natural Science Foundation of Beijing Municipality(4202037);National Natural Science Foundationof China(61972018)收稿日期:2022-04-01定稿日期:2022-09-05290Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023more attention than before.At present,the methods to improve the efficiency of SM4 algorithm aremainly focused on shortening the operation time of S-box.Most of the methods using compositefield are based on AES,while few composite fields for SM4 software implementation are proposedover GF(24)2).This paper presents a composite field on GF(24)2)for the software implementationof S-box in SM4,gives a fast software implementation of SM4 based on composite field,optimizesthe mathematical construction of the S-box composite field by exhaustive search and mathematicalanalysis,constructs isomorphic mapping matrix and its minimum objective function,and completes S-box operation by only 175 gate functions with each output bit occupying an average of 22 gate functions.Based on bit-slicing technics,the parallel encryption of 256 groups of messages in SM4 algorithm isrealized by using the extended instruction set AVX2.The average encryption and decryption timeper byte is only 6.5 clock cycles.The proposed method has a low dependence on hardware.Thetesting experiments show a significant improvement of the computational efficiency of SM4 on Inteli5,Intel i7 and AMD R7 platforms.The proposed method can be a good reference for fast softwareimplementation of other cryptographic algorithms with S-box structures like that in SM4.Key words:SM4 algorithm;S-box;composite field;bit slicing;AVX2 extend instructions1引言SM4 算法1是我国自主研发的无线局域网标准的分组密码算法,于 2012 年 3 月成为中国密码行业标准,2016 年 8 月转化为中国国家标准,已为众多信息系统提供了安全、完整的数据加密服务.2021 年 6月 SM4 算法正式成为 ISO/IEC 国际标准,不仅进一步增强了我国商用密码产业的国际竞争力,并且让学者们更加关注 SM4 算法高性能实现的研究.2000 年,Rijmen2提出使用子域 GF(24)上的运算完成有限域 GF(28)上的求逆运算方法,将 8 比特元素的计算问题转换为若干个 4 比特元素的计算,从而降低实现 S 盒的代数复杂度,这种方法被用于AES3的 S 盒.Rudra 等4利用合成域方法,将有限域 GF(28)同构映射到复合域 GF(24)2),利用子域 GF(24)完成 Rijndael 算法的二次扩域上的求逆运算,同时指出复合域的选取和构造会影响算法的实现性能,并基于汉明距离从硬件电路角度选择实现的复合域.2007 年,Liu 等5对 SM4 算法的 S 盒进行分析,给出了 S 盒的代数结构及其参数值.2014 年,Liang 等6基于 SM4 算法 S 盒的解析表达式,将有限域 GF(28)上的运算同构映射到塔域 GF(22)2)2)上,实现了 SM4 算法的硬件优化,在选择复合域时更多地考虑了相关性能量攻击和差分能量攻击,并在 Matlab 上进行了仿真验证.Chantarawon 等7则指出,基域的选择并非越小越好,不同的基域表示有各自的工程适应性.比特切片方法于 1997 年由 Biham8首次提出,其核心思想是将处理器视为以 1 比特为单位的处理器,该方法被用于 DES9算法的快速软件实现,在 64 位平台实现了 64 组 DES 消息的并行加解密.此后,比特切片方法被广泛用于分组密码算法的软件设计中.2006 年,Rebeiro 等10基于 Satoh 等11的研究成果,设计出了 AES 算法的比特切片实现,大幅提升了 AES 算法的软件实现性能.2018 年,Zhang等12采用比特切片技术,使用普通指令集完成切片操作,将算术运算等价转换为逻辑运算,给出了一种SM4 算法在复合域 GF(22)2)2)中的软件实现优化方法,其复合域直接采用了 Canright 等13针对AES 硬件实现选择的复合域,最终实现了 64 组消息的并行加解密,其加解密效率相比普通实现方法提升了 80%120%.2020 年,张笑从等14同样采用比特切片技术,通过构造选择函数和改进搜索算法的方式,化简了 S 盒的逻辑表达式,显著降低了实现 S 盒逻辑表达式所需的逻辑门电路数量.除了上述软件优化实现方法外,还有许多其它方式能够提高分组密码算法的实现性能.郎欢等15于2018 年通过分析 SM4 算法的轮函数,将 S 盒查表与线性变换函数结合,使用粒度为 32 位的切片技术,给出了两种查表优化实现方法,并用 AVX2 指令集给出了高效软件实现.Hajihassani 等16于 2019 年提出了一种利用多核特性并行处理 AES 加密的切片方法,并使用 CUDA 编程的方式在 GPU 上给出了 AES的 CTR 模式和 ECB 模式的实现.Alkim 等17在 2020 年设计并评估了一套 RISC-V 扩展指令集,提高了有限域运算的性能,这些指令同样有助于 AES 等密码算法的快速实现.Saarinen 等18则更进一步,陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法291直接设计了一种提高 AES 和 SM4 算法性能的 RISC-V 扩展指令集,不仅在速度上具有明显优势,而且在同时需要 AES 和 SM4 算法实现的芯片上能够明显减少资源消耗和硬件延迟.此外,学者们还给出了许多 SM4 算法的硬件优化实现方法1921,如何诗洋等22在 2021 年针对 SM4 算法提出 4 套硬件架构,并在 XILINX KINTEX-7 FPGA 上实现,吞吐量最高可达 42.10 Gbit/s.除了学术论文中给出的方法外,许多专利中也给出了性能良好的 SM4 实现方法.龚征等23给出的基于塔域优化 S 盒的 SM4 加解密算法并行化实现方法实现 S 盒仅使用了 115 个门函数.其实现方法基于 AVX-512 指令集,采用塔域优化 S 盒的方法给出了 SM4 加解密算法的并行化实现方法,在 Inteli7-1160G7 平台 ECB 工作模式下加密性能达到了 6542 Mbps.这些方法启发了 SM4 算法软件实现的优化思路.通过上述研究成果可以发现,SM4 的快速实现方法大都在于缩短 S 盒的运算时间,而目前基于复合域的 S 盒优化方法存在如下问题:(1)目前公开文献中采用复合域方式实现 SM4 算法 S 盒的方法,其复合域大都直接使用了 Canright等13针对 AES 算法构造的复合域,复合域构造在 GF(22)2)2)上且未作任何针对 SM4 算法的优化,对 SM4 算法 S 盒实现性能提升有限;(2)目前针对 AES 算法的复合域构造方法仅采用简单的穷举搜索方法,且由于考虑了硬件电路规模而没有找到计算效率最优的复合域.针对上述问题,本文提出了一种基于复合域优化选取和比特切片并行化技术相结合的 SM4 算法快速软件实现方法,首次找到了一个针对 SM4 算法 S 盒软件实现的复合域,将加密每字节所需的时钟周期降低到了 6.5 个时钟周期,大幅提升了 SM4 算法的软件实现效率.本文的主要贡献包括:基于 GF(24)求逆运算实现了有限域 GF(28)上的 S 盒高效求逆算法.本文从数学角度给出了一种较优的复合域表示,给出了有限域 GF(28)和复合域 GF(24)2)之间的同构映射矩阵的构造算法,并最小化相应的最优化目标函数,从而降低了有限域 GF(28)上的求逆运算的复杂度,仅使用 175 个门函数完成了 S 盒运算,平均每个输出比特只占用了 175/8 22 个门函数.基于找到的复合域,采用比特切片方法和 AVX2 指令集对 SM4算法进行了实现,通过调整计算过程中使用的汇编指令,使用了较少时钟周期就完成了 SM4 的加解密运算,加密每字节只需要 6.5 个时钟周期.本文的组织结构如下:第2节介绍 SM4 快速软件实现方法的相关知识;第3节详细介绍对于 SM4 算法的 S 盒如何选取较优的复合域表示形式进而减少计算开销;第4节对所提基于复合域的 SM4 算法优化给出具体的比特切片实现;第5节对实现算法的加解密效率进行对比测试;第6节总结全文,提出后续研究方向.2相关知识2.1SM4 算法简介SM4 算法是一个分组密码算法,分组长度和密钥长度均为 128 比特,运算轮数为 32 轮.SM4 的解密算法和加密算法结构相同,只是轮密钥的使用顺序相反.算法的加密过程由 32 次轮函数运算 F 和1 次反序变换 R 组成.假设每轮输入为(Xi,Xi+1,Xi+2,Xi+3)(Z322)4,每轮输出为(Xi+1,Xi+2,Xi+3,Xi+4)(Z322)4,则 SM4 算法的轮函数 F 如图1所示.其中 rki Z322,i=0,1,31 表示轮密钥,T 为一个 Z322 Z322的可逆变换.轮函数 F 为:Xi+4=F(Xi,Xi+1,Xi+2,Xi+3)=Xi T(Xi+1 Xi+2 Xi+3 rki),明文数据经过 32 轮迭代后,最后的输出经过 1 次反序变换 R,得到输出密文 Y 为:Y=R(X32,X33,X34,X35)=(X35,X34,X33,X32),292Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023图 1 SM4 轮函数 FFigure 1 Round function F in SM4在轮函数 F 中,T 变换包含了一个线性变换 L 和一个非线性变换,即:T(A)=L(A),A Z322,其中输入 A 表示为:A=(a0,a1,a2,a3)(Z82)4.非线性变换 由 4 个并行的 S 盒构成,S 盒是一个字节代替表,输入和输出均为 8 比特.用 Sbox()表示 S 盒,则非线性变换 的计算公式为:(A)=(Sbox(a0),Sbox(a1),Sbox(a2),Sbox(a3).线性变换 L 以非线性变换 的输出作为输入.设 L 输入为 B Z322,代表循环左移,则线性变换L 的计算公式为:L(B)=B (B 2)(B 10)(B 18)(B 24).密钥扩展算法将初始密钥扩展成各轮子密钥.令初始密钥 MK=(MK0,MK1,MK2,MK3)(Z322)4,则按如下方式生成轮密钥:(K0,K1,K2,K3)=(MK0 FK0,MK1 FK1,MK2 FK2,MK3 FK3),rki=Ki+4=Ki T(Ki+1 Ki+2 Ki+3 CKi),其中 i=0,1,31,且(1)FK 是系统参数,CK 是超参数.(2)T=L(),L表示为:L(B)=B (B 13)(B 23).2.2比特切片方法比特切片方法是一种分组密码软件高效实现的有效方法,其主要思路是在每个寄存器中存入多组比特粒度的数据切片,通过同时操作多个寄存器实现多组明文数据的并行化加解密.该方法通常包括数据重排、算法实现和数据逆重排三个步骤.明文数据由左至右,正常存储在内存中的明文数据经过数据重排改变了存储方式,再通过计算机指令实现算法的加密过程,最后经过数据逆重排恢复为原本的存储方式,详细过程如下:陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法293(1)数据重排比特切片要求处理器以比特为粒度对数据进行操作.数据重排通过改变数据的存储方式,将数据组织形式由“串行”变为“并行”,使得所有并行分组的同一位集中在一个字中.(2)算法实现比特之间的操作包括基本与、或、非等运算,因此需要对分组密码算法进行逻辑运算,即将整数之间的加、减、乘、除运算表示为比特之间的与、或、非等基本运算.算法实现将查表操作等价转换为布尔函数,从而使用基本门电路元件实现分组密码算法.(3)数据逆重排为了能正确显示加解密数据,数据逆重排将数据的组织形式恢复为字节形式,以显示加密结果.相比普通的分组密码算法软件实现,基于比特切片的软件实现需要额外增加两次数据重排.但由于比特切片能够并行处理多组数据,并行带来的优势足以抵消数据重排带来的消耗,因此基于比特切片方法实现一组数据加解密所需的平均时间远小于普通软件实现的平均时间.另外,如果加密方和解密方默认消息在内存中以比特形式存储,则可省略数据重排,从而使得基于比特切片方法的软件实现相比普通方法的软件实现更占优势.2.3AVX2 指令集简介AVX(advanced vector extensions)指令集是宽度为 256 比特的向量指令集,指令操作对象为 256 比特的 YMM 寄存器.根据不同的数据粒度,YMM 寄存器可同时操作 4 组 64 比特、8 组 32 比特、16 组16 比特或 32 组 8 比特的数据进行并行计算.AVX2 在 AVX 基础上做了扩展,表1给出了部分可用于SM4 切片实现的 AVX2 指令.表 1 部分 AVX2 指令Table 1Partial AVX2 instructions指令名称函数名指令作用vmovdqa_mm256_load_si256/_mm256_store_si256加载/存储 256 比特数据(要求内存对齐)vmovdqu_mm256_loadu_si256/_mm256_storeu_si256加载/存储 256 比特数据(不要求内存对齐)vpor_mm256_or_si256256-比特逻辑或vpxor_mm256_xor_si256256-比特逻辑异或vpshufhw_mm256_shufflehi_epi164 道 64 位数据重排vpermq_mm256_permute4x64_epi644 道 64 位数据重排vpslld_mm256_slli_epi328 道 32 位逻辑左移vpsrld_mm256_srli_epi328 道 32 位逻辑右移vpgatherdd_mm256_i32gather_epi328 道 32 位查表vpshufb_mm256_shuffle_epi832 道 8 位数据重排使用 AVX2 扩展指令集能够高效完成大部分任务需求,如:(1)8 道数据并行移位.vpslld、vpsrld 指令可实现 8 道 32 比特数据并行左移、右移,结果存放在目的操作数中.(2)8 道数据并行查表.vpgatherdd 指令能够实现 8 道 32 比特数据并行查表,操作数 1 指向查找表的起始地址,操作数 2 表示待查表的数据,结果存放在目的操作数中.(3)32 道数据字节置换.vpshufb 指令可实现 32 道数据字节置换,操作数 YMM1 决定了目的操作数 YMM0 的 32 个字节的置换结果,操作数 YMM2 中每个字节的低 4 位作为置换掩码选取YMM1 中某一位置的字节.相比普通指令集提供的 64 位寄存器,扩展指令集能够提供更长的寄存器,如 128 位、256 位,甚至512 位.如果将普通指令集和比特切片方法结合,能够并行处理的消息分组最大为 64 组;如果将扩展指令294Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023集与比特切片方法结合,能够并行处理更长的消息分组,既能发挥扩展指令集的加速效果,又能充分利用比特切片方法的并行优势.3复合域下 SM4 的 S 盒优化方法SM4 的 S 盒基于有限域 GF(28)上的运算构建,代数表达式为:S(x)=I(x A+C)A+C,其中,I()为 GF(28)上的求逆运算,不可约多项式为:F(z)=z8+z7+z6+z5+z4+z2+1,行向量 C 为:C=11010011,循环矩阵 A 为:A=|1110010111110010011110011011110001011110001011111001011111001011|.因此可以使用代数表达式直接计算 S 盒的结果.为了提高代数表达式的计算效率,本文使用子域GF(24)上的运算完成有限域 GF(28)上的求逆运算,将 8 比特元素的计算转换为若干个 4 比特元素的计算,从而降低实现 S 盒的代数计算复杂度.使用子域 GF(24)上的运算完成有限域 GF(28)上的求逆运算包含两个核心步骤:构建 GF(24)2)的复合域和构造将有限域 GF(28)映射到复合域 GF(24)2)上的同构映射矩阵.本节给出一种复合域GF(24)2)的优化选取方法,和一种有限域间同构映射矩阵的优化构造方法.3.1复合域 GF(24)2)的优化选取方法有限域 GF(2n)中的元素在其多项式基 1,2,n1 下,A=n1i=0 xii可表示为 n 元组(x0,x1,xn1)Fn2.为简便起见,本文中与整数不加区别地表示为n1i=0 xi2i 0,1,2,2n1.复合域 GF(2n)m)可由 GF(2n)上的 m 次不可约多项式 P(x)来构建,GF(2n)由 GF(2)上的 n次不可约多项式 Q(y)构建.当 k=n m 时,复合域 GF(2n)m)和有限域 GF(2k)代数同构,二者的元素之间存在保持加法和乘法的一一对应关系.本文 SM4 算法的 S 盒实现采用的复合域为 GF(24)2),构建它需要两个多项式 P(x)和 Q(y),其中P(x)是 GF(24)上的二次不可约多项式,Q(y)是 GF(2)上的四次不可约多项式.P(x)定义了复合域GF(24)2)上的元素运算,Q(y)定义了有限域 GF(24)上的元素运算.周知,有限域 GF(q)上的 n 次不可约多项式个数为1nd|n(nd)qd,其中()为莫比乌斯函数.因此 GF(2)上的四次不可约多项式只有 3 个,分别为:y4+y+1,y4+y3+1,y4+y3+y2+y+1,陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法295Q(y)只能取上述三个不可约多项式中的一个.考虑有限域 GF(24)上的二次不可约多项式 P(x)=p2x2+p1x+p0,p2,p1,p0 GF(24).同样,由公式1nd|n(nd)qd知有限域 GF(24)上的二次不可约多项式有 120 个,下面分析 P(x)的取值对复合域上求逆运算的影响.在多项式基 1,下,复合域 GF(24)2)上的元素 a,b 表示为:a=a1 +a0,a1,a0 GF(24),b=b1 +b0,b1,b0 GF(24),则:a b=(a1 +a0)(b1 +b0)=a1 b1 2+(a1 b0+a0 b1)+a0 b0=a1 b1 p12(p1 +p0)+(a1 b0+a0 b1)+a0 b0=(a1 b1 p12 p1+a1 b0+a0 b1)+a1 b1 p12 p0+a0 b0.令 b 是 a 的逆元素,则 a,b 满足a b=1,此时有a1 b1 p12 p1+a1 b0+a0 b1=0a1 b1 p12 p0+a0 b0=1,解得b1=1 a1b0=1(a1 p12 p1+a0),其中 =a1 a0 p12 p1+a1 a1 p12 p0+a0 a0.为了简化复合域求逆运算,令 p2=p1=1,即 P(x)=x2+x+p0,此时求逆简化为:b1=1 a1b0=1(a1+a0),(1)其中 =a1 a0+a1 a1 p0+a0 a0.为了简化实现子域乘法所需的门函数,需要使得 p0的二进制比特 1 的个数尽可能少,因此 p0优先取1、2、4、8 中的一个,接着取 3、5、6、9、10、12 中的一个,由此可缩小 P(x)的可能取值范围.进一步分析简化后的求逆表达式,计算量主要集中在变量 的计算上,因此接下来进一步降低变量 的计算量.由公式(1)可知:=a1 a0+a21 p0+a20,296Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023变量 的计算中包含 2 个平方项,若能将 2 个平方项合并成 1 个平方项,可进一步提高运算效率,即=a1 a0+(c a1+a0)2,其中,c 为有限域 GF(24)上的元素.这种方式可以减少 1 次平方运算的操作.若要满足这种变换,则:=a1 a0+(c a1+a0)2=a1 a0+c2 a21+a20,需要使得 c2=p0.当 p0=1 或 p0=4 时,其对应的 c 分别为 1 或 2,形式最简单,乘法复杂度也最小,有利于提高实现时的速率,因此 p0应当从 1 或 4 中选取.当 p0=1 时,令 Q(y)分别取 y4+y+1、y4+y3+1 和 y4+y3+y2+y+1,相应地 P(x)=x2+x+1可以分解为 P(x)=(x+6)(x+7)、P(x)=(x+10)(x+11)和 P(x)=(x+12)(x+13),即 P(x)总是可约多项式,因此 p0应取 4,即 P(x)=x2+x+4.当 Q(y)取 y4+y+1 时,P(x)可以分解为 P(x)=(x+8)(x+12),即 P(x)为可约多项式,因此Q(y)只能选择 y4+y3+1 或 y4+y3+y2+y+1.为了简化子域乘法运算,选择 Q(y)=y4+y3+1.综上,最终选取的复合域为:GF(24)2),P(x)=x2+x+4,GF(24),Q(y)=y4+y3+1.(2)在此复合域上,复合域求逆表示为:b1=1 a1,b0=1(a1+a0),(3)其中 =a1 a0+(2 a1+a0)2.在此复合域上完成求逆运算后,需将结果通过同构映射矩阵逆映射回有限域 GF(28),从而实现 S 盒运算.接下来介绍同构映射矩阵的构造.3.2同构映射矩阵的优化构造方法SM4 算法的 S 盒基于有限域 GF(28)上的运算构建,使用的 GF(2)上的不可约多项式 F(z)为F(z)=z8+z7+z6+z5+z4+z2+1.令 为 F(z)的一个根,则 B1=1,2,7 构成了有限域 GF(28)上的一组基.对于任意元素 A GF(28)都可以表示为 B1 的线性组合,即 A=7i=0aii,ai GF(2).令 为 P(x)的一个根,由公式(2)可知,B2=1,构成了复合域 GF(24)2)在 GF(24)上的一组基.对于任意元素 B GF(24)2)都可表示为 B2 的线性组合,即 B=b1+b0,b1,b0 GF(24).令 为 Q(y)的一个根,则 B3=1,2,3 构成了有限域 GF(24)在 GF(2)上的一组基.对于任意元素C GF(24),都可表示为 B3 的线性组合,即 C=3i=0cii,ci GF(2).为了将有限域 GF(28)上的元素映射到复合域 GF(24)2)上,需构建基 B1 到基 B2 和 B3 之间的映射.显然,GF(28)中的元素“1”应该映射到 GF(24)2)中的元素“1”,假设元素 映射到元素 t,则 2应映射到 2t,以此类推.假设映射 T 将有限域上的元素映射到复合域,映射 T 满足下列关系:T(i)=it,i=0,1,7.陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法297为了保证映射 T 的同构映射性质,指数 t 需满足:F(t)=0.因此只需求出指数 t,便可求解出映射矩阵 T.算法1给出一种求解转换矩阵 T 的方法,该方法具有一般性,可推广为一般的 GF(2m)n)上的算法.算法 1 映射矩阵 T 算法Input:F(z),P(x),Q(y)Output:T1令 是 GF(24)2)的本原元(验证对任意的 1 i 254,i/=1),且满足 P()=0.设置 t=1,准备一个包括 255 个地址的列表,每个地址对应的存储单元初始化为二进制 1,把向量(0,0,0,1)放入 T 的最后一列;2计算 F(t).若结果为 0,则找到所需元素,跳转到第 7 步.3t2j,j 0,1,7 都不是 所映射的元素,把地址 t2j(mod255),j 0,1,7 对应的存储单元设置为 0.4设置 t=t+1.如果地址 t 对应的存储单元的值为 0,重复执行第 4 步.5计算 gcd(t,255),若 gcd(t,255)1,跳转到第 4 步.6跳转到第 2 步.7把 t,2t,7t按照二进制向量表达形式依次放入 T 的自右侧第 2 列直至最左侧一列.利用算法1求出 8 组同构映射矩阵如下:T1=109,253,212,240,143,137,94,1,T2=209,59,124,60,253,240,137,1,T3=116,87,196,91,59,60,240,1,T4=115,82,200,94,56,63,255,1,T5=199,143,110,137,82,94,63,1,T6=220,56,123,63,242,255,129,1,T7=107,242,217,255,135,129,91,1,T8=203,135,104,129,87,91,60,1.上述矩阵为十进制表示,实际映射矩阵的构建是将第 i 个元素的二进制向量表示形式依次放入矩阵自右侧的第 i 列.由于本文中的元素为行向量,因此在使用时需要对矩阵 Ti进行转置.为了从 8 组映射矩阵中选择最优映射,从 S 盒的表达式出发,选取原则是使得仿射变换尽量简单,用二进制矩阵中比特 1 的个数衡量仿射变换的复杂度,比特 1 的个数越多,仿射变换越复杂.将 S 盒变换到复合域上有如下公式:S(x)=I(x A+C)A+C=I(x A+C)T T1)A+C=I(x A T+C T)T1 A+C=I(x A1+C1)A2+C2,其中,I()表示有限域 GF(28)上的求逆运算,I()表示复合域 GF(24)2)上的求逆运算,T 表示选取的映射矩阵,A1=A T,C1=C T,A2=T1 A,C2=C.令函数 cnt(M)表示矩阵 M 中比特 1 的个数,则选取映射矩阵 T 的优化目标为:minTf=cnt(A1)+cnt(C1)+cnt(A2)+cnt(C2).298Journal of Cryptologic Research 密码学报 Vol.10,No.2,Apr.2023据此,选择映射矩阵 T7 作为最终的映射关系,即映射矩阵 T 为T=|0110101111110010110110011111111110000111100000010101101100000001|.通过映射矩阵 T,可分别计算矩阵 A1、C1、A2和 C2分别为A1=|1100000011100100010100100100101101010000100001010100111101000100|,C1=00111100,A2=|1110010001101110101101001100011011111110011110110000101011001011|,C2=11010011.4基于复合域的 SM4 软件优化实现为了提高 SM4 算法在处理多组明文数据时的加解密效率,本文采用了比特切片方法,并使用 AVX2指令集进行实现,主要包括数据编排优化、S 盒优化以及线性变换优化三部分.4.1数据编排优化实现AVX2 指令集的 YMM 寄存器长度为 256 比特,因此采用 AVX2 的比特切片能够同时并行处理最大256 个明文分组.SM4 算法的输入和输出为 128 比特,所以一个 YMM 字能够存储两个消息分组,使用128 个 YMM 字即可存储 256 个消息分组,如图2所示,其中 bij表示第 i 个消息的从最高有效位到最低有效位的第 j 个比特,0 i 256,0 j 128.为了实现比特分离,需要让 256 个消息分组的第 j 个比特存储在第 j 个 YMM 字中,即将图2中的内存分布调整为如图3所示.此时每一个消息分组的第一个比特存储在第一个 YMM 字中,第二个比特存储在第二个 YMM 字中,以此类推.编排后的数据作为待加密的消息传送给 SM4 轮函数,此时处理器相当于一个同时执行 1 比特运算的 SIMD 机器,因此每执行一条逻辑运算指令(与、或、非等运算),可同时陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法299b00b01b0126b0127b10b11b1126b1127b20b21b2126b2127b30b31b3126b3127.b2540b2541b254126b254127b2550b2551b255126b255127图 2 256 个消息分组在内存中的存储分布Figure 2 Distribution of 256 message packets in memory进行 256 组消息的逻辑运算.加密结束后需再次进行数据编排,恢复数据的正确组织形式.b00b20b2520b2540b10b30b2530b2550b01b21b2521b2541b11b31b2531b2551.b0127b2127b252127b254127b1127b3127b253127b255127图 3 基于比特切片方法的 256 个消息分组在内存中的存储分布Figure 3 Distribution of 256 message packets in memory based on bit slicing由图2可知,256 组消息存储在一个 128 256 的比特矩阵中,第 i 个消息存储在第 i/2 个 YMM字中.为了实现比特分离,当 i 为偶数时,把第 i 个消息的第 j 个比特放在第 j 个 YMM 字的第 i/2 个比特位置中;当 i 为奇数时,把第 i 个消息的第 j 个比特放在第 j 个 YMM 字的第 128+i/2 个比特位置中.算法2描述了一种 n n 比特矩阵转置方法,时间复杂度为 O(n2log2(n).算法 2 数据编排算法Input:n n 数组 AOutput:无1m0(5555555555555555)16;2m1(3333333333333333)16