Isomorphism and Equivalence of Galois Nonlinear Feedback Shift Registers

Nonlinear feedback shift registers (NFSRs) have been used in many recent stream ciphers. They are generally classified as Fibonacci NFSRs and Galois NFSRs in terms of their implementation configurations. Two NFSRs are said to be isomorphic if their state diagrams are isomorphic, and two NFSRs are equivalent if their sets of output sequences are equal. Equivalent NFSRs must be isomorphic NFSRs, but not the vice versa. Previous work has been done on the isomorphism and equivalence of Fibonacci NFSRs. This paper continues this research for Galois NFSRs. It first gives some characterizations for several kinds of isomorphic Galois NFSRs, which improves and generalizes the previous corresponding results for Fibonacci NFSRs. It then presents some characterizations for two kinds of equivalent Galois NFSRs, helpful to the design of NFSR-based stream ciphers.