非线性组合序列的新攻击算法

New Algorithm for Attacking Nonlinear Combined Sequences

给出了一种攻击非线性组合序列的新算法,该方法只需要知道每个驱动序列的级数,便可恢复驱动序列的初始状态及生成多项式.研究了该方法的数据复杂性,文章指出:单纯增加驱动序列的个数并不能从本质上提高系统的安全性.给出了一种新的衡量布尔函数密码学性能的指标,讨论了该指标的基本性质.指出在设计非线性组合序列时,该指标值应尽可能小.并列出了所有该指标值为0的2元和3元布尔函数,对4元以上的情形,给出了指标值为0的布尔函数计数的一个上界.

To attack nonlinear combined sequences, we propose a new method that only requires the stage of the linear feedback shift register＇ s （LFSR） and enough sample bits to recover the initial states and the feedback polynomial. Complexity of the algorithm is studied. We show that security cannot be improved essentially by just increasing the number of LFSRs. We propose a new metric to evaluate the cryptographic ability of Boolean functions in order to resist this kind of attack, and study some properties of the metric. We show that this metric should be small in designing a nonlinear combined sequence. We gave all the functions that the new metric is 0 when the variable number is 2 and 3. An up-bound of the metric is given when the number of variable is equal to or greater than 4.