Design And Analysis Of Extensive Generalized Self-shrinking Generator

One of the current trends of designs in key stream generators is to use irregular clocking. By analyzing some existing attacks, we give the model of Extensive Generalized Self-shrinking Generator for the first time, which is based on the Self-shrinking Generator and Generalized Self-shrinking Generator. Then each correlative sequence of this generator is analyzed by the knowledge of Probability, Stochastic Processes, Feedback Shift Register, etc. Finally, we give the arithmetic of Exhaustive Search Attack, Time/Memory Tradeoff Attack and Entropy Leak Attack to this generator. The result indicates that the capability against the above attacks can be improved by choosing proper parameters.The main results are given as follows:According to the recent central guide line of designing key stream generators, Extensive Generalized Self-shrinking Generator is given on the base of Generalized Self-shrinking Generator. This generator preserves the advantage of Generalized Self-shrinking Generator, such as easily constructed and analyzed. At the same time, the number of output sequences which have good properties (longer periods, higher linear complexity) is increased by introducing nonlinear combination functions into the generator. Self-shrinking Generator and Generalized Self-shrinking Generator are special cases of Extensive Generalized Self-shrinking Generator.The probability model of Extensive Generalized Self-shrinking Generator is constructed. The output time sequences and the output sequences are analyzed: the output time sequences are proved as a homogeneous Markov chain, and the output sequences are independent and identically uniform distributed. The coincidence between the output sequences and some correlation sequences in this generator is given. The conclusions indicate that Extensive Generalized Self-shrinking Generator preserves the advantage of Generalized Self-shrinking Generator. The coincidence between the output sequences and the original sequences can be reduced by choosing proper parameters.The arithmetic of Exhaustive Search Attack, Time/Memory Tradeoff Attack and Entropy Leak Attack to Extensive Generalized Self-shrinking Generator is given. The results indicate that the capability against the preceding attack is contacted with the length of the LFSR used in this generator. The capability against the Entropy Leak Attack is also related to the nonlinearity of the combination function used in the generator. So, this generator can improve the capability of resisting the above attacks, by using large Line Feedback Shift Registers and the combination functions with higher nonlinearity.