基于Feistel-NFS...结构的16比特S盒设计方法_武小年.pdf
《基于Feistel-NFS...结构的16比特S盒设计方法_武小年.pdf》由会员分享,可在线阅读,更多相关《基于Feistel-NFS...结构的16比特S盒设计方法_武小年.pdf(9页珍藏版)》请在咨信网上搜索。
1、密码学报ISSN 2095-7025 CN 10-1195/TNJournal of Cryptologic Research,2022,10(1):146154密码学报编辑部版权所有.E-mail:http:/Tel/Fax:+86-10-82789618基于 Feistel-NFSR 结构的 16 比特 S 盒设计方法*武小年,豆道饶,韦永壮,张润莲,李灵琛桂林电子科技大学 广西密码学与信息安全重点实验室,桂林 540014通信作者:武小年,E-mail:摘要:为构造具有强安全性的 16 比特密码 S 盒,将 Feistel 结构和 NFSR 相结合,设计一种 4 轮的平衡二分支 Feis
2、tel-NFSR 新结构,任意选取 4 个 AES 算法 S 盒仿射等价获得的 8 比特 S 盒作为轮函数,增加结构的可变性;设计 2 个 NFSR 组件提高结构的扩散效果;并通过遍历搜索 16 比特 S 盒.基于GPU 技术实现对 16 比特 S 盒的非线性度、差分均匀度的并行计算,提高对所构造 S 盒的性质的评估效率.测试结果表明,新构造的 16 比特 S 盒满足双射性且代数次数达到最优 15,非线性度最高为 31986,差分均匀度最低为 18,信噪比最低为 146.423,具有较好的抵御数学攻击和差分能量攻击的能力.关键词:S 盒;Feistel 结构;NFSR;仿射等价;GPU中图分类
3、号:TP309.7文献标识码:ADOI:10.13868/ki.jcr.000585中文引用格式:武小年,豆道饶,韦永壮,张润莲,李灵琛.基于 Feistel-NFSR 结构的 16 比特 S 盒设计方法J.密码学报,2022,10(1):146154.DOI:10.13868/ki.jcr.000585英文引用格式:WU X N,DOU D R,WEI Y Z,ZHANG R L,LI L C.A 16-bit S-box design methodbased on Feistel-NFSR structureJ.Journal of Cryptologic Research,2022,10
4、(1):146154.DOI:10.13868/ki.jcr.000585A 16-bit S-box Design Method Based on Feistel-NFSR StructureWU Xiao-Nian,DOU Dao-Rao,WEI Yong-Zhuang,ZHANG Run-Lian,LI Ling-ChenGuangxi Key Laboratory of Cryptography and Information Security,Guilin University of ElectronicTechnology,Guilin 541004,ChinaCorrespond
5、ing author:WU Xiao-Nian,E-mail:Abstract:As an important non-linear transformation component in symmetric cryptographic algo-rithms,the security of the cryptographic S-box determines the security of the cryptographic algorithm.In order to construct a 16-bit cipher S-box with strong security,a new 4-r
6、ound balanced two-branchFeistel-NFSR structure is designed based on the Feistel structure and NFSR component.In the newstructure,four 8-bit S-boxes obtained by affine equivalence with S-boxes of the AES algorithm areselected at random as the round function,which increases the variability of the stru
7、cture.Two NFSRcomponents are designed to improve the diffusion effect of the structure.Then,16-bit S-boxes are*基金项目:部分受国家自然科学基金(62062026,61872103);广西创新研究团队项目(2019GXNSFGA245004);广西青年创新人才科研专项(桂科 AD20238082)支持Foundation:This work is supported partly by National Natural Science Foundation of China(62062
8、026,61872103);Innovation Research Team Project of Guangxi(2019GXNSFGA245004);Scientific Research Project of Young InnovativeTalents of Guangxi(guike AD20238082)收稿日期:2022-01-13定稿日期:2022-11-06武小年 等:基于 Feistel-NFSR 结构的 16 比特 S 盒设计方法147constructed by traversal search.In practical implementations,the GPU
9、 technology can be used tocompute the non-linearity and differential uniformity of 16-bit S-box in parallel to improve the effi-ciency of the evaluation for the constructed 16-bit S-boxes.The experimental results show that the16-bit S-box constructed by the proposed method satisfies bijectivity,the
10、algebraic degree is 15 whichis optimal,the highest nonlinearity is 31986,the lowest differential uniformity is 18,and the lowestsignal-to-noise ratio is 146.423,which has good resistance against mathematical attacks and differentialpower analysis.Key words:S-box;Feistel structure;NFSR;affine equival
11、ence;GPU1引言分组密码算法的设计需要遵循香农的扩散和混淆原则1,S 盒作为分组密码算法的唯一非线性部件,为密码算法提供必要的混淆性.鉴于 S 盒的重要性,目前大多数针对分组密码算法的攻击都是针对 S 盒的攻击,因此 S 盒的安全性很大程度上影响着加密算法的安全性.为有效抵抗高性能计算带来的攻击威胁,如何设计具有强安全性和更高复杂度的 S 盒是研究的重点.密码 S 盒的构造方法主要有数学构造、结构构造和基于智能算法构造等.采用数学方法构造 S 盒,常用的数学方法有代数函数2、有限域上的幂函数3、有限域上的逆映射4和乘法子群5等.近年来,4比特轻量化的 S 盒构造较多,如 2020 年,D
12、ey 等人6研究了 4 比特布尔函数的平衡性、严格雪崩准则、线性以及非线性,使用伽罗瓦域多项式生成 4 比特 S 盒,并通过密码分析和 SAC 算法分析搜索最佳 4 比特 S 盒;Kim 等人7对符合 BOGI(bad output must go to good input)设计策略的 4 比特 S 盒进行了搜索,并对 PXE(permutation-XOR-equivalence)类别的差分均匀性和线性度进行分类,提出了 20 个BOGI 适用的最佳 PXE 类别.而针对 8 比特 S 盒的设计中,Zahid 等人8于 2019 年提出使用三次多项式映射来产生一个 8 位 S 盒,经测试用
13、该方法构造的 S 盒非线性度的最大值为 108;2020 年,Chew 等人9基于线性分数变换和置换函数构造 8 比特 S 盒,并对 S 盒在应用置换前后进行对比分析,表明具有置换函数的 S 盒达到了最优.采用结构构造方法,针对 4 比特 S 盒,在 CHES 2014 会议上,Li 等人10利用 3 轮 Feistel 结构构造了具有低硬件实现的最优 S 盒;2018 年,李昂等人11使用混合运算和广义 Feistel 结构进行了构造.针对 8 比特 S 盒,2017 年,龚涛等人12利用 3 轮平衡的 Feistel 结构和 3 轮平衡的 MISTY 结构构造 8比特 S 盒;2021 年
14、,Kim 等人13使用较小的 S 盒,利用非平衡 MISTY 结构和非平衡 Bridge 结构构造了 DBN(difference branch number)和 LBN(linear branch number)至少为 3 的 8 比特 S 盒,且其能高效地实现比特切片;董新锋等人14提出一种基于 8 分支 Feistel 结构的 8 比特轻量化 S 盒设计方法,在较小的硬件实现情况下达到了差分均匀度和非线性度的最优.基于智能算法的 S 盒构造方法,针对 4 比特 S 盒,2018 年,Ghoshal 等人15通过使用重复迭代简单的元胞自动机规则构建了最优 4 比特 S 盒,在实现面积和功耗
15、方面进行了优化;2019 年,Mariot 等人16研究了 CA 定义的 S 盒的密码性质,证明了其非线性和差分均匀性的一些上界,并使用遗传编程扩展了已有的基于 CA 的 S 盒结果,对 4 比特 S 盒进行了详尽搜索和仿射等价分类;Sadhukhan 等人17提出能预测 S 盒动态功耗的具备监督的机器学习辅助自动化框架,并开发模型基于进化算法以生成性质优良和低功耗的 4 比特 S 盒;2020 年,张润莲等人18在文献 15 的基础上,采用变元分量部分固定和分别搜索的策略,提出一种 4 比特最优 S 盒的搜索方法.针对 8 比特 S 盒,2014 年,Picek 等人19基于遗传算法构造了具
16、有较低透明阶的 S 盒;2020 年,Wang 等人20将布尔函数作为 S 盒的染色体,提出一种新的遗传算法来构造具有高非线性度的双射 S 盒.随着密码分析方法的优化和计算机计算能力的提升,存在安全缺陷的 S 盒和低复杂度的 S 盒,更容易被攻击,如文献 21 采用非线性不变子攻击,对使用 4 比特 S 盒的 Midori64 算法和使用 8 比特 S 盒的SCREAM、iSCREAM 算法进行了有效攻击.为有效抵抗各种攻击,如何设计强安全性的 S 盒一直以来都是研究的重点.近年来,具有更高复杂度的 16/32/64 比特 S 盒构造被提出,相应算法也被设计.2019年,徐洪等人22在 NBC
17、 算法中,基于含有 4 个状态更新函数的 16 级 NFSR(nonlinear feedback shift148Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2022register)迭代 20 拍构造出 16 比特 S 盒,并测试了所构造 S 盒的安全性指标.同年,田甜等人23在SPRING 算法中,使用 NFSR-SR 迭代 20 轮或者 32 轮实现了 32 比特 S 盒的构造,该 S 盒在迭代到 32轮时其输入的每一比特能够充分扩散到输出的每一比特,但由于 32 位 S 盒的复杂度较高,难以测试出其非线性度和差分均匀度,仅
18、计算出 S 盒的最大差分概率为 20/231.Beierle 等人24也于同年基于 ARX结构构造了 64 比特 S 盒 Alzette,并对其安全性指标的上下界进行了分析,Alzette 迭代一次的差分性质与线性特性与 AES 相当,迭代两次则其安全性与 AES 超级 S 盒相同.为设计 16 比特 S 盒,本文将 Feistel 结构与 NFSR 组件相结合,设计一种 4 轮的 Feistel-NFSR 新结构,以 4 个 8 比特 S 盒作为轮函数,以两个新设计的 NFSR 组件进行运算,并通过遍历搜索 16 比特 S盒.为测试所构造的 16 比特 S 盒的非线性度、差分均匀度和信噪比,
19、基于 GPU 并行计算方法提高计算效率.测试结果表明,所构造的 16 比特 S 盒具有优良的密码学性质,满足双射性且代数次数达到最优 15,非线性度最高达到 31986,差分均匀度最低为 18.2基于 Feistel-NFSR 结构的 16 比特 S 盒构造16 比特密码 S 盒的输入输出位数较高,一个完整的 16 比特 S 盒实例实质上是 0 到 216 1 的一种排列组合,其复杂程度明显高于 4/8 比特 S 盒.作为对称密码算法的核心部件,一个密码学性质优良的密码 S 盒通常需要具有双射性、高非线性、低差分均匀性等代数性质.为构造密码学性质好且复杂度高的16 比特 S 盒,提出一种基于
20、Feistel 结构和 NFSR 组件相结合构造 16 比特 S 盒的方法.2.1Feistel-NFSR 结构设计Feistel 结构25由 Feistel 于 1973 年提出,具有结构简单、加解密一致且易于实现等优点,并符合香农提出的扩散和混淆原则,但 Feistel 结构扩散速度慢.作为密码学中经典的算法结构,Feistel 结构在对称密码算法设计中被广泛应用.NFSR 即非线性反馈移位寄存器,常用于序列密码算法的构造中,具有结构简单、易于实现、状态更新函数变更灵活的优势;NFSR 将当前寄存器的状态作为下一拍迭代的输入,在迭代一定拍数之后,将其当前寄存器状态作为最终的输出,以此来完成
21、数据的变换和加密;经过精心构造的 NFSR,其当前的状态序列是符合扩散和混淆原则的.将 NFSR 作为一个运算组件加入到 Feistel 结构中有利于加快整体的扩散性.基于 Feistel-NFSR 构造 16 比特密码 S 盒的结构如图1所示.图 1 Feistel-NFSR 结构Figure 1 Feistel-NFSR structure图1所示的结构是一个 4 轮的平衡二分支结构,总体上仍然是 Feistel 结构.针对 Feistel 结构,文献 10 论证了当 Feistel 结构达到 3 轮时所构造的 S 盒是安全的.尽管轮数的增加能够为整体结构提供足够的安全性26,但也会提高计
22、算的复杂度.为降低 Feistel-NFSR 结构的复杂度,设定轮数为 4 轮.武小年 等:基于 Feistel-NFSR 结构的 16 比特 S 盒设计方法149轮函数的高复杂性会增加整体结构密码分析的难度26,为提高 Feistel-NFSR 结构的安全性,并增加整个部件的可变性,以 AES 算法的密码性质优良的 8 比特 S 盒作为样本仿射等价出一批同样具有优良性质的 8 比特 S 盒,并任意选取 4 个 8 比特 S 盒作为 Feistel-NFSR 结构中的轮函数.在实际应用中,通过替换这些 8 比特 S 盒就可以方便地构造出新的 16 比特 S 盒,增加了部件的可变性,提高了应用的
23、安全性.为了能够在有限的轮数中提高总体结构的扩散效果,设计了两个相类似的 NFSR 组件参与运算,借助非线性反馈移位寄存器的状态更新函数进行移位和非线性操作.在图1中,以 L 和 R 表示左右两分支的 8 比特输入,L,R F82;L和 R表示该结构左右两个分支的 8 比特输出,L,R F82;NFSR1 和 NFSR2 为两个 8 级非线性反馈移位寄存器;表示异或运算;S0、S1、S2、S3分别表示每一轮中采用的 8 比特 S 盒.以 R1 和 R2 表示 NFSR1 和 NFSR2 运算的结果,则 Feistel-NFSR 结构的最终输出函数 SFN(L,R)如下:R1(L,R)=NFSR
24、1(S0(L)R)R2(L,R)=NFSR2(S1(R1(L,R)L)L=R1 S2(R2)R=S3(L)R2SFN(L,R)=(L|R)(1)2.2NFSR 结构设计在两个 NFSR 组件中,每个 NFSR 中有 8 个状态寄存器,以 Si(0 i 7)表示寄存器迭代前的某个比特位状态,以 Si(0 i 7)表示寄存器迭代后的比特位状态,表示异或运算,表示与运算,且两个 NFSR 组件都分别设置了 4 个状态更新函数.在 NFSR 结构中,若状态更新函数含有异或运算和与运算,则该反馈移位寄存器为非线性的;若只有异或操作,则反馈移位寄存器是线性的.为保证两个 NFSR 组件的非线性,每个 NF
25、SR 组件中都有 2 个状态更新函数包含了异或运算和与运算,使得 NFSR 组件可以每迭代一拍就会以非线性的方式完成寄存器状态的更新.两个 NFSR 结构具体如图2和图3所示.图 2 NFSR1 结构图Figure 2 NFSR1 structure图 3 NFSR2 结构图Figure 3 NFSR2 structureNFSR1 状态更新函数如公式(2).为简化设计,NFSR2 状态更新函数仅在 S5位与 NFSR1 不同,NFSR2 状态更新函数如公式(3).S1=S0 1S3=S0 S1 S2 S6S5=S4 1S7=S4 S5 S6 S7S0=S7Si=Si1,i 2,4,6(2)S
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Feistel NFS 结构 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。