提高S盒非线性度的有效算法

S盒是分组密码算法中的重要的非线性部件.William Millan曾给出一个能改善S盒非线性度的Hill Climbing算法,它通过交换S盒的两个输出向量来提高S盒的非线性度直到非线性度达到一个局部最优值,即交换任何两个输出向量也不能提高S盒的非线性度.本文研究了如何同时改变S盒的三个输出向量的位置来提高S盒的非线性度,并给出了MHC算法,它能在Hill Climbing算法的基础上进一步提高非线性度.实验证明,MHC算法对随机S盒的优化效果明显大于Hill Climbing算法.

An Effective Algorithm to Increase the Nonlinearity of S-boxes

A S-box is the important nonlinear eonponent of block cipher algorithms, William Millian provied the Hill Climbing algorithm for improving the nonlinearity of S-boxes, which can increase the nonlinearity of a S-box by swapping two output vectors, Under the algorithm, the nonlinearity will reach a local maximum,which means that swapping any two output vectors can not increase the nonlinearity any more. In this paper, how to improve the nonlinearity of Sboxes by changing the positions of three output vectors simultaneously is explored. The MHC algorithm is given which can increase the nonlinearity on the basis of the Hill Climbing algorithm. The experimental results show that, the MHC algorithm is apparently more effective than the Hill Climbing to improve the nonlinearity of random S-boxes.