【作者】 徐红如；

【导师】 胡予濮；

【作者基本信息】 西安电子科技大学 ， 密码学， 2004， 硕士

【摘要】 对密钥流生成器的设计与分析一直是序列密码研究的中心课题。本文主要分析讨论了广义自缩序列的伪随机性以及安全性。其中第一章主要介绍了序列密码的研究现状，包括生成现状和攻击现状，另外在本章章末介绍了广义自缩序列设计思想的来源—缩减序列的研究现状。第二章介绍了广义自缩序列族的一些基本伪随机性特性，包括最小周期以及线性复杂度等结果。第三章讨论了穷举攻击和区分性攻击，这是两种最为常规的对于每一种密钥流序列都可以适用的攻击方法，但是区分性攻击往往比穷举性攻击来得有效。第四章简单介绍了当前一个主流的攻击方法—快速相关攻击，并结合熵分析对广义自缩序列的安全性进行了讨论。第五章介绍了在很多领域都有广泛应用的数据结构BDDs在密码学领域的应用，在章末将其中一个具有特殊特性的BDD用于分析广义自缩序列生成器，得到了一个更为有效的理论结果。 主要工作结果如下： 1、针对广义自缩生成器采用弱反馈多项式(设为已知)的情形提出了一个有效的区分性攻击，得到的攻击复杂度是目前已知攻击中最小的，进一步地，给出了反馈多项式是未知情况的破解思路。 2、利用熵分析构造了一个拟合序列后采用快速相关攻击方法对广义自缩序列进行了分析，给出了实现的具体步骤，指出了该方法在理论上的可行性。 3、利用BDDs中的FBDD对广义自缩序列进行攻击，指出了其实现方法和复杂度。更多还原

【Abstract】 The design and analysis of the key stream generators are always the central task of the stream cipher. In this paper we mainly investigate the pseudo-randomness and security of a new designed sequence-generalized self-shrinking sequences. In chapter one, the research status quo of the stream cipher including its generation and attacks are introduced, at the same time since the main design idea of the generalized self-shrinking sequences results from that of the shrinking sequences, the research status quo of the shrinking sequence is also presented in this chapter. The basic pseudo-randomness of the generalized self-shrinking sequences family such as their least period, linear complexity and others are introduced in chapter two. In chapter three, exhaustive key attack and distinguishing attack are introduced and applied to self-shrinking sequences. In chapter four, a brief review of fast correlation attacks is given, then an attack to generalized self-shrinking sequences is discussed by combining with entropy analysis. In the last chapter, BDD attacks which widely applied in many fields is introduced, and further, a special class of BDDs is applied to generalized self-shrinking sequences, our analysis shows in theory the attack is more efficient.The main work of this paper are followed:1. We showed that certain known weak feedback polynomials allow very efficient distinguishing attack on generalized self-shrinking sequences, and further give a new note if the generator uses a secret feedback polynomial.2. First a quasi-like sequence is constructed by using entropy analysis,and then a fast correlation attack is taken to recover the origin sequence. The detail steps of the attack is given. The cryptanalysis shows that in theory the attack is practical.3. An attack called FBDD is applied to generalized self-shrinking sequence,the realization step and time complexity and space complexity are showed.更多还原