Lengthening the Period of a Linear Feedback Shift Register

Abstract

A linear feedback shift register (LFSR) is the basic element of the pseudo-random generators used to generate a sequence of pseudo-random values for a stream cipher. It consists of several cells; each cell is a flip-flop and a feedback function. The feedback function is a linear polynomial function; this function has a degree equal to the number of cells in the register. The basic elements of the register are connected to each other in two different ways, either in Fibonacci mode or in Galois mode. In the best case, the length of an LFSR is equal to two to the power of the number of cells of this register minus one, which is very low for cryptographic applications. To increase this length, one must look for primitive polynomials of great degree or to use adequate methods to lengthen LFSR with a reduced number of cells and, this is the objective of this work. Our method of lengthening of period of a LFSR is based on the logistics map.

Keywords

• LFSR
• LFSR
• cryptography
• stream cipher
• pseudo-random generation
• Fibonacci mode
• Galois mode
• logistic map

References

1. [1] Schneier, B., “Applied Cryptography-Protocols, Algorithms and Source Code in C”, John Wiley & Sounds, Inc, New York, Second Edition, (1996).
2. [2] Menezes, A.J., Oorschot, P.C.V., Vanstone, S. A., “ Handbook of applied cryptography” by CRC Press LLC (1997).
3. [3] George, M., Alfke, P., “Linear feedback shift registers in virtex devices (application note)”_http://www.xilinx.com/bvdocs/appnotes/xapp210.pdf.
4. [4] Goresky, M., Klapper, A., “Fibonacci and galois representations of feedback withcarry shift registers”, IEEE Transactions on Information Theory 48(11) (2002 : 2826-2836.
5. [5] Stackoverflow. “Galois VS Fibonacci LFSR, more computer-friendly but what else?”, novembre 2011, .[https://stackoverflow.com/questions/ 5781458/galois-vs-fibonacci].
6. [6] S. W. Golomb, Shift Register Sequences, Aegean Park Press, Laguna Hills, CA, 1982 (consulté le 21 mars 2018).
7. [7] Nyathi, J., Delgado-Frias, J.G., Lowe, J., “A high-performance, hybrid wave--pipelined linear feedback shift register with skew tolerant clocks” 46th IEEE Midwest Symposium on Circuits and Systems, Cairo, Egypt, In Press, Dec. (2003).
8. [8] Mioc, M.A., Stratulat, M., “Study of software implementation for linear feedback shift register based on 8th degree irreducible polynomials”, International Journal Of Computers 8 (2014) : 46-55.

9. [9] Devaney, L, “A First course in chaotic dynamical systems”, Westview Press Studies in Nonlinearity (1992).
10. [10] Gleick, J., “Chaos: Making a new science”, Albin Michel edition (1987).
11. [11] Knuth, D.E., “The Art of Computer Programming", Addison-Wesley (1998).
12. [12] Berbain, C., “Analysis and design of stream algorithm - in French language - » PhD thesis, University Paris 7. Diderot, (2007).
13. [13] Chen, G., Mao, Y., Chui, C. K., (2004), “A symmetric image encryption scheme based on 3D chaotic cat maps”, Chaos, Solitons and Fractals 21 (2004) : 749-761.
14. [14] Noura, H., “Conception et simulation des générateurs, crypto-systèmes et fonctions de hachage basés chaos performants”, Thèse de Docteur de l’Université de Nantes, (2012).
15. [15] Li, S., Mou, X., Cai, Y., Ji, Z., Zhang, J., “On the security of a chaotic encryption scheme: problems with computerized chaos in finite computing precision”, Computer Physics Communications 153 (1) (2003) : 52-58.