GL-S-NFSR: A new NFSR structure and its period properties

Recently nonlinear feedback shift registers (NFSRs) have frequently been used as basic building blocks for stream ciphers. A major problem concerning NFSRs is to construct NFSRs with large periods. In this paper, a new NFSR structure whose period could be theoretically analyzed is proposed and studied, called GL-S-NFSR. A GL-S-NFSR is a selective cascade connection of a primitive Galois LFSR into a standard Galois NFSR with a linear simplified feedback function, where standard Galois NFSRs with linear simplified feedback functions are very useful in stream ciphers, e.g., Trivium. It is proved that the periods of the output sequences of a GL-S-NFSR are lower bounded by the product of all the Zsigmondy primes of \( 2^n-1 \) $2^n-1$ with a probability close to 1 under a weak assumption, and particularly, if n is a prime, then \(2^n-1\) $2^n-1$ divides the periods of the output sequences with a high probability, where n is the stage of the Galois LFSR. Besides, it is also proved that there are several registers satisfying that the periods are multiples of Zsigmondy primes without any assumption. Note that the main building block of Kreyvium consists of a standard Galois NFSR with a linear simplified feedback function and two pure cycling registers (PCRs). Periodic results on GL-S-NFSR are applied to Kreyvium by modifying one PCR to a primitive LFSR and the modified building block of Kreyvium is called M-Kreyvium. It is shown that the sequences involved in M-Kreyvium could have large periods with high probabilities.