An equivalence preserving transformation from the Fibonacci to the Galois NLFSRs

2008/01/28 by Elena Dubrova, Dubrova, Elena
Computer Science · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Security (cs.CR) #Error Correcting Code Techniques #FOS: Computer and information sciences #cs.CR

paper · pdf · doi:10.48550/arxiv.0801.4079

14 pages, 4 figures, one reference added, example 4 corrected

openalex publication_date 2008/01/28 · arxiv created 2008/01/30 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Conventional Non-Linear Feedback Shift Registers (NLFSRs) use the Fibonacci configuration in which the value of the first bit is updated according to some non-linear feedback function of previous values of other bits, and each remaining bit repeats the value of its previous bit. We show how to transform the feedback function of a Fibonacci NLFSR into several smaller feedback functions of individual bits. Such a transformation reduces the propagation time, thus increasing the speed of pseudo-random sequence generation. The practical significance of the presented technique is that is makes possible increasing the keystream generation speed of any Fibonacci NLFSR-based stream cipher with no penalty in area.

Related

• An improved transformation between Fibonacci FSRs and Galois FSRs
• Fibonacci and Galois representations of feedback-with-carry shift registers
• Generalized NLFSR Transformation Algorithms and Cryptanalysis of the Class of Espresso-like Stream Ciphers
• An Algorithm for Constructing a Smallest Register with Non-Linear Update Generating a Given Binary Sequence
• Vectorial Feedback with Carry Registers and Memory requirements