Improved transformation between Fibonacci FSRs and Galois FSRs based on semi-tensor product.

Feedback shift registers (FSRs), which have two configurations: Fibonacci and Galois, are a primitive building block in stream ciphers. In this paper, a transformation between Fibonacci FSRs and Galois FSRs is improved based on semi-tensor product (STP) of matrices. It is verified that a weakly equivalent Galois FSR with fewer stages cannot be found for a Fibonacci FSR with n stages, but not vice versa. Furthermore, for a given Fibonacci FSR with n stages, there are totally (2 n − 1) ! 2 − 1 weakly equivalent Galois FSRs. Additionally, an effective algorithm is developed to reduce the number of variables of the Galois FSRs while keeping it weakly equivalent to the given Fibonacci FSR. Finally, the feasibility of the proposed strategies is demonstrated by numerical examples. [ABSTRACT FROM AUTHOR]