Research On The Design And Analysis Of Several Classes Of Pseudorandom Sequence And Sequence Families

Pseudorandom sequences and sequence families have wide applications in cryptography, spreading communication, error-correcting code, etc. The design and analysis of pseudorandom sequences and sequence families are hot topic in the world all the time. In this dissertation, we mainly concentrate on the design and analysis of several classes of pseudorandom sequences and sequence families used in cryptography and spreading communication.Pseudoramdom sequence is used as keystrearn sequence in stream cipher, which is XORed with plaintext sequence to generate ciphertext sequence. The security of a stream cipher is determined by the keystream sequence. Thus the key of stream cipher is to generate good keystream sequence. Traditional stream ciphers usually use a LFSR as key source generator, then by filter, clock control or combination to generate nonlinear sequence. As the result of linear property of the sequence generated by LFSR, such nonlinear sequence is prone to be attacked by correlation attack and algebraic attack. Furthermore, the slow software realization speed of these stream ciphers cannot satisfy the need of encrypting a large amount of date rapidly.In recent years, with the rapid development of computer technology, there appear many word-oriented stream ciphers, which can be rapidly realized in software, thus they can be applied in the environments of encrypting a large amount of date rapidly. Many of these stream ciphers, such as ABC, TSC and Mir presented at eSTREAM, all use single cycle T-functions as key source generator. The sequence generated by T-function has provable long period property, is well distributed, and does not have obvious linear structure. Thus it can efficiently resist correlation attack and algebraic attack. Then it is possible for the T-function to replace LFSR as key source generator of new stream ciphers.In the first part of this dissertation, we do some research on the analysis of the sequences generated by single word single cycle T-functions, the main results are as follows:1. The four conjectures on the algebraic structure of the sequence (x0,x1,…) generated by Klimov-Shamir T-function f(x)=x+x2∨5 mod 2n are proved, where x is an n-bit word, V is OR operation. It demonstrates that the sequence generated by this T-function has simple algebraic structure, that is, the sum of two elements [xi]j, [Xi+2j-2]j(or [xi]j,[xi+2j-3]j) is connected with [xi]j-1, [xi]j-2(or [xi]j-1, [xi]j--2,[xi]j-3) and [xj]0, [xi]1(or [xi]0, [xi]1, [xi]2), where [x]j represents the j-th bit of x. So if we get a long piece of the generated sequences, then the information of lower level sequence can be partly recovered from the j-th level sequence, thus tail-truncated Klimov-Shamir T-function is not secure enough. 2. Another proof of the sufficient and necessary conditions on whether a polynomial func-tion is a single cycle T-function. Suppose that (x0,x1,…) is the sequence generated by the polynomial function, then we get that the sum of two elements [xi]j and [xi+2j-1]j of the j-th level sequence is equal to [xi]j-1+(?)([xi]1.[xi]0), where (?) is a boolean function.3. Based on the results of 1 and 2, we further analyze the complexity of algebraic structure of sequence (x0,x1,…) generated by single word single cycle T-function f(x)=x+r(x) mod 2n, which is mainly determined by r(x), where r(x) is an even parameter. We also show that the sum of two elements [xi]j, [xi+2j-1]j (or [xi]j,[xi+2j-2]j) is connected with [xi]j-i,[xi]j-2,…, [xi]0, which helps to analyze the security of stream cipher containing single word single cycle T-function.The second part of this dissertation mainly use the theory of finite field, combination to design and analyze the low correlation sequence family used in A-CDMA communication system, more precisely, we have the following results:4. The construction of Bent function is analyzed, then we present the sufficient and nec essary condition whether the linear combination of Gold-like items is a Bent function, then we propose three classes of Bent functions with fast generation. The presentation of Bent sequences is also analyzed, then the trace function representation of Bent sequences is given, thus we can construct Bent sequence family with fast generation from these Bent functions proposed by us.5. By choosing some Gold-like items, we construct four sequence families S1,S2,S3 and S4 with low correlation, where S1 has six-value correlation, for S2,S3 and S4, corresponding to different choices of parameters, S2 and S3 have either six-value correlation or eight-value correla-tion, S4 has either eight-value correlation or ten-value correlation. Compared with the sequence families constructed by Kim and No, our proposed sequence families have better correlation property and large range of parameter choices.6. A class of (p(p+2),p+3,3p+4) interleaved sequence family is constructed from two Legendre sequences of period p and p+2, where p and p+2 are a pair of twin primes and p≡3 mod 4. The linear complexity of this sequence family is the highest among all known sequence families.The third part of this dissertation concentrates on the analysis of ZCZ sequence families used in QS-CDMA communication system. From the ZCZ sequence families constructed by Torii et. al and Hayashi, we mainly consider the construction method of long period ZCZ sequence family generated from an original ZCZ sequence family and an orthogonal sequence family by interleaved structure. The results are as follows: 7. Two basic period extending methods are proposed:1. keeping the family size unchange-able, the multiple of zero correlation zone length extending equals to that of period extending; 2. keeping zero correlation zone length unchangeable or slightly diminished, the multiple of the family size equals to that of period extending. Then we give two construction methods corresponding to these two period extending methods. We use D-matrix to control the zero cor-relation zone length of generated ZCZ sequence family, then we give two classes of D-matrices corresponding to these two period extending methods.8. For the second period extending method, chosen a binary or quaternary sequence family as original sequence family, if period extends 2e times, it can be realized by two methods: (1) period doubles, then recursively use this operation e times; (2) period directly extends 2e times. We present the difference of these two methods, prove that all the ZCZ sequence families generated by (1) can be derived by (2), then we give two classes of ZCZ sequence families generated by (2) that cannot derived by (1).