一种提高S盒非线性度的新算法

doi:10.3969/j.issn.1001-2400.2010.06.007

J4 ›› 2010, Vol. 37 ›› Issue (6): 1017-1021.doi: 10.3969/j.issn.1001-2400.2010.06.007

一种提高S盒非线性度的新算法

高胜;马文平;郭娜;严亚俊

(西安电子科技大学计算机网络与信息安全教育部重点实验室，陕西西安 710071)

收稿日期:2009-11-04 出版日期:2010-12-20 发布日期:2011-01-22
通讯作者: 高胜
作者简介:高胜(1982-)，男，西安电子科技大学博士研究生，E-mail: gaosheng@mail.xidian.edu.cn．
基金资助:
国家863计划资助项目(2007AA01Z472);国家自然科学基金资助项目(60773002,61072140);教育部留学回国人员科研启动基金资助项目;高等学校创新引智计划资助项目(B08038)

Novel method for increasing the nonlinearity of S-Boxes

GAO Sheng;MA Wen-ping;GUO Na;YAN Ya-jun

(Ministry of Education Key Lab. of Computer Network and Information Security,

Received:2009-11-04 Online:2010-12-20 Published:2011-01-22
Contact: GAO Sheng

摘要/Abstract

摘要：

S盒是构成分组密码算法重要的非线性部件．利用交换S盒两个输出向量来达到提高其非线性度的思想，提出一个通过交换S盒3个输出向量来提高其非线性度的方法，即三点爬山法．该方法简洁且执行效率较高，而且在William Millan两点爬山法不能提高S盒非线性度的情况下，能进一步改进非线性度．在此基础上，提出一个基于爬山算法的S盒优化算法，弥补了原有算法不能进一步改善非线性度的缺陷．对一些小变量S盒的实验结果验证了该算法的正确性和高效性．

关键词: S盒, 非线性度, Walsh变换, 爬山算法

Abstract:

An S-box is an important nonlinear component of block cipher algorithms.Using the idea of swapping two output vectors to increase nonlinearity of the S-Boxes, we propose a method for improving the nonlinearity by swapping three output vectors, namely, a new three-point hill-climbing algorithm.This method is simple and more efficient in implementation. Moreover, it could further improve the nonlinearity when William Millan's two-point hill-climbing could not. On the basis of this, an optimization algorithm based on the hill-climbing algorithm for improving the nonlinearity of the S-Boxes is presented, which overcomes the disadvantage of existing algorithms that cannot improve the nonlinearity further. Numerical results of testing for some small variables S-Boxes show the correctness and efficiency of the proposed algorithm.

Key words: S-Boxes, nonlinearity, Walsh transformation, hill-climbing algorithm

高胜;马文平;郭娜;严亚俊. 一种提高S盒非线性度的新算法[J]. J4, 2010, 37(6): 1017-1021.

GAO Sheng;MA Wen-ping;GUO Na;YAN Ya-jun. Novel method for increasing the nonlinearity of S-Boxes[J]. J4, 2010, 37(6): 1017-1021.

参考文献

[1] Matsui M. Linear Cryptanalysis Method for DES Cipher[C]//Advances in Cryptology-EUROCRYPT'93, LNCS765. Berlin: Springer-Verlag, 1994: 386-397.
[2] Millan W. How to Improve the Nonlinearity of Bijective S-boxes[C]//ACISP'98, LNCS1438. Berlin: Springer-Verlag, 1998: 181-192.
[3] Millan W, Clark A, Dawson E. Smart Hill Climbing Finds Better Boolean Functions[C]//Proceedings of the First International Conference on Information and Communications Security, LNCS 1334. Berlin: Springer-Verlag, 1997: 149-158.
[4] Millan W, Burnett L, Carter G, et al. Evolutionary Heuristics for Finding Cryptographically Strong S-Boxes[C]//ICICS'99, LNCS1726. Berlin: Springer-Verlag, 1999: 263-274.
[5] 陈华, 吴文玲, 冯登国. 提高S盒非线性度的有效算法[J]. 计算机科学, 2005, 32(10): 68-70.
Chen Hua, Wu Wenling, Feng Dengguo. An Effective Algorithm to Increase the Nonlinearity of S-Boxes[J]. Computer Science, 2005,32(10): 68-70.
[6] 于亦舟, 欧海文. 一种改善双射S盒非线性度的方法[J]. 微计算机信息, 2007, 23(18): 29-30.
Yu Yizhou, Ou Haiwen. An Algorithm to Improve the Nonlinearity of Bijective S-Boxes[J]. Microcomputer Information, 2007, 23(18): 29-30.
[7] Chen H, Feng D G. An Effective Evolutionary Strategy for Bijective S-Boxes[C]//Proceeding of the IEEE Congress on Evolutionary Computation 2004(CEC'04). Portland: IEEE, 2004: 2120-2123.
[8] Nyberg K. Perfect Nonlinear S-Boxes[C]//Advances in Cryptology-EUROCRYPT'91, LNCS547. New York: Springer-Verlag, 1991: 378-386.
[9] Rothaus O S. On Bent Functions[J]. Journal of Combinatorial Theory(A), 1976(20): 300-305.
[10] Seberry J, Zhang X-M, Zheng Y. Relationships Among Nonlinearity Criteria[C]//Advances in Cryptology-EUROCRYPT'94, LNCS950. Berlin: Springer-Verlag, 1994: 376-388.
[11] 刘景伟,韦宝典,吕继强,等. AES S盒的密码特性分析[J]. 西安电子科技大学学报, 2004, 31(2): 256-259.
Liu Jingwei, Wei Baodian, Lü Jiqiang, et al. Analysis of the Cryptographic Properties of the AES S-box[J]. Journal of Xidian University, 2004, 31(2): 256-259.
[12] 韦宝典, 马文平, 王新梅. AES S盒的代数表达式[J]. 西安电子科技大学学报, 2003, 30(1): 29-32.
Wei Baodian, Ma Wenping, Wang Xinmei. The Algebraic Expression for the AES S Boxes[J].Journal of Xidian University, 2003, 30(1): 29-32.

一种提高S盒非线性度的新算法

Novel method for increasing the nonlinearity of S-Boxes

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

Metrics

本文评价

推荐阅读 10

[1]	董新锋,张文政,许春香. Feistel结构的8比特轻量化S盒[J]. 西安电子科技大学学报, 2021, 48(1): 69-75.
[2]	刘景美1;赵林森2;王新梅1. 一种具有最小实现代价的AES改进方法 [J]. J4, 2009, 36(1): 52-57.
[3]	韦宝典;刘景伟;王新梅. 求解域元素分量表达式的两种新方法[J]. J4, 2004, 31(4): 518-522.
[4]	刘景伟;韦宝典;吕继强;王新梅. AES S盒的密码特性分析[J]. J4, 2004, 31(2): 255-259.
[5]	郑连清1;张串绒1;2;董庆宽2;傅晓彤2;肖国镇2. 布尔函数非线性度界的问题[J]. J4, 2003, 30(2): 281-283.
[6]	韦宝典;马文平;王新梅. AES S盒的代数表达式[J]. J4, 2003, 30(1): 29-32.
[7]	张串绒;肖鸿;肖国镇. 基于两类重要函数的非线性组合函数[J]. J4, 2002, 29(1): 138-142.
[8]	暂时无作者信息. 一种改进的非线性正形置换构造方法及其性能分析[J]. J4, 1997, 24(4): 0-0.
[9]	暂时无作者信息. 关于正形置换的构造及计数[J]. J4, 1997, 24(3): 0-0.
[10]	暂时无作者信息. 一种特殊S盒的构造及其快速实现[J]. J4, 1997, 24(1): 0-0.