一种基于复合域的国密SM4算法快速软件实现方法_陈晨.pdf
《一种基于复合域的国密SM4算法快速软件实现方法_陈晨.pdf》由会员分享,可在线阅读,更多相关《一种基于复合域的国密SM4算法快速软件实现方法_陈晨.pdf(17页珍藏版)》请在咨信网上搜索。
1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2023,10(2):289305密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618一种基于复合域的国密 SM4 算法快速软件实现方法*陈 晨1,2,郭 华1,2,王 闯3,刘源灏1,刘建伟11.北京航空航天大学 空天网络安全工业和信息化部重点实验室,北京 1001912.密码科学技术国家重点实验室,北京 1008783.国防科技大学 计算机学院,长沙 410073通信作者:郭华,E-mail:摘要:成为 ISO/IEC
2、国际标准算法后,SM4 的性能受到更多关注.目前针对 SM4 算法实现效率提升的方法主要集中在缩短 S 盒的运算时间,其中采用复合域实现的方法大都基于 AES 算法实现的复合域,而在 GF(24)2)上鲜有针对 SM4 算法软件实现的复合域被提出.本文首次在 GF(24)2)上找到了一个针对 SM4 算法 S 盒软件实现的复合域,给出一种基于复合域的 SM4 算法快速软件实现方法,使用穷举搜索和数学分析优化了算法 S 盒的复合域数学构造,构建了同构映射矩阵及其最小化目标函数,仅使用 175个门函数就完成了 S 盒运算,平均每个输出比特占用 22 个门函数.基于比特切片技术,利用扩展指令集AVX
3、2 实现了 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:
4、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 Chu
5、ang3,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,Chang
6、sha 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 Chi
7、na(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
8、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 constructio
9、n 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,t
10、he 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 improveme
11、nt 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 exten
12、d instructions1引言SM4 算法1是我国自主研发的无线局域网标准的分组密码算法,于 2012 年 3 月成为中国密码行业标准,2016 年 8 月转化为中国国家标准,已为众多信息系统提供了安全、完整的数据加密服务.2021 年 6月 SM4 算法正式成为 ISO/IEC 国际标准,不仅进一步增强了我国商用密码产业的国际竞争力,并且让学者们更加关注 SM4 算法高性能实现的研究.2000 年,Rijmen2提出使用子域 GF(24)上的运算完成有限域 GF(28)上的求逆运算方法,将 8 比特元素的计算问题转换为若干个 4 比特元素的计算,从而降低实现 S 盒的代数复杂度,这种方法
13、被用于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 算法的硬件优化,在选择复合域时更多地考虑了相关性能量攻击和差分
14、能量攻击,并在 Matlab 上进行了仿真验证.Chantarawon 等7则指出,基域的选择并非越小越好,不同的基域表示有各自的工程适应性.比特切片方法于 1997 年由 Biham8首次提出,其核心思想是将处理器视为以 1 比特为单位的处理器,该方法被用于 DES9算法的快速软件实现,在 64 位平台实现了 64 组 DES 消息的并行加解密.此后,比特切片方法被广泛用于分组密码算法的软件设计中.2006 年,Rebeiro 等10基于 Satoh 等11的研究成果,设计出了 AES 算法的比特切片实现,大幅提升了 AES 算法的软件实现性能.2018 年,Zhang等12采用比特切片技术
15、,使用普通指令集完成切片操作,将算术运算等价转换为逻辑运算,给出了一种SM4 算法在复合域 GF(22)2)2)中的软件实现优化方法,其复合域直接采用了 Canright 等13针对AES 硬件实现选择的复合域,最终实现了 64 组消息的并行加解密,其加解密效率相比普通实现方法提升了 80%120%.2020 年,张笑从等14同样采用比特切片技术,通过构造选择函数和改进搜索算法的方式,化简了 S 盒的逻辑表达式,显著降低了实现 S 盒逻辑表达式所需的逻辑门电路数量.除了上述软件优化实现方法外,还有许多其它方式能够提高分组密码算法的实现性能.郎欢等15于2018 年通过分析 SM4 算法的轮函数
16、,将 S 盒查表与线性变换函数结合,使用粒度为 32 位的切片技术,给出了两种查表优化实现方法,并用 AVX2 指令集给出了高效软件实现.Hajihassani 等16于 2019 年提出了一种利用多核特性并行处理 AES 加密的切片方法,并使用 CUDA 编程的方式在 GPU 上给出了 AES的 CTR 模式和 ECB 模式的实现.Alkim 等17在 2020 年设计并评估了一套 RISC-V 扩展指令集,提高了有限域运算的性能,这些指令同样有助于 AES 等密码算法的快速实现.Saarinen 等18则更进一步,陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法291直接设计了
17、一种提高 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 个门函数.
18、其实现方法基于 AVX-512 指令集,采用塔域优化 S 盒的方法给出了 SM4 加解密算法的并行化实现方法,在 Inteli7-1160G7 平台 ECB 工作模式下加密性能达到了 6542 Mbps.这些方法启发了 SM4 算法软件实现的优化思路.通过上述研究成果可以发现,SM4 的快速实现方法大都在于缩短 S 盒的运算时间,而目前基于复合域的 S 盒优化方法存在如下问题:(1)目前公开文献中采用复合域方式实现 SM4 算法 S 盒的方法,其复合域大都直接使用了 Canright等13针对 AES 算法构造的复合域,复合域构造在 GF(22)2)2)上且未作任何针对 SM4 算法的优化,对
19、 SM4 算法 S 盒实现性能提升有限;(2)目前针对 AES 算法的复合域构造方法仅采用简单的穷举搜索方法,且由于考虑了硬件电路规模而没有找到计算效率最优的复合域.针对上述问题,本文提出了一种基于复合域优化选取和比特切片并行化技术相结合的 SM4 算法快速软件实现方法,首次找到了一个针对 SM4 算法 S 盒软件实现的复合域,将加密每字节所需的时钟周期降低到了 6.5 个时钟周期,大幅提升了 SM4 算法的软件实现效率.本文的主要贡献包括:基于 GF(24)求逆运算实现了有限域 GF(28)上的 S 盒高效求逆算法.本文从数学角度给出了一种较优的复合域表示,给出了有限域 GF(28)和复合域
20、 GF(24)2)之间的同构映射矩阵的构造算法,并最小化相应的最优化目标函数,从而降低了有限域 GF(28)上的求逆运算的复杂度,仅使用 175 个门函数完成了 S 盒运算,平均每个输出比特只占用了 175/8 22 个门函数.基于找到的复合域,采用比特切片方法和 AVX2 指令集对 SM4算法进行了实现,通过调整计算过程中使用的汇编指令,使用了较少时钟周期就完成了 SM4 的加解密运算,加密每字节只需要 6.5 个时钟周期.本文的组织结构如下:第2节介绍 SM4 快速软件实现方法的相关知识;第3节详细介绍对于 SM4 算法的 S 盒如何选取较优的复合域表示形式进而减少计算开销;第4节对所提基
21、于复合域的 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,
22、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 变换包含了一个线性变换
23、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=(MK
24、0,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比特切片方法比特切片方法是一种分组密码软件高效实现的有效方法,其主要思路是在每个寄存器中存入多组比特粒度的数据切片,通过同时操作多个寄存器实现多组明文数据的并行化加解密.该方法通常包括数据重排、算法实现和数据逆重排三个步骤.明文
25、数据由左至右,正常存储在内存中的明文数据经过数据重排改变了存储方式,再通过计算机指令实现算法的加密过程,最后经过数据逆重排恢复为原本的存储方式,详细过程如下:陈晨 等:一种基于复合域的国密 SM4 算法快速软件实现方法293(1)数据重排比特切片要求处理器以比特为粒度对数据进行操作.数据重排通过改变数据的存储方式,将数据组织形式由“串行”变为“并行”,使得所有并行分组的同一位集中在一个字中.(2)算法实现比特之间的操作包括基本与、或、非等运算,因此需要对分组密码算法进行逻辑运算,即将整数之间的加、减、乘、除运算表示为比特之间的与、或、非等基本运算.算法实现将查表操作等价转换为布尔函数,从而使用
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 基于 复合 SM4 算法 快速 软件 实现 方法 陈晨
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。