基于L-M-NFSR结构的16比特S盒设计方法

武小年，舒 瑞，豆道饶，张润莲，韦永壮

桂林电子科技大学 广西密码学与信息安全重点实验室，广西 桂林 541004

S盒是分组密码算法的重要组成部件，为密码算法提供非线性变换，增加必要的混淆特性。S盒最早出现在Lucifer 算法中，随后被广泛推广使用。在目前针对分组密码算法的攻击中，大多攻击都是针对其S盒的攻击。研究并设计强安全的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 个仿射等价类。2015 年，Canteaut 等[4]利用Feistel 和MISTY 结构设计S 盒；Cheng 等[5]提出一种4 比特双射S 盒的置换等价类改进搜索算法，性能较2011年Saarinen等提出的算法大大提升。2016 年，Perrin 等[6]基于蝴蝶结构设计S盒。2017年，Kapuściński等[7]将多目标遗传算法用于S盒。2018年，Ghoshal等[8]通过使用重复迭代简单的元胞自动机规则构建最优4比特S盒，并优化其实现面积和功耗成本。2019年，Mishra等[9]以监督机器学习的辅助自动化框架解决S 盒设计与分析问题；Zahid等[10]提出使用三次多项式映射生成8比特S盒，其构造的S盒非线性度的最大值为108。2020年，张润莲等[11]在文献[8]的基础上，采用变元分量部分固定和分别搜索的策略，提出搜索4 比特S 盒的新方法；黄俊君等[12]提出基于元胞自动机（cellular automata，CA）设计的S盒的镜面对称性、互补性以及移位不变性三个性质并进行证明，进一步提出一种权重阈值搜索算法实现对4元布尔函数的有效搜索；Wang等[13]将n比特S 盒的构造看作将n个布尔函数放入容器的过程，其将布尔函数作为组成S 盒的染色体，提出一种新的遗传算法，以S 盒的非线性为优化目标，以双射性为优化约束，并以此设计遗传算法的交叉和变异算子，构造高非线性度的双射S 盒。2021 年，Kim等[14]使用较小的S盒，利用非平衡MISTY结构和非平衡Bridge结构构造了差分分支数（difference branch number，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（substitution permutation substitution）结构利用4个并置的轻量级4比特S盒与MDS（maximum distance separable）矩阵组合充当16比特S盒；类似的，在2019年的美国国家标准与技术研究院（National Institute of Standards and Technology，NIST）第二轮算法Saturnin[16]中，同样使用4个4比特置换S盒基于SPS结构充当16比特S盒。2019年，徐洪等[17]在NBC算法中，基于含有4个状态更新函数的16 级非线性反馈移位寄存器（nonlinear feedback shift 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 encryption standard）相当，迭代两次其安全性与AES 超级S盒相同。

本文将Lai-Massey结构与NFSR组件相结合，设计一个三轮迭代的L-M-NFSR 结构，构造16 比特S盒。在L-M-NFSR结构中，在左右分支各增加一个迭代少量拍数即可符合严格雪崩特性的NFSR 组件用于提高结构的扩散性，以具有优良密码学性质的AES算法8比特S盒通过仿射等价构造一个样本集，并从中选择3 个8 比特S 盒作为轮函数，最后通过遍历搜索生成16比特S盒，并采用图形处理器（graphics processing unit，GPU）进行并行计算，评估所生成S盒的差分均匀度、非线性度、信噪比、代数次数等密码性质。测试结果表明基于L-M-NFSR 结构可以生成性质优良的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.1 L-M-NFSR结构的设计

Lai-Massey密码结构也称为L-M结构，是典型的迭代分组密码结构，该结构源自IDEA（international data encryption algorithm）算法，随后由Vaudenay[20]在1999年从IDEA算法中抽象出Lai-Massey模型，该结构架构简洁，在软件实现多拍迭代时较为容易。利用Lai-Massey 设计加密算法时，轮函数的设计是关键，简单的轮函数抵御各种攻击的能力较差，而复杂的轮函数往往构造困难并增加实现的复杂性。本方案中，拟采用具有优良密码性质的AES算法8比特S盒仿射等价构造的8比特S盒作为轮函数。

为了提高Lai-Massey结构的扩散性和混淆性，在结构的左右分支中添加NFSR组件参与运算。NFSR常被用于流密码中作为密钥产生器，具有结构简单、易于实现、状态函数更新灵活的优势。添加的NFSR组件都能够在迭代多拍之后达到严格雪崩特性，为新结构搜索16比特S盒提供更好的扩散性支持。新的L-M-NFSR结构如图1所示。

图1 L-M-NFSR结构图Fig.1 L-M-NFSR structure diagram

L-M-NFSR结构是一个平衡的二分支结构，迭代轮数为3 轮。针对Lai-Massey 结构的安全性的研究较多，其安全性的高低取决于轮函数的设计是否性质优良，如Vaudenay曾证明出当函数为伪随机函数，并满足双射变换σ是α-的近乎正型函数时，此时3轮的Lai-Massey 结构是安全的，当达到4 轮时，该结构甚至在选择密文分析的情况下仍然是安全的[20]；2010 年，Luo 等[21]证明出该结构在3 轮时就已经达到伪随机特性，在4轮时可以达到超伪随机特性。轮数的增加会提高整体结构的安全性，但此时整体结构的算法实现也会变得更加复杂。因此，L-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∈；L′和R′表示该结构左右两个分支的8比特输出，L′,R′∈；NFSR1和NFSR2为设计的两个8 级非线性反馈移位寄存器；⊕表示异或运算；S0、S1、S2分别表示每一轮中采用的8 比特S 盒。NFSR1和NFSR2在结构第一轮中的计算结果分别以A1和B1表示，在结构第二轮计算中的结果分别以A2和B2表示，||表示连接符号，即结构左右两个分支的输出比特串首位相接，则L-M-NFSR结构的输出函数SLMN(L,R)如式（1）：

1.2 NFSR结构设计

NFSR由异或运算和与运算构成，一个n级NFSR概念图如图2所示。

图2 NFSR概念图Fig.2 NFSR concept diagram

图2 中，一个NFSR 由n个状态寄存器和一个状态反馈函数组成，每经过一个移位脉冲信号，寄存器中的所有位向右移动，最右边那一位移出，而反馈函数f的结果反馈到寄存器最左边的存储单元中，按此过程循环。其中，寄存器状态xi的取值为0 或者1，其随着寄存器每一轮的计算不断更新。

在NFSR结构中，若状态更新函数含有异或运算和与运算，则该反馈移位寄存器是非线性的；若只有异或操作，则反馈移位寄存器是线性的。为保证图1中NFSR组件的非线性，设计时定义状态更新函数包含与运算。为获得迭代少量拍数即可达到严格雪崩特性的NFSR 组件，尝试在每一轮的迭代前，先取其中两个位置进行与操作，然后判断其非线性性质，这确保设计的NFSR 组件中都有2 个状态更新函数包含了异或运算和与运算，从而使得NFSR 组件可以每迭代一拍就会以非线性的方式完成寄存器状态的更新。

具体地，为构造图1 中的两个NFSR 组件，设置每个NFSR组件有8个状态寄存器，以表示寄存器迭代前的某个比特位状态，以表示寄存器迭代后的比特位状态；⊕表示异或运算，⊗表示与运算。通过多次测试，确定了两个符合要求的NFSR 组件，每个NFSR 组件设置了4 个状态更新函数，其更新位置分别为，其结构如图3所示。

图3 NFSR1结构图Fig.3 NFSR1 structure diagram

NFSR1状态更新函数如式（2）：

为简化NFSR2的设计，对NFSR1的两个位置的状态更新函数进行更改，NFSR2的具体结构如图4所示。

图4 NFSR2结构图Fig.4 NFSR2 structure diagram

NFSR2状态更新函数如式（3）：

在迭代至10拍时，NFSR1符合严格雪崩准则，雪崩效应程度能够达到n/2，即4；迭代至23 拍时，NFSR2也符合严格雪崩准则。

1.3 16比特S盒搜索过程

在L-M-NFSR结构中，使用了3个8比特S盒、两个NFSR 组件，再通过遍历左右两个分支输入数据，构造出16 比特S 盒。针对基于L-M-NFSR 结构搜索16比特S盒的搜索过程如算法1所示。

算法1基于L-M-NFSR结构生成S盒流程

输入：基于AES 算法S 盒仿射等价构造的8 比特S 盒样本集SBox8，Sbox8 中S盒的个数n。

输出：生成的16比特S盒txt文件。

基于L-M-NFSR 结构生成的16 比特S 盒的数量取决于所构造8比特S盒样本集的大小，假设8比特S盒样本集的大小为n，则基于该方法可搜索出n3个16比特S盒。

2 测试结果及分析

2.1 测试环境

在计算机处理器为Intel®CoreTMi5-4210U，主频1.70 GHz，RAM为8 GB，操作系统为64位Windows 10专业版环境下，先采用Java语言实现对AES算法S盒的仿射等价，产生一批8比特S盒样本集；再采用Java实现基于L-M-NFSR结构的16比特S盒搜索算法，生成一批16比特S盒。

为评估S 盒的密码学性质，测试所生成的16 比特S 盒是否满足双射性，并测试其差分均匀度、非线性度、信噪比、代数次数。由于计算16比特S盒的非线性度、差分均匀度等性质的复杂度较高，采用常用CPU 计算方式耗时较长，在此采用GPU 技术进行并行计算，大大缩短各个性质的计算时间，提高测试效率。

2.2 S盒性质测试及分析

在S盒构造中，8比特S盒样本集共放置了7个性质优良的8 比特S 盒，最终生成了343 个16 比特S盒。尽管采用GPU 技术提高了测试效率，但其密码学性质计算仍然耗时较长，如一个16 比特S 盒的非线性度计算还需要3天。在此只选取前256个S盒进行测试，测试结果表明这些S 盒都满足双射性，其他性质的测试结果如表1所示。

表1 16比特S盒性质测试的上下限Table 1 Upper and lower limits of 16-bit S-box

差分攻击在密码算法攻击中具有极强的威胁性，而防御差分攻击的能力与密码算法使用的S盒息息相关。差分均匀度是评估S 盒能否抵御差分攻击的一个重要指标，S 盒的差分分布越均匀，差分均匀度越小，其抵抗差分攻击的可能性就越高。256 个S盒的差分均匀度最大为22，最小为18，差分均匀度散点图如图5所示。

图5 S盒的差分均匀度散点图Fig.5 S-box differential uniformity scatterplot

非线性度用于检验S 盒抵抗线性攻击的能力，S盒的非线性度越高，或者线性度越小，则有效抵御线性攻击的能力越强。256个S盒的非线性度值最高为31 992，所有S盒的非线性度散点图如图6所示。

图6 S盒的非线性度散点图Fig.6 S-box nonlinearity scatterplot

侧信道攻击通过采集密码算法运行过程中泄漏的侧信息进行分析，从物理层面实现对密码算法的攻击，常用方法有差分功耗分析（differential power analysis，DPA）、相关功耗分析（correlation power analysis，CPA）等。信噪比（signal-to-noise ratio，SNR）在2004 年CARDIS 会议上由Guilley 等[22]提出，是根据传统密码分析框架对信息泄露进行完整建模，获取密钥猜测值的汉明重量的自相关值，其具体定义如下：对于n比特的S盒函数S是的映射布尔函数，其信噪比为：

其中，fiw(a)表示构成S 盒的分量布尔函数fi(x)的Walsh 谱变换，i=0,1,…,n-1。信噪比模型和定义表明，非线性S盒的噪声对密码算法的DPA信号起着决定性作用，S 盒的信噪比越低，其抵抗DPA 攻击的能力越强。对所生成的256 个S 盒的信噪比计算发现，其大多低于148，散点图如图7所示。

图7 S盒的信噪比散点图Fig.7 S-box signal-to-noise ratio scatterplot

代数次数是评估S盒抵抗插值攻击、立方攻击等代数攻击的评估指标，这256个16比特S盒的代数次数均达到最优15。

2.3 NFSR对L-M-NFSR结构的影响分析

NFSR 组件的加入，增加了L-M-NFSR 结构实现的成本开销，但其优化了所生成S 盒的密码学性质。为评估其对S盒性质的影响，去掉L-M-NFSR结构中的NFSR组件，其结构如图8所示。

图8 去掉NFSR组件的L-M-NFSR结构图Fig.8 L-M-NFSR structure diagram without NFSR components

基于图8，按照上述搜索方法生成16 比特S 盒，并测试其差分均匀度，这些S盒的差分均匀度散点图如图9所示。

图9 去掉NFSR后生成的S盒的差分均匀度散点图Fig.9 Scatterplot of differential uniformity of S-boxes without NFSR components

由图9 可看出，在去掉NFSR 组件后，所生成16比特S 盒的差分均匀度非常高，其差分特性很差，不能抵抗差分攻击。图5结果表明，在加入了两个符合严格雪崩准则的NFSR组件之后，其差分均匀度得到极大优化，最高仅为22。

2.4 S盒性质对比分析

目前16 比特S 盒的构造方法，主要有Piccolo 和Saturnin 算法中使用的SPS 结构16 比特S 盒，以及NBC算法中使用16级NFSR构造16比特S盒。NBC算法入选全国密码算法设计竞赛分组算法第二轮，该算法在抵抗线性、差分、积分分析等方面具有较高的安全性，其在测试中给出了S 盒的线性度、差分均匀度以及代数次数等性质的具体结果。基于上述同样的实验环境，测试了Piccolo、Saturnin 和NBC 算法S 盒的相关性质，并与本文方法构造的3 个S 盒SLMN1、SLMN2 和SLMN3 的测试结果列举如表2所示。

表2 不同方法构造的S盒性质测试结果Table 2 Properties results of S-box constructed by different methods

由表2 可知，Piccolo 和Saturnin 算法中的S 盒代数次数仅为9，其他性质也都较弱。NBC算法S盒和本文构造的16 比特S 盒的代数次数都达到最优15，其他相关性质都明显增强。Piccolo 和Saturnin 算法中的S 盒都是采用4 比特S 盒基于SPS 结构与MDS矩阵组合充当16 比特S 盒，其硬件实现成本较高。NBC 算法S 盒采用NFSR 构造，其实现比较简单，硬件成本较低。本文基于L-M-NFSR结构所构造的16比特S 盒，其密码学性质稍优于NBC 算法S 盒，但在S 盒的具体实现中，由于采用了8 比特S 盒提供混淆特性，其硬件实现成本高于NBC 算法S 盒。尽管NBC 算法S 盒实现的硬件成本较低，但其需要迭代20 轮才能达到最优的密码学性质，而本文方法只需迭代1 轮，实现速度更快。此外，本文方法的可变性强，通过更换8比特S盒可以快速构造出许多新的性质较优的16比特S盒。

3 结束语

本文将Lai-Massey结构与NFSR组件相结合，构造一种新的L-M-NFSR结构，以AES算法S盒进行仿射等价获得的8比特S盒作为新结构中的轮函数，左右分支增加NFSR 组件，通过3 轮迭代和遍历搜索，构造出16 比特S 盒。为提高对所构造S 盒性质的评估效率，采用GPU技术进行并行计算，测试S盒的差分均匀度、非线性度、信噪比等。测试结果表明，本文方法构造的16 比特S 盒具有较优的差分均匀度、非线性度和信噪比，具有一定的抵御数学攻击和差分功耗攻击的能力。今后的工作中，考虑进一步优化结构，降低实现成本。