打开文本图片集
摘要：针对三点和四点爬山算法对随机置换盒（S盒）的非线性度进行优化时计算量大及效率低的问题，提出了一种组合式爬山算法（CHC）。该算法把交换S盒两个输出数据的行为定义为一个交换元，利用加权择优函数，筛选出若干个对非线性度的提升贡献较大的交换元，然后通过同时应用多个交换元，达成提高S盒非线性度的目标。实验中利用CHC算法，一次最多交换了12个输出数据，使得大部分8输入8输出随机S盒的非线性度超过了102，最高可达106。实验结果表明，所提出的CHC算法相比于三点和四点爬山算法，不仅降低了计算量，而且对随机S盒的非线性度也有着更为明显的提升作用。
关键词：分组密码；S盒；非线性度；WalshHadamard变换；爬山算法
中图分类号： TP309.7
文献标志码：A
Method for increasing Sbox nonlinearity based on combination of hill climbing
QIN Guanjie， MA Jianshe， CHENG Xuemin*
Shenzhen Branch of Optical Memory National Engineering Research Center， Graduate School at Shenzhen， Tsinghua University， Shenzhen Guangdong 518055， China
Abstract：
Focusing on the issue that the 3point and 4point hill climbing algorithms have high calculation and low efficiency in enhancing the nonlinearity of a Substitution box （Sbox）， an algorithm named Combination of Hill Climbing （CHC）， which could apply multiple swap elements at a time， was proposed. The algorithm defined the behavior of swapping 2 output data of an Sbox as a swap element， and used weighting prioritizing function to select swap elements that have larger contribution to the enhancement of nonlinearity， then simultaneously applied multiple selected swap elements to enhance the nonlinearity of an Sbox. In the experiments， a maximum of 12 output data were swapped at a time by using the CHC algorithm， and most of the random 8input and 8output Sboxes nonlinearity surpassed 102， with a maximum of 106. The experimental results show that the proposed CHC algorithm not only reduces the amount of calculation， but also enhances the nonlinearity of random Sboxes more significantly in comparison with the 3point and 4point hill climbing algorithms.
Key words：
block cipher； Substitution box （Sbox）； nonlinearity； WalshHadamard Transformation （WHT）； hill climbing algorithm
0引言
置换盒（Substitution box， S盒）是许多分组密码算法结构中的非线性部件，例如数据加密标准（Data Encryption Standard， DES）、Rijndael、Camellia等分组密码算法。在一个分组密码算法中，S盒的作用是将当前数据按照非线性的映射规则进行变换，所以其性能的好坏对整个算法的安全性能有着关键性的影响。衡量S盒安全性能的指标主要有非线性度、差分均匀性、平衡性、扩散性、相关免疫性等[1]，如何构造安全性能良好的S盒是密码学研究的一个重点。构造S盒的一种途径是利用数学函数，如Rijndael算法采用的S盒，其优点是可以使特定的衡量指标达到最优值，但是因为其明确的代数结构，容易引来针对性的攻击，比如基于代数表达式的密码分析[2-3]；另外一种途径是随机生成并筛选，通常这样生成的S盒性能指标不佳，筛选出较为满意的结果要付出大量的搜索代价，从而需要有针对性地对其进行优化。
Millan等[4]给出了交换S盒两个输出数据来提高S盒非线性度的Hill Climbing算法，又称为两点爬山算法，其基本原理是通过交换两个输出数据，并验证S盒的Walsh谱，若Walsh谱中元素的最大绝对值有所降低，则说明提高了S盒的非线性度。近年来有学者对Hill Climbing算法进行了改善，如文献[5]给出了三点爬山算法，即交换任意两个输出数据都不能提高S盒的非线性度时，按照确定的顺序同时交换三个输出数据，以进一步提高非线性度；文献[6]对文献[5]的算法进行了精简，针对其算法中对集合的利用存在多余和重复的现象，去除了无需验证的集合，给出了一种新的三点爬山算法；文献[7]则给出一种四点爬山算法，即交换任意两个输出数据都不能提高S盒的非线性度时，按照确定的顺序同时交换四个输出数据，以进一步提高非线性度；而文献[8]对Hill Climbing爬山算法以及四点爬山算法进行了比较。在实际操作过程中，利用三点爬山算法和四点爬山算法，其提高S盒非线性度的能力要高于Hill Climbing爬山算法，但是也存在着一些有待改进的地方：一是交换输出数据的数量仍然有限；二是交换的顺序单一；三是验证交换输出数据带来的效果时，采用遍历的方法，计算量大。本文针对以上三个需改进的地方，提出一种组合式爬山（Combination of Hill Climbing， CHC）算法。CHC算法利用加权择优函数，能够筛选出有利于提高S盒非线性度的交换元，不仅提升了计算的效率，从结果方面也增强了提升S盒非线性度的能力。
1基本概念与定理
定义1设f（x）：Fn2→F2是n元布尔函数。称F^（w）为f（x）的沃尔什哈达玛变换（WalshHadamard Transformation， WHT），是指：F^（w）=∑x∈Fn2（-1）f（x）⊕Lw（x）。其中：w=（w1，w2，…，wn）∈Fn2， Lw（x）=w1x1⊕w2x2⊕…⊕wnxn，⊕为有限域上定义的加法[9]。
定义2设f（x）：Fn2→F2是n元布尔函数，则可定义其非线性度Nf=dmin（f（x），l（x））。其中：dmin代表最小汉明距离；l（x）∈Ln，Ln为全体n元线性函数与仿射函数的集合。Nf代表着布尔函数与任意线性、仿射函数之间的最小汉明距离。若将定义1中F^（w）的最大绝对值表示为WHmax，那么Nf=2-1（2n-WHmax）为布尔函数非线性度的值[10]。
定义3令S（x）=（f1（x），f2（x），…，fm（x））：Fn2→Fm2（n≥m≥1）为一个多输出布尔函数，则可定义其非线性度Ns=dmin（u·S（x），l（x））。其中：dmin代表最小汉明距离；0≠u∈Fm2，l（x）∈Ln，Ln为全体n元线性函数与仿射函数的集合[11]。Ns代表着构成S（x）的各分量布尔函数的非零线性组合所形成的布尔函数与任意线性、仿射函数之间的最小汉明距离。若对各分量布尔函数的非零线性组合所形成的布尔函数都进行WalshHadamard变换，则可形成WHT矩阵，矩阵中的每一个元素可表示为B^（v，w）=∑x∈Fn2L^v（y）·L^w（x）。其中：v∈Fm2，w∈Fn2，L^v（y）=（-1）Lv（y），L^w（x）=（-1）Lw（x），Lv（y）=v1y1⊕v2y2⊕…⊕vmym， Lw（x）=w1x1⊕w2x2⊕…⊕wnxn。同样可以将WHT矩阵中元素的最大绝对值表示为WHmax，则有：Ns=2-1（2n-WHmax）为S（x）的非线性度的值[12]。
从定义3中可以看出，将S盒对应的WHmax降低，可以提高其非线性度。
定义4对于一个已知的S盒，可定义以下集合：
W+i：{（v，w）"B^（v，w）=WHmax+2-2i）}
W-i：{（v，w）|B^（v，w）=-WHmax-2+2i）}
其中i=1，2，3，…，为正整数。
2Hill Climbing算法
定理1设b（x）=y是一个双射S盒，x1和x2为两个不同的输入，并且y1=b（x1），y2=b（x2），令b′（x）为b（x）交换y1和y2之后得到的S盒。若x1和x2满足条件1的内容，那么b′（x）对应的WHmax将比b（x）有所降低。
条件1：
1）Lw（x1）≠Lw（x2），对于所有的（v，w）∈W+1∪W-1。
2）Lv（y1）≠Lw（x2），Lv（y2）≠Lw（x1），对于所有的（v，w）∈W+1。
3）Lv（y1）=Lw（x2），Lv（y2）=Lw（x1），对于所有的（v，w）∈W-1。
4）对于所有的（v，w）∈W+2∪W+3，下列式子不全为真：
权重值wti与满足条件2的组合种类数量成反比。以同时应用2个交换元的情况为例，对于（v，w）∈W+1，需要满足的约束条件为最终ΔB^（v，w）<0，此时两个交换元组合的ΔB^（v，w）可以为{-4，-4}、{-4，0}、{0，-4}这三种情况，它们的组合总分分别为8分、6分、6分。更完整的内容见表1分析。
从表1中可以看出，不同的集合的ΔB^（v，w）约束不同，由此对应着不同的组合总分要求，以及符合要求的组合数。组合数越少，代表着条件越苛刻，所以需要优先考虑。另外由于对称关系，W+i和W-i的组合数是一样的。因为组合数与权重成反比，那么以n=2的情况为例，可以得到权重的比例为wt1∶wt2∶wt3∶wt4∶wt5=8∶4∶4∶3∶3。
至此，式（1）中的所有参数的计算方法均已给出，式（1）中交换元的得分g越高，代表其对S盒非线性度提升带来的贡献越大。择优选出前k个得分值最大的交换元进行下一步的组合验证。
3.2交换元组合的验证方法
同时运用个交换元的情况下，有ΔB^（v，w）=ΔB^1（v，w）+ΔB^2（v，w）+…+ΔB^n（v，w）。不同的ΔB^（v，w）对应着不同的组合，进而对应着不同的分值。要满足条件2中的要求，首先n个交换元包含的输出数据相互之间不能有交集，然后只需分别检查每个W+i以及W-i中得分最低的（v，w）的分数是否大于得分阈值，即每个W+i以及W-i均满足：
4实验测试以及结果
4.1实验环境设置
为测试CHC算法对随机S盒非线性度的优化性能，在64位Windows 7上利用Matlab R2012b进行了测试，程序的流程如图1所示。
如图1所示，对于输入的S盒，先利用Hill Climbing两点爬山算法和文献[5]中提出的三点爬山算法进行尝试，如果无法提升S盒的非线性度，则依次应用交换元数量n=2，3，4，5，6的CHC算法进行尝试，这些参数分别对应着同时交换4、6、8、10、12个不同的输出数据。通过调整优选数量k，可以影响判断量的多少，即需要判断是否满足条件2的组合个数。在实验中所设置的交换元优选数量k的值如表2所示。
因为每一个解是从优选的k个交换元中选出n个交换元进行组合，所以需判断的解数量为Cnk。文献[4-7]中的爬山算法均采用遍历交换元的方法，没有优选的步骤。如果不进行优选，而是遍历所有的交换元的话，那么将有kmax=C2255=32385，以n=5为例，需判断的解有C532385≈2.97×1020个，这将耗费大量的资源和时间。根据计算机的性能，CHC算法不仅可以调整同时应用的交换元数量n，也可调整优选数量k，n和k的值越大，找到满足条件2的解可能性也越大，同时耗费的时间和资源也越多。
4.2CHC算法运行结果
运用CHC算法，对8输入8输出的S盒进行了优化实验。首先随机生成10000个初始S盒，然后按照图1的流程进行优化，分别设置最大交换元数量nmax=3，4，5，6，得出的结果如图2所示，其中“随机”指随机生成的S盒非线性度分布情况，即未优化前的分布情况。
从图2中可以看出：随着nmax的增加，CHC算法对随机S盒非线性度的提升效果越来越明显；当nmax=6时，随机S盒的非线性度经过优化后集中在100和102上，并有少量的随机S盒非线性度达到了104和106。表3中给出了一个经过CHC算法优化后非线性度达到106的S盒，输入输出均为8位，用16进制表示。
表4中给出了CHC算法和三点、四点爬山算法的性能比较。在表4中，A3256代表256选3的排列；A4256代表256选4的排列；Cnk代表k选n的组合，其中n为交换元组合中的交换元数量，k为优选交换元的数量。
实验结果表明，无论从交换数据能力、智能择优处理能力或是非线性度优化结果上，CHC算法对随机S盒非线性度的优化性能都优于文献[5-7]中的算法。此外，根据计算机性能的不同，通过控制优选数量k的值，在节省时间和资源的前提下，CHC算法的nmax能够进一步地提高，从而能够同时交换更多的输出数据。
5结语
现有的三点爬山算法和四点爬山算法在提高S盒非线性度的过程中，由于其较大的计算量，降低了算法的效率。本文提出的CHC算法，以交换两个输出数据的操作作为一个交换元，先利用加权择优的方法，筛选出对非线性度的提升贡献较大的若干个交换元，再从筛选后的交换元中提取交换元组合进行验证。实验结果表明，CHC算法相比三点爬山算法和四点爬山算法，不仅提高了计算效率，而且使得随机S盒的非线性度得到了更佳的提升效果。当交换元组合中包含的交换元个数较多时，CHC算法也会面临较大的计算量，如何设计出更加智能有效的交换元择优方法，以及并行计算方法，是进一步改善算法时需要考虑的下一个问题。
参考文献：
[1]YANG H， HAN W， ZHAO L. Construction method of Sbox suitable for hardware implementation [J]. Journal of Computer Applications， 2010， 30（3）： 674-676， 684. （杨宏志，韩文报，赵龙.适于硬件实现的S盒构造方法[J].计算机应用，2010，30（3）：674-676，684.）
[2]CAI Z， WANG Y， LI R. Differential power analysis attack based on algebraic expression for power model [J]. Journal of Computer Applications， 2014， 34（2）： 448-451， 463. （蔡泽民，王奕，李仁发.基于代数表达式功耗模型的差分功耗分析攻击[J].计算机应用，2014，34（2）：448-451，463.）
[3]
YAN Y. Research on the algebraic attacks and its applications [D]. Chengdu： University of Electronic Science and Technology of China， 2012： 22-27. （闫耀军.代数攻击及其应用研究[D].成都：电子科技大学，2012：22-27.）
[4]
MILLAN W， CLARK A， DAWSON E. Smart hill climbing finds better boolean functions [C]// SAC 1997： Proceedings of the 1997 Workshop on Selected Areas in Cryptology. Berlin： Springer， 1997： 50-63.
[5]
CHEN H， WU W， FENG D. An effective algorithm to increase the nolinearity of Sboxes [J]. Computer Science， 2005， 32（10）： 68-70，86. （陈华，吴文玲，冯登国.提高S盒非线性度的有效算法[J].计算机科学，2005，32（10）：68-70，86.）
[6]
GAO S， MA W， GUO N， et al. Novel method for increasing the nonlinearity of Sboxes [J]. Journal of Xidian University， 2010， 37（6）： 1017-1021. （高胜，马文平，郭娜，等.一种提高S盒非线性度的新算法[J].西安电子科技大学学报，2010，37（6）：1017-1021.）
[7]
YU Y， OU H. An algorithm to improve the nonlinearity of bijective Sboxes [J]. Microcomputer Information， 2007， 23（18）： 29-30. （于亦舟，欧海文.一种改善双射S盒非线性度的方法[J].微计算机信息，2007，23（18）：29-30.）
[8]
YU Y， OU H. Two algorithms to improve the nonlinearity of bijective Sboxes and their comparison [J]. China New Telecommunications， 2007， 9（3）： 36-39. （于亦舟，欧海文.两种提高双射S盒非线性度的方法及其比较[J].中国新通信，2007，9（3）：36-39.）
[9]
NING X. Cryptographic properties of the block cipher Sboxes [D]. Changsha： Hunan University， 2007： 5-6. （宁学军.分组密码中S盒的密码学特性[D].长沙：湖南大学，2007：5-6.）
[10]
ZHUO Z. On properties and constructions of boolean functions in cryptography [D]. Xian： Xidian University， 2012： 11. （卓泽朋.密码学中布尔函数的性质和构造[D].西安：西安电子科技大学，2012：11.）
[11]
LU B. Research on optimization and improvement of Sbox in block cipher [D]. Chengdu： Southwest Jiaotong University， 2013： 11-12. （卢昺晅.分组密码中S盒的优化改进研究[D].成都：西南交通大学，2013：11-12.）
[12]
YUAN H， YANG X. Construction of almost optimal resilient boolean functions via concatenation [J]. Journal of Computer Applications， 2013， 33（12）： 3503-3505， 3510. （袁宏博，杨晓元.基于毗连的几乎最优弹性布尔函数的构造[J].计算机应用，2013，33（12）：3503-3505，3510.）
[13]
MILLIAN W. How to improve the nonlinearity of bijective Sboxes [C]// ACISP98： Proceedings of the 1998 Australasian Conference on Information Security and Privacy， LNCS 1438. Berlin： Springer， 1998： 181-192.