Research On Nonlinear Feedback Shift Register Sequences

Feedback shift registers (FSRs) have been widely used in modern communication systems, coding theory and cryptography. In cryptography, linear feedback shift regis-ters (LFSRs) are basic components of keystream generators for stream cipher applica-tions. The maximum-length LFSR sequences, called m sequences, have long periods and many good randomness properties. However, they are not cryptographically secure since they have small linear complexities. To design keystream sequences with large complexities, several methods are proposed to modify the m sequences such as com-bining the outputs of several LFSRs by a nonlinear function, nonlinearly filtering states of an LFSR and irregularly clocking an LFSR. With the development of the theory and techniques of correlation attacks and algebraic attacks, the security of the stream ci-phers based on LFSRs have been seriously threatened. The eSTREAM project greatly promoted the development of the design and analysis of stream ciphers. The hardware-oriented finalists in the project like Trivium and Grain utilize nonlinear feedback shift registers (NFSRs) as their main building blocks, and that nonlinear sequences are used as driving sequences has been a new trend in the design of stream ciphers based on feedback shift registers. The stream ciphers based on NFSRs attract more and more attention. However, the theory of NFSRs is not well established, and many basic prob-lems remain open.One of the challenging problems in the theory of NFSR is to construct maximum-length NFSR sequences. The maximum-length NFSR sequences, called de Bruijn se-quences, have many properties such as long periods, large complexities and good ran-domness properties. It is believed that they have a good application prospect in cryp-tography. A general method of constructing de Bruijn sequences is the cycle joining method proposed by Golomb, which is by joining all the cycles produced by an FSRs into a single one. By employing this method, maximum-length NFSRs are created and used to generate de Bruijn sequences. Maximum-length LFSRs, pure cycling registers and pure summing registers have special cycle structure, and have been used to generate de Bruijn sequences by the cycle joining method.The purpose of this paper is to construct new de Bruijn sequences. Specifically, by employing the tools of combinatorics and algebra, we will determine the cycle structure and adjacency graphs of several classes of LFSRs. Then several classes of de Bruijn sequences are constructed by applying the cycle joining method to the LFSRs. The feedback functions of the corresponding maximum-length NFSRs are given. Some fast algorithms for producing the feedback functions are also proposed. These studies have important theoretical and practical value for developing methods and techniques in the design and analysis of stream ciphers based on feedback shift registers.