What is the maximun period generated by LSFR of degree m?

/ / Published in Cybersecurity, EITC/IS/CCF Classical Cryptography Fundamentals, Stream ciphers, Stream ciphers and linear feedback shift registers

A Linear Feedback Shift Register (LFSR) is a fundamental component in the field of classical cryptography, particularly in the design and implementation of stream ciphers. The maximum period generated by an LFSR of degree m is a topic of significant importance due to its implications on the security and efficiency of cryptographic systems.

An LFSR is essentially a shift register whose input bit is a linear function of its previous state. The 'degree' of an LFSR, denoted as m, refers to the number of stages or flip-flops it contains. The state of the LFSR is typically represented by an m-bit vector, and the linear function that determines the feedback is often represented by a characteristic polynomial.

For an LFSR of degree m, the characteristic polynomial is of the form:

    \[ P(x) = x^m + c_{m-1}x^{m-1} + \cdots + c_1x + c_0 \]

where c_i are coefficients that can be either 0 or 1. The feedback function is defined by this polynomial, and the new bit entering the register is a linear combination of the bits currently in the register, determined by the coefficients c_i.

The maximum period of an LFSR is the length of the sequence before it starts repeating. For an LFSR to achieve its maximum period, the characteristic polynomial must be a primitive polynomial. A primitive polynomial of degree m over the finite field GF(2) (Galois Field of two elements) has the property that it generates all the non-zero elements of GF(2^m) as its sequence of output bits. The maximum period of an LFSR of degree m is:

    \[ 2^m - 1 \]

This period is achieved only if the characteristic polynomial is primitive. If the polynomial is not primitive, the period will be a divisor of 2^m - 1, but it will not reach the maximum possible value.

To illustrate, consider an LFSR of degree 3. The characteristic polynomial for this LFSR could be:

    \[ P(x) = x^3 + x + 1 \]

This polynomial is known to be primitive. Therefore, the LFSR with this characteristic polynomial will have a maximum period of:

    \[ 2^3 - 1 = 7 \]

The sequence generated by this LFSR will go through all possible non-zero 3-bit states before repeating. If we start with an initial state of [1, 0, 0], the sequence of states will be:

1. [1, 0, 0] 2. [0, 1, 0] 3. [0, 0, 1] 4. [1, 1, 0] 5. [0, 1, 1] 6. [1, 0, 1] 7. [1, 1, 1]

After this, the sequence will repeat.

It is important to understand the role of the primitive polynomial in achieving the maximum period. The properties of primitive polynomials are deeply rooted in number theory and algebra. A polynomial P(x) of degree m is primitive if it cannot be factored into polynomials of lower degree over GF(2), and if x is a root of P(x), then x generates the multiplicative group of the field GF(2^m).

Finding primitive polynomials is a non-trivial task. There are known algorithms and tables that list primitive polynomials for various degrees. For practical purposes in cryptographic applications, these precomputed tables are often used to ensure that the LFSR achieves the desired maximum period.

The significance of the maximum period in cryptographic applications cannot be overstated. A longer period implies that the sequence generated by the LFSR will take longer to repeat, which enhances the security of the cryptographic system. In stream ciphers, the keystream generated by the LFSR is used to encrypt the plaintext by combining it with the plaintext bits using the XOR operation. If the period of the LFSR is too short, the keystream will repeat, making the cipher vulnerable to attacks such as the known-plaintext attack.

Consider an example where an LFSR with a non-primitive polynomial is used. Suppose the characteristic polynomial is:

    \[ P(x) = x^3 + x^2 + 1 \]

This polynomial is not primitive. The period of the LFSR with this polynomial will be shorter than 2^3 - 1 = 7. In fact, the period will be 3, as the sequence of states will repeat after 3 steps. Starting with an initial state of [1, 0, 0], the sequence of states will be:

1. [1, 0, 0] 2. [0, 1, 0] 3. [0, 0, 1] 4. [1, 0, 0]

This short period makes the LFSR unsuitable for cryptographic purposes, as the keystream will quickly repeat, exposing the encrypted message to potential attacks.

To ensure the security of stream ciphers, it is essential to use LFSRs with primitive polynomials that guarantee the maximum period. Additionally, the initial state of the LFSR should be chosen carefully to avoid the all-zero state, which would result in a degenerate sequence of all zeros.

In practice, multiple LFSRs are often combined to create more complex keystream generators with longer periods and better statistical properties. One common method is the use of a combination generator, where the outputs of several LFSRs are combined using a nonlinear function. Another method is the use of a shrinking generator, where the output of one LFSR is used to control the output of another LFSR.

The study of LFSRs and their properties is a rich field that intersects with algebra, number theory, and computer science. Understanding the maximum period of an LFSR and the conditions under which it is achieved is fundamental to the design of secure and efficient cryptographic systems.

Other recent questions and answers regarding Stream ciphers and linear feedback shift registers:

View more questions and answers in Stream ciphers and linear feedback shift registers

More questions and answers:

Tagged under: , , , , ,