RU173172U1 - NON-LINEAR FEEDBACK Pseudorandom Generator - Google Patents

Abstract

The utility model relates to computer technology and can be used in information processing and protection tools. A pseudo random number generator with nonlinear feedback is proposed, including a control signal block, a clock pulse generator, a shift register made in the form of a series of N “m-bit” memory registers and stochastic transformation blocks. New is that for the formation of non-linear feedback two blocks of stochastic transformation are sufficient, and the generator additionally contains a quasi-random switching block, including N / 2 logical summation channels, each of which implements one affine Boolean function. A non-linear feedback pseudo-random number generator is characterized by low resource consumption and allows generating gamma whose properties correspond to a truly random process with a maximum entropy value. 1 ill.

Description

The utility model relates to computer technology and can be used in the processing and protection of information.

Modern Earth remote sensing satellites have a radio line capable of transmitting information at speeds of 300 Mbit / s and higher. To protect the high-speed flow of information from unauthorized access, pseudo random number generators (PRNGs) are used.

A known pseudorandom number generator with nonlinear feedback [1], which is essentially the closest to the proposed utility model and selected as a prototype. The known PRNG contains a control signal block, a clock, a shift register, consisting of N "m-bit" memory registers and stochastic transformation blocks (R-blocks and S-blocks).

Each R-block is an adder, the main and auxiliary correspondence tables stored in the ROM-cells of the non-volatile memory device. The R-block has two inputs and one output. The S-block is a special case of the R-block with one input and consists of one main correspondence table. All S-blocks are connected in parallel to the shift register and their outputs (except the last) are connected to the offset input of the corresponding R-block. The output of the last S-block is connected to the recording input of the first memory register. The address input of each R-block is connected to the output of the corresponding memory register, and the output is connected to the recording input of the next memory register, while the output of the R-block located at the output of the last memory register is connected to the “m-bit” feedback bus, which is connected with the inputs of all S-blocks and at the same time is the output of the generator, and its bias input is with the control signal block. The output of the clock generator is electrically connected to the synchronization inputs of all memory registers and to the input of the control signal block.

The use of a large number of stochastic transformation blocks (R-blocks and S-blocks) gives the output gamut the necessary statistical properties. However, storing information in the form of a large number of correspondence tables and working with them requires a sufficiently large amount of ROM memory. This creates a high resource consumption of the known pseudo-random number generator with non-linear feedback, which complicates its hardware implementation.

The objective of the utility model is to reduce the resource consumption of a pseudo-random number generator with nonlinear feedback while maintaining the necessary statistical properties of the output gamma.

The problem is achieved in that the non-linear feedback pseudo-random number generator includes a control signal block, a clock pulse generator, a shift register made in the form of a series of N “m-bit” memory registers, the first and second stochastic transformation blocks. The output of the clock generator is electrically connected to the synchronization inputs of all the memory registers and to the input of the control signal block, the output of which is connected to the bias input of the first stochastic conversion block. The address input of the first block of stochastic conversion is connected to the output of the last storage register, and its output with the offset input of the second block of stochastic conversion. The address input of the second block of stochastic conversion is connected to the output of the first storage register, and the output to its recording input. The outputs of all the storage registers are combined into the output bus of the shift register. The generator further comprises a quasi-random switching unit, including N / 2 logical summation channels, each of which has 2m inputs and one output. The channel inputs are electrically connected in a given order determined by a random law on the set of non-repeating numbers from 0 to mx (N-1) with the output register shift bus, and the channel outputs are combined into the output bus of the quasi random switching unit.

A complete rejection of S-blocks and a significant reduction in the number of R-blocks can reduce the resource consumption of a pseudo-random number generator with nonlinear feedback.

The use of a multichannel quasi random switching unit that implements a system of affine Boolean functions of instantaneous states of the shift register allows us to provide the necessary statistical properties of the output gamma.

The utility model is illustrated by drawings: in FIG. 1 is a structural diagram of a non-linear feedback pseudo-random number generator; FIG. 2 shows a block diagram of a stochastic transformation block.

A non-linear feedback pseudo-random number generator (Fig. 1) consists of a control signal block 1, a clock pulse generator 2, a shift register made in the form of N “m-bit” memory registers 3 connected in series with each other, the first block of stochastic transformation 4 , the second block of stochastic transformation 5 and the block of quasi random switching 6.

Blocks of stochastic transformation 4, 5 (Fig. 2) are an adder of 7 Galois field elements modulo 2 ^{m of} dimension m × 2 ^m , the main correspondence table 8 and the auxiliary correspondence table 9. The tables are filled with non-repeating elements of the Galois field GF (2 ^m ), randomly mixed. Stochastic conversion blocks 4,5 have address input A, offset input B and output R.

The output of the clock 2 is electrically connected to the synchronization inputs C of all memory registers 3 and to the input of the control signal 1, the output of which is connected to the bias input B of the first block of stochastic conversion 4 (Fig. 1). The address input A of the first block of stochastic transformation 4 is connected to the output of the last storage register RG _N , and its output R is connected to the input of the offset B of the second block of stochastic conversion 5, whose output R is connected to the recording input DI of the first storage register RG ₁ . And the DO output of the first storage register RG _{1 is} connected to the address input A of the second block of stochastic conversion 5. The outputs DO of all the storage registers 3 are combined in the output bus 10 of the shift register.

The quasi random switching unit 6 includes N / 2 channels of logical summation 11. Each channel 11 has 2m inputs and one output and is implemented on (2m-1) two-input exclusive-OR logic elements. The channel inputs are electrically connected in a given order determined by a random law on the set of non-repeating numbers from 0 to mxN-1 with the output bus 10 of the shift register, and the channel outputs are combined in the output bus 12 of the quasi random switching unit 6.

The proposed device can be implemented both inside the chip programmable logic integrated circuit (FPGA), and on the basis of digital circuits of various series. For example, for the PRNG configuration N = 16 and m = 4, TTL microcircuits of the K155 series were selected as the elemental base. Namely, 16 K155TM8 microcircuits were used as 16 “4-bit” memory registers; in the block of stochastic transformation 5 for storing the main and auxiliary correspondence tables - K155RE6, as an adder 7 modulo 2 ^m (excluding carry bits) - K155IM3; In the quasi random switching unit 6, 14 K155LP5 microcircuits were used.

A pseudo random number generator with nonlinear feedback operates as follows. Upon the arrival of a positive edge of the clock pulse from the clock generator 2 simultaneously to the synchronization inputs From all memory registers 3, they store the signal from their recording inputs DI and transmit it to their outputs DO, from which the “m-bit” signals are transmitted to the output bus 10 of the register shift and simultaneously to the input of the recording of the subsequent storage register. From the DO output of the last storage register RG _{N, the} signal is transmitted to the address input A of the first block of stochastic conversion 4, to the bias input which simultaneously receives the signal from the block of control signal 1. The signals received at the first block of stochastic conversion 4 are summed in its adder 7 with summation in Galois field GF (2 ^m ), forming the output signal of the first block of stochastic transformation 4, which is transmitted to the bias input B of the second block of stochastic conversion 5, to address input A which At the same time, a signal is output from the DO output of the first memory register RG ₁ . In this case, all signals in the shift register are simultaneously shifted by “t” positions to the right. The signals arriving at the second block of stochastic transformation 5 are summed in its adder 7 with summation in the Galois field GF (2 ^m ), forming the output signal of the second block of stochastic transformation 5, which is transmitted to the input of the DI record of the first storage register RG ₁ , forming nonlinear feedback for next generator duty cycle.

All signals (“mxN”) received on the output bus 10 of the shift register are distributed in a predetermined order determined by a random law on the set of non-repeating numbers from 0 to mxN-1 over 2 m inputs of N / 2 channels of logical summation 11 of the block of quasi random switching 6. In each channel 11 2 tons of signal are transmitted to the inputs of two-input logic elements "exclusive OR". At the output of each channel, a signal is generated based on one affine Boolean function. The output signals of the channels are fed to the output bus 12 of the quasi random switching unit 6, forming a quasi random sequence of bits.

For example, for N = 16h m = 4, the following system of affine Boolean functions is used:

where x _k (t) is the instantaneous value of the signal of the kth output of the storage register (k = 1 ÷ 64);

y [1] -y [8] - output signals of the first and eighth channels of the quasi-random switching unit, which form the output pseudo-random sequence of bits.

The gammas of the proposed device passed Diehard [2] STSNIST [3] battery tests with a positive rating, which allows us to conclude that their properties correspond to a truly random process with a maximum entropy value.

A non-linear feedback pseudo-random number generator is characterized by low resource consumption and allows generating gamma whose properties correspond to a truly random process with a maximum entropy value. The properties of the generated scales make it possible to use them in the means of processing and protecting information.

Information sources:

1. Ivanov M.A. Cryptographic methods of information protection in computer systems and networks: textbook. allowance. Moscow, KUDITS-IMAGE, 2001, pp. 73-79.

2. Kharin Yu.S., Bernik VB, Matveev G.V. Mathematical foundations of cryptology: textbook. allowance. Minsk, BSU, 1999, pp. 69-71.

3. Rukhin A., Soto J., Nechvatal J., Smid M. A. Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST: NISTSpecialPublication, 2010, p.p. 2-1 - 2-40.

Claims (1)

A non-linear feedback pseudo-random number generator, including a control signal block, a clock, a shift register made in the form of a series of N “m-bit” memory registers, the first and second stochastic transform blocks, while the address input of the first stochastic transform block is connected to the output of the last memory register, the output of the clock generator is electrically connected to the synchronization inputs of all the memory registers and to the input of the control signal block, you One of which is connected to the bias input of the first stochastic transform block, characterized in that the output of the first stochastic transform block is connected to the bias input of the second stochastic transform block, the output of which is connected to the recording input of the first storage register, the output of which is connected to the address input of the second stochastic transform block, and the outputs of all the storage registers are combined into the output bus of the shift register, additionally contains a quasi-random switching unit, including conductive N / 2 logical summation of channels, each of which has 2m inputs and one output, the inputs of channels are electrically connected in a predetermined order determined by random law to set recurring numbers from 0 to

, with the output bus of the shift register, and the channel outputs are combined into the output bus of the quasi-random switching unit.

Images