On two circuit configurations of non-linear feedback shift registers

摘要

Key-stream generators are widely used in many areas, such as digital signal processing, radar ranging, Monte Carlo simulation, spread spectrum communications, steganography, cryptography devices, etc. Non-linear feedback shift register (NLFSR) is one of the most popular devices which is used to construct key-stream generators. Conventional NLFSRs use the Fibonacci circuit configuration, in which the feedback is applied to the last bit only. The Galois configuration, in which the feedback can be applied to every bit, is attractive to key-stream generators, to which high throughput is very important. In this paper, the transformation from Galois NLFSRs to their equivalent Fibonacci configuration is proposed. By this transformation, the relationship between these two circuit configurations of NLFSRs is clear. A method of matching initial states between two equivalent NLFSRs is derived. Moreover, some properties of Galois NLFSRs are presented. The results of this paper are useful in analysis of stream ciphers based on Galois NLFSRs.