Research On Several Cryptographic Properties Of Primitive σ-lfsr

Along with the development of NESSIE and eSTREAM projects, stream ciphers are becoming one of focuses of cryptology research in the past years.σ-LFSR could generate sequences with better cryptographic properties on fewer basic instructions of computer, so the characters of high efficiency and low-level resource consumption are suitable for the design of driven component of stream ciphers.Primitiveσ-LFSR has the advantages of maximal period and well pseudorandom properties, so its application values are very important. With the interrelated knowledge of finite field, LFSR and matrix polynomial, our research is focused on the interval vectors, linear complexity and decimation sequences of primitiveσ-LFSR. Our contributions to the field are as follows:The first part studies the interval vectors of primitiveσ-LFSR. By proving the equivalent sequences have the same interval vectors, we indicate that interval vectors are one character of primitiveσ-LFSR. Then with the analysis of the interval vectors of primitive LFSR based on word, a sufficient and necessary condition for one interval vector to be a primitive LFSR is given. At last, the interval vectors of primitiveσ-LFSR are studied, some properties of primitiveσ-LFSR are offered and a search algorithm constructing primitiveσ-LFSR sequences is obtained.The second part discusses the linear complexity of primitiveσ-LFSR. Firstly, we point out that the linear complexity of primitiveσ-LFSR on 2mF is kn where k is an integer from 1 to m. Secondly, we study the distributing for the linear complexity of primitiveσ-LFSR from the sum of sequences: it is proved that the upper bound of the linear complexity is tight and a class of primitiveσ-LFSR sequences with maximal linear complexity is constructed; with the trace representation of coordinate sequences, it is proved that the k above can get all values of integer from 1 to m; then the lower bound of expection and the upper bound of variance about primitiveσ-LFSR are given; in particular, when m is 8 and n is 16, the valus are 0.99999mn and 0.1 respectively, so it is illuminated that the linear complexity of primitiveσ-LFSR concentrates on the upper bound; menanwhile, we get a lower bound of the counting about primitiveσ-LFSR with the similar method. At last, with the tools of root representation and circulant matrix, two methods to calculate the linear complexity of primitiveσ-LFSR sequence are obtained.The third part analyzes the decimation sequences'properities of primitiveσ-LFSR. By reviewing the decimation sequence's interval vector of primitiveσ-LFSR, the idiographic expression of the interval vector is given. Comparing with the decimation properties of primitive LFSR, we indicate that the primitiveσ-LFSR is different from primitive LFSR distinctly: there are some t decimation sequences not primitive where t is coprime with the sequence's period, and then two results about the primitive properity of decimation sequences are obtained. At last, it is proved that the linear complexity of decimation sequence about primitiveσ-LFSR is the same as the original sequence.