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

An Effective Algorithm to Increase the Nonlinearity of S-boxes

作　　者：陈华[1] 吴文玲[1] 冯登国[1] 

机构地区：[1]中国科学院软件研究所信息安全国家重点实验室,北京100080

出　　处：《计算机科学》2005年第10期68-70,86,共4页Computer Science

基　　金：国家自然科学基金重大研究计划项目(90304007);国家自然科学基金(60373047);863高科技发展计划(2001AA141010)

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

关 键 词：分组密码 S盒 非线性度 非线性度 有效算法 S盒 分组密码算法 输出向量 非线性部件 实验证明 MHC 最优值 

分 类 号：TN918.1[电子电信—通信与信息系统] O157.5[电子电信—信息与通信工程]