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

• 网络、通信、安全 • 上一篇    下一篇

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

李晓东,陶  涛   

  1. 北京电子科技学院 计算机科学与技术系,北京 100071
  • 出版日期:2012-12-11 发布日期:2012-12-21

Different algorithms on computation of Boolean expression of S box

LI Xiaodong, TAO Tao   

  1. Department of Computer Science and Technology, Beijing Electronic Science and Technology Institute, Beijing 100071, China
  • Online:2012-12-11 Published:2012-12-21

摘要: 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