基于L-M-NFSR结构的16比特S盒设计方法.pdf
《基于L-M-NFSR结构的16比特S盒设计方法.pdf》由会员分享,可在线阅读,更多相关《基于L-M-NFSR结构的16比特S盒设计方法.pdf(8页珍藏版)》请在咨信网上搜索。
1、计算机科学与探索Journal of Frontiers of Computer Science and Technology1673-9418/2023/17(10)-2511-08doi:10.3778/j.issn.1673-9418.2207012基于L-M-NFSR结构的16比特S盒设计方法武小年+,舒瑞,豆道饶,张润莲,韦永壮桂林电子科技大学 广西密码学与信息安全重点实验室,广西 桂林 541004+通信作者 E-mail:摘要:S盒是分组密码算法的重要部件,为密码算法提供非线性变换,S盒的安全强度在一定程度上决定着密码算法的安全强度。为构造具有优良密码学性质的16比特S盒,设计一
2、种以Lai-Massey结构和非线性反馈移位寄存器(NFSR)组件相结合的L-M-NFSR新结构。该结构以与高级加密标准(AES)算法S盒仿射等价的8比特S盒作为新结构的轮函数,减少设计的复杂性并提高结构的可变性;左右分支各增加一个迭代少量拍数即可符合严格雪崩特性的NFSR组件用于提高结构的扩散性;通过3轮迭代和遍历生成16比特S盒。进一步地,基于该结构,以AES算法S盒仿射等价新生成的8比特S盒替换轮函数中的8比特S盒,可方便地生成大量新的16比特密码 S 盒。为提高对所构造 16比特 S 盒性质的评估效率,采用图形处理器(GPU)进行并行计算,测试结果表明,所生成的 16比特 S盒具有较优
3、的密码学性质,均满足双射性,代数次数为 15,非线性度最优为31 992,差分均匀度最低为18,信噪比最低为146.712,具有较好地抵御数学攻击和差分功耗分析的安全性。关键词:S盒;Lai-Massey结构;非线性反馈移位寄存器(NFSR);差分均匀度文献标志码:A中图分类号:TP30916-bit S-box Design Method Based on L-M-NFSR StructureWU Xiaonian+,SHU Rui,DOU Daorao,ZHANG Runlian,WEI YongzhuangGuangxi Key Laboratory of Cryptography an
4、d Information Security,Guilin University of Electronic Technology,Guilin,Guangxi 541004,ChinaAbstract:S-box is an important component for non-linear transformation in symmetric cryptographic algorithm,and the security of S-box determines the security of the cryptographic algorithm.In order to constr
5、uct 16-bit S-boxwith strong security,a new L-M-NFSR structure is designed based on the Lai-Massey structure and nonlinearfeedback shift register(NFSR)component.In the new structure,8-bit S-boxes with advanced encryption standard(AES)algorithm S-box affine equivalence are selected as the round functi
6、on to reduce the complexity of designingand increase the variability of the structure.Two designed NFSR components that can conform to strict avalancheproperties with a small number of iterations are placed into two branches of the structure to improve the diffusioneffect of the structure.Then,16-bi
7、t S-boxes are constructed by 3-round iteration and traversal search.Furthermore,based on this structure,a large number of new 16-bit S-boxes can be generated by replacing 8-bit S-boxes in theround function with 8-bit S-boxes which are affine equivalent to the AES algorithm S-box.To improve the effic
8、i-基金项目:国家自然科学基金(62062026,61872103);广西创新研究团队项目(2019GXNSFGA245004);广西自然科学基金(2019GXNSFFA245015);研究生创新计划项目(2022YCXS082)。This work was supported by the National Natural Science Foundation of China(62062026,61872103),the Innovation Research TeamProject of Guangxi(2019GXNSFGA245004),the Natural Science Fou
9、ndation of Guangxi(2019GXNSFFA245015),and the GraduateInnovation Plan Fund(2022YCXS082).收稿日期:2022-07-05修回日期:2022-10-21Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(10)S盒是分组密码算法的重要组成部件,为密码算法提供非线性变换,增加必要的混淆特性。S盒最早出现在 Lucifer算法中,随后被广泛推广使用。在目前针对分组密码算法的攻击中,大多攻击都是针对其S盒的攻击。研究并设计强安全
10、的S盒,有效抵抗各种攻击威胁,以增强分组密码算法的安全性是密码算法设计研究的关键。多年来,在对 S 盒的研究中,逐步形成了构造 S盒的一些主要方法,包括数学方法构造、利用密码结构构造和基于计算智能算法构造等。在理论研究和实际应用中,基于上述方法,研究者们已经构造了各种强密码学性质的S盒,包括4/5/6/8/16/32/64比特的S 盒。目前,针对 4/8比特 S 盒的研究工作较多。早在 2007年,Leander等1提出最优 S盒的概念,对 S盒的性质进行分析总结。2011年,Saarinen展示了所有4比特S盒的置换等价类2;Ullrich等3将便于硬件实现的 4比特 S盒划分为 302个仿
11、射等价类。2015年,Canteaut 等4利用 Feistel 和 MISTY 结构设计 S 盒;Cheng等5提出一种 4比特双射 S盒的置换等价类改进搜索算法,性能较2011年Saarinen等提出的算法大大提升。2016 年,Perrin 等6基于蝴蝶结构设计 S盒。2017年,Kapuciski等7将多目标遗传算法用于S盒。2018年,Ghoshal等8通过使用重复迭代简单的元胞自动机规则构建最优4比特S盒,并优化其实现面积和功耗成本。2019年,Mishra等9以监督机器学习的辅助自动化框架解决 S 盒设计与分析问题;Zahid等10提出使用三次多项式映射生成8比特S盒,其构造的S
12、盒非线性度的最大值为108。2020年,张润莲等11在文献8的基础上,采用变元分量部分固定和分别搜索的策略,提出搜索 4比特 S盒的新方法;黄俊君等12提出基于元胞自动机(cellular automata,CA)设计的S盒的镜面对称性、互补性以及移位不变性三个性质并进行证明,进一步提出一种权重阈值搜索算法实现对4元布尔函数的有效搜索;Wang等13将n比特 S盒的构造看作将n个布尔函数放入容器的过程,其将布尔函数作为组成 S盒的染色体,提出一种新的遗传算法,以 S盒的非线性为优化目标,以双射性为优化约束,并以此设计遗传算法的交叉和变异算子,构造高非线性度的双射 S 盒。2021 年,Kim等
13、14使用较小的S盒,利用非平衡MISTY结构和非平衡Bridge结构构造了差分分支数(difference branchnumber,DBA)和线性分支数(linear branch number,LBN)至少为3的8比特S盒,且其能高效地实现比特切片。相对于4/8比特S盒,16/32/64比特S盒的输入输出位数较高,如一个完整的 16比特 S盒实例实质上是 0到 216-1的排列组合,其复杂程度明显提高。在保证S盒优良密码学性质基础上,这类高比特S盒的复杂度大大提升,其抵抗攻击的能力也会相应增强,但目前这类 S 盒的研究工作并不太多。2011 年,Piccolo 算 法15采 用 了 SPS
14、(substitution permutationsubstitution)结构利用4个并置的轻量级4比特S盒与MDS(maximum distance separable)矩阵组合充当 16比特S盒;类似的,在2019年的美国国家标准与技术研究院(National Institute of Standards and Technology,NIST)第二轮算法Saturnin16中,同样使用4个4比特置换S盒基于SPS结构充当16比特S盒。2019年,徐洪等17在NBC算法中,基于含有4个状态更新函数的16 级 非 线 性 反 馈 移 位 寄 存 器(nonlinear feedbacksh
15、ift register,NFSR)迭代20拍构造出16比特S盒;田甜等18在 SPRING 算法中,使用 NFSR-SR 迭代 20 轮或者 32轮实现对 32比特 S盒的构造,但由于 S盒的复杂度较高,仅计算出S盒的最大差分概率为20/231。2020年,Beierle等19基于 And、Rotation、XOR操作通过8轮迭代设计一个构造64比特S盒的Alzette结构,并对其安全性指标的上下界进行了分析,其迭代一次的差分性质与线性特性与 AES(advanced encryp-tion standard)相当,迭代两次其安全性与 AES超级 S盒相同。本文将Lai-Massey结构与N
16、FSR组件相结合,设ency of the evaluation of the properties of the constructed 16-bit S-boxes,parallel computation is performed usinggraphics processing unit(GPU).The test results show that the newly constructed 16-bit S-boxes have good crypto-graphic properties,which satisfy bijectivity with optimal algebra
17、ic number 15,the highest nonlinearity 31992,thelowest differential uniformity 18,and minimum signal-to-noise ratio 146.712,with excellent security againstmathematical attacks and differential power analysis.Key words:S-box;Lai-Massey structure;nonlinear feedback shift register(NFSR);differential uni
18、formity2512武小年 等:基于L-M-NFSR结构的16比特S盒设计方法计一个三轮迭代的 L-M-NFSR 结构,构造 16 比特 S盒。在L-M-NFSR结构中,在左右分支各增加一个迭代少量拍数即可符合严格雪崩特性的 NFSR组件用于提高结构的扩散性,以具有优良密码学性质的AES算法8比特S盒通过仿射等价构造一个样本集,并从中选择 3个 8比特 S盒作为轮函数,最后通过遍历搜索生成16比特S盒,并采用图形处理器(graphicsprocessing unit,GPU)进行并行计算,评估所生成S盒的差分均匀度、非线性度、信噪比、代数次数等密码性质。测试结果表明基于 L-M-NFSR结构
19、可以生成性质优良的16比特S盒。1基于L-M-NFSR结构的16比特S盒构造16比特密码S盒的输入输出位数较高,一个完整的16比特S盒实例实质上是0到216-1的一种排列组合,复杂度明显高于 4/8比特 S盒。由于 16比特 S盒的分量布尔函数的多项式复杂,使用数学方法或智能算法构造较困难,本文将以 Lai-Massey 结构和NFSR组件相结合构造16比特S盒。1.1L-M-NFSR结构的设计Lai-Massey密码结构也称为L-M结构,是典型的迭代分组密码结构,该结构源自 IDEA(internationaldata encryption algorithm)算法,随后由Vaudenay2
20、0在1999年从IDEA算法中抽象出Lai-Massey模型,该结构架构简洁,在软件实现多拍迭代时较为容易。利用 Lai-Massey 设计加密算法时,轮函数的设计是关键,简单的轮函数抵御各种攻击的能力较差,而复杂的轮函数往往构造困难并增加实现的复杂性。本方案中,拟采用具有优良密码性质的AES算法8比特S盒仿射等价构造的8比特S盒作为轮函数。为了提高Lai-Massey结构的扩散性和混淆性,在结构的左右分支中添加NFSR组件参与运算。NFSR常被用于流密码中作为密钥产生器,具有结构简单、易于实现、状态函数更新灵活的优势。添加的NFSR组件都能够在迭代多拍之后达到严格雪崩特性,为新结构搜索16比
21、特S盒提供更好的扩散性支持。新的L-M-NFSR结构如图1所示。L-M-NFSR结构是一个平衡的二分支结构,迭代轮数为 3轮。针对 Lai-Massey结构的安全性的研究较多,其安全性的高低取决于轮函数的设计是否性质优良,如Vaudenay曾证明出当函数为伪随机函数,并满足双射变换是-的近乎正型函数时,此时 3轮的 Lai-Massey结构是安全的,当达到 4轮时,该结构甚至在选择密文分析的情况下仍然是安全的20;2010年,Luo等21证明出该结构在 3轮时就已经达到伪随机特性,在4轮时可以达到超伪随机特性。轮数的增加会提高整体结构的安全性,但此时整体结构的算法实现也会变得更加复杂。因此,L
22、-M-NFSR结构的迭代轮数被设定为3轮。轮函数采用8比特S盒替代,在此以密码性质优良的 AES算法的 8比特 S盒作为样本通过仿射等价构造出一批具有同样优良性质的 8 比特 S 盒样本集。样本集中的8比特S盒都具有双射性,非线性度为 112,差分均匀度为 4,代数次数为 7。这些 S盒作为轮函数,可以为 16比特 S盒的构造提供良好的非线性以及差分均匀性支持。同时,通过替换这些被选择作为轮函数的8比特S盒,可以方便地构造出新的 16 比特 S 盒,增加了部件的可变性,结构变换灵活,在实际应用中也更加安全。在图1中,以L和R表示左右两分支的8比特输入,L,R F82;L和R表示该结构左右两个分
23、支的8比特输出,L,R F82;NFSR1和NFSR2为设计的两个8 级非线性反馈移位寄存器;表示异或运算;S0、S1、S2分别表示每一轮中采用的 8 比特 S 盒。NFSR1和 NFSR2在结构第一轮中的计算结果分别以A1和B1表示,在结构第二轮计算中的结果分别以A2和B2表示,|表示连接符号,即结构左右两个分支的输出比特串首位相接,则L-M-NFSR结构的输出函数图1L-M-NFSR结构图Fig.1L-M-NFSR structure diagram2513Journal of Frontiers of Computer Science and Technology计算机科学与探索2023
24、,17(10)SLMN(L,R)如式(1):A1=NFSR1(S0(LR)L)B1=NFSR2(S0(LR)R)A2=NFSR1(S1(A1B1)A1)B2=NFSR2(S1(A1B1)B1)L=NFSR1(S2(A2B2)A2)R=NFSR2(S2(A2B2)B2)SLMN(L,R)=(L|R)(1)1.2NFSR结构设计NFSR由异或运算和与运算构成,一个n级NFSR概念图如图2所示。图 2中,一个 NFSR由n个状态寄存器和一个状态反馈函数组成,每经过一个移位脉冲信号,寄存器中的所有位向右移动,最右边那一位移出,而反馈函数f的结果反馈到寄存器最左边的存储单元中,按此过程循环。其中,寄存器
25、状态xi的取值为 0 或者1,其随着寄存器每一轮的计算不断更新。在NFSR结构中,若状态更新函数含有异或运算和与运算,则该反馈移位寄存器是非线性的;若只有异或操作,则反馈移位寄存器是线性的。为保证图1中NFSR组件的非线性,设计时定义状态更新函数包含与运算。为获得迭代少量拍数即可达到严格雪崩特性的 NFSR组件,尝试在每一轮的迭代前,先取其中两个位置进行与操作,然后判断其非线性性质,这确保设计的 NFSR 组件中都有 2 个状态更新函数包含了异或运算和与运算,从而使得 NFSR 组件可以每迭代一拍就会以非线性的方式完成寄存器状态的更新。具体地,为构造图 1 中的两个 NFSR 组件,设置每个N
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 NFSR 结构 16 比特 设计 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。