RU2294559C1 - Device for generating pseudo-random series of binary numbers with usage of elliptic curves - Google Patents

Abstract

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

Description

The invention relates to the field of telecommunications and computer technology, and more particularly to the field of methods and devices for cryptographic data conversion, and can be used in communication, computing and information systems for cryptographic closing of binary information and calculating close random numbers when it is necessary to calculate session values keys and other information, to which requirements of low predictability and high entropy of values are imposed, when exchanging government data, etc. -enforcement, defense, banking and industrial institutions, when it becomes necessary to store and transmit sensitive information, as well as the organization of communication on the basis of noise-like signals.

A device for generating random numbers is known [Tezuka S. Pseudorandom number generator. US patent No. 5046036 from 3.09.1991, cl. G 06 F 007/38], in which to compute the values of pseudo-random sets of numbers using the combination of the sync package using a generator of the so-called M-sequences and three types of conversion of the obtained sequences:

multiplying the vector P with the values obtained from the M-sequence generator by the initially given matrix G, modulo 2 addition of two output bits of the M-sequence generator; bitwise permutations S _{i of the} result of multiplying the vector P by the matrix G.

However, the device has drawbacks in the low cryptographic stability of generator operations (due to the use of generators of M-sequences that do not have sufficient cryptographic stability [Ivanov MA, Chugunkov IV Theory, application and quality assessment of pseudo-random sequence generators. M. : Kudits-image, 2003 - 240 pp.]), As well as the need for a truly random value of the clock package, with the help of which the calculation of M-sequences is performed [Agranovsky A.V., Khadi R.A. Practical cryptography: algorithms and their programming. M .: Solon-Press, 2002 - 256 S.], which is essential for the use of this device in practice.

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

However, this device has disadvantages associated with the possibility of cryptanalysis of the output sequences due to the high predictability of the next calculated bit in the case when the 0-criteria and 1-criteria are known to the cryptanalyst, as well as the low speed of the operations performed, since a large amount of information is analyzed at each iteration about the already calculated output sequence and only one bit of information is calculated.

The closest in technical essence to the proposed is a device for generating pseudo-random sequences [DeBellis R.S., Smith R.M., Yeh P.C. Pseudorandom number generator with backup and restoration capability. US patent No. 6104810 from 08/15/2000, class. G 01 C 019/72], taken as a prototype. The principle of operation of the device is based on the fact that to calculate the values of a pseudo-random set of binary numbers, a computational transformation of the input nonrandom data is used to obtain the output pseudo-random binary sequence. In the prototype, the values of the pseudo-random sequence are calculated by applying a known cryptographic function to a value that depends on the current time and a secret parameter, then the received bits are fed to the MDC-4 hash function [Schneier B. Applied cryptography. Protocols, algorithms, source codes in the C language. SPb: Triumph, 2002 - 816 pp.], And its result is stored as a pseudo-random sequence value. The value of the secret parameter is regularly updated by calculating a hash function from the combination of the current value of the secret parameter and the current time value. The algorithm of the device also provides for the storage of reserve values of the secret parameter used in the event of a restart of the system. Thus, the likelihood of recalculating an already used sequence of pseudo-random numbers after restarting the device is reduced.

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

The technical result obtained from the implementation of this invention is the elimination of these disadvantages, that is, increasing the complexity of cryptanalysis of the resulting pseudorandom sequences, reducing the likelihood of confident prediction of the following binary numbers of the output sequence.

This technical result is achieved due to the fact that the device for generating a pseudo-random sequence of binary numbers using elliptic curves consists of block 1 - a memory block for storing the parameters of the elliptic curve used 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 - to read the parameter S _y, output 2 - for reading the parameters of the elliptic curve, the outputs 3 and 4 - to read the coordinate of primitive elements in the group of points of an elliptic curve), block 2 (a timer block, which has one output from which it reads the current timer value as a sequence of bits), operating blocks 3.1 and 3.2, which calculate the values of the MD5 hash function (blocks have one input, to which a sequence of bits is supplied, and to one output from which the value of the MD5 hash function is read from the input information in the form of a sequence of bits), an operation unit 4 that converts a sequence of bits into a pair of bit sequences, represents they are the coordinates of the point of the elliptic curve (the block has two inputs: input 1, to which the sequence of bits is fed, and input 2, to which the value of the parameters of the elliptic curve is supplied as a sequence of bits, as well as two outputs from which the coordinates of the obtained point of the elliptic curve are read in the form of sequences of bits), computing unit 5, which multiplies two points of the elliptic curve, the coordinates of which are input in the form of sequences of bits (block 5 has inputs 1, 2, 3 and 4, to which the coordinates of the multiplication operands are presented in the form of sequences of bits — one input per coordinate of each operand, as well as input 5, to which the parameters of the elliptic curve are supplied as a sequence of bits, and output 1, from which the sequence of bits is read, which is the y-coordinate of the result of multiplication ), operating blocks 6.1 and 6.2, which concatenate two blocks of bit sequences received at the input of blocks (each block has two inputs 1 and 2 for input bit sequences and one output, with torogo read result of the concatenation of the input sequences), the memory unit 7, accumulator output pseudorandom bit sequence (block has one input for taking accumulated binary information and one output for its reader), with the output of one unit 1 is connected to input unit 2 6.1; the output 2 of block 1 is connected to the input 2 of block 4 and the input 5 of block 5; the output 3 of block 1 is connected to the input 3 of block 5; the output 4 of block 1 is connected to the input 4 of block 5; the output 1 of block 2 is connected to the input 1 of block 6.1 and the input 2 of block 6.2; the output 1 of block 3.1 is connected to the input 1 of block 4; the output 1 of block 3.2 is connected to the input 1 of block 7; the output 1 of block 4 is connected to the input 1 of block 5; the output 2 of block 4 is connected to the input 2 of block 5; the output 1 of block 5 is connected to the input 1 of block 6.2; output 1 of block 6.1 is connected to input 1 of block 3.1; output 1 of block 6.2 is connected to input 1 of block 3.2.

The principle of operation of the device is based on calculations in the multiplicative group of points of an elliptic curve of the form E (X) = {(x, y) | y ² = x ³ + a * x + b} over the field GF (p, n). The device operates as follows. Initialization data is loaded into block 1 (parameters p and n, a and b, primitive element B of the point group of curve E, secret parameter S _y ). Further work is as follows. Block 6.1, the inputs of which are connected to the output of block 2 and the output 1 of block 1, concatenates the bit sequence received at the output of timer 2 and the bit sequence representing the current value of S _y . Block 3.1, the input 1 of which is connected to the output 1 of block 6.1, calculates the value of the hash function of the sequence of bits obtained during the operation of block 6.1. Block 4, the input 1 of which is connected to the output 1 of block 3.1, and the input 2 to the output 2 of block 1, converts the output of block 3.1 to the coordinates of the point of the elliptic curve E over the field GF (p, n), reading information about E, p , n from block 1. Block 5 (its inputs 1 and 2 are connected to the outputs 1 and 2 of block 4, the inputs 3, 4, 5 to the outputs 3, 4, 2 of block 1, respectively) calculates the product of the point of the elliptic curve E obtained by the previous step and the primitive element of the group of points E (information about a, b, p, n and the coordinates of point B is read from block 1 through its outputs 2, 3, 4), and It yields the y-coordinate of the resulting point. The result is recorded in the corresponding cells of block 1 (its input 1 is connected to the output). Block 6.2 concatenates the value obtained in block 5 and the output value of block 2. Block 3.2 calculates the value of the hash function from the result of the operation of block 6.2. The resulting value is transferred to drive 7.

Thus, the operation of the proposed device for generating a pseudo-random sequence of bits using elliptic curves consists of two stages. At the first stage of operation of the device, the information necessary for operation is initialized. Then the second stage begins, during which calculations are performed with an elliptic curve and the output binary sequence is formed. If the length of the output sequence is less than required, the calculation step with an elliptic curve is repeated, and the result is added to the output sequence as many times as needed to achieve the required length of the output sequence.

To describe the operation of the device, we introduce the following notation:

- parameters p and n, allowing to describe the Galois field GF (p, n);

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

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

- a primitive element In the multiplicative group of points of the curve E;

- secret parameter S _y , which is the y-coordinate of the point of the elliptic curve E;

- integer variable T;

- output binary sequence Q of variable length.

To generate a pseudo-random sequence of binary numbers, a non-random data computational transformation is used to obtain an output pseudo-random binary sequence. As a computational transformation, we use an algorithm of calculation with an elliptic curve of the form E (X) = {(x, y) | y ² = x ³ + a * x + b}, in which the user sets the value of the secret parameter S _y equal to the y-coordinate of the point In the case of the first data conversion, either the previously stored value S _y is loaded, the binary sequence Q is cleared to store the output sequence of values; the integer variable T is assigned the value of the current time in the form of the number of seconds elapsed from 1970 to the current time, the secret parameter S _{y is} assigned the y-coordinate of the point B * e (h (S _y | T)), where e (x) - the function that converts the number to a point of the elliptic curve E, the function h (x) is a MD5 hash function, S _y - the current value of the secret parameter - is stored for later use, the value h (T | S _y ) is added to the binary sequence Q, when the need to take action to calculate the new steam value meter S _y and complement the sequence Q are repeated, the output sequence is the binary sequence Q.

To implement the work, use the input data about the Galois field GF (p, n), the parameters of the elliptic curve E, which has at least 30 * 2 ¹²⁸ points over the field GF (p, n), and the primitive element В of the multiplicative group of points of the elliptic curve E.

Function h (x) according to [Schneier B. Applied cryptography. Protocols, algorithms, source codes in the C language. SPb: Triumph, 2002 - 816 pp.] Accepts a binary sequence of arbitrary length as input and calculates a hash value represented as a binary sequence of a fixed length of 128 bits.

над соответствующим полем - см., например [Коблиц И. Курс теории чисел и криптографии. М.: Научное издательство ТВП, 2001 - 254 с.]). Затем вычисляют значение

, из полученного V извлекают квадратный корень; если корень удалось извлечь, принимают за результат точку с координатами (

, sqrt(V)), иначе присваивают переменной j другое целое значение из интервала [1, 30] и повторяют вычисления до тех пор, пока число V не станет полным квадратом. Вероятность того, что применение этого алгоритма не даст результата, составляет приблизительно 2^-30.The function e (x) converts the binary sequence x of 128 bits in length to a point on the elliptic curve E. The value of e (x) is calculated by the following algorithm. The integer 1≤j≤30 is selected. Between numbers of the form 30 * x + j from the interval [0, (2 ¹²⁸ -1) * 30] and part of the set of elements of the field GF (p, n), a one-to-one correspondence is established (the method for establishing such a correspondence known from the prior art consists in interpreting the digits p -ary notation of the number X as coefficients of the polynomial

above the corresponding field - see, for example, [Koblitz I. Course in number theory and cryptography. M.: Scientific Publishing House of TVP, 2001 - 254 p.]). Then calculate the value

, from the obtained V, the square root is extracted; if the root can be extracted, take for the result a point with coordinates (

, sqrt (V)), otherwise they assign the variable j another integer value from the interval [1, 30] and repeat the calculation until the number V becomes a full square. The likelihood that applying this algorithm will not produce a result is approximately ^2-30 .

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

Claims (1)

A device for generating a pseudo-random sequence of binary numbers using elliptic curves, comprising a first memory block having cells for storing the parameters of the used elliptic curve and a cell for recording and storing the current value of the secret parameter S _y , a timer from which the current time value is read in the form of a sequence of binary bit, two hash function calculation blocks, an operation block for converting a sequence of binary bits into a pair of sequences of binary bits, pre representing the coordinates of the points of the elliptic curve, a computing unit that multiplies the coordinates of the points of the elliptic curve, two concatenation blocks that concatenate the sequences of binary bits received at their inputs, a second memory block designed to accumulate the output pseudorandom sequence of binary numbers, while the first information output the first memory block, from which the value of the current secret parameter S _y is read, is connected to the second input of the first block concatenation, with the first input of which the timer output and the second input of the second concatenation block are connected, the output of the first concatenation block is connected to the input of the first hash function calculation block, the output of which is connected to the first input of the operation block, the second input of which is from the second information output of the first block the memory receives the parameters of the elliptic curve, the first and second outputs of the operating unit, on which the coordinates of the point of the elliptic curve are formed, are connected to the first and second information inputs the data of the computing unit, the third and fourth information inputs of which are connected to the third and fourth information outputs of the first memory unit, from which the coordinates of the primitive element B of the group of points of the elliptic curve are read, the fifth information input of the computing unit is connected to the second information output of the first memory unit, the output of the computing unit on which a sequence of binary bits is formed, which is the y-coordinate of the result of the multiplication and is the current value secret parameter S _y , connected to the first input of the second concatenation block and the cell input of the first memory block, which stores the value of the current secret parameter S _y , the output of the second concatenation block is connected to the input of the second hash function calculation block, the output of which is connected to the input of the second block memory, while the MD5 hash function is used as a hash function.