Study On Design And Analysis Of Pseudorandom Sequences

This dissertation firstly discusses the ability of the generalized self-shrinking generator and balanced shrinking generator to resist the fault attack. Secondly, a new type of generalized self-shrinking generator is presented to resist the fault attack, and pseudorandomness and security of new sequences are investigated. Finally, the relationship between autocorrelation and linear complexity is discussed. The main results are as follows: The author gives a cryptanalysis of the generalized self-shrinking generator and balanced shrinking generator by using the fault attack technique. The results show that, for the generalized self-shrinking generator given the feedback polynomial, the attacker can obtain the secret keys by 4 faulty keystreams with 60 stages LFSR, where the length of the keystream required is about 2⁸ bits.For the balanced shrinking generator, the attacker can obtain the secret keys by analyzing faulty output sequences which is produced by changing control clock of one of LFSRs. A new type of generalized self-shrinking generator is presented and the least period, run length and the pseudorandom property of sequences family of which are investigated. The results show that, by our method, 2^n-3 sequences with the least period 2^n-1 can be found. Besides, we show that the maximal run length of the new sequences is less than n²-2.5n+3. The security of the new generalized self-shrinking generator is discussed. The results show that, If the vector G is known for the attacker, then he/she can obtain the secret keys with a complexity O(12n⁴2^0.694n). If the vector G is unknown but the C₁={01,10} is known, then the attacker can find a correlation weakness, which can be used to attack the new generalized self-shrinking generator; However, if C₁≠ {01,10}, there does not exist the above correlation weakness. The stability of the linear complexity of the new generalized self-shrinking generator is discussed. The results show that the linear complexity will increase if odd bits are changed in the sequences. If even bits are changed and the situations of bit changed satisfy some conditions, then the linear complexity will decrease, except this, the linear complexity will increase. For the 2ⁿ-periodic pseudorandom sequences, the relationship between autocorrelation and linear complexity is presented and the application of which in three aspects are given, that is: 1)Estimating/Evaluating the value of autocorrelation functions by the linear complexity; 2) A simpler proof of Games-Chan algorithm is given by the autocorrelation; 3) Evaluating the correlation of a given sequence family by the linear complexity. For a sort of sequences with period 2ⁿ, we denote that the autocorrelation is related to linear complexity and k-error linear complexity,that is, the autocrrelation can be estimated by the linear complexity and k-error linear complexity.