Analysis Of Cryptographic Properties Of Two Classes Of Pseudorandom Sequences

Pseudorandom sequences witness wide applications in spread spectrum com-munication system,radar navigation systems and stream ciphers.With the further development of the research,according to different key stream generators and attack on stream ciphers,scholars have proposed many indexes to measure the security of a sequence.Linear complexity and k-error linear complexity are the two of important indexes.They characterize the unpredictability of a sequence,thereby measuring whether the sequence is suitable for the domain of cryptography.By the Berlekamp-Messey(B-M)algorithm,the linear complexity of a good sequence must not be less than the half of its period,but also under small perturbations must not cause a drastic decrease of the linear complexity.This dissertation investigates the linear complexity of binary sequences derived from Euler quotients modulo 2pm,where p is an odd prime and integer m? 1.The linear complexity and k-error linear complexity of the binary generalized cyclotomic sequences with a period 2pm are examied,where p is an odd prime,m?2 and(p2-/2?k<p2-p.The main work is as follows:(1).Based on the construction presented by Zhang et al.,according to the theory of residue class ring,a new classes of binary sequences with period 2pm+1 is constructed using Euler quotients modulo 2pm.Under the condition of 2p-1?1(mod p2),the linear complexity of the sequence is examined with method of determining the roots of polynomial over finite field F2.Finally,the correctness of the result is verified by Magma program.(2).First,we demonstrate the conjecture of Ouyang et al.,that is,the linear complexity of binary generalized cyclotomic sequences with a period of 2pm is determined.Secondly,using the method presented by Wu et al.,the bounds of k-error linear complexity of the sequences are given,under the condition that 2 is a primitive root modulo p2 and(p2-1)/2?k<p2-p.The results show that the two kinds of sequences have large linear complexity and k-error linear complexity,respectively.The former can resist the attack of B-M algorithm and the latter has better stability.They are good pseudorandom sequences from the viewpoint of cryptography.