RU2815485C1 - Pseudorandom number generator - Google Patents

Abstract

FIELD: computer engineering; electrical communication equipment.

SUBSTANCE: present technical solution relates to computer engineering for telecommunication. Technical result is achieved due to the fact that the pseudorandom numbers generator, consisting of two n-bit registers, an addition unit in GF(2ⁿ), two multiplication units in GF(2ⁿ), where outputs of the second register are connected to inputs of multiplication units in GF(2ⁿ), outputs of the first multiplication unit in GF(2ⁿ) are connected to inputs of the first register, outputs of the second multiplication unit in GF(2ⁿ) are connected to the first inputs of the addition unit in GF(2ⁿ), the second inputs of which are connected to the outputs of the first register, additionally comprises the second addition unit in GF(2ⁿ) and modulo 2ⁿ addition unit, wherein the outputs of the first multiplier in GF(2ⁿ) are connected to the first inputs of the second addition unit in GF(2^W) and the third inputs of the first addition unit in GF(2ⁿ), which outputs are connected to the first inputs of modulo 2ⁿ addition unit, the second inputs of which form the control inputs of the generator, second inputs of the second addition unit in GF(2ⁿ) are connected to outputs of modulo 2ⁿ addition unit, and outputs of the second addition unit in GF(2ⁿ) are connected to inputs of the second register.

EFFECT: increased period of generated sequence.

1 cl, 4 dwg

Description

The invention relates to computer technology and telecommunications, and is intended to solve problems of protecting computer information. The most preferred area of use of the invention is the implementation of stochastic methods of information security.

In the set of features of the claimed invention, the following terms are used.

Finite field or Galois field GF(g) (GF - Galois Field, q=p ⁿ - number of field elements, p - simple, n - natural) - a finite set of elements with the following properties:

1) two operations are defined in the field, one is conventionally called addition, the other - multiplication;

2) for the field elements α, β, γ the following relations are valid: α+β=β+α, αβ=βα, (α+β)γ=αγ+βγ;

3) in the field there are zero and unit elements, denoted respectively as 0 and 1, for which 0+α=α, 0α=0, 1α=α are true;

4) in the field for any α≠0 there is an element inverse to it by addition, denoted (-α), for which α+(-α)=0; and its inverse element by multiplication, denoted α ^-1 , for which αα ^-1 =1;

5) any non-zero element of the field can be represented as a degree of a primitive element: ∀α≠0 α=ω ⁱ , thus, the finite field can be represented as GF(q)={0, ω ⁰ = ^: 1, ω, ω ² ,…,ω ^q-2 }.

Pseudo-random number generators (PRNG) are the basis of stochastic methods of information security; the use of GPS ensures unpredictable behavior of a digital object and its means of protection.

A pseudorandom number generator is known, operating in a finite field GF(2 ⁿ ), consisting of N registers of capacity n, N addition blocks in GF(2 ⁿ ), where n>1 is an integer, N multiplication blocks in GF(2 ⁿ ), and the value by which the multiplication occurs in the (i+1)-th multiplication block is equal to the coefficient a _{i of} the characteristic polynomial ϕ(x)=(x+1)λ(x)=x ^N +a ^N-1 +…+a ₂ x ² +a ₁ x+a ₀ , where i=0, 1, 2, …, (N-1), a _i ,∈GF(2 ⁿ ),λ(x) is a polynomial of degree (N-1), primitive over GF(2 ⁿ ), a block of control actions, the outputs of the Nth register are connected to the inputs of all multiplication blocks, the outputs of the (j+1) multiplication blocks and the outputs of jx registers are connected, respectively, to the first and second inputs of jx addition blocks, outputs which are connected to the inputs of the (j+1) registers, where j=1,2,... (N-1), the first inputs of the N-th addition blocks in GF(2 ⁿ ) are connected to the outputs of the first multiplication block, and the outputs are connected with the inputs of the first register, the second inputs of the N-th addition block and the third inputs of the jx addition blocks are connected to the corresponding outputs of the control action block (RF Patent No. 2740339, Pseudo-random number generator, BI No. 2, 01/13/2021).

The disadvantage of the known device is its complexity (a block of control actions is required) and the linear law of the formation of a pseudo-random sequence (all calculations are performed in finite fields).

As a prototype, a pseudo-random number generator was selected, operating in a finite field GF(2 ⁿ ), where n>1 is an integer consisting of N registers of bit depth n, (N-1) addition blocks in GF(2 ⁿ ), N multiplication blocks in GF(2 ⁿ ), and the value by which the multiplication occurs in the (i+1)th multiplication block is equal to the coefficient a of the characteristic polynomial of degree N ϕ(x)=x ^N +a ^N-1 +…+a ₂ x ² +a ₁ x+a ₀ , where i=0, 1, 2, …, (N-1), a _i ∈GF(2 ⁿ ), the outputs of the Nth register are connected to the inputs of all multiplication blocks, the outputs (j+1 )-th multiplication blocks and the outputs of the jx registers are connected, respectively, to the first and second inputs of the jx addition blocks, the outputs of which are connected to the inputs of the (j+1)-th registers, where j=1, 2, ...(N-1), the inputs of the first registers are connected to the outputs of the first multiplication block (US Patent No. 9298423, Methods and systems for determining characteristics of sequence of N-state symbols, Mar. 29, 2016, Fig. 1). A similar device is described in the textbook ^“ Stochastic methods and means of protecting information in computer systems and networks / M. A. Ivanov, I. V. Chugunkov, N. A. Matsuk et al. - M.: Kudits-Press, 2009 ^” , page 82, fig. 2.12c.

If a polynomial of the form ϕ(x)=(x+1)λ(x)=x ² +a ₁ x+a ₀ is chosen as a characteristic polynomial, where λ(x) is a polynomial of the first degree, primitive over GF(2 ⁿ ) , the switching diagram of the device consists of 2 ⁿ cycles of length 2 ⁿ -1 and 2 ⁿ cycles of length 1, i.e. has the form (2 ⁿ -1)(2 ⁿ )-1(2 ⁿ ). Thus, despite the presence of 2n memory elements, the maximum length of the generated sequence is 2 ⁿ -1, which is much less than the potentially possible 2 ²ⁿ .

The purpose of the invention is to increase the length of the generated sequence to a value of 2 ⁿ (2 ⁿ -1) = (2 ²ⁿ -2 ⁿ ), i.e. 2 ⁿ times greater than in the prototype.

The declared effect is ensured due to the fact that the switching diagram of the generator includes not 2 ⁿ⁺¹ cycles as in the prototype, but only two cycles of length (2 ²ⁿ -2 ⁿ ) and 2 ⁿ .

This goal is achieved by the fact that a pseudo-random number generator consisting of two registers of capacity n, an addition block in GF(2 ⁿ ), two multiplication blocks in GF(2 ⁿ ), where n>1 is an integer, and the values by which the multiplication occurs in the first and second multiplication blocks in GF(2 ⁿ ), are equal, respectively, to the coefficients a ₀ and a ₁ of the characteristic polynomial ϕ(x)=(x+1)λ(x)=x ² +a ₁ x+a ₀ , where a ₁ , and ₀ ∈GF(2 ⁿ ), λ(x) is a polynomial of the first degree, primitive over GF(2 ⁿ ), the outputs of the second register are connected to the inputs of the multiplication blocks in GF(2 ⁿ ), the outputs of the first multiplication block in GF( 2 ⁿ ) are connected to the inputs of the first register, the outputs of the second multiplication block in GF(2 ⁿ ) are connected to the first inputs of the addition block in GF(2 ⁿ ), the second inputs of which are connected to the outputs of the first register, additionally contains a second addition block in GF(2 ⁿ ) and an addition block modulo 2 ⁿ , and the outputs of the first multiplication block in GF(2 ⁿ ) are connected to the first inputs of the second addition block in GF(2 ⁿ ) and the third inputs of the first addition block in GF(2 ⁿ ), the outputs of which are connected with the first inputs of the addition block modulo ²ⁿ , the second inputs of which form the control inputs of the generator, the second inputs of the second addition block in GF( ²ⁿ ) are connected to the outputs of the addition block modulo ²ⁿ , and the outputs of the second addition block in GF( ²ⁿ ) connected to the inputs of the second register.

In fig. Figure 1 shows the circuit of the prototype device with N=2, ϕ(x)=x ² +a ₁ x+a ₀ , where 1.1, 1.2 are n-bit registers; 2 - addition block in the GF(2 ⁿ ) field; 3.1 and 3.2 - multiplication blocks a ₀ and a ₁ in the GF(2 ⁿ ) field, respectively. In fig. 1 shows the type of switching diagram in the general case and for n=2, 3 and 4.

In fig. Figure 2 shows an example of a prototype device for the case N=n=2, ϕ(x)=(x+1)(x+ω)=x ² +ω ² x+ω, where λ(x)=x+ω is a polynomial , primitive over GF(2 ² )={0,1,ω, ω ² }, ω ³ =1, ω ² +ω+1=0, its operating equations, as well as its switching diagram, consisting of four cycles of length 3 and four cycles of length 1.

In fig. Figure 3 shows the diagram of the proposed device for the case ω(x)=x ² +a ₁ x+a ₀ , 1.1 and 1.2 are n-bit registers, 2 is the first n-bit addition block in the field GF(2 ⁿ ), 3.1 and 3.2 - first and second n-bit multiplication blocks in the GF(2 ⁿ ) field, 4 - second n-bit addition block in the GF(2 ⁿ ) field, 5 - second n-bit modulo 2 ⁿ addition block, 6 - control inputs generator (the number of which is n). The clock input of the device is connected to the clock inputs of the registers and is not shown in the diagram. In fig. Figure 3 also shows the operating equations of the generator and the type of its switching diagram for n=2, 3 and 4. The number of possible values at the control inputs 6 is equal to the number of numbers that are smaller and relatively prime to the number 2 ⁿ .

In fig. Figure 4 shows an example of the proposed device for the case n=2, ϕ(x)=(x+1)(x+ω)=x ² +ω ² x+ω, where λ(x)=x+ω is a polynomial, primitive over GF(2 ² )={0, 1, ω, ω ² }, ω ³ =1,ω ² +ω+1=0. 1.1 and 1.2 are two-bit registers, 2 is a two-bit first addition block in the GF(2 ² ) field, 3.1 and 3.2 are two-bit multiplication blocks by ω and ω ² in the GF(2 ² ) field, respectively, 4 is a two-bit second addition block in field GF(2 ² ), 5 - two-bit addition block modulo 2 ⁿ , 6 - control inputs of the generator. The number of possible values at control inputs 6 is two, these are 1 and 3 (in binary form, 01 and 11, respectively). In fig. Figure 4 shows generator switching diagrams for c ₁ =1 and c ₁ =3. In both cases, the switching diagram looks like 12-4, i.e. consists of two cycles of length 12 and 4.

The device works as follows. Before starting work, all generator memory elements are set to their initial state, which must belong to a larger cycle of the switching diagram. The reset circuits are not shown in Figs. 3 and 4. For example, for the cases shown in FIG. 4, registers 1.1 and 1.2 are set to any state of the large cycle of the switching diagram (cycle of length 12), for example 00 (with ₁ = 1) and 11 (with ₁ = 3). The output pseudo-random sequence is read from the output of one of the generator registers.

In the general case, the PRNG operating equations have the form shown in Fig. 3, where Qi(t) and Qi(t+1) are the states of the i-th register of the generator, respectively, at times t and (t+1), with ₁ - control action, i=1,2. The switching diagram of the device has the form (2 ²ⁿ -2 ⁿ )-2 ⁿ , i.e. consists of two code rings of length (2 ^{2 and} -2 ⁿ ) and 2 ⁿ .

For the case considered in FIG. 4, the switching diagram of the device looks like 12-4, i.e. consists of two code rings of length 12 and 4. It can be seen that when the generator operates correctly, the value of the convolution of the contents of all registers changes according to the law 0 1 ω ω ² 0 1 ^ω ω 2 0 1 ω ω ² ... with ₁ = 1 or according to the law 0 ω ² ω 1 0 ω ² ω 1 0 ω ² ω 1… with ₁ =3, i.e. changes in each clock cycle by 1 in the first case and by ω ² in the second.

It is important to note that the states of the generator that fall into the small code ring of the switching diagram depend on the type of control action from ₁ and the law of change in convolution in the small ring is the same as in the larger code ring.

The generator is focused on implementing the mechanism of hidden functions, which assumes that the PRNG is integrated into the structure of the protected digital device (DU). The execution of each function of the protected control center is permitted when the PRNG is in the appropriate state, while the states of the PRNG included in a small code ring of length 2 ⁿ allow the execution of hidden, especially important functions of the protected control center.

In addition to achieving the main goal of the invention - increasing the period of generated sequences, a number of additional advantages of the proposed technical solution can be noted:

- by choosing the appropriate value of n, it is possible to implement a different number of hidden functions in the protected data center;

- the device is effectively implemented, not only in software, but also in hardware, taking into account that all operations in the GF(2 ⁿ ) field are simply performed on XOR elements, and the device itself, due to its regular structure, is easily implemented in an integrated design;

- by monitoring the law of changes in the convolution of the contents of the generator’s memory elements, it is possible to organize self-monitoring of the correctness of its functioning in real time;

- the presence of a modulo ²ⁿ adder ensures the nonlinear nature of the law for generating the output sequence, which complicates the task of determining the structure of the generator from an intercepted fragment of a pseudo-random sequence of finite length.

Claims (1)

Pseudo-random number generator, consisting of two registers of capacity n, an addition block in GF(2 ⁿ ), two multiplication blocks in GF(2 ⁿ ), where n>1 is an integer, and the values by which the multiplication occurs in the first and second multiplication blocks in GF(2 ⁿ ), are equal, respectively, to the coefficients a ₀ and a ₁ of the characteristic polynomial ω(x)=(x+1)λ(x)=x ² +a ₁ x+a ₀ , where a ₁ , a ₀ ∈ GF (2 ⁿ ), λ(x) is a polynomial of the first degree, primitive over GF(2 ⁿ ), the outputs of the second register are connected to the inputs of the multiplication blocks in GF(2 ⁿ ), the outputs of the first multiplication block in GF(2 ⁿ ) are connected to the inputs first register, the outputs of the second multiplication block in GF(2 ⁿ ) are connected to the first inputs of the addition block in GF(2 ⁿ ), the second inputs of which are connected to the outputs of the first register, characterized in that it additionally contains a second addition block in GF(2 ⁿ ) and an addition block modulo 2 ⁿ , and the outputs of the first multiplication block in GF(2 ⁿ ) are connected to the first inputs of the second addition block in GF(2 ⁿ ) and the third inputs of the first addition block in GF(2 ⁿ ), the outputs of which are connected to the first inputs of the addition block modulo ²ⁿ , the second inputs of which form the control inputs of the generator, the second inputs of the second addition block in GF( ²ⁿ ) are connected to the outputs of the addition block modulo ²ⁿ , and the outputs of the second addition block in GF( ²ⁿ ) are connected with the inputs of the second register.

Images