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 算法中,基于含有 4 个状态更新函数的 16 级 NFSR(nonlinear feedback shift148Journal of Cryptologic Research 密码学报 Vol.10,No.1,Feb.2022register)迭代 20 拍构造出 16 比特 S 盒,并测试了所构造 S 盒的安全性指标.同年,田甜等人23在SPRING 算法中,使用 NFSR-SR 迭代 20
