Shift registers with feedback. Theoretical basis of operation Linear feedback

Linear shift register c feedback(Linear Feedback Shift Register - LFSR) - a mechanism for creating a pseudo-random sequence of binary bits. The register (Fig. 1) consists of a number of cells that are set by an initialization vector (most often a secret key). The operation of the register is determined by the presence or absence of a connection from each bit to the feedback. The taps of the feedback register are not fixed, but are part of the key. At the next step, the contents of the register cells are shifted one position to the right, and one bit remaining free as a result of the XOR operation is placed in the leftmost cell.

Rice. one. Linear register feedback shift

To achieve the maximum cipher gamma period, the number of digits m shift register is chosen to be one of the Mersenne primes (2, 3, 5, 7, 13, 17, 31, 61, 89, 107, 127, 521, 607, 1279, 2203 ...), and the internal links of the register must be chosen according to with irreducible primitive polynomials with highest degree m. In this case, the cipher gamma period can reach (2 m-1).

LFSR is fast and easy to implement in both software and hardware. With proper choice of feedback bits, the generated sequences have good statistical properties. LFSR is used as base element for building highly secure systems.

A cascade of registers is a set of LFSRs linked in such a way that the behavior of one LFSR depends on the behavior of the previous LFSR in the cascade. This "dependant" behavior is usually set up to control the shift counter of the next LFSR by the first LFSR.

For example, the register is shifted by one step if the value of the previous register is 1, and if the value is 0, then the register is shifted by two steps or otherwise. A large number of Such combinations provide very high security.

The most secure sequences are produced by a shrinking generator based on a simple interaction between the results of two LFSR registers. The bits of one result determine whether the corresponding bits of the second result will be used as part of the full "stream key". The compression generator is simple, scalable, and has good security properties. Its disadvantage is that the rate at which the "streaming key" is generated will not be constant unless some precautions are taken.

Fibonacci method with delays One of the widely used Fibonacci generators is based on the following iterative formula:

where Y k - real numbers out of range

Rice. 2. Round-robin encryption

The DES output feedback mode can be used to generate pseudo-random numbers, similar to how it is used to stream encryption. The output of each encryption stage is a 64-bit value, of which only the upper j bits are fed back for encryption. The 64-bit outputs constitute a sequence of pseudo-random numbers with good statistical properties.

The pseudo-random number generator, described in the ANSI X9.17 standard, is one of the most cryptographically secure pseudo-random number generators. Applications using this technology include financial security and PGP applications.

The ANSI X9.17 generator consists of the following parts (Figure 3):

1. Input: The generator is controlled by two pseudo-random inputs. The first input is a 64-bit representation of the current date and time ( DT i) that change each time the number is created. The second input is a 64-bit initial value, which is initialized to some arbitrary value and changed during the generation of a sequence of pseudo-random numbers ( Vi).

2. Keys: The generator uses three triple DES modules with two keys K 1 , K 2 . All three use the same 56-bit key pair, which must be kept secret and used only to generate a pseudo-random number.

Rice. 3. ANSI X9.17 pseudo-random number generator

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 is a simple XOR operation on some bits of a 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.

At software implementation LFSRs use a modified scheme: to generate a new significant bit, instead of using the tap sequence bits, each bit of the tap sequence is XORed with the generator output, replacing the old tap sequence bit. 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 generator based on RLSS, 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.

Feedback shift register ( FSR ) consists of two parts: shift register And feedback functions .

Shift register (Error: Reference source not found) is a sequence of bits. When a bit needs to be extracted, all bits of the shift register are shifted to the right by 1 position. The new leftmost bit is the value of the feedback function from the remaining bits in the register. Period The shift register is the length of the resulting sequence before it starts to repeat.

The simplest type of feedback shift register is linear shift register with feedback (LFSR – Left Feedback Shift Register) (Error: Reference source not found). The feedback is simply the XOR of some p bits. register, the list of these bits is called bypass sequence.

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 2 n -1 bits. The number of internal states and the period are equal, because filling the register with zeros will cause it to produce an infinite sequence of zeros, which is absolutely useless. Only with certain tap sequences, the LFSR will cycle through all 2 n -1 internal states. Such LFSRs are called LFSRwith a maximum period.

For a particular LFSR to have a maximum period, the polynomial formed from the tap sequence and the constant 1 must be primitive modulo 2 .

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, you can find the following entry: (32,7,5,3,2,1,0) . This means that to generate a new bit, you need to sum the thirty-second, seventh, fifth, third, second, and first bits using the XOR function.

The code for such an LFSR in C++ would be:

// Any value other than zero

ShiftRegister = ((((ShiftRegister >> 31)

^(ShiftRegister>>6)

^(ShiftRegister>>4)

^(ShiftRegister>>2)

^(ShiftRegister>>1)

^ShiftRegister)

& 0x00000001)<<31)

| (ShiftRegister >> 1);

return ShiftRegister & 0x00000001;

Software implementations of LFSRs are quite slow and run faster if they are written in assembler rather than C. One solution is to use 16 LFSRs in parallel (or 32 depending on the word length in the architecture of a particular computer). In this scheme, an array of words is used, the size of which is equal to the length of the LFSR, and each unit of a word in the array refers to its own LFSR. Provided that the same tap sequence numbers are used, this can give a noticeable performance gain.

FROM the feedback circuit 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 leftmost bit of the tap sequence bits to generate a new 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 (Error: Reference source not found).

This modification is called Galois configuration. In C language it looks like this:

static unsigned long ShiftRegister = 1;

void seed_LFSR (unsigned long seed)

ShiftRegister = seed;

int Galua_LFSR(void)

if (ShiftRegister & 0x00000001) (

ShiftRegister = (ShiftRegister ^ mask >> 1) | 0x8000000;

ShiftRegister >>= 1;

The payoff is that all XORs are performed in one operation. This circuit can also be parallelized.

By themselves, LFSRs are good pseudo-random sequence generators, but they have some undesirable non-random properties. Sequential bits are linear, making them useless for encryption. For LFSR length n the internal state represents the previous n generator output bits. Even if the feedback scheme is kept secret, it can be determined by 2 n generator output bits using special algorithms. In addition, large random numbers generated using consecutive bits of this sequence are highly correlated and, for some types of applications, are not random. Despite this, LFSRs are often used to create encryption algorithms. For this, several LFSRs are used, usually with different lengths and tap sequence numbers. The key is the initial state of the registers. Each time a new bit is needed, all registers are shifted. This operation is called clocking. The output bit is a function, preferably non-linear, of some bits of the LFSR. This function is called combining, and the generator as a whole - combining generator. Many of these generators are still safe today.

Linear Feedback Shift Register(RSLOS, eng. linear feedback shift register, LFSR ) is a bit word shift register, in which the value of the input (inserted) 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 generator output and its outputs. constituent parts. Then, by observing the output sequence, one can obtain information about these intermediate outputs, and thus hack the generator. Thomas Siegenthaler has shown that correlation independence can be precisely defined, 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 can be performed in one operation through parallelization, 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 should be noted that a loop of a fixed number of calls to the LFSR_Galois function in the Galois configuration is executed 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 of 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.

disadvantages

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 LM − 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. IN best case 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, that is, 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 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

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 is a simple XOR operation on some bits of a 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.

In addition to LFSR, shift registers with non-linear feedback, transfer feedback, etc. are also used.

A number of generators have been developed on the basis of the number-theoretic approach (Blum-Micali generators, RSA, BBS, compression, additive generators, etc.).

Mathematical support for the synthesis of stream cryptographic algorithms has been developed more fully and in detail in comparison with block cryptographic algorithms. However, to create stream ciphers, block cipher algorithms in OFB or CFB modes are often used.