Study Of Algorithm For Attacks On Generalized Self-Shrinking Sequences

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.