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

Different algorithms on computation of Boolean expression of S box

作　　者：李晓东[1] 陶涛[1] 

机构地区：[1]北京电子科技学院计算机科学与技术系,北京100071

出　　处：《计算机工程与应用》2012年第35期85-87,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61170037);北京市自然科学基金(No.4092040);北京电子科技学院重点实验室基金(No.YQNJ0910;No.YZDJ0801)

摘　　要：S盒是许多加密算法唯一的非线性部件,其安全性对这些算法的密码分析至关重要。S盒输出的布尔表达式(即模2域上的代数多项式)被用于衡量S盒的非线性度等用途。在已知S盒真值表情况下,对求S盒各输出布尔表达式的各种算法进行了探讨和总结。其中,折半异或法在普通PC计算机上只需要m2m-1次操作,其中m为S盒的输入位数,且不需要占用额外的内存。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 rn2m-1 operations in PC computers where m is the input bit number of S box, and does not require additional memory.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]