Title: On two circuit configurations of non-linear feedback shift registers

Authors: Zhiqiang Lin

Addresses: College of Mathematics and Information Science, Guangzhou University, Guangzhou 510006, China; Key Laboratory of Mathematics and Interdisciplinary Sciences of Guangdong, Higher Education Institutes, Guangzhou University, Guangzhou 510006, China

Abstract: 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.

Keywords: RFID; radio frequency identification; smartcards; wireless networks; pseudo-random sequence; key stream generators; security; cryptography; stream ciphers; linear feedback shift register; LFSR; nonlinear feedback shift register; NLFSR; Fibonacci circuit configuration; Galois circuit configuration.

DOI: 10.1504/IJICT.2015.068378

International Journal of Information and Communication Technology, 2015 Vol.7 No.2/3, pp.185 - 201

Received: 01 Oct 2013
Accepted: 08 Nov 2013
Published online: 01 Apr 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article