In a shift register with a linear feedback there are two parts (modules): the shift register itself and the circuit (or subroutine) that calculates the value of the inserted bit. The register consists of function cells (or bits of a machine word or several words), each of which stores the current state of one bit. The number of cells is called the length of the register. Bits (cells) are usually numbered by numbers, each of which is capable of storing a bit, and the calculated bit is pushed into the cell, and the next generated bit is pulled out from the cell. The calculation of the inserted bit is usually performed before the shift of the register, and only after the shift is the value of the calculated bit placed in the cell.

The period of the shift register is the minimum length of the resulting sequence before it starts to repeat. Since the register of bit cells has only different non-zero states, then, in principle, the period of the register cannot exceed this number. If the period of the register is equal to this number, then such a register is called the register of the maximum period.

For LFSR, the feedback function is a linear Boolean function of the states of all or some bits of the register. For example, the sum modulo two or its logical inverse is a linear Boolean function (XOR operation, denoted as in formulas) and is most often used in such registers.

At the same time, those bits that are function variables feedback, commonly referred to as bends.

Register control in hardware implementations is performed by applying a shift pulse (otherwise called clock or sync pulse) to all cells, in software - by executing a program cycle, including the calculation of the feedback function and bit shift in the word.

During each clock tick, the following operations are performed:

Linear Feedback Shift Register

Thus, as a feedback function, we take logical operation XOR (exclusive OR), that is:

Properties of primitive polynomials

Properties

The properties of the sequence produced by LFSR are closely related to the properties of the associated polynomial. Its non-zero coefficients are called bends, as well as the corresponding cells of the register, supplying the values ​​of the arguments of the feedback function.

Linear complexity

The linear complexity of a binary sequence is one of the most important characteristics of LFSR operation. Let us introduce the following notation:

The linear complexity of an infinite binary sequence is called a number, which is defined as follows:

The linear complexity of a finite binary sequence is called the number , which is equal to the length of the shortest LFSR, which generates a sequence that has as the first terms .

Linear Complexity Properties

Let and be binary sequences. Then:

Correlation Independence

To get high linear complexity, cryptographers try to non-linearly combine the results of multiple output sequences. In this case, the danger is that one or more output sequences (often even the outputs of individual LFSRs) can be connected by a common key stream and uncovered using linear algebra. Hacking based on such a vulnerability is called correlation autopsy. Thomas Siegenthaler has shown that correlation independence can be precisely defined, and that there is a trade-off between correlation independence and linear complexity.

The main idea of ​​such a hack is to find some correlation between the output of a generator and the output of one of its constituent parts. Then, by observing the output sequence, information about this intermediate output can be obtained. Using this information and other correlations, it is possible to collect data on other intermediate outputs until the generator is hacked.

Correlation attacks or variations such as fast correlation attacks have been successfully used against many linear feedback shift register based keystream generators, which involve a trade-off between computational complexity and efficiency.

Example

For LFSR with an associated polynomial, the generated sequence has the form . Suppose, before the start of the process, the sequence is written in the register, then the period of the generated bit stream will be equal to 7 with the following sequence:

Since the internal state at the seventh step returned to its original state, then, starting from the next step, there will be a repetition. In other words, the period of the sequence turned out to be equal to 7, which happened due to the primitiveness of the polynomial.

Algorithms for generating primitive polynomials

Ready tables

Calculating the primitiveness of a polynomial is a fairly complex mathematical problem. Therefore, there are ready-made tables that list the numbers of tap sequences that provide the maximum period of the generator. For example, for a 32-bit shift register, there is a sequence . This means that to generate a new bit, it is necessary to sum the 31st, 30th, 29th, 27th, 25th and 0th bits using the XOR function. The code for such LFSR in the C language is as follows:

Int LFSR (void ) ( static unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); return S & 1 ; )

Software implementations of RSLOS generators are quite slow and work faster if they are written in assembler rather than in C. One solution is to use 16 RLLS in parallel (or 32, depending on the word length in the architecture of a particular computer). In such a scheme, an array of words is used, the size of which is equal to the length of the LFSR, and each bit of the array word refers to its LFSR. Provided that the same tap sequence numbers are used, this can give a noticeable performance gain. [need sample code] (See: bitslice).

Galois configuration

Galois configuration of a linear feedback shift register

The feedback scheme can also be modified. In this case, the generator will not have greater cryptographic strength, but it will be easier to implement it programmatically. Instead of using the bits of the tap sequence to generate a new leftmost bit, XOR each bit of the tap sequence with the output of the generator and replace it with the result of this action, then the result of the generator becomes the new leftmost bit. In C language it looks like this:

Int LFSR (void ) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

The benefit is that all XORs are performed in one operation.

• it can be proved that the Fibonacci configuration given first and the Galois configuration given here give the same sequences (of length 2 32 −1), but shifted in phase from one another
• a loop of a fixed number of calls to the LFSR function in the Galois configuration is approximately twice as fast as in the Fibonacci configuration (MS VS 2010 compiler on Intel Core i5)
• note that in the Galois configuration, the order of the bits in the feedback word is reversed compared to the Fibonacci configuration

Generator examples

stop-go generators

Alternating stop-and-go generator

This oscillator uses the output of one LFSR to control the clock frequency of another LFSR. The clock output of RSLOS-2 is controlled by the output of RSLOS-1, so that RSLOS-2 can change its state at time t only if the output of RSLOS-1 at time t-1 was equal to one. But this scheme did not resist the correlation opening.

Therefore, an improved generator based on the same idea has been proposed. It is called the stop-and-go interleaved generator. It uses three LFSRs of different lengths. LFSR-2 is clocked when the output of LFSR-1 is equal to one, and LFSR-3, when the output of LFSR-1 is equal to zero. The output of the generator is the modulo 2 sum of RSLOS-2 and RSLOS-3. This generator has a large period and a large linear complexity. Its authors also showed a method for the correlation opening of RLOS-1, but this does not greatly weaken the generator.

Gollmann Cascade

Gollmann Cascade

The Gollmann Cascade is an enhanced version of the stop-go generator. It consists of a sequence of LFSRs, the timing of each of which is controlled by the previous LFSR. If the output of LFSR-1 at time t is 1, then LFSR-2 is clocked. If the output of LFSR-2 at time t is 1, then LFSR-3 is clocked, and so on. The output of the last LFSR is the output of the generator. If the length of all LFSRs is the same and equals n, then the linear complexity of the system of k LFSRs is .

This idea is simple and can be used to generate sequences with huge periods, large linear complexities, and good statistical properties. But, unfortunately, they are susceptible to an opening, called "locking" (lock-in). For greater stability, it is recommended to use k at least 15. Moreover, it is better to use more short LFSR than less long LFSR.

threshold generator

threshold generator

This generator attempts to circumvent the security issues of previous generators by using a variable number of shift registers. In theory, when applied more shift registers, the complexity of the cipher increases, which was done in this generator.

This generator consists of a large number of shift registers, the outputs of which are fed to the majorization function. If the number of units at the outputs of the registers is more than half, then the generator produces a unit. If the number of zeros on the outputs is more than half, then the generator produces a zero. In order for the comparison of the number of zeros and ones to be possible, the number of shift registers must be odd. The lengths of all registers must be relatively prime, and the feedback polynomials must be primitive so that the period of the generated sequence is maximum.

For the case of three shift registers, the generator can be represented as:

This generator is similar to the Geff generator, except that the threshold generator has more linear complexity. Its linear complexity is:

where , , are the lengths of the first, second and third shift registers.

Its disadvantage is that each output bit gives some information about the state of the shift register. More precisely, 0.189 bits. Therefore, this generator may not resist the correlation opening.

Other types

Self-thinning

Self-decreasing generators are called generators that control their own frequency. Two types of such generators have been proposed. The first one consists of a linear feedback shift register and some circuit that clocks this register, depending on what the output values ​​of the shift register are. If the LFSR output is equal to one, then the register is clocked d times. If the output is zero, then the register is clocked k times. The second one has almost the same design, but somewhat modified: in the clocking circuit, as a check for 0 or 1, not the output signal itself, but XOR of certain bits of the shift register with linear feedback, is received at the input. Unfortunately, this kind of generator is not safe.

Multirate oscillator with inner product

This generator uses two shift registers with linear feedback with different clock frequencies: LFSR-1 and LFSR-2. Clock frequency RLOS-2 is d times larger than RLOS-1. The individual bits of these registers are combined with an AND operation. The outputs of the AND operation are then XORed. The output sequence is taken from this XOR block. Again, this generator is not perfect (It did not survive the opening of linear consistency. If - the length of LFSR-1, - the length of LFSR-2, and d is the ratio of clock frequencies, then the internal state of the generator can be obtained from the output sequence of length ), but it has high linear complexity and excellent statistical performance.

Feedback shift register consists of two parts: the shift register and feedback functions.

Figure 19. Feedback shift register.

In general, a shift register is a sequence of some elements of a ring or field. Most commonly used bit shift registers. The length of such a register is expressed as a number of bits. Each time a bit is retrieved, all bits in the register are shifted to the right by one position. The new most significant bit is calculated as a function of all other bits in the register. The output is usually the least significant bit. The period of the shift register is the length of the output sequence before it begins to repeat.

The simplest type of shift registers is a linear feedback shift register (LFSR or LRS). Feedback - simple operation XOR over some bits of the register. The list of these bits is defined characteristic polynomial and called tap sequence. Sometimes this scheme is called Fibonacci configuration.

Fig.20. LFOS of the Fibonacci configuration.

In the software implementation of LFSR, a modified scheme is used: to generate a new significant bit, instead of using the bits of the tap sequence, an XOR operation is performed on each of its bits with the output of the generator, replacing the old bit of the tap sequence. This modification is sometimes called Galois configuration.

Fig.21. RLOS of the Galois configuration.

n-bit LFSR can be in one of 2 n– 1 internal states. This means that, theoretically, such a register can generate a pseudo-random sequence with a period of 2 n– 1 bits (padding with zeros is completely useless). Passage of all 2 n– 1 internal states only possible with certain tap sequences. Such registers are called LFSR with a maximum period. To ensure the maximum period of LFSR, it is necessary that its characteristic polynomial be primitive modulo 2. The degree of the polynomial is the length of the shift register. Primitive degree polynomial n- it's such irreducible a polynomial that is a divisor but is not a divisor x d+ 1 for all d, which are divisors of 2 n– 1. (When discussing polynomials, the term Prime number replaced by the term irreducible polynomial). The characteristic polynomial of the LFSR shown in the figures:

x 32 + x 7 + x 5 + x 3 + x 2 + x + 1

is primitive modulo 2. The period of such a register will be maximum, cycling through all 2 32 - 1 values ​​until they repeat. The most commonly used are thinned polynomials, i.e. which have only some coefficients. the most popular trinomials.

An important parameter of the generator based on LFSR is linear complexity. It is defined as the length n the shortest LFSR that can simulate the generator output. Linear complexity is important because with a simple Berlenkamp-Massey algorithm it is possible to recreate such a LFSR by checking only 2 n gamma bits. With the definition of the desired LFSR, the stream cipher is actually broken.

To build stream ciphers, sequences on shift registers are very often used. A feedback shift register consists of two parts: a shift register and a feedback function, as shown in Fig. 87. The shift register itself is a sequence of bits, the number of which determines the length of the register. So, if n bits are involved in the register, then they say that the n-bit shift register. Each time a bit is retrieved, all bits of the shift register are shifted to the right by one position, usually towards the least significant bits. The period of the shift register is the length of the resulting sequence before it begins to repeat.

Rice. 87.

Any mathematical function that performs an operation on bits can act as feedback. The simplest type of feedback shift register is the linear feedback shift register (LFSR). In LFSR, feedback is simply a modulo 2 addition (XOR) operation on some bits of a register; the list of these bits is called a sequence of taps, or pickup points, as shown in fig. 88. Sometimes such a pattern is called a Fibonacci configuration. Due to the simplicity of the feedback sequence, a fairly developed mathematical theory can be used to analyze LFSR. In any case, the quality of the produced SRP is evaluated by a special set of tests.

Rice. 88.

LFSR are written in the form of polynomials. In this case, the degree of the first element of the polynomial indicates the number of bits in the shift register, and the exponential exponents of the remaining members of the polynomial indicate which pickup points will be used. So, for example, writing x 4 + x + 1 means that a register of four elements will be used, for which bits bi and b 0 will participate in the formation of feedback (Fig. 89).

Rice. 89.4

Consider the operation of the register shown in Fig. 89. Initialize it, for example, with the value 0101 (the initial initialization can be performed by any sequence of bits, except for a sequence of only zeros, since in this case the feedback will always form a value of zero and the register will not produce the expected PSP). So, in the register there is a shift to the right by one position. The least significant bit, equal to 1, is forced out of the register and forms the first bit of the PRS. Those bits that were in positions b, and b 0 before the shift are added modulo 2 and form a new

high bit of the register. An illustrative example of the operation of the considered LFSR is shown in fig. 90.

Rice. 90.

As can be seen from fig. 90, the register filling will go through a weight of 15 out of 16 possible states (we previously determined that the sixteenth state, when LFSR is 0000, cannot be considered). After that, the filling of the register will again be equal to the initial value of 0101, and the generation of the bit sequence will begin to repeat. The output sequence of the register will be a string of least significant bits (up to horizontal line in fig. 90): 101011110001001. The size of a bit sequence before it is repeated is called a period. To ensure the maximum period of a particular LFSR (i.e., in order for the register to go through the weight of possible internal states), the polynomial that determines the operation of the register must be primitive modulo 2. As in the case of large prime numbers, there is no way to generate such polynomials. One can only take a polynomial and check whether it is irreducible modulo 2 or not. In the general case, a primitive polynomial of degree n is such an irreducible polynomial that is a divisor of x 2 "+1, but is not a divisor of x d +1 for all d that are divisors of 2 "-1. A table of some polynomials is given in the work of B. Schneier, which are irreducible modulo 2.

Summarizing the knowledge obtained as a result of considering the example of the operation of LFSR (Fig. 90), we can say that the n-bit LFSR can be in one of the 2”-1 internal states. Theoretically, such a register can generate a pseudo-random sequence with a period of 2 n -1 bits. Such registers are called LFSR registers with a maximum period. The resulting output is called a t-sequence.

In the shift register with linear feedback, two parts (modules) are distinguished: the shift register itself and the circuit (or subroutine) that calculates the value of the inserted bit. The register consists of function cells (or bits of a machine word or several words), each of which stores the current state of one bit. The number of cells is called the length of the register. Bits (cells) are usually numbered by numbers, each of which is capable of storing a bit, and the calculated bit is pushed into the cell, and the next generated bit is pulled out from the cell. The calculation of the inserted bit is usually performed before the shift of the register, and only after the shift is the value of the calculated bit placed in the cell.

The period of the shift register is the minimum length of the resulting sequence before it starts to repeat. Since the register of bit cells has only different non-zero states, then, in principle, the period of the register cannot exceed this number. If the period of the register is equal to this number, then such a register is called the register of the maximum period.

For LFSR, the feedback function is a linear Boolean function of the states of all or some bits of the register. For example, the sum modulo two or its logical inverse is a linear Boolean function (XOR operation, denoted as in formulas) and is most often used in such registers.

In this case, those bits that are variables of the feedback function are usually called bends.

Register control in hardware implementations is performed by applying a shift pulse (otherwise called clock or sync pulse) to all cells, in software - by executing a program cycle, including the calculation of the feedback function and bit shift in the word.

During each clock tick, the following operations are performed:

Linear Feedback Shift Register

Thus, the logical operation XOR (exclusive OR) is taken as a feedback function, that is:

Properties of primitive polynomials

Properties

The properties of the sequence produced by LFSR are closely related to the properties of the associated polynomial. Its non-zero coefficients are called bends, as well as the corresponding cells of the register, supplying the values ​​of the arguments of the feedback function.

Linear complexity

The linear complexity of a binary sequence is one of the most important characteristics of LFSR operation. Let us introduce the following notation:

The linear complexity of an infinite binary sequence is called a number, which is defined as follows:

The linear complexity of a finite binary sequence is called the number , which is equal to the length of the shortest LFSR, which generates a sequence that has as the first terms .

Linear Complexity Properties

Let and be binary sequences. Then:

Correlation Independence

To get high linear complexity, cryptographers try to non-linearly combine the results of multiple output sequences. In this case, the danger is that one or more output sequences (often even the outputs of individual LFSRs) can be connected by a common key stream and uncovered using linear algebra. Hacking based on such a vulnerability is called correlation autopsy. Thomas Siegenthaler has shown that correlation independence can be precisely defined, and that there is a trade-off between correlation independence and linear complexity.

The main idea behind this hack is to find some correlation between the output of a generator and the output of one of its component parts. Then, by observing the output sequence, information about this intermediate output can be obtained. Using this information and other correlations, it is possible to collect data on other intermediate outputs until the generator is hacked.

Correlation attacks or variations such as fast correlation attacks have been successfully used against many linear feedback shift register based keystream generators, which involve a trade-off between computational complexity and efficiency.

Example

For LFSR with an associated polynomial, the generated sequence has the form . Suppose, before the start of the process, the sequence is written in the register, then the period of the generated bit stream will be equal to 7 with the following sequence:

Since the internal state at the seventh step returned to its original state, then, starting from the next step, there will be a repetition. In other words, the period of the sequence turned out to be equal to 7, which happened due to the primitiveness of the polynomial.

Algorithms for generating primitive polynomials

Ready tables

Calculating the primitiveness of a polynomial is a fairly complex mathematical problem. Therefore, there are ready-made tables that list the numbers of tap sequences that provide the maximum period of the generator. For example, for a 32-bit shift register, there is a sequence . This means that to generate a new bit, it is necessary to sum the 31st, 30th, 29th, 27th, 25th and 0th bits using the XOR function. The code for such LFSR in the C language is as follows:

Int LFSR (void ) ( static unsigned long S = 1 ; S = ((( (S>> 31 ) ^ (S>> 30 ) ^ (S>> 29 ) ^ (S>> 27 ) ^ (S>> 25 ) ^ S ) & 1 )<< 31 ) | (S>> 1); return S & 1 ; )

Software implementations of RSLOS generators are quite slow and work faster if they are written in assembler rather than in C. One solution is to use 16 RLLS in parallel (or 32, depending on the word length in the architecture of a particular computer). In such a scheme, an array of words is used, the size of which is equal to the length of the LFSR, and each bit of the array word refers to its LFSR. Provided that the same tap sequence numbers are used, this can give a noticeable performance gain. [need sample code] (See: bitslice).

Galois configuration

Galois configuration of a linear feedback shift register

The feedback scheme can also be modified. In this case, the generator will not have greater cryptographic strength, but it will be easier to implement it programmatically. Instead of using the bits of the tap sequence to generate a new leftmost bit, XOR each bit of the tap sequence with the output of the generator and replace it with the result of this action, then the result of the generator becomes the new leftmost bit. In C language it looks like this:

Int LFSR (void ) ( static unsigned long Q = 1 ; Q = (Q>> 1 ) ^ ( Q& 1 ? 0x80000057 : 0 ) ; return Q & 1 ; )

The benefit is that all XORs are performed in one operation.

• it can be proved that the Fibonacci configuration given first and the Galois configuration given here give the same sequences (of length 2 32 −1), but shifted in phase from one another
• a loop of a fixed number of calls to the LFSR function in the Galois configuration is approximately twice as fast as in the Fibonacci configuration (MS VS 2010 compiler on Intel Core i5)
• note that in the Galois configuration, the order of the bits in the feedback word is reversed compared to the Fibonacci configuration

Generator examples

stop-go generators

Alternating stop-and-go generator

This oscillator uses the output of one LFSR to control the clock frequency of another LFSR. The clock output of RSLOS-2 is controlled by the output of RSLOS-1, so that RSLOS-2 can change its state at time t only if the output of RSLOS-1 at time t-1 was equal to one. But this scheme did not resist the correlation opening.

Therefore, an improved generator based on the same idea has been proposed. It is called the stop-and-go interleaved generator. It uses three LFSRs of different lengths. LFSR-2 is clocked when the output of LFSR-1 is equal to one, and LFSR-3, when the output of LFSR-1 is equal to zero. The output of the generator is the modulo 2 sum of RSLOS-2 and RSLOS-3. This generator has a large period and a large linear complexity. Its authors also showed a method for the correlation opening of RLOS-1, but this does not greatly weaken the generator.

Gollmann Cascade

Gollmann Cascade

The Gollmann Cascade is an enhanced version of the stop-go generator. It consists of a sequence of LFSRs, the timing of each of which is controlled by the previous LFSR. If the output of LFSR-1 at time t is 1, then LFSR-2 is clocked. If the output of LFSR-2 at time t is 1, then LFSR-3 is clocked, and so on. The output of the last LFSR is the output of the generator. If the length of all LFSRs is the same and equals n, then the linear complexity of the system of k LFSRs is .

This idea is simple and can be used to generate sequences with huge periods, large linear complexities, and good statistical properties. But, unfortunately, they are susceptible to an opening, called "locking" (lock-in). For greater stability, it is recommended to use k at least 15. Moreover, it is better to use more short LFSR than less long LFSR.

threshold generator

threshold generator

This generator attempts to circumvent the security issues of previous generators by using a variable number of shift registers. In theory, when using a larger number of shift registers, the complexity of the cipher increases, which was done in this generator.

This generator consists of a large number of shift registers, the outputs of which are fed to the majorization function. If the number of units at the outputs of the registers is more than half, then the generator produces a unit. If the number of zeros on the outputs is more than half, then the generator produces a zero. In order for the comparison of the number of zeros and ones to be possible, the number of shift registers must be odd. The lengths of all registers must be relatively prime, and the feedback polynomials must be primitive so that the period of the generated sequence is maximum.

For the case of three shift registers, the generator can be represented as:

This generator is similar to the Geff generator, except that the threshold generator has more linear complexity. Its linear complexity is:

where , , are the lengths of the first, second and third shift registers.

Its disadvantage is that each output bit gives some information about the state of the shift register. More precisely, 0.189 bits. Therefore, this generator may not resist the correlation opening.

Other types

Self-thinning

Self-decreasing generators are called generators that control their own frequency. Two types of such generators have been proposed. The first one consists of a linear feedback shift register and some circuit that clocks this register, depending on what the output values ​​of the shift register are. If the LFSR output is equal to one, then the register is clocked d times. If the output is zero, then the register is clocked k times. The second one has almost the same design, but somewhat modified: in the clocking circuit, as a check for 0 or 1, not the output signal itself, but XOR of certain bits of the shift register with linear feedback, is received at the input. Unfortunately, this kind of generator is not safe.

Multirate oscillator with inner product

This generator uses two shift registers with linear feedback with different clock frequencies: LFSR-1 and LFSR-2. The clock frequency of RLOS-2 is d times higher than that of RLLS-1. The individual bits of these registers are combined with an AND operation. The outputs of the AND operation are then XORed. The output sequence is taken from this XOR block. Again, this generator is not perfect (It did not survive the opening of linear consistency. If - the length of LFSR-1, - the length of LFSR-2, and d is the ratio of clock frequencies, then the internal state of the generator can be obtained from the output sequence of length ), but it has high linear complexity and excellent statistical performance.

Linear Feedback Shift Register(RSLOS, eng. linear feedback shift register, LFSR ) is a shift register of bit words, in which the value of the input (sliding) bit is equal to a linear Boolean function from the values ​​of the remaining bits of the register before the shift. It can be organized by both software and hardware. It is used to generate pseudo-random sequences bits, which is used, in particular, in cryptography.

Description

Register control in hardware implementations is performed by applying a shift pulse (otherwise called clocked or sync pulse) for all cells. Register management in software implementations is performed by executing a loop. At each iteration of the loop, the feedback function is calculated and the bits in the word are shifted.

Principle of operation

Linear complexity

Correlation Independence

In an attempt to obtain a high linear complexity of the generated sequence, cryptographers non-linearly combine the outputs of several shift registers. In this case, one or more output sequences (or even outputs of individual LFSRs) can be connected by a common stream and opened by a cryptanalyst. Hacking based on such a vulnerability is called correlation opening. The main idea of ​​such a hack is to find some correlation between the output of the generator and the outputs of its component parts. Then, by observing the output sequence, one can obtain information about these intermediate outputs, and thus hack the generator. Thomas Siegenthaler showed that it is possible to define correlation independence exactly, and that there is a trade-off between correlation independence and linear complexity.

Software implementation

Software implementations of RSLOS are quite slow and work faster if they are written in assembler. One of the solutions is the parallel use of 16 RLLS (or 32, depending on the word length in the computer architecture). In such a scheme, an array of words is used, the size of which is equal to the length of the shift register, and each bit of the word refers to its own LFSR. Since the same numbers of tap sequences are used, this can give a noticeable gain in generator performance.

Fibonacci configuration

Consider a 32-bit shift register. It has an escape sequence (32 , 31 , 30 , 28 , 26 , 1) (\displaystyle \left(32,\;31,\;30,\;28,\;26,\;1\right)). This means that to generate a new bit, it is necessary to sum the 31st, 30th, 29th, 27th, 25th and 0th bits using the XOR operation. The resulting LFSR has a maximum period 2 32 − 1 (\displaystyle 2^(32)-1). The code for such a register in C is as follows:

int LFSR_Fibonacci (void ) ( static unsigned long S = 0x00000001 ; S = ((((S >> 31 ) ^ (S >> 30 ) ^ (S >> 29 ) ^ (S >> 27 ) ^ (S >> 25 ) ^ S ) & 0x00000001 )<< 31 ) | (S >> 1); return S & 0x00000001 ; )

Galois configuration

This generator does not have greater cryptographic strength, but it gives a performance gain: all XOR operations through parallelization can be performed in one operation, and not sequentially one after the other, as in the Fibonacci configuration. This scheme will also give a gain in hardware implementation.

The code for a 32-bit shift register in C is as follows:

int LFSR_Galois (void ) ( static unsigned long S = 0x00000001 ; if (S & 0x00000001 ) ( S = (S ^ 0x80000057 >> 1 ) | 0x80000000 ; return 1 ;) else ( S >>= 1 ; return 0 ;) )

It is worth noting that the cycle of a fixed number of calls to the LFSR_Galois function in the Galois configuration is approximately 2 times faster than the LFSR_Fibonacci function in the Fibonacci configuration (MS VS 2010 compiler on Intel Core i5).

Generated Sequence Example

Fibonacci configuration

Let LFSR be given by the characteristic polynomial x 3 + x + 1 (\displaystyle x^(3)+x+1). This means that the tap bits will be 2nd and 0th, and the unit in the polynomial formula means that the 0th bit is the input. The feedback function has the form S j = S j − 1 ⊕ S j − 3 (\displaystyle S_(j)=S_(j-1)\oplus S_(j-3)). Suppose the initial state of the shift register was the sequence . Further states of the register are shown in the table below:

Since the internal state at the seventh step returned to its original state, then, starting from the next step, the bits will be repeated. So the generated sequence is: [ 1 , 0 , 0 , 1 , 1 , 1 , 0 , 1 . . . ] (\displaystyle\left)(the order of the bits in the sequence corresponds to the order in which they were generated by the LFSR). Thus, the period of the sequence is 7, that is, the maximum possible value, which happened due to the primitiveness of the given polynomial.

Galois configuration

Let us take the same characteristic polynomial, that is, c 3 = c 1 = 1 (\displaystyle c_(3)=c_(1)=1), c2 = 0 (\displaystyle c_(2)=0). Only the 1st bit is added to the output bit. The initial state is the same. Further states of the register:

The internal state of the register at the seventh step returned to its original state, therefore, its period is also equal to 7. Unlike the Fibonacci configuration, the internal states of the register turned out to be different, but the generated sequence is the same, only shifted by 4 cycles: [ 0 , 1 , 1 , 1 , 0 , 0 , 0 , 0 , 1 , 1 , . . . ] (\displaystyle\left)(the order of the bits in the sequence corresponds to the order in which they were generated by the LFSR).

Generating primitive polynomials

Advantages and disadvantages

Advantages

• high performance cryptographic algorithms, created on the basis of LFSR (for example, stream ciphers);
• the use of only the simplest bit operations of addition and multiplication, implemented in hardware in almost all computing devices;
• good cryptographic properties (LFSRs can generate long period sequences with good statistical properties);
• due to their structure, LFSRs are easily analyzed using algebraic methods.

Flaws

Ways to improve the cryptographic strength of generated sequences

Generators with multiple shift registers

This type of generator consists of several linear feedback shift registers that generate bits x 1 , i , x 2 , i , … , x M , i (\displaystyle x_(1,i),\;x_(2,i),\;\dots ,\;x_(M,i)) respectively. Further, the generated bits are transformed by some boolean function f (x 1 , i , x 2 , i , … , x M , i) (\displaystyle f(x_(1,i),\;x_(2,i),\;\dots ,\;x_(M ,i))). It should be noted that generators of this type have register lengths L i (\displaystyle L_(i)), i = 1 , 2 , … , M (\displaystyle i=1,\;2,\;\dots ,\;M), are coprime with each other.

The period of this generator is T = (2 L 1 − 1) ⋅ (2 L 2 − 1) ⋯ (2 L M − 1) ≲ 2 L (\displaystyle T=(2^(L_(1))-1)\cdot (2^( L_(2))-1)\cdots (2^(L_(M))-1)\lesssim 2^(L)), Where L = ∑ i = 1 M L i (\displaystyle L=\sum \limits _(i=1)^(M)L_(i))- total number of cells. Therefore, the use of several LFSRs increases the period of the generated sequence compared to a single register, which increases the cryptographic strength of the generator. It also increases the linear complexity or the length of the shortest register corresponding to a given generator. Such a register is found using the Berlekamp-Massey algorithm using the generated sequence. At best, its length is commensurate with the period of the generated sequence.

Generators with non-linear transformations

The block diagram of such a generator is no different from the diagram of the previous generator. The main difference is that the transform device is given by a non-linear Boolean function f (x 1 , x 2 , … , x M) (\displaystyle f(x_(1),x_(2),\dots ,x_(M))). For example, the Zhegalkin polynomial is taken as such a function (according to the Zhegalkin theorem, any Boolean function can be uniquely represented by the Zhegalkin polynomial).

A nonlinear generator can also be implemented on non-linear feedback shift register. He can give 2 2 L − 1 − L (\displaystyle 2^(2^(L-1)-L)) variants of sequences maximum period , which is more than that of LFSR .

The cryptographic strength of this generator is increased due to the non-linearity of the function used. Determining the state of the registers from the generated bit sequence is a complex mathematical problem, because no algorithm is known that restores the original states.

This method is used, for example, in generator Geff and the generalized Geff generator, however, such generators can be broken by a correlation attack.

Generators with different shift register timing

stop-go generator

stop-go generator(English Stop-and-Go , Both-Piper ) uses the output of LFOS-1 to control the clock frequency of LFOS-2, so that LFSR-2 changes its state at some point in time only if the output of LFOS-1 at the time was equal to unit. This scheme did not resist the correlation opening.

In order to increase cryptographic strength, it was proposed stop-and-go alternator. It uses three shift registers of different lengths. Here LFOS-1 controls the clock frequency of the 2nd and 3rd registers, i.e. LFSR-2 changes its state when the LFSR-1 output is equal to one, and LFSR-3 - when the LFSR-1 output is equal to zero. The output of the generator is the operation of adding modulo two outputs of RSLOS-2 and RSLOS-3. This generator has a large period and a large linear complexity. There is a method of correlation opening of RLOS-1, but this does not greatly weaken the cryptographic properties of the generator.

A sophisticated clocking scheme is used in two-way stop-and-go generator, which uses 2 shift registers of the same length. If the output of RLOS-1 at some point in time t i − 1 (\displaystyle t_(i-1))- one, then RLOS-2 is not clocked at the time t i (\displaystyle t_(i)). If the output of RLOS-2 at the moment of time t i − 1 (\displaystyle t_(i-1)) equals zero, and at time t i − 2 (\displaystyle t_(i-2))- one, and if this register is clocked at the time t i (\displaystyle t_(i)), then at the same moment RLOS-1 is not clocked. The linear complexity of this circuit is approximately equal to the period of the generated sequence.

Self-decimating generator

Multirate oscillator with inner product

This generator uses two shift registers RSLOS-1 and RSLOS-2. Clock frequency of RSLOS-2 in d (\displaystyle d) times more than that of RSLOS-1. Certain bits of these registers are multiplied with each other using the AND operation. The results of the multiplications are added by the XOR operation, and the output sequence is obtained. This generator has a high linear complexity and has good statistical properties. However, its state can be determined from an output sequence of length L 1 + L 2 + log 2 ⁡ d (\displaystyle L_(1)+L_(2)+\log _(2)(d)), Where L 1 (\displaystyle L_(1)) And L 2 (\displaystyle L_(2)) are the lengths of LFOS-1 and LFOS-2, respectively, and d (\displaystyle d)- the ratio of their clock frequencies.

Gollmann Cascade

This circuit is an improved version of the stop-go generator. It consists of a sequence of LFSRs, the timing of each of which is controlled by the previous LFSR. If the output of RLOS-1 at the time t i (\displaystyle t_(i)) is 1, then RLOS-2 is clocked. If the output of RLOS-2 at the moment of time t i (\displaystyle t_(i)) is 1, then RLOS-3 is clocked, and so on. The output of the last LFSR is the output of the generator. If the length of all LFSRs is the same and equal to L (\displaystyle L), then the period of the system from M (\displaystyle M) LFSR is equal to (2 L − 1) M (\displaystyle (2^(L)-1)^(M)), and the linear complexity is L (S) = L (2 L − 1) M − 1 (\displaystyle L(S)=L(2^(L)-1)^(M-1)) .

This idea is simple and can be used to generate sequences with huge periods, large linear complexities, and good statistical properties. But, unfortunately, they are sensitive to an autopsy called locking(eng. lock-in) when