Research On Equivalence Between Galois NFSRs And Fibonacci NFSRs

With the development of cryptanalysis, the stream ciphers based on nonlinear feedbackshifted registers (NFSRs) attract more and more attention. NFSRs contain two types: FibonacciNFSRs and Galois NFSRs. And Fibonacci NFSR is a special type of Galois NFSR. The sequenceof each stage in Fibonacci NFSR is just the shift sequence of the neighbor stage’s. The output ofeach stage in Galois NFSR might be completely different. From this point, Galois NFSRs arepreperable to the cipher design. However, there exist some Galois NFSRs whose set of outputsequences is equal to the one of a Fibonacci NFSR of same stage. So, the output of this type ofGalois NFSR is euqivalent to the one of the Fibonacci NFSR of same stage. This is theEquivalence Problem between Fibonacci NFSRs and Galois NFSRs.In this paper, we mainly study the sufficient and necessary condition of EquivalenceProblem between Fibonacci NFSRs and Galois NFSRs. The main results are,1. A Galois NFSR is equivalent to a Fibonacci NFSR of same stage if and only if the statefunctions of the stage in the Galois NFSR from time0to time n1induce a bijective map overF2n. Furthermore, this map is same to the one between the initial states of the Galois NFSR andthat of the equivalent Fibonacci NFSR when they generate the same sequence. This map is calleda similarity map. A method is proposed to determining the equivalent relationship betweenGalois NFSRs and Fibonacci NFSRs.2. A Galois NFSR is linearly equivalent to a Fibonacci NFSR of same stage if and only ifthe similarity map is linear. The cardinality of the set of Galois NFSRs which are linearlyequivalent to a same Fibonacci NFSR is computed. Then an algorithm is presented to testwhether a given Galois NFSR is linearly equivalent to a Fibonacci NFSR of same stage. Thecomplexity of the algorithm mainly depends on the number of the terms appeared in thefeedback function of the Galois NFSR.3. A Galois NFSR is triangularly equivalent to a Fibonacci NFSR of same stage if and onlyif the similarity map is a triangular map. The feedback functions of Galois NFSRs in this type areformulated. Then the proof of equivalence is given. The relationship between the periods of theoutput of different stages in a Galois NFSR of this type is characterized. Furthermore, a methodto construct an NFSR wiht a guaranteed long period is proposed. It’s remarkable that Graincipher uses Galois NFSR of this type.