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

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