On Galois NFSRs Equivalent to Fibonacci Ones

摘要

Nonlinear feedback shift registers (NFSRs) are used in many stream ciphers as their main building blocks. According to implementation configurations, NFSRs are generally classified as Fibonacci NFSRs and Galois NFSRs. Compared to Fibonacci NFSRs, Galois NFSRs have potentially shorter propagation time and higher throughput. Moreover, if a Galois NFSR is equivalent to a Fibonacci NFSR in the sense that they have the same set of output sequences, then this particular Galois NFSR can overcome some drawbacks of a general one, and therefore may improve the security of NFSR-based stream ciphers. Previous work has found some types of Galois NFSRs equivalent to Fibonacci NFSRs, and has shown many Galois NFSRs equivalent to a given Fibonacci NFSR with the same stage number. This paper gives another type of Galois NFSRs equivalent to a given Fibonacci NFSR, in which their all corresponding states have either equal or complementary components at the same positions. As an application of this result, the paper shows that the stream ciphers Grain, Trivium and Acorn have used the NFSRs with the lowest cost of hardware implementation among their own equivalent Galois NFSRs of this type. The paper also enumerates the Galois NFSRs equivalent to a given Fibonacci NFSR with the same stage number. Moreover, it reveals some common characterizations of Galois NFSRs that are equivalent to Fibonacci ones from the perspectives of their stage number and feedback functions, helpful to the design of stream ciphers.