Research On Cryptographic Properties Of Pseudorandom Sequences Based On Discrete Logarithm

Cryptography is a key technology to ensure network and information security.Pseudorandom sequences have extremely important applications in many fields such as cryptography,communications,radar navigation,remote control and measurement,various noise sources,and so on.The security of stream ciphers depends on the cryptographic properties of the pseudorandom sequence used as the key stream.Therefore,constructing pseudorandom sequences and analyzing their cryptographic properties are the key research contents of stream ciphers.Two European cryptographic research projects:NESSIE(New European Schemes for Signatue,Integrity,and Encryption),ECRYPT(European Network of Excellence for Cryptology),and Chinese commercial cryptographic algorithm—ZUC stream cipher algorithm was adopted as international encryption standards,which greatly promoted the research of modern stream ciphers.Legendre sequence is a kind of pseudorandom sequence with many good cryptographic properties,such as high linear complexity,ideal autocorrelation,good random distribution,large 2-adic complexity,and so on.Legendre sequence is considered to be a typical representative of cyclotomic binary sequences modulo prime number.In recent years,based on arithmetical functions such as Fermat quotient and Euler quotient,as well as the newly proposed Zeng-Cai-Tang-Yang(ZCTY for short)generalized cyclotomy,many pseudorandom sequences with good cryptographic properties have been constructed,which draws increasing attentions from scholars.Since the mathematical structures on which these pseudorandom sequences have been constructed are all related to(or can be transformed to)discrete logarithms,these sequences together are called pseudorandom sequences based on discrete logarithms in this dissertation.The stability of a sequence(i.e.k-error linear complexity)is critical to the application of the sequence.The trace representation of a sequence is an important method for generating the sequence and analyzing the cryptographic properties of the sequence.In this dissertation,the above pseudorandom sequences based on discrete logarithm are studied,and the main contributions are three-folded as follows.1.Research the cryptographic properties of classical cyclotomic sequences such as Legendre sequence,Ding-Helleseth-Lam sequence and Hall's sextic residue sequences.(1)This dissertation gives the trace representations of Legendre sequence over non-binary fields,which provides a method for analyzing the cryptographic properties of Legendre sequence over non-binary fields.For example,the linear complexity of the Legendre sequence over non-binary fields can be directly calculated,and the results are completely consistent with the existing results.By using Discrete Fourier Transform(DFT)of the Legendre sequence,Ding-Helleseth-Lam sequence and Hall's sextic residual sequence,this dissertation obtains the Mattson-Solomon polynomials over the binary field of these sequences.Based on the obtained Mattson-Solomon polynomial,this dissertation derives the trace representations of the Ding-Helleseth-Lam sequence over the binary field.(2)By using Discrete Fourier Transform,this dissertation determines the 1-error linear complexity of the Legendre sequence,Ding-Helleseth-Lam sequence and Hall's sextic residual sequence.Furthermore,by introducing the DFT-leader-vector,this dissertation investigates the k-error linear complexity of these three kinds of sequences over the binary field under several conditions of the order of 2 modulo p,where p is the period of these sequences.This dissertation also gives concrete examples to verify the correctness of the results.The obtained results solve the stability problem of the above three kinds of classical cyclotomic binary sequences,and the method used can be further applied to solve the trace representation problem of other cyclotomic sequences.2.Research the stability of the generalized cyclotomic sequences related to the Fermat/Euler quotients.(1)Using the method of matrix structure analysis,this dissertation studies the k-error linear complexity of the Fermat quotient sequence,and the results show that the stability of the Fermat quotient sequence is very good.Moreover,this dissertation presents a fast algorithm for calculating the k-error linear complexity of a q-ary sequence with odd prime square period,and uses some examples to compare the efficiency of the proposed algorithm with the existing classical algorithm.The results show that the proposed algorithm in this dissertation is more efficient than the existing classical algorithm.(2)Using the decimal sequence analysis method,this dissertation studies the k-error linear complexity of a binary 2p~2periodic sequence based on Euler quotient modulo 2p,this sequence is the first sequence that was constructed from Euler quotient whose period has two diffirent primes.The results show that the sequence has good stability.Furthermore,this dissertation studies the k-error linear complexity of the q-ary sequence with period p~rbased on Euler quotient,defines a q-ary sequence with period2p~rand studies the k-error linear complexity of it.The results show that the k-error linear complexity of the Euler quotient q-ary sequence with periodic 2p~ris twice as that of the Euler quotient q-ary sequence with periodic p~r(r32,q(29)2).This dissertation gives concrete examples to verify the correctness of the above results.The above results and with the existing results solve the stability problem of the Fermat/Euler quotient binary or q-ary sequences with periods of p~ror 2p~r.3.Research the cryptographic properties of the newly generalized cyclotomic binary sequences based on ZCTY generalized cyclotomy.(1)This dissertation studies the k-error linear complexity of the first construction of binary sequence with period p~2based on ZCTY generalized cyclotomy,which was proposed by Z.Xiao et al.in 2018.In the construction of Z.Xiao et al.,the parameter f is required to be power of 2 where f|(p-1).This dissertation not only proves the stability of this kind of sequence,but also only requires the parameter f be an even number which restriction is weaker than Z.Xiao et al.'s construction.(2)A conjecture on the linear complexity of a binary sequence of period p~nbased on ZCTY generalized cyclotomy was proposed by Z.Xiao et al.This dissertation not only proves the conjecture,but also gives a general definition of a binary sequence of period p~nbased on ZCTY generalized cyclotomy,where the value of the parameter f is no longer restricted.By establishing the recurrence relationship,this dissertation also studies the k-error linear complexity of the ZCTY generalized cyclotomic binary sequence with period p~ndefined by Z.Xiao et al.Moreover,this analysis method is extended to study the k-error linear complexity of the ZCTY generalized cyclotomic binary sequence with period 2p~nthat was proposed by Professor Yi Ouyang et al.in2019.This dissertation also gives concrete examples to verify the correctness of the aobove results.The results obtained in this dissertation solve the stability problem of the ZCTY generalized cyclotomic binary sequences with periods of p~nor 2p~n(n?2).