Abstract:

Focusing on the issue that the 3-point and 4-point hill climbing algorithms have high calculation and low efficiency in enhancing the nonlinearity of a Substitution box (S-box), 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 S-box 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 S-box. In the experiments, a maximum of 12 output data were swapped at a time by using the CHC algorithm, and most of the random 8-input and 8-output S-boxes' 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 S-boxes more significantly in comparison with the 3-point and 4-point hill climbing algorithms.

Key words: block cipher, Substitution box (S-box), nonlinearity, Walsh-Hadamard Transformation (WHT), hill climbing algorithm

摘要：

针对三点和四点爬山算法对随机置换盒(S盒)的非线性度进行优化时计算量大及效率低的问题,提出了一种组合式爬山算法(CHC)。该算法把交换S盒两个输出数据的行为定义为一个交换元,利用加权择优函数,筛选出若干个对非线性度的提升贡献较大的交换元,然后通过同时应用多个交换元,达成提高S盒非线性度的目标。实验中利用CHC算法,一次最多交换了12个输出数据,使得大部分8输入8输出随机S盒的非线性度超过了102,最高可达106。实验结果表明,所提出的CHC算法相比于三点和四点爬山算法,不仅降低了计算量,而且对随机S盒的非线性度也有着更为明显的提升作用。

关键词: 分组密码, S盒, 非线性度, Walsh-Hadamard变换, 爬山算法