Combinatorial Construction And Cryptographic Properties Analysis Of Pseudorandom Sequences

Pseudo-random sequences have a wide range of applications in communication systems,radar navigation,spread spectrum communication,stream ciphers and other fields.The indicators for measuring the pseudorandomness of sequences mainly include periodicity,balance,autocorrelation,linear complexity,2-adic complexity,4-adic complexity and so on.Therefore,it is an important topic to study the construction of pseudo-random sequences and analyze their cryptographic properties.This thesis focuses on the construction method and linear complexity of binary interleaved sequences with period 2N and 4N,and the construction method and 4-adic complexity of quaternary interleaved sequences with period 2N.The main research results are as follows.(1)Based on the interleaving and concatenation methods,two new classes of binary interleaved sequences with period 4N are constructed.By calculating the number of polynomial zeros,the linear complexity of binary interleaved sequences constructed by Legendre sequences and Hall sequences over finite fields of characteristic 2 is obtained.The results show that the linear complexity of the constructed new sequences can reach 3N+1,which is greater than half of the period of sequences,and can resist the attack of Berlekamp-Massey(B-M)algorithm.These sequences can be viewed as two classes of pseudo-random sequences with good cryptographic properties.(2)A new class of binary interleaved sequences with period 2N is constructed based on sign alternation transformation and interleaving techniques.Three kinds of sequence pairs,namely Legendre sequence pair,Twin-prime sequence pair and GMW sequence pair,are selected as the base sequences,and the exact value of the linear complexity of the sequence over the finite field F2 is obtained.When the base sequences are Legendre sequence pair and GMW sequence pair,the linear complexity is 2N;when the base sequence is Twin-prime sequence pair,the linear complexity is 2N-1.The results show that the linear complexity of the sequence is greater than half of the period,and can reach the maximum under certain conditions,which is a good pseudo-random sequence.(3)A new class of quaternary interleaved sequences is constructed by using interleaving technique and Gray mapping.And taking Twin-prime sequence pair and GMW sequence pair as the base sequences,the 4-adic complexity of quaternary interleaved sequences with period 2N is studied.The results show that the 4-adic complexity of the sequence can reach the maximum,which is enough to resist the attack of rational approximation algorithm.