求S盒布尔表达式的若干算法探讨

计算机工程与应用 ›› 2012, Vol. 48 ›› Issue (35): 85-87.

求S盒布尔表达式的若干算法探讨

李晓东，陶涛

北京电子科技学院计算机科学与技术系，北京 100071

出版日期:2012-12-11 发布日期:2012-12-21

Different algorithms on computation of Boolean expression of S box

LI Xiaodong, TAO Tao

Department of Computer Science and Technology, Beijing Electronic Science and Technology Institute, Beijing 100071, China

Online:2012-12-11 Published:2012-12-21

摘要/Abstract

摘要： S盒是许多加密算法唯一的非线性部件，其安全性对这些算法的密码分析至关重要。S盒输出的布尔表达式（即模2域上的代数多项式）被用于衡量S盒的非线性度等用途。在已知S盒真值表情况下，对求S盒各输出布尔表达式的各种算法进行了探讨和总结。其中，折半异或法在普通PC计算机上只需要[m2m-1]次操作，其中[m]为S盒的输入位数，且不需要占用额外的内存。

关键词: 密码, S盒, 布尔函数, 布尔表达式, 算法

Abstract: S box is the only nonlinear component of many encryption algorithms, its security is important to the cryptanalysis of these algorithms. Output Boolean expression of the S box is used to measure the degree of the nonlinearity of S box. Known?truth table, various algorithms on computing output?Boolean expression?of the?S?box?are discussed and?summarized. Among them, the?fold?XOR?method only?requires [m2m-1] operations in PC?computers where [m] is the input bit number of S box, and does not require?additional memory.

Key words: cryptology, S box, Boolean function, Boolean expression, algorithm

李晓东，陶涛. 求S盒布尔表达式的若干算法探讨[J]. 计算机工程与应用, 2012, 48(35): 85-87.

LI Xiaodong, TAO Tao. Different algorithms on computation of Boolean expression of S box[J]. Computer Engineering and Applications, 2012, 48(35): 85-87.

[1]	兰红，黄敏. 融合KNN优化的密度峰值和FCM聚类算法[J]. 计算机工程与应用, 2021, 57(9): 81-88.
[2]	张岐山，陈露露. 基于均衡接近度灰关联的Slope One算法[J]. 计算机工程与应用, 2021, 57(9): 96-102.
[3]	王永贵，李倩玉. 基于KNN-GBDT的混合协同过滤推荐算法[J]. 计算机工程与应用, 2021, 57(9): 103-108.
[4]	孙泽宇，徐琛，苏艳超，李传锋，聂雅琳. 雾计算中跨层感知分簇路由协议[J]. 计算机工程与应用, 2021, 57(9): 109-117.
[5]	张朕通，单玉刚，袁杰. 联合多尺度和注意力机制的遥感影像检测[J]. 计算机工程与应用, 2021, 57(9): 212-216.
[6]	闫晓燊，高强，朱思萌，奚学程，赵万生. 亮度不均匀低质量图像中压印字符分割方法[J]. 计算机工程与应用, 2021, 57(8): 185-191.
[7]	高一锴，彭力，徐龙壮. 改进AFSA算法优化TWSVM的火焰识别方法[J]. 计算机工程与应用, 2021, 57(8): 204-213.
[8]	孔继利，张鹏坤，刘晓平. 双向搜索机制的改进A*算法研究[J]. 计算机工程与应用, 2021, 57(8): 231-237.
[9]	槐创锋，郭龙，贾雪艳，张子昊. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(8): 244-248.
[10]	高铖铖，陈锡程，张瑞，宋秋月，易东，伍亚舟. 三种新型智能算法在疫情预警模型中的应用——基于百度搜索指数的COVID-19疫情预警[J]. 计算机工程与应用, 2021, 57(8): 256-263.
[11]	史春天，曾艳阳，侯守明. 群体智能算法在图像分割中的应用综述[J]. 计算机工程与应用, 2021, 57(8): 36-47.
[12]	张松灿，普杰信，司彦娜，孙力帆. 基于种群相似度的自适应改进蚁群算法及应用[J]. 计算机工程与应用, 2021, 57(8): 70-77.
[13]	谢锐强，张惠珍. 求解柔性作业车间调度问题的两段式狼群算法[J]. 计算机工程与应用, 2021, 57(7): 251-256.
[14]	沈新烽，姜平，周根荣. 改进SSD算法在零部件检测中的应用研究[J]. 计算机工程与应用, 2021, 57(7): 257-262.
[15]	雍玖，王阳萍，党建武，雷晓妹. 改进TLD与ORB的AR系统长时跟踪注册方法[J]. 计算机工程与应用, 2021, 57(7): 178-184.