Construction of Maximum Period Linear Feedback Shift Registers (LFSR) (Primitive Polynomials and Linear Recurring Relations)
Babacar Alassane Ndaw
Central Technical Service of Cipher and Information Security Systems, Graduated of the Centre of Superior Cryptographic Studies of Paris, Department of Mathematics and Computer Science, University Cheikh Anta Diop, Dakar, Senegal.
Djiby Sow
Department of Mathematics and Computer Science, University Cheikh Anta Diop, Dakar, Senegal.
Mamadou Sanghare *
Department of Mathematics and Computer Science, University Cheikh Anta Diop, Dakar, Senegal.
*Author to whom correspondence should be addressed.
Abstract
Feedback Shift Register (FSR) is generally the basic element of pseudo random generators used to generate cryptographic channel or set of sequences for encryption keys. This type of generator is widely used in stream cipher and communication systems such as C.D.M.A (Code Division Multiple Access), mobile communication systems, ranging and navigating systems, spread spectrum communication systems.
The objective of the present paper is to propose a method for determining linear recurring sequences generating linear feedback shift register (LFSR) from primitive polynomials (and vice-versa). The linear recurring sequences facilitate the construction of maximum length LFSR. It also insists, in the last part, on the cryptographic security of LFSR and indicates some open problems in the area of nonlinear feedback shift registers (NLFSR) based pseudo random generators.
Keywords: Pseudo random generator, linear feedback shift register (LFSR), nonlinear feedback shift register (NLFSR), primitive feedback polynomial, linear recurrence, cryptographic security.