布尔函数零化子的构造及其在流密码中的应用

代数攻击的基本思想是建立密钥比特和输出比特之间的方程,然后通过解超定的低次方程组来恢复密钥。在代数攻击中,可以通过布尔函数的零化子建立低次方程,从而使算法的复杂度降低。文章首先给出了两种布尔函数零化子的构造方法,然后将构造2分别应用于LILI-128和Toyocrypt中,得到低次零化子,通过此低次零化子建立低次方程进行攻击。与已知的攻击方法相比较,攻击的复杂度大大降低。

On Construction of Annihilators of Boolean Function and its Application in Stream Ciphers

The basic idea of algebraic attacks is that setting up equations on key bits and output bits,and recovering the secret key by solving an overdefined system of multivariate algebraic equations.In algebraic attacks,in order to reduce the computational complexity,we can set up low degree equations by annihilators of Boolean functions.In this paper,we first give two methods on construction of annihilators of Boolean function,then apply construction 2 in LILI-128 and Toyocrypt,and get low degree annihilators.Compared with the known attacks,setting up low degree equations by the low degree annihilators makes the complexity much reduced.