Linear Feedback Shift Register

Linear feedback shift register (RSLOS, English linear feedback shift register , LFSR ) is a bit-word shift register , in which the value of the input (inserted) bit is equal to the linear Boolean function from the values of the remaining bits of the register to the shift. It can be organized by both software and hardware. It is used to generate pseudorandom sequences of bits , which finds application, in particular, in cryptography ^[1] .

Description

Four-digit random number generator from one element "exclusive or" and four registers. Note the lack of status "0000"

Linear Feedback Shift Register

In the shift register with linear feedback (RSLOS) there are two parts (modules):

the shift register itself;
a feedback circuit (or subroutine) that calculates the value of the inserted bit .

The register consists of functional memory cells (bits of one or more machine words), each of which stores the current state (value) of one bit. Number of cells $L$ ${\ displaystyle L}$ $L$ is called the length of the register. Bits (cells) are usually numbered with numbers $i=0,\;1,\;\dots ,\;L-1$ ${\ displaystyle i = 0, \; 1, \; \ dots, \; L-1}$ $i = 0,\;1,\;\dots,\;L-1$ , contents $i$ ${\ displaystyle i}$ $i$ th cell is denoted by $S_{(L-1)-i}$ ${\ displaystyle S _ {(L-1) -i}}$ $S_{(L-1)-i}$ . The value of the new bit $S_{L}$ ${\ displaystyle S_ {L}}$ $S_L$ determined before the shift of bits in the register and only after the shift is recorded in the cell $0$ ${\ displaystyle 0}$ $0$ , and from the cell $L-1$ ${\ displaystyle L-1}$ $L-1$ the next generated bit is retrieved.

The feedback function for RSLOS is a linear Boolean function of the values of all or some bits of the register. The function multiplies the register bits by the coefficients $c_{i}$ ${\ displaystyle c_ {i}}$ where $i=1,\;2,\;\dots ,\;L$ ${\ displaystyle i = 1, \; 2, \; \ dots, \; L}$ . The number of coefficients matches the number of bits of the register $L$ ${\ displaystyle L}$ . Odds $c_{i}$ ${\ displaystyle c_ {i}}$ take values $\{0,\;1\}$ ${\ displaystyle \ {0, \; 1 \}}$ , and the last coefficient $c_{L}$ ${\ displaystyle c_ {L}}$ is equal to $c_{L}=1$ ${\ displaystyle c_ {L} = 1}$ , since RSLOS is given by a characteristic polynomial of degree $L$ ${\ displaystyle L}$ . Addition modulo 2 (operation "XOR", denoted in the formulas by the symbol " $\oplus$ ${\ displaystyle \ oplus}$ ”) Or its logical inversion“ XNOR ”are linear Boolean functions and are most often used in such registers ^[2] . In this case, the bits, which are variables of the feedback function, are called taps , and the register itself is called the Fibonacci configuration ^[3] .

Register control in hardware implementations is performed by applying a shifting pulse (otherwise called a clock or clock ) to 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 bit shift in the word is performed.

Principle of Operation

During each cycle, the linear feedback shift register performs the following operations:

the bit located in the cell is read $L-1$ ${\ displaystyle L-1}$ ; this bit is the next bit of the output sequence;
feedback function calculates the new value for the cell $0$ ${\ displaystyle 0}$ using current cell values;
the contents of each $i$ ${\ displaystyle i}$ th cell moves to the next cell $i+1$ ${\ displaystyle i + 1}$ where $i=0,\;1,\;\dots ,\;L-2$ ${\ displaystyle i = 0, \; 1, \; \ dots, \; L-2}$ ;
to cell $0$ ${\ displaystyle 0}$ the bit previously calculated by the feedback function is recorded.

If the feedback function performs the logical operation “ XOR ” (exclusive OR), the values of bits (cells) can be calculated using the following formulas ^[4] : $S_{L}=(c_{1}*S_{L-1})\oplus (c_{2}*S_{L-2})\oplus \dots \oplus (c_{L}*S_{0})$ ${\ displaystyle S_ {L} = (c_ {1} * S_ {L-1}) \ oplus (c_ {2} * S_ {L-2}) \ oplus \ dots \ oplus (c_ {L} * S_ { 0})}$ $S_{L+1}=(c_{1}*S_{L})\oplus (c_{2}*S_{L-1})\oplus \dots \oplus (c_{L}*S_{1})$ ${\ displaystyle S_ {L + 1} = (c_ {1} * S_ {L}) \ oplus (c_ {2} * S_ {L-1}) \ oplus \ dots \ oplus (c_ {L} * S_ { one})}$ $. . .$ ${\ displaystyle ...}$ $S_{L+j-1}=(c_{1}*S_{L+j-2})\oplus (c_{2}*S_{L+j-3})\oplus \dots \oplus (c_{L}*S_{j-1})$ ${\ displaystyle S_ {L + j-1} = (c_ {1} * S_ {L + j-2}) \ oplus (c_ {2} * S_ {L + j-3}) \ oplus \ dots \ oplus (c_ {L} * S_ {j-1})}$

Properties

Frequency

The shift register period is the minimum length of the resulting sequence before it begins to repeat. RSLOS length $L$ ${\ displaystyle L}$ It has $2^{L}$ ${\ displaystyle 2 ^ {L}}$ initial states that specify the values of the bits in the cells. Of them $2^{L}-1$ ${\ displaystyle 2 ^ {L} -1}$ states are nonzero, so the generated sequence has a period $T\leq 2^{L}-1$ ${\ displaystyle T \ leq 2 ^ {L} -1}$ . The period of the generated sequence is maximum and equal to $2^{L}-1$ ${\ displaystyle 2 ^ {L} -1}$ if the feedback polynomial (or the characteristic polynomial) $C(x)=c_{L}x^{L}+c_{L-1}x^{L-1}+\dots +c_{1}x+1$ ${\ displaystyle C (x) = c_ {L} x ^ {L} + c_ {L-1} x ^ {L-1} + \ dots + c_ {1} x + 1}$ over the field $\mathrm {GF} (2)$ ${\ displaystyle \ mathrm {GF} (2)}$ is primitive . For this, it is necessary (but not enough) that the following 2 conditions are met:

an even number of taps;
branch numbers, taken all together, and not in pairs, are mutually simple .

The number of all possible primitive polynomials is ${\tfrac {\phi (2^{L}-1)}{L}}$ ${\ displaystyle {\ tfrac {\ phi (2 ^ {L} -1)} {L}}}$ where $\phi$ ${\ displaystyle \ phi}$ is the Euler function ^[5] . The register specified by such a polynomial is called the maximum period shift register (or pseudo-random sequence generator ), and the generated sequences are called maximum period sequences (or M-sequences ) ^[4] ^[6] .

Linear complexity

The linear complexity of an infinite binary sequence $S=(S_{0},\;S_{1},\;S_{2},\;\dots )$ ${\ displaystyle S = (S_ {0}, \; S_ {1}, \; S_ {2}, \; \ dots)}$ called a number $L(S)$ ${\ displaystyle L (S)}$ which is defined as follows:

if a $S=(0,\;0,\;0,\;\dots )$ ${\ displaystyle S = (0, \; 0, \; 0, \; \ dots)}$ Is the zero sequence then $L(S)=0$ ${\ displaystyle L (S) = 0}$ ;
if there is no RSLOS that generates $S$ ${\ displaystyle S}$ then $L(S)=\infty$ ${\ displaystyle L (S) = \ infty}$ ;
otherwise $L(S)$ ${\ displaystyle L (S)}$ equal to the length of the shortest RSLOS that generates $S$ ${\ displaystyle S}$ .

Linear complexity of a finite binary sequence $S_{n}=(S_{0},\;S_{1},\;\dots ,\;S_{n})$ ${\ displaystyle S_ {n} = (S_ {0}, \; S_ {1}, \; \ dots, \; S_ {n})}$ called a number $L(S_{n})$ ${\ displaystyle L (S_ {n})}$ equal to the length of the shortest RSLOS that generates this sequence.

The linear complexity of the shift register with linear feedback shows how close the generated sequence is to random . An effective algorithm for determining the linear complexity of a finite binary sequence is the Berlekamp-Massey algorithm .

Correlation Independence

Trying to get high linear complexity of the generated sequence, cryptographs nonlinearly combine the outputs of several shift registers. In this case, one or more output sequences (or even the outputs of individual RSLOSs) can be connected by a common stream and opened by a cryptanalyst . Hacking based on this vulnerability is called correlation autopsy . The main idea of such a hack is to detect some correlation between the output of the generator and the conclusions of its components. Then, observing the output sequence, you can obtain information about these intermediate conclusions, and thus hack the generator. Thomas Sigentaler showed that correlation independence can be precisely determined, and that there is a trade-off between correlation independence and linear complexity ^[7] .

Software Implementation

RSLOS software implementations are rather slow and work faster if they are written in assembler . One solution is the parallel use of 16 RSLOS (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 RSLOS. Since the same numbers of tap sequences are used, this can give a noticeable gain in generator performance ^[3] .

Fibonacci Configuration

Consider a 32-bit shift register. There is a tap sequence for it $\left(32,\;31,\;30,\;28,\;26,\;1\right)$ ${\ displaystyle \ left (32, \; 31, \; 30, \; 28, \; 26, \; 1 \ right)}$ . This means that to generate a new bit, it is necessary to add the 31st, 30th, 29th, 27th, 25th and 0th bits using the XOR operation. The resulting RSLOS has a maximum period $2^{32}-1$ ${\ displaystyle 2 ^ {32} -1}$ . The code for such a C register 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

Galois Linear Feedback Shift Register Configuration

As in the Fibonacci configuration, the feedback scheme is a set of XOR operations of the tap bits with the generator output, but the order of the bits in the register is reversed: the input is $L-1$ ${\ displaystyle L-1}$ bit, and the weekend $0$ ${\ displaystyle 0}$ th. The result of the addition is written to the next cell, and the new output bit is written to $L-1$ ${\ displaystyle L-1}$ -Yu. Thus, if the generated bit is equal to zero, then all the bits in the cells are shifted to the right without changes, if the generated bit is equal to one, then the retraction bits change their value to the opposite, and all bits are shifted to the right. Both the Fibonacci configuration and the Galois configuration of the same length generate identical, but time-shifted sequences from one another (the internal states of the registers may differ) ^[8] .

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

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

  int LFSR_Galois ( void )
 {
     // for polynomial 0x80000057, reversed 0xea000001
     static unsigned long S = 0x00000001 ;
     if ( S & 0x00000001 ) {
         S = (( S ^ 0xea000001 ) >> 1 ) |  0x80000000 ;
         return 1 ;}
     else {
         S >> = 1 ;
         return 0 ;}
 }

It is worth noting that a 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 ).

Example generated sequence

Fibonacci Configuration

Example FELOC Fibonacci Configuration

Let RSLOS be given by a characteristic polynomial $x^{3}+x+1$ ${\ displaystyle x ^ {3} + x + 1}$ . This means that the retraction bits will be the 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}\oplus S_{j-3}$ ${\ displaystyle S_ {j} = S_ {j-1} \ oplus S_ {j-3}}$ . Suppose the initial state of the shift register was a sequence $\left[0,\;0,\;1\right]$ ${\ displaystyle \ left [0, \; 0, \; 1 \ right]}$ . Further register states are shown in the table below:

Step number	condition	Bit generated
0	$\left[0,\;0,\;1\right]$ ${\ displaystyle \ left [0, \; 0, \; 1 \ right]}$	one
one	$\left[1,\;0,\;0\right]$ ${\ displaystyle \ left [1, \; 0, \; 0 \ right]}$	0
2	$\left[1,\;1,\;0\right]$ ${\ displaystyle \ left [1, \; 1, \; 0 \ right]}$	0
3	$\left[1,\;1,\;1\right]$ ${\ displaystyle \ left [1, \; 1, \; 1 \ right]}$	one
four	$\left[0,\;1,\;1\right]$ ${\ displaystyle \ left [0, \; 1, \; 1 \ right]}$	one
five	$\left[1,\;0,\;1\right]$ ${\ displaystyle \ left [1, \; 0, \; 1 \ right]}$	one
6	$\left[0,\;1,\;0\right]$ ${\ displaystyle \ left [0, \; 1, \; 0 \ right]}$	0
7	$\left[0,\;0,\;1\right]$ ${\ displaystyle \ left [0, \; 0, \; 1 \ right]}$	one

Since the internal state at the seventh step returned to its original state, then, starting from the next step, the bits will be repeated. That is, the generated sequence is as follows: $\left[1,\;0,\;0,\;1,\;1,\;1,\;0,\;1\;...\right]$ ${\ displaystyle \ left [1, \; 0, \; 0, \; 1, \; 1, \; 1, \; 0, \; 1 \; ... \ right]}$ (the order of the bits in the sequence corresponds to the order of their generation of the RSLOS). 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

Sample Galos configuration Galois

Take the same characteristic polynomial, i.e. $c_{3}=c_{1}=1$ ${\ displaystyle c_ {3} = c_ {1} = 1}$ , $c_{2}=0$ ${\ displaystyle c_ {2} = 0}$ . Only the 1st bit is added to the output bit. The initial state is the same. Further register states:

Step number	condition	Bit generated
0	$\left[0,\;0,\;1\right]$ ${\ displaystyle \ left [0, \; 0, \; 1 \ right]}$	-
one	$\left[1,\;0,\;0\right]$ ${\ displaystyle \ left [1, \; 0, \; 0 \ right]}$	0
2	$\left[0,\;1,\;1\right]$ ${\ displaystyle \ left [0, \; 1, \; 1 \ right]}$	one
3	$\left[1,\;0,\;1\right]$ ${\ displaystyle \ left [1, \; 0, \; 1 \ right]}$	one
four	$\left[1,\;1,\;1\right]$ ${\ displaystyle \ left [1, \; 1, \; 1 \ right]}$	one
five	$\left[1,\;1,\;0\right]$ ${\ displaystyle \ left [1, \; 1, \; 0 \ right]}$	0
6	$\left[0,\;1,\;0\right]$ ${\ displaystyle \ left [0, \; 1, \; 0 \ right]}$	0
7	$\left[0,\;0,\;1\right]$ ${\ displaystyle \ left [0, \; 0, \; 1 \ right]}$	one

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 measures : $\left[0,\;1,\;1,\;1,\;0,\;0,\;0,\;0,\;1,\;1,\;...\right]$ ${\ displaystyle \ left [0, \; 1, \; 1, \; 1, \; 0, \; 0, \; 0, \; 0, \; 1, \; 1, \; ... \ right]}$ (the order of the bits in the sequence corresponds to the order of their generation of the RSLOS).

Primitive polynomial generation

Computing a primitive polynomial over a field $\mathrm {GF} (2)$ ${\ displaystyle \ mathrm {GF} (2)}$ - a rather complicated mathematical problem: to generate a primitive polynomial of degree $k$ ${\ displaystyle k}$ need to know the number factors $2^{k}-1$ ${\ displaystyle 2 ^ {k} -1}$ . It is easier to randomly select a polynomial and check it for primitiveness ^[3] . Another method is to use ready-made tables that list the numbers of tap sequences that provide the maximum generator period. Below is a table of primitive polynomials over a field $\mathrm {GF} (2)$ ${\ displaystyle \ mathrm {GF} (2)}$ for shift registers with a maximum period of up to 19 bits ^[5] . It is worth considering that a generator of any given length can have more than one primitive polynomial according to their properties . A complete list for registers from 4 to 32 bits long can be found here .

Bits $n$ ${\ displaystyle n}$	Primitive polynomial	Period, $2^{n}-1$ ${\ displaystyle 2 ^ {n} -1}$	The number of primitive polynomials
2	$x^{2}+x+1$ ${\ displaystyle x ^ {2} + x + 1}$	3	one
3	$x^{3}+x^{2}+1$ ${\ displaystyle x ^ {3} + x ^ {2} +1}$	7	2
four	$x^{4}+x^{3}+1$ ${\ displaystyle x ^ {4} + x ^ {3} +1}$	15	2
five	$x^{5}+x^{3}+1$ ${\ displaystyle x ^ {5} + x ^ {3} +1}$	31	6
6	$x^{6}+x^{5}+1$ ${\ displaystyle x ^ {6} + x ^ {5} +1}$	63	6
7	$x^{7}+x^{6}+1$ ${\ displaystyle x ^ {7} + x ^ {6} +1}$	127	18
eight	$x^{8}+x^{6}+x^{5}+x^{4}+1$ ${\ displaystyle x ^ {8} + x ^ {6} + x ^ {5} + x ^ {4} +1}$	255	sixteen
9	$x^{9}+x^{5}+1$ ${\ displaystyle x ^ {9} + x ^ {5} +1}$	511	48
ten	$x^{10}+x^{7}+1$ ${\ displaystyle x ^ {10} + x ^ {7} +1}$	1023	60
eleven	$x^{11}+x^{9}+1$ ${\ displaystyle x ^ {11} + x ^ {9} +1}$	2047	176
12	$x^{12}+x^{11}+x^{10}+x^{4}+1$ ${\ displaystyle x ^ {12} + x ^ {11} + x ^ {10} + x ^ {4} +1}$	4095	144
13	$x^{13}+x^{12}+x^{11}+x^{8}+1$ ${\ displaystyle x ^ {13} + x ^ {12} + x ^ {11} + x ^ {8} +1}$	8191	630
14	$x^{14}+x^{13}+x^{12}+x^{2}+1$ ${\ displaystyle x ^ {14} + x ^ {13} + x ^ {12} + x ^ {2} +1}$	16383	756
15	$x^{15}+x^{14}+1$ ${\ displaystyle x ^ {15} + x ^ {14} +1}$	32767	1800
sixteen	$x^{16}+x^{14}+x^{13}+x^{11}+1$ ${\ displaystyle x ^ {16} + x ^ {14} + x ^ {13} + x ^ {11} +1}$	65535	2048
17	$x^{17}+x^{14}+1$ ${\ displaystyle x ^ {17} + x ^ {14} +1}$	131071	7710
18	$x^{18}+x^{11}+1$ ${\ displaystyle x ^ {18} + x ^ {11} +1}$	262143	7776
nineteen	$x^{19}+x^{18}+x^{17}+x^{14}+1$ ${\ displaystyle x ^ {19} + x ^ {18} + x ^ {17} + x ^ {14} +1}$	524287	27594
20 - 168	[one]
2 - 786, 1024, 2048, 4096	[2]

Advantages and disadvantages

Benefits

high speed cryptographic algorithms created on the basis of RSLOS (for example, stream ciphers );
the use of only the simplest bit operations of addition and multiplication, hardware implemented in almost all computing devices;
good cryptographic properties (RSLOS can generate sequences of a large period with good statistical properties);
Due to its structure, DFIDs are easily analyzed using algebraic methods.

Weaknesses

One of the main problems of RSLOS is that their software implementation is extremely ineffective: sparse feedback polynomials must be avoided, since they lead to easier cracking by correlation breaking, and dense polynomials are very slowly calculated. Therefore, the software implementation of such a generator does not work faster than the DES implementation.
The linearity of the sequence at the output of the register allows you to uniquely determine the feedback polynomial $C(x)$ ${\ displaystyle C (x)}$ by $2L$ ${\ displaystyle 2L}$ consecutive bits using the Berlekamp – Massey algorithm or the Euclidean algorithm ^[3] ^[4] .
The relative ease of analysis by algebraic methods not only facilitates development, but also increases the chances of breaking a generator based on RSLOS.

Ways to Improve the Cryptographic Strength of Generated Sequences

Multi Shift Generators

Multi shift register generator

This type of oscillator consists of several linear feedback shift registers that generate bits $x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i}$ ${\ displaystyle x_ {1, i}, \; x_ {2, i}, \; \ dots, \; x_ {M, i}}$ respectively. Next, the generated bits are transformed by some Boolean function $f(x_{1,i},\;x_{2,i},\;\dots ,\;x_{M,i})$ ${\ displaystyle f (x_ {1, i}, \; x_ {2, i}, \; \ dots, \; x_ {M, i})}$ . It should be noted that generators of this type of register length $L_{i}$ ${\ displaystyle L_ {i}}$ , $i=1,\;2,\;\dots ,\;M$ ${\ displaystyle i = 1, \; 2, \; \ dots, \; M}$ are mutually simple among themselves.

The period of this generator is $T=(2^{L_{1}}-1)\cdot (2^{L_{2}}-1)\cdots (2^{L_{M}}-1)\lesssim 2^{L}$ ${\ displaystyle T = (2 ^ {L_ {1}} - 1) \ cdot (2 ^ {L_ {2}} - 1) \ cdots (2 ^ {L_ {M}} - 1) \ lesssim 2 ^ { L}}$ where $L=\sum \limits _{i=1}^{M}L_{i}$ ${\ displaystyle L = \ sum \ limits _ {i = 1} ^ {M} L_ {i}}$ - total number of cells. Therefore, the use of several RSLOS increases the period of the generated sequence in comparison with one register, which increases the cryptographic stability of the generator. Also increases the linear complexity or length of the shortest register corresponding to this generator. Such a register is found using the Berlekamp-Massey algorithm in the generated sequence. In the best case, its length is commensurate with the period of the generated sequence ^[4] .

Nonlinear Transform Generators

The structural diagram of such a generator is no different from the circuit of the previous generator. The main difference is that the conversion device is defined by a nonlinear Boolean function $f(x_{1},x_{2},\dots ,x_{M})$ ${\ displaystyle f (x_ {1}, x_ {2}, \ dots, x_ {M})}$ . As such a function, for example, the Zhegalkin polynomial is taken (according to the Zhegalkin theorem, every Boolean function can be uniquely represented by the Zhegalkin polynomial).

A non-linear generator can also be implemented on a . He can give $2^{2^{L-1}-L}$ ${\ displaystyle 2 ^ {2 ^ {L-1} -L}}$ sequence variants of the maximum period , which is greater than that of RSLOS ^[5] .

The cryptographic stability of this generator is increased due to the nonlinearity of the function used. Determining the state of registers by the generated sequence of bits is a difficult mathematical task, because an algorithm that restores the initial states is not known.

This method is used, for example, in the Geff generator and the generalized Geff generator, however, such generators can be cracked by correlation autopsy ^[7] .

Generators with different shift register timing

Stop-go generator

Alternating Stop-Run Generator

Two-way stop-go generator

Stop-go Generator

The Stop-and-Go generator ( Stop-and-Go , Both-Piper ) uses the RSLOS-1 pin to control the RSLOS-2 clock frequency, so the RSLOS-2 changes its state at some point in time $t_{i}$ ${\ displaystyle t_ {i}}$ , only if the output of RSLOS-1 at time $t_{i-1}$ ${\ displaystyle t_ {i-1}}$ was equal to one. This scheme could not resist the correlation autopsy ^[3] .

In order to increase cryptographic strength, an alternating stop-go generator was proposed. It uses three shift registers of various lengths. Here, RSLOS-1 controls the clock frequency of the 2nd and 3rd registers, that is, RSLOS-2 changes its state when the output of RSLOS-1 is unity, and RSLOS-3 - when the output of RSLOS-1 is zero. The output of the generator is the operation of adding modulo two outputs RSLOS-2 and RSLOS-3. This generator has a large period and a large linear complexity. There is a correlation autopsy method for RSLOS-1, but this does not greatly weaken the cryptographic properties of the generator.

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

Self-cutting generator

Self-decimating generators control their own frequency. There are two types of such generators. The first was proposed by Rainer Ruppel . It consists of a shift register and a linear feedback circuit that clocks this register depending on what the output values of the shift register are. If the output of the RSLOS is equal to one, then the register is clocked with one frequency, and if the output is zero, then with another. The second type was proposed by Bill Chambers and Dieter Callman . It is not the output signal itself that receives the feedback circuit, but the result of the XOR operation of certain RSLOS bits.

There are also decimated ( English shrinking ) and self- decimated ( English self-shrinking ) generators. They are fairly new, and not all of their properties are well understood. The first uses two RSLOS. If a clock pulse is applied to the generator, and the output of RSLOS-1 is one, then the output of the generator will be the output of RSLOS-2. Otherwise, when applying a clock pulse, both bits are reset, the clock starts again. In the second generator, instead of checking the outputs of two registers for 0 or 1, 2 bits of one register are checked.

A decimated generator can be hacked if the feedback polynomials are decimated. In addition, its generation rate is not constant. For a self-decimating generator, approximately 2 times less memory is needed than the first, but at the same time it works 2 times slower ^[7] .

Multi-speed Internal Product Generator

This generator uses two shift registers RSLOS-1 and RSLOS-2. RSLOS-2 clock frequency $d$ ${\ displaystyle d}$ times more than RSLOS-1. Certain bits of these registers are multiplied with each other by the AND operation. The results of the multiplications are summed by the XOR operation, and an output sequence is obtained. This generator has high linear complexity and has good statistical properties. However, its condition can be determined by 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}}$ - the lengths of RSLOS-1 and RSLOS-2, respectively, and $d$ ${\ displaystyle d}$ - the ratio of their clock frequencies.

Gollmann Cascade

This diagram is an improved version of the stop-go generator. It consists of a sequence of RSLOS, the timing of each of which is controlled by the previous RSLOS. If the output of RSLOS-1 at a time $t_{i}$ ${\ displaystyle t_ {i}}$ is 1, then RSLOS-2 is clocked. If the output of RSLOS-2 at a time $t_{i}$ ${\ displaystyle t_ {i}}$ is 1, then RSLOS-3 is clocked, and so on. The output of the last RSLOS is the output of the generator. If the length of all RSLOS is the same and equal $L$ ${\ displaystyle L}$ , then the period of the system from $M$ ${\ displaystyle M}$ RSLOS is equal $(2^{L}-1)^{M}$ ${\ displaystyle (2 ^ {L} -1) ^ {M}}$ and linear complexity is $L(S)=L(2^{L}-1)^{M-1}$ ${\ displaystyle L (S) = L (2 ^ {L} -1) ^ {M-1}}$ ^[7] .

This idea is simple and can be used to generate sequences with huge periods, large linear complexity and good statistical properties. But, unfortunately, they are sensitive to an autopsy called lock-in , when a cryptanalyst , first restoring the input sequence of the last register in a cascade, breaks the entire cascade, register by register. With the increasing number of registers $M$ ${\ displaystyle M}$ the generated sequence approaches random , so it is better to use more short-wavelength MLRS than fewer long MLRS.

Majority Generators

Shift Register System in A5 / 1 Encryption Algorithm

The majority (or threshold ) generator consists of a large number of shift registers, the outputs of which are supplied to the device specified by the majorization function, for example, a majority element . The peculiarity of this generator is that each of the shift registers has its own clock bit $a_{i}$ ${\ displaystyle a_ {i}}$ , $i=1,\;2,\;\dots ,\;M$ ${\ displaystyle i = 1, \; 2, \; \ dots, \; M}$ , which are the variables of the majority function. For example, for three registers, such a function has the form $b(t)=(a_{1}\land a_{2})\oplus (a_{1}\land a_{3})\oplus (a_{2}\land a_{3})$ ${\ displaystyle b (t) = (a_ {1} \ land a_ {2}) \ oplus (a_ {1} \ land a_ {3}) \ oplus (a_ {2} \ land a_ {3})}$ . Only those registers whose clock bits equal the value are shifted $b(t)$ ${\ displaystyle b (t)}$ , that is, the shift of the registers occurs for most of the values of these bits: 0 or 1.

Thus, we get a generator with a variable number of RSLOS. Its linear complexity $L(S)=\sum \limits _{i,j=1}^{M}L_{i}L_{j}$ ${\ displaystyle L (S) = \ sum \ limits _ {i, j = 1} ^ {M} L_ {i} L_ {j}}$ where $L_{i}$ ${\ displaystyle L_ {i}}$ - length $i$ ${\ displaystyle i}$ -th register ^[7] . The disadvantages of such a generator are the possibility of direct enumeration and correlation autopsy (each output bit gives some information about the state of the shift register, or rather, 0.189 bits).

Similar generators are used in A5 encryption algorithms (A5 / 1, A5 / 2).

Application

Shift registers with linear feedback can be implemented in hardware, which allows them to be used to quickly generate a pseudo-random sequence , for example, when expanding the spectrum using the direct sequence method or to generate a noise signal ^[9] .

Use in cryptography

Linear feedback shift registers have long been used as pseudo-random sequence generators for stream ciphers (especially in military cryptography ). However, RSLOS is a linear scheme and in some cases can be easily cracked. For example, a cryptanalyst can intercept a part of the ciphertext and, using the aforementioned Berlekamp-Massey algorithm, restore the minimum size RSLOS that imitates the original RSLOS. Then, the intercepted text can be submitted to the received register and decrypted. Methods to increase the cryptographic strength of stream ciphers based on RSLOS are given above .

Linear feedback shift registers are based on stream ciphers such as A5 / 1 and A5 / 2 used in the GSM standard and the cipher used in Bluetooth . The cipher A5 / 2 was cracked, and the ciphers A5 / 1 and E0 have serious shortcomings ^[10] ^[11] .

Регистр сдвига с линейной обратной связью тесно связан с линейным конгруэнтным генератором ^[12] .

Использование в качестве счётчиков

Периодичность генерируемой последовательности РСЛОС позволяет использовать его в качестве делителя тактовой частоты или счётчика ^[13] . Счётчик на основе такого генератора имеет упрощенную схему обратной связи, в отличие от обычных двоичных счётчиков или счётчиков кода Грея , и, следовательно, может работать на высоких тактовых частотах. Однако необходимо убедиться, чтобы такой счётчик никогда не входил в нулевое состояние.

Тестирование цифровых устройств

В отличие от обычного счётчика, РСЛОС переходит из одного состояния в другое не в порядке двоичного счёта, что позволяет его использовать для генерации тестового сигнала при обнаружении ошибок в логических схемах ^[6] .

Также регистры сдвига с линейной обратной связью применяются во ( англ. built-in self-test , BIST ) для сигнатурного анализа (выявления ошибочных битов) в логических схемах. Подобные системы применяют ввиду ограниченности числа выводов микросхем (не все промежуточные значения битов можно подать на выход). Система BIST представляет собой 3 блока: генератор тестовой последовательности и сигнатурный анализатор, которые и строятся на основе РСЛОС, и контроллер тестов. Регистр сдвига в анализаторе «сжимает» результат схемы на тестовую последовательность в сигнатуру и продолжает работать до тех пор, пока всего его биты, кроме 0-го, не станут равными нулю, то есть до состояния $\left[1,\;0,\;0,\;...,\;0\right]$ $\left[1,\;0,\;0,\;...,\;0\right]$ . Наряду с РСЛОС работает двоичный счётчик, подсчитывающий количество тактов с момента окончания сжатия тестовой реакции. Если изначальное состояние регистра соответствовало эталонной сигнатуре (сигнатуре безошибочной схемы), то показание счётчика соответствует номеру ошибочного бита ^[14] ^[15] .

Так как РСЛОС производит сжатие с потерей данных, то есть вероятность, что в схеме с ошибками получившаяся сигнатура будет равна эталонной. Этого можно избежать, используя сигнатурный анализатор с несколькими входами.

Скремблирование

Регистры сдвига с линейной обратной связью применяются при скремблировании с целью получения цифрового потока со свойствами случайной последовательности. Псевдослучайная последовательность РСЛОС максимальной длины складывается по модулю 2 с потоком передаваемых битов, причём генерация последовательности происходит с той же скоростью, что и передача данных. Некоторые системы и технологии, использующие скремблирование:

ATSC ^[16] ;
DAB ;
DVB-T ;
NICAM ;
CDMA ;
Fast Ethernet ;
1000BASE-T Gigabit Ethernet ;
PCI Express 3.0 ;
SATA ;
Serial Attached SCSI ;
USB 3.0 ;
IEEE 802.11a ;
Bluetooth LE .

Notes

↑ Б. Скляр, 2007 .
↑ Linear Feedback Shift Registers in Virtex Devices
↑ ¹ ² ³ ⁴ ⁵ Б. Шнайер, 2013 .
↑ ¹ ² ³ ⁴ Габидулин, Кшевецкий, Колыбельников, 2011 .
↑ ¹ ² ³ Ю.Б. Кобзарев, 2013 .
↑ ¹ ² Ларин, 2008 .
↑ ¹ ² ³ ⁴ ⁵ Фомичёв, 2003 .
↑ Beker, Piper, 1982 .
↑ А. Сизоненко, 2012 .
↑ E. Barklan, E. Biham, N. Keller, 2008 .
↑ Y. Lu, W. Meier, S. Vaudenay, 2005 .
↑ D. Eastlake, J. Schiller, S. Crocker, 2005 .
↑ Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators
↑ B. Harrington, 2008 .
↑ О. Дяченко .
↑ В. Варгаузин, 1999 .

Literature

Шнайер Б. Прикладная криптография. Protocols, algorithms, source codes in the C language. — Триумф, 2013. — 816 с. — ISBN 978-5-89392-527-2 .
Габидулин Э. М. , Кшевецкий А. С. , Колыбельников А. И. Защита информации : учебное пособие — М. : МФТИ , 2011. — 225 с. - ISBN 978-5-7417-0377-9
<a href=" https://wikidata.org/wiki/Track:Q4130888 "> </a> <a href=" https://wikidata.org/wiki/Track:Q26887236 "> </a> <a href = " https://wikidata.org/wiki/Track:Q26887244 "> </a> <a href=" https://wikidata.org/wiki/Track:Q26887242 "> </a>
Ларин А. Л. Основы цифровой электроники — М. : МФТИ , 2008. — 314 с. — ISBN 978-5-7417-0228-4
<a href=" https://wikidata.org/wiki/Track:Q26906223 "></a><a href=" https://wikidata.org/wiki/Track:Q26906219 "></a>
Скляр Б. Цифровая связь. Теоретические основы и практическое применение. — Вильямс, 2007. — 1104 с. — ISBN 978-5-8459-0497-3 .
Кобзарев Ю. Б. Современная радиолокация. — Рипол Классик, 2013. — 708 с. — ISBN 978-5-4584-7357-6 .
Фомичёв В. М. Дискретная математика и криптология : Курс лекций / под ред. Н. Д. Подуфалов — М. : Диалог-МИФИ , 2013. — 397 с. — ISBN 978-5-86404-185-7
<a href=" https://wikidata.org/wiki/Track:Q26896777 "></a><a href=" https://wikidata.org/wiki/Track:Q26896775 "></a><a href=" https://wikidata.org/wiki/Track:Q26896778 "></a><a href=" https://wikidata.org/wiki/Track:Q26906187 "></a>
Beker H. , Piper F. Cipher systems: the protection of communications — London : Northwood Books , 1982. — 427 p. — ISBN 978-0-7198-2611-5
<a href=" https://wikidata.org/wiki/Track:Q84 "></a><a href=" https://wikidata.org/wiki/Track:Q27077665 "></a><a href=" https://wikidata.org/wiki/Track:Q27077669 "></a><a href=" https://wikidata.org/wiki/Track:Q27077663 "></a><a href=" https://wikidata.org/wiki/Track:Q27077671 "></a>
Сизоненко А. Б. Многоканальный цифровой источник шума на основе рекуррентного регистра сдвига . — Журнал «Спецтехника и связь» №3, 2012. Архивная копия от 29 ноября 2014 на Wayback Machine
Barklan E. , Biham E. , Keller N. Instant ciphertext-only cryptanalysis of GSM encrypted communication . — Journal of cryptology №21-3, 2008.
Lu Y. , Meier W. , Vaudenay S. Instant ciphertext-only Cryptanalysis of GSM encrypted communication . — Crypto №3621, 2005. (недоступная ссылка)
Eastlake D. , Schiller J. , Crocker S. Randomness requirements for security . - 2005.
Harrington B. Get your boost from BIST . — 2008. (недоступная ссылка)
Дяченко О. Н. Компактный анализ над полем GF(3).
Варгаузин В. Принципы цифрового телевидения стандарта ATSC. — Журнал Теле-Спутник №9(47), 1999.

Links

LFSR reference (англ.) . Теория и реализация LFSR, последовательности максимальной длины и полные таблицы отводных последовательностей для длин от 7 до 16 миллионов (от 3 до 24 битов), а также частичные таблицы для длин до 4 миллиардов (от 25 до 32 битов)
International telecommunications union recommendation O.151 (англ.) . Август 1992
Pseudo-random number generation routine (англ.)
[3] (англ.)
Simple explanation of LFSRs for engineers (англ.)
Feedback terms (англ.)
An implementation of a cryptographically secure shrinking pseudorandom number generator (англ.)
Методы и задачи криптографической защиты информации (недоступная ссылка)

[_884bb731adfcf1a4-1] Б. Скляр, 2007 .

[2] Linear Feedback Shift Registers in Virtex Devices

[_97c38d0090b94b50-3] ¹ ² ³ ⁴ ⁵ Б. Шнайер, 2013 .

[_e98c0fc999e22496-4] ¹ ² ³ ⁴ Габидулин, Кшевецкий, Колыбельников, 2011 .

[_e45da462888d0612-5] ¹ ² ³ Ю.Б. Кобзарев, 2013 .

[_58cbe161b14dd848-6] ¹ ² Ларин, 2008 .

[_73a3c0e3e43d81d6-7] ¹ ² ³ ⁴ ⁵ Фомичёв, 2003 .

[_358d977e8a5ca770-8] Beker, Piper, 1982 .

[_3229f1d045579e8b-9] А. Сизоненко, 2012 .

[_418b5d45bba5a6a6-10] E. Barklan, E. Biham, N. Keller, 2008 .

[_8a90d56207508cdf-11] Y. Lu, W. Meier, S. Vaudenay, 2005 .

[_8a8c5ecfc44bdf7e-12] D. Eastlake, J. Schiller, S. Crocker, 2005 .

[13] Efficient Shift Registers, LFSR Counters and Long Pseudo-Random Sequence Generators

[_024587bf89713b83-14] B. Harrington, 2008 .

[_7352782730a45699-15] О. Дяченко .

[_07cd4a48066a7751-16] В. Варгаузин, 1999 .

Linear Feedback Shift Register

Description

Principle of Operation

Properties

Frequency

Linear complexity

Correlation Independence

Software Implementation

Fibonacci Configuration

Galois Configuration

Example generated sequence

Fibonacci Configuration

Galois Configuration

Primitive polynomial generation

Advantages and disadvantages

Benefits

Weaknesses

Ways to Improve the Cryptographic Strength of Generated Sequences

Multi Shift Generators

Nonlinear Transform Generators

Generators with different shift register timing

Stop-go Generator

Self-cutting generator

Multi-speed Internal Product Generator

Gollmann Cascade

Majority Generators

Application

Use in cryptography

Использование в качестве счётчиков

Тестирование цифровых устройств

Скремблирование

See also

Notes

Literature

Links

More articles: