# Device for generating pseudo-random series of binary numbers with usage of elliptic curves

FIELD: engineering of methods for cryptographic transformation of data, possible use in communication, computer and informational systems for cryptographic encryption of information and computation of numbers close to random.

SUBSTANCE: device contains two memory blocks, current time moment timer, two concatenation blocks, two hash-function computation blocks, operation block, computing block.

EFFECT: increased complexity of encryption analysis and decreased probability of reliable prediction of next values of pseudo-random series bits while increasing operation speed of generator.

1 dwg

The invention relates to the field of telecommunications and computing, and more particularly to methods and devices for cryptographic transformation of data, and can be used in communication, computing and information systems for cryptographic close binary information and calculate numbers that are close to random, when it is necessary to compute the values of the session keys and other information, which must meet the requirements of low predictability and high entropy values when communicating government, law enforcement, defense, banking and industrial institutions, when there is a need of storing and transferring confidential information, and communication on the basis of noise-like signals.

A device for generating random numbers [Tezuka S. Pseudorandom number generator. The US patent No. 5046036 from 3.09.1991,, CL G 06 F 007/38]in which to calculate the values of pseudo-random sets of numbers using a set of conversion synchrophasing with the help of the generator of the so-called M-sequences and three kinds of conversion of the received sequences:

multiplication of a vector R with values obtained from a generator of M-sequences is initially given a matrix G, addition modulo 2 two output bits of the generator M-posledovatel the values;
bit lookup S_{i}the result of multiplying a vector R for the matrix G.

However, the device has drawbacks consisting in low reliability of the operations of the generator (due to the use of generators of M-sequences that do not have sufficient cryptographic strength [Ivanov M.A., Chugunkov I.V. Theory, application and evaluation of the quality of pseudorandom generators. M: Cadiz image, 2003 - 240 C.]), as well as the need for a truly random values synchrophasing with which the computation of M-sequences [agranovski AV, Hadi R.A. Practical cryptography: algorithms and their programming. M: salt Press, 2002 - 256 C.], which is essential for use of this device in practice.

It is also known another device for generating a pseudorandom sequence of bits [Mark, J.G., Tazartes D.A., Tazartes D.I., Wiener D.P. Fiber-optic gyro utilizing pseudorandom-bit-sequence light modulation. The US patent No. 6130755 from 10.10.2000,, CL G 01 C 019/72], which is based on the choice of 0 or 1 as the next bit pseudo-random sequence depending on the test results of the previous bits in the sequence in accordance originally specified criteria. The principle of operation is based on two types of criteria - if one group of criteria (the so-called "0-criter and"), select the zero value of the next output bit sequence, if satisfied the second criteria (the so-called "1-criteria"), as the output bits of the selected unit. The essence of the criteria is to measure the properties of a chain of previous output bits of sufficient length. As a next bit of the calculated pseudo-random sequence is selected the next bit received other more arbitrary method (for example, by adding the last j (j=1, 2, 3...) bits modulo 2).

However, this device has the disadvantages that are associated with the possibility of cryptanalysis output sequences due to the high predictability of the next computed bit when 0-criteria 1 and criteria known cryptanalytic and low speed of operations, since at each iteration analyzed a large amount of information about the computed output sequence and evaluated only one bit of information.

The closest in technical essence to the present invention is a device for generating pseudo-random sequences [DeBellis R.S., Smith R., Yeh P.C. Pseudorandom number generator with backup and restoration capability. The US patent No. 6104810 from 15.08.2000,, CL G 01 C 019/72], adopted for the prototype. The principle of the device is based on the fact that to calculate importance is th pseudo-random set of binary numbers is used computational conversion of the input random data to obtain the output pseudo-random binary sequence. In the prototype values of the pseudo-random sequence is calculated by using a deliberately strong function to the value dependent on the current time, and a secret parameter, then the received bits are fed to the input of the hash function of MDC-4 [Schneier B., Applied cryptography. Protocols, algorithms, and source code in C language. SPb: Triumph, 2002 - 816 S.], and its result is stored as the value of the pseudo-random sequence. The value of the secret parameter is updated regularly by computing a hash function from the aggregate current value of the secret parameter and the current value of time. The algorithm also provides the backing of the secret values of the parameter used in the event of a system restart. This reduces the likelihood of re-calculations used pseudo-random number sequences after the device is restarted.

The disadvantages of the prototype are low speed, caused by the need for repeated application of the hash function of MDC-4, as well as additional requirements for high entropy and the lengths of bit blocks of information about the current time and the current secret parameter used when generating the values of the pseudo-random sequence.

The technical result obtained from unedr the of the present invention, is to eliminate these disadvantages, i.e. an increase in the complexity of the cryptanalysis of the received pseudo-random sequences, reducing the likelihood of a confident prediction of the following values of binary numbers output sequence.

This technical result is achieved due to the fact that the device for generating pseudo-random sequence of binary numbers using elliptic curve consists of block 1 - block memory for storing parameters used elliptic curve and the current value of the secret parameter S_{y}(block 1 has one input for updating the secret parameter S_{y}and four outputs: output 1 for reading the parameter S_{y}exit 2 for reading the parameters of the elliptic curve, the outputs 3 and 4 for reading the coordinates of the primitive element In the group of points of an elliptic curve), block 2 (block timer, which has one output, which reads the current value of the timer in a sequence of bits), operating units 3.1 and 3.2, calculate the values of the hash function MD5 (blocks have one input to which is fed a sequence of bits, and a single output which reads the value of the hash functions MD5 filed on the block of input data in the form of a sequence of bits), operational unit 4 converts placentas the activity bit in a couple of sequences of bits,
representing the coordinates of a point of an elliptic curve (the block has two inputs: input 1 to which is fed a sequence of bits, and input 2 to which is fed the value of the parameters of the elliptic curve as a sequence of bits, and two outputs, which reads the coordinates of the resulting point ellpitical curve in the form of sequences of bits), the computing unit 5, producing the multiplication of two points of the elliptic curve whose coordinates are sent to the input in the form of sequences of bits (block 5 has inputs 1, 2, 3 and 4, which serves the coordinates of the operands of the multiplication in the form of sequences of bits - one input to the coordinate of each operand and input 5, which serves the parameters of the elliptic curve as a sequence of bits, and output 1, which reads the bit sequence representing the y-coordinate of the multiplication), operating units 6.1 and 6.2, producing a concatenation of input blocks of two sequences of bits (each block has two inputs 1 and 2 for input sequences of bits and one output which reads the result of the concatenation of the input sequence), memory block 7, accumulating the output pseudo-random bit sequence (unit has one the entrance to the adoption accumulated on oinoi information and one output for reading),
the yield of 1 block 1 is connected to input 2 block 6.1; exit 2 unit 1 is connected to input 2 of block 4 and input 5 of block 5; output 3 block 1 is connected to input 3 of block 5; output 4 unit 1 is connected to input 4 of block 5; exit 1 unit 2 is connected to the input 1 unit 6.1 and input 2 unit 6.2; exit 1 unit 3.1 is connected to the input 1 of block 4; exit 1 unit 3.2 is connected to the input 1 of block 7; exit 1 unit 4 is connected to the input 1 of block 5; output 2 unit 4 is connected to the input 2 of block 5; exit 1 unit 5 is connected to the input unit 1 6.2; exit 1 block 6.1 is connected to the input unit 1 3.1; exit 1 unit 6.2 is connected to the input unit 1 3.2.

The principle of the device is based on computing the multiplicative group of points of an elliptic curve of the form E(X)={(x,y)|y^{2}=x^{3}+a*x+b} over the field GF(p,n). The device operates as follows. In block 1 boot initialization data (parameters p and n, a and b, a primitive element In the group of points of the curve E, the secret parameter S_{y}). Further work is as follows. Unit 6.1, the input of which is connected to the output unit 2 and output 1 unit 1 produces the concatenation of a bit sequence obtained at the output of the timer 2 and the bit sequence representing the current value of S_{y}. Block 3.1, input 1 which is connected to the output 1 block 6.1, performs calculation of a hash function from the obtained work unit 6.1 sequence b is so
Unit 4, an input 1 which is connected to the output 1 of block 3.1, and the input 2 - output 2 block 1 converts the output of block 3.1 coordinates of points of an elliptic curve E over the field GF(p,n), reading information on E, p, n from the block 1. Block 5 (inputs 1 and 2 are connected to the outputs 1 and 2 of block 4, the inputs 3, 4, 5 - outputs 3, 4, 2 block 1, respectively) computes the product of points of an elliptic curve E obtained in the previous step and the primitive element of the group of points E (a, b, p, n, and the coordinates of a point To read from unit 1 through its output terminals 2, 3, 4), and outputs the value of the y-coordinates of the resulting point. The result is written into the corresponding cell block 1 (input 1 is connected to the output). Unit 6.2 produces the concatenation of the values obtained in block 5, and the output value of block 2. Box 3.2 computes the value of the hash function from the unit 6.2. The resulting value is transmitted to the drive 7.

Thus, the work of the proposed device for generating a pseudorandom sequence of bits using elliptic curve consists of two stages. At the first stage of operation of the device initialization is required for information. Then the second stage begins, during which the calculations with elliptic curve and generates an output binary sequence is. If the length of the output sequence is less than desired, the step of computing with elliptic curve is repeated, and the result is appended to the output sequence as many times as necessary to achieve the required length of the output sequence.

To describe the operation of the device will introduce the following notation:

the parameters p and n, which allows to describe the Galois field GF(p,n);

the parameters a and b of the elliptic curve E, represented by the equation

E(X)={(x,y)|y^{2}=x^{3}+a*x+b}, where X is the point on the curve E, a and b are variables, x and y are the coordinates of X;

is a primitive element of the multiplicative group of points of the curve E;

- secret parameter S_{y}, which is the y-coordinate of the elliptic curve E;

- an integer variable T;

- output binary sequence Q of variable length.

For generating pseudo-random sequence of binary numbers is used computational transformation of non-random data to obtain the output pseudo-random binary sequence. As computational transformations use the algorithm for computing with elliptic curve of the form E(X)={(x,y)|y^{2}=x^{3}+a*x+b}, where the user sets the value of the secret parameter S_{y}equal to the y-coordinate of the point In the first data conversion or proishodit loading previously saved values of S_{
y}, cleaning the binary sequence Q to store the output sequence of values; integer variable T is assigned the value of the current time as the number of seconds since 1970 to the current time, the secret parameter S_{y}value is assigned to the y-coordinates of a point In e(h(S_{y}|T)), where e(x) is a function that converts a number to a point of the elliptic curve E, the function h(x) is a hash function MD5, S_{y}- the current value of the secret parameter stored for subsequent use, to a binary sequence Q appends the value of h(T|S_{y}), if necessary, the steps for computing the new value of the parameter S_{y}and the addition sequence Q are repeated, the output sequence is a binary sequence Q.

To implement the operation using the input data on the Galois field GF(p,n), the parameters of the elliptic curve E having over the field GF(p,n) is not less than 30*2^{128}points, and a primitive element of the multiplicative group of points of an elliptic curve E.

The function h(x) according to [Schneier B., Applied cryptography. Protocols, algorithms, and source code in C language. SPb: Triumph, 2002 - 816 S.] accepts binary sequence of arbitrary length and computes the hash value represented in binary is posledovatelnosti fixed length, equal to 128 bits.

The function f(x) converts a binary sequence x of length 128 bits at a point on the elliptic curve E. the Value of e(x) is computed by the following algorithm. Selected integer 1≤j≤30. Between the number of species 30*x+j from the interval [0, (2^{128}-1)*30], and part of the many elements of GF(p,n) establish a one-to-one correspondence (known from the prior art method of establishing such compliance is in the interpretation of the numbers p-primary account number X as coefficients of a polynomialabove the relevant field - see, for example [Koblitz I. Course in number theory and cryptography. M: Scientific publishing house NT, 2001 - 254 S.]). Then calculate the value offrom the obtained V take the square root; if the root has been extracted, accept for the point with coordinates (, sqrt(V)), otherwise assign to variable j another integer value from the interval [1, 30] and repeat the calculation until such time as the number of V will not be a complete square. The probability that the application of this algorithm will not yield results, is about 2^{-30}.

The invention is illustrated by the drawing, which shows a block diagram of the proposed computing device.

Device for generating a pseudorandom sequence is binary integers using elliptic curves,
containing the first block of memory having cells for storing parameters used elliptic curve and the cell for recording and storing the current value of the secret parameter S_{y}the timer, which reads the current value of time as a sequence of binary bits, two blocks compute the hash function operation unit for converting the sequence of binary bits in a couple of sequences of binary bits representing the coordinates of a point of the elliptic curve computational unit that produces the multiplication of coordinate values of points on an elliptic curve, two block concatenation producing concatenation received at their inputs sequences of binary bits, the second block of memory that is used to accumulate the output pseudo-random sequence of binary numbers, with the first data output of the first memory block from which to read the value of the current secret parameter S_{y}connected with the second input of the first block concatenation, with the first input connected to the output of the timer and the second input of the second block concatenation, the output of the first block concatenation is connected to the input of the first unit for computing a hash function whose output is connected to the first input of the operational block, the second input is from the second information out first what about the memory block receives the parameters of the elliptic curve,
the first and second outputs of the operational unit, on which are formed the coordinate values of points of an elliptic curve, is connected with the first and second information inputs of the computing unit, the third and fourth information the input of which is connected with the third and fourth information outputs of the first memory block from which to read the coordinates of the primitive element In the group of points of an elliptic curve, the fifth information input of the computing unit is connected with the second information output of the first memory block, the output of the computing unit, which is formed by a sequence of binary bits representing the y-coordinate of the multiplication and the current value of the secret parameter S_{y}connected to the first input of the second block concatenation and the input cell of the first memory block that stores the value of the current secret parameter S_{y}the output of the second block concatenation is connected to the input of the second unit for computing a hash function whose output is connected to the input of the second memory block, the hash function used by the hash function MD5.

**Same patents:**

FIELD: cryptographic method and chip-card for encoding information, methods for creating electronic signatures.

SUBSTANCE: at least one calculation step is performed, providing for realization of E operation of modular exponentiation in accordance to formula E=x^{d}(mod p·q), where d and mod p·q are components of a secret key, while parallel represent first simple multiplier, q is second simple multiplier, d is level coefficient, and x represents base, while operation E of modular exponentiation is performed in accordance to Chinese theorem about remainders.

EFFECT: decreased amount of computing operations and machine time costs during simultaneous increase of level of data protection from unsanctioned access.

4 cl

FIELD: computer engineering; cryptographic systems.

SUBSTANCE: method is based on entropy valuation calculation and writing of mixed packed data into corresponding cells in different memory block areas. On the basis of written data new initial value is formed. Device for initial value of pseudorandom value generator forming contains data source analysis and current entropy valuation calculation means, data package means, data mix means, data accumulation and entropy valuation forming means, new initial value forming means.

EFFECT: method and device provide the capability of initial values forming, which provide dynamic source speed valuation, classification of sources by fast and slow, reliable and unreliable, and also forming of initial values taking into account speed characteristics of sources and reliability of these sources.

10 cl, 2 dwg

FIELD: computer science, possible use in imitators of random processes, and also in specialized and universal computing machines.

SUBSTANCE: device has random number sensor, clock impulse generator, stepped voltage generator, comparison block, counter, decoder, trigger, impulse generator, memory blocks, delay elements, AND elements, multiplexer, adder, block for setting source data, block of adders, block of subtracters, block of amplitude discriminators, code-amplitude transformer, blocks of elements AND, elements OR.

EFFECT: expanded functional capabilities of device.

1 dwg

FIELD: computer science.

SUBSTANCE: generator has set-point generator 1, generator 2 of exponential voltage, generator 3 of evenly distributed random numbers, digital-analog converter 4, elements OR 5,6, block 7 for comparison, device for pulse generation 8, forbidding element 9, trigger 10, multiplication block 11, input 12 and output 13 of device. Requests stream is formed of elementary stream by excluding one request with preservation of second request, i.e. at output 13 of generator through temporal ranges, distributed in accordance to Erlang law of second order, pulses are generated, modeling receipt of requests.

EFFECT: decreased hardware costs.

1 dwg

FIELD: engineering of pseudo-noise series generators with arbitrary number of bits, while said number of bits is transferred in parallel manner during each clock pulse.

SUBSTANCE: beginning values of states are loaded in registers of parallel pseudo-noise generator, which immediately generates following n bits of pseudo-noise series, where n - arbitrary number, depending on required productiveness level. Then, first sub-portion of pseudo-noise generator in accordance to invention receives current state of pseudo-noise generator and outputs state of n bits pseudo-noise generator in the future.

EFFECT: increased speed of operation, realization of parallel processing for capturing and demodulating processes.

3 cl, 9 dwg

FIELD: computer science.

SUBSTANCE: device has random numbers source, N-digit selector-multiplexer, RAM, ranges control block, generations number control block, J-input OR element, AND elements block. Because series of given values of data set is broken in ranges and frequency of their appearance is set within certain limits, random series is generated with distribution law, presented in form of ranges.

EFFECT: broader functional capabilities.

3 cl, 7 dwg

FIELD: cryptography.

SUBSTANCE: method includes generating random numbers with use of displacement register with check connection, elementary digit of which is a q-based symbol (q=2^{l}, l - binary symbol length) at length of q-based digits register, in check connection networks nonlinear two-parameter operations on q-based symbols F (u_{b}, u_{d}) are used, on basis of random replacement tables, for generating next random number values z_{1}=F(u_{i}, u_{j}), z_{2}=F(u_{t}, u_{m}), z_{g}=F(z_{1}, z_{2}) are calculated, where u_{i}, u_{j}, u_{t}, u_{m} - values of filling of respective register digits, value of result in check connection networks z_{g} is recorded to g digit of displacement register and is a next result of random numbers generation, after which displacement of register contents for one q-based digit is performed.

EFFECT: higher speed and efficiency.

3 cl

FIELD: cryptography.

SUBSTANCE: method includes generating random numbers with use of displacement register with check connection, elementary digit of which is a q-based symbol (q=2^{l}, l - binary symbol length) at length of q-based digits register, in check connection networks nonlinear two-parameter operations on q-based symbols F (u_{b}, u_{d}) are used, on basis of random replacement tables, for generating next random number values z_{1}=F(u_{i}, u_{j}), z_{2}=F(u_{t}, u_{m}), z_{g}=F(z_{1}, z_{2}) are calculated, where u_{i}, u_{j}, u_{t}, u_{m} - values of filling of respective register digits, value of result in check connection networks z_{g} is recorded to g digit of displacement register and is a next result of random numbers generation, after which displacement of register contents for one q-based digit is performed.

EFFECT: higher speed and efficiency.

3 cl

FIELD: computer science.

SUBSTANCE: device has random numbers source, N-digit selector-multiplexer, RAM, ranges control block, generations number control block, J-input OR element, AND elements block. Because series of given values of data set is broken in ranges and frequency of their appearance is set within certain limits, random series is generated with distribution law, presented in form of ranges.

EFFECT: broader functional capabilities.

3 cl, 7 dwg

FIELD: engineering of pseudo-noise series generators with arbitrary number of bits, while said number of bits is transferred in parallel manner during each clock pulse.

SUBSTANCE: beginning values of states are loaded in registers of parallel pseudo-noise generator, which immediately generates following n bits of pseudo-noise series, where n - arbitrary number, depending on required productiveness level. Then, first sub-portion of pseudo-noise generator in accordance to invention receives current state of pseudo-noise generator and outputs state of n bits pseudo-noise generator in the future.

EFFECT: increased speed of operation, realization of parallel processing for capturing and demodulating processes.

3 cl, 9 dwg

FIELD: computer science.

SUBSTANCE: generator has set-point generator 1, generator 2 of exponential voltage, generator 3 of evenly distributed random numbers, digital-analog converter 4, elements OR 5,6, block 7 for comparison, device for pulse generation 8, forbidding element 9, trigger 10, multiplication block 11, input 12 and output 13 of device. Requests stream is formed of elementary stream by excluding one request with preservation of second request, i.e. at output 13 of generator through temporal ranges, distributed in accordance to Erlang law of second order, pulses are generated, modeling receipt of requests.

EFFECT: decreased hardware costs.

1 dwg