对广义自缩生成器的区分攻击  

Distinguishing attacks on generalized self-shrinking generators

作　　者：李雪莲[1] 高军涛[2,3] 胡予濮[2] 张凤荣[2] 

机构地区：[1]西安电子科技大学理学院,陕西西安710071 [2]西安电子科技大学计算机网络与信息安全教育部重点实验室,陕西西安710071 [3]信息安全国家重点实验室中国科学院软件研究所,北京100190

出　　处：《西安电子科技大学学报》2012年第4期114-119,共6页Journal of Xidian University

基　　金：973资助项目(2007CB311201);国家自然科学基金资助项目(60833008);保密通信重点实验室基金资助项目(9140C110201110C1102);中央高校基本科研业务费专项资金资助项目(K50511010007)

摘　　要：广义自缩生成器是一类结构简单、易于实现的流密码生成器.研究了广义自缩序列的安全性,利用生成器中反馈多项式及序列v对广义自缩生成器进行了区分攻击,表明如果广义自缩生成器的反馈多项式f(x)存在重量为w、次数为h的倍式,那么攻击者只要选择hw-1个密钥流比特就可以进行区分攻击;另一方面,如果f(x)本身的重量很低,那么也可以进行区分攻击,攻击的复杂度依赖于f(x)的重量.因此,在广义自缩序列中不能使用这两类多项式作为反馈多项式.其反馈多项式需要仔细选择,否则广义自缩生成器就容易受区分攻击.With simple construction and easy implementation, the generalized self-shrinking generator is a keystream generator intended to be used as a stream cipher. This paper investigates the security of the generalized self-shrinking generator. We propose two distinguishing attacks on the generalized self-shrinking sequences by using the feedback polynomial and the sequence v. The results show that the attacker can launch a distinguishing attack by choosing the h^ω-1 keystream bit of the generalized self-shrinking generator, if the feedback polynomial f（x） is of hamming weight w and degree h. On the other hand, if the hamming weight of f（x） is low, then the attacker can launch a distinguishing attack, and the attack complexity depends on the weight of f（x）. Therefore, neither type of the polynomials can be chosen as the feedback polynomials of the generalized self-shrinking generator. Users should choose the feedback polynomial carefully, otherwise the stream cipher can suffer from distinguishing attacks.

关 键 词：密码学 广义自缩生成器 区分攻击 线性反馈移位寄存器 多项式 

分 类 号：TN918.1[电子电信—通信与信息系统]