Periods Of Sequences Generated By The Cascade Connection Of Feedback Shift Registers

Feedback shift registers are important building blocks in key stream generators of stream ciphers,which are divided into linear feedback shift registers(LFSRs)and nonlinear feedback shift registers(NFSRs).For Grain,the finalist in the eSTREAM project,the design is based on the cascade connection of an LFSR into an NFSR to resist some cryptographic attacks,such as algebraic attacks and correlation attacks.The cascade connection has been studied since 1970s.However,for a sequences generated by the cascade connection,its many cryptographic properties are still unknown,such as the period and the linear complexity.One of the most attractive problems is to construct the cascade connection such that it could output sequences with long periods and desired cryptographic properties.On the contrary,the cascade connection should avoid outputting a sequence of short period in practice.In this paper,we will study periods of sequences generated by the cascade connec-tion of feedback shift registers.For the cascade connection,its period is defined as the period of the longest it generates.By using the tools of combinatorics and algebra,we will establish an upper bound for the periods of two kinds of cascade connections,the cascade connection of an NFSR into an LFSR and of an LFSR into an LFSR.Moreover,for the cascade connection of an NFSR into an LFSR,a necessary and sufficient con-dition to achieve this bound is proposed.Based on previous work on LFSR sequences,by using combination tools,we propose two classes of(n+n)-stage Grain-like NFSRs such that the minimal period 2n-1 is achievable,where n is a positive integer.This partly answers the open problem proposed by Hu and Gong.Finally,by employing the Boolean network approach and some properties of the cascade connection,we will also give a method and some corresponding algorithms to determine the period of a sequence generated by the cascade connection of two feedback shift registers.