Research On The Complexity Of Periodic Binary Sequences

Stream ciphers are widely used in commercial,military and diplomatic secrecy systems since they are extremely fast and easy to implement.The security of a stream cipher depends largely on the "randomness" of the keystream,so a central issue in the security analysis of stream ciphers is the quality assessment of keystreams.Most practi-cal keystream generators use feedback shift registers as their main building blocks.For different types of feedback shift registers and attacks against stream ciphers,several complexity measures for sequences are proposed to assess their cryptographic strength,such as linear complexity,?-error linear complexity,nonlinear complexity and 2-adic complexity.These complexity measures are necessary criteria to characterise the un-predictability of sequences,and closely related to the security of corresponding stream ciphers.Discussing about the relationship of different complexity measures,consider-ing how to construct sequences with large complexity,and researching the calculation of the complexity are of great cryptographic significance.In this thesis,we investigate some problems related to linear complexity,nonlinear complexity and 2-adic complexity of periodic binary sequences.The main results are as follows:1.2-Adic complexity of two classes of generalized cyclotomic binary sequences of order 2 is investigated.The sequences in the first class have period p(p+4),and their 2-adic complexity attains the maximum,where both p and p+4 are primes,and gcd(p-1,p+3)= 2.The sequences in the second one have period p2,and their 2-adic complexity also reaches the maximum if p is an odd prime with p(?)5,19(mod 24).That means the aforementioned sequences are safe enough to resist the attack of the rational approximate algorithm.2.New generalized cyclotomic binary sequences of period p2 are proposed in this paper,where p is an odd prime.The sequences are almost balanced and their linear complexity is completely determined.The results show that the proposed sequences can have large linear complexity if p is a non-Wieferich prime,which is equal to or very close to the period.In addition,the numerical result(for small odd primes p)indicates that the cyclotomic sequences constructed in this paper are "good" in terms of the linear complexity profile,the well-distribution measure and the correlation measure of pseudorandom sequences.3.Periodic sequences with period N? 4 and nonlinear complexity N-2,which will be called near maximum nonlinear complexity sequences,are intensively investi-gated.A necessary and sufficient condition for a sequence to achieve near maximum nonlinear complexity is first established.On the basis of this condition,the structure of near maximum nonlinear complexity binary sequences is characterized and a recursive construction of all near maximum nonlinear complexity binary sequences with arbitrary period is proposed.In addition,the exact formula to count the number of the binary near maximum nonlinear complexity sequences of period N,up to shift equivalence,is derived.