English

应用科学学报

• 论文 • 上一篇    

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

孙 兵，李 超   

  1. 国防科技大学 数学与系统科学系，湖南 长沙 410073
  • 收稿日期:2007-07-03 修回日期:2008-01-09 出版日期:2008-05-31 发布日期:2008-05-31

New Algorithm for Attacking Nonlinear Combined Sequences

SUN Bing, LI Chao   

  1. Department of Mathematics and System Science, National University of Defense Technology, Changsha 410073, China
  • Received:2007-07-03 Revised:2008-01-09 Online:2008-05-31 Published:2008-05-31

被引次数

1

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

关键词: 布尔函数, 非线性组合, Walsh谱, 相关攻击

Abstract:

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.

Key words:

Boolean function, nonlinear combined, Walsh spectra, correlation attack