RU2774099C1 - Method of controlling integrity of multidimensional data arrays based on rules for constructing triangular codes - Google Patents

Abstract

FIELD: computer engineering.

SUBSTANCE: method for controlling integrity of multidimensional data arrays based on rules for constructing triangular codes comprises arranging in a triangle

data units M_i,j, to which a hash function is applied according to the rules for constructing triangular codes, from the obtained reference hash codes H_i,k, H_k,j, a hash code H_k,k is calculated, the value of which is compared with the value of the hash code

, which is calculated when requesting the use of data to be protected.

EFFECT: possibility of controlling integrity of reference hash codes in conditions of limitations on allowable resource costs.

1 cl, 1 tbl, 7 dwg

Description

The field of technology to which the invention belongs

The present invention relates to information technology and can be used to control the integrity of data in multidimensional storage systems based on the application of cryptographic hash functions to protected data blocks under restrictions on the allowable resource costs.

State of the art

a) Description of analogues

Known methods of data integrity control through the use of cryptographic methods: key and keyless hashing, electronic signature means (Patent for invention RUS No. 26207030 07.12.2015; Patent for invention RUS No. 2669144 28.11.2017; Patent for invention RUS No. 2680033 22.05.2017; Invention patent RUS No. 2680350 May 2, 2017; Invention patent RUS No. 2680739 November 28, 2017; Invention patent RUS No. 2686024 April 25, 2018; Invention patent RUS No. 2696425 May 22, 2018; Knuth, D.E. The Art of Computer Programming Volume 3. Sorting and search / D.E. Knut - M.: "Mir", 1978. - 824 pp. Dichenko, S. Two-dimensional control and assurance of data integrity in information systems based on residue number system codes and cryptographic hash functions / S. Dichenko, O. Finko // Integrating Research Agendas and Devising Joint Challenges International Multidisciplinary Symposium ICT Research in Russian Federation and Europe, 2018, pp. 139-146; method control and restoration of data integrity for secure information-analytical systems / S. Dichenko, O. Finko // Issues of cybersecurity. - 2019. - No. 6 (34). - P. 17-36), which are characterized by three generalized schemes for applying the hash function:

- with the calculation of one common hash code from k data blocks (Fig. 1);

- with the calculation of one hash code from each of the data blocks (Fig. 2);

- with the construction of a fully connected hashing network (Fig. 3).

The disadvantages of these methods are:

- for the hash function application scheme with the calculation of one common hash code from k data blocks:

- does not allow, after data integrity control, to localize a data block with integrity violation;

- low probability of determining the fact of data integrity violation (error detection) when an error is missed (false error signal) by means of control;

- the lack of the ability to control the integrity of the reference hash codes;

- for the hash function application scheme with the calculation of one hash code from each of the data blocks:

- high redundancy of control information when checking the integrity of data blocks represented by binary vectors of small dimension;

- low probability of determining the fact of data integrity violation (error detection) when an error is missed (false error signal) by means of control;

- the lack of the ability to control the integrity of the reference hash codes;

- for the hash function application scheme with the construction of a fully connected hashing network:

- high redundancy of control information when checking the integrity of data blocks represented by binary vectors of small dimension;

- in general, this model does not allow, after monitoring the integrity of the data, to localize the data block with integrity violation;

- the lack of the ability to control the integrity of the reference hash codes.

b) Description of the closest analogue (prototype)

The closest in technical essence to the claimed invention (prototype) is a data integrity control method based on a hash code system, the construction rules of which are similar to the rules for constructing linear redundant codes (Fig. 4), obtained by applying a hash function to data in order, determined by a special procedure for selecting a data block based on the mathematical apparatus of linear algebra (Dichenko S.A. Monitoring and ensuring the integrity of information in data storage systems // Science-intensive technologies in space research of the Earth. 2019. V. 11. No. 1. P. 49-57 ), where data integrity control (error detection), by analogy with linear codes, is carried out by calculating the syndrome, when checking which, one can conclude that the data integrity has been violated (the presence of an error).

The disadvantage of the known method is the inability to control the integrity of the reference hash codes in terms of restrictions on the allowable resource costs.

Disclosure of invention

a) The technical result to which the invention is directed

The purpose of the present invention is to develop a data integrity control method based on the application of cryptographic hash functions to protected data blocks with the ability to control the integrity of reference hash codes under restrictions on the allowable resource costs.

b) A set of essential features

, к каждой строке и столбцу которого добавляются эталонные хэш-коды H_i,k, H_k,j (i=j=0,1,…,k-1), которые вычисляются от совокупности

блоков данных M_i,j, расположенных в соответствующих строках и столбцах треугольника, при этом для контроля целостности эталонных хэш-кодов H_i,k, H_k,j вычисляется хэш-код H_k,k, значение которого сравнивается со значением хэш-кода

, вычисляемого при запросе на использование данных, подлежащих защите.This goal is achieved by the fact that in the known method of data integrity control, which consists in the fact that the detection and localization of the data block M _i (i=1,2,…,k) with signs of integrity violation is carried out by calculating a system of hash codes formed from hash codes calculated from a set of k data blocks M ₁ , M ₂ , ..., M _k , and comparing its values with the values of the reference system of hash codes, in the presented method, data blocks M _i,j (i=j=0, 1,…,k-1) are located in a triangle of size

, to each row and column of which reference hash codes H _i,k , H _k,j (i=j=0,1,…,k-1) are added, which are calculated from the set

data blocks M _i,j located in the corresponding rows and columns of the triangle, while to control the integrity of the reference hash codes H _i,k , H _k,j the hash code H _k,k is calculated, the value of which is compared with the value of the hash code

, calculated when requesting the use of data to be protected.

блоков данных M_i,j, к которым хэш-функция применяется по правилам построения треугольных кодов (Hamming, R. Coding and Information Theory. Prentice-Hall, 1980. - 259 p.), от полученных при этом эталонных хэш-кодов H_i,k, H_k,j вычисляется хэш-код H_k,k, что позволяет контролировать целостность эталонных хэш-кодов в условиях ограничений на допустимые затраты ресурса.A comparative analysis of the claimed solution and the prototype shows that the proposed method differs from the known one in that the goal is achieved due to the arrangement in a triangle

data blocks M _i,j , to which the hash function is applied according to the rules for constructing triangular codes (Hamming, R. Coding and Information Theory. Prentice-Hall, 1980. - 259 p.), from the resulting reference hash codes H _{i ,k} , H _k,j , the hash code H _k,k is calculated, which makes it possible to control the integrity of the reference hash codes under restrictions on the allowable resource costs.

, вычисляемого при запросе на использование данных, подлежащих защите. Новым является то, что блоки данных M_i,j располагаются в треугольнике размером

, к каждой строке и столбцу которого добавляются эталонные хэш-коды H_i,k, H_k,j по правилам построения треугольных кодов. Новым является то, что применение хэш-функции по правилам построения треугольных кодов позволяет контролировать целостность эталонных хэш-кодов H_i,k, H_k,j путем вычисления хэш-кода H_k,k и сравнения его значения со значением хэш-кода

, вычисляемого при запросе на использование данных, подлежащих защите.The integrity of the reference hash codes H _i,k , H _k,j will be carried out by calculating the hash code H _k,k from them, which will allow at time t, under conditions of restrictions on the allowable resource costs, to compare its value with the value of the hash code

, calculated when requesting the use of data to be protected. What is new is that the data blocks M _i,j are located in a triangle of size

, to each row and column of which reference hash codes H _i,k , H _k,j are added according to the rules for constructing triangular codes. What is new is that the use of a hash function according to the rules for constructing triangular codes allows you to control the integrity of the reference hash codes H _i,k , H _k,j by calculating the hash code H _k,k and comparing its value with the value of the hash code

, calculated when requesting the use of data to be protected.

c) Causal relationship between features and technical result

Thanks to a new set of essential features, the method implements the possibility of:

блоков данных, подлежащих защите, с низкой избыточностью контрольной информации;- integrity control

blocks of data to be protected with low redundancy of control information;

- localization of data blocks with violation of integrity;

- increasing the probability of determining the fact of data integrity violation (error detection) when an error is missed (false error signal) by means of control;

- control of the integrity of the reference hash codes under conditions of restrictions on the allowable resource costs.

Evidence of compliance of the claimed invention with the conditions of patentability "novelty" and "inventive step"

The analysis of the prior art made it possible to establish that there are no analogues characterized by a set of features identical to all the features of the claimed technical solution, which indicates the compliance of the claimed method with the condition of patentability "novelty".

The results of the search for known solutions in this and related fields of technology in order to identify features that match the distinguishing features of the prototype of the claimed object showed that they do not follow explicitly from the prior art. The prior art also did not reveal the fame of distinctive essential features that cause the same technical result that is achieved in the claimed method. Therefore, the claimed invention meets the condition of patentability "inventive step".

Brief description of the drawings

The claimed method is illustrated by drawings, which show:

fig. 1 - a scheme for applying a hash function with the calculation of one common hash code from k data blocks;

fig. 2 is a diagram of the application of the hash function with the calculation of one hash code from each of the data blocks;

fig. 3 is a diagram of the application of the hash function with the construction of a fully connected hash network;

fig. 4 - a system of hash codes based on the rules for constructing linear redundant codes;

fig. 5 is a data hashing scheme based on the rules for constructing triangular codes;

fig. 6 - hashing network for a triangular hash code system, where k=3;

fig. 7 is a scheme for checking the integrity of reference hash codes.

Implementation of the invention

.Data blocks M _i,j (i=j=0,1,…k-1) are located in the exchange triangle

.

блоков данных, подлежащих защите, к каждой строке и столбцу треугольника добавляются хэш-коды H_i,k, H_k,j (i=j=0,1,…,k-1), вычисленные от совокупности блоков данных Mjj, расположенных в соответствующих строках и столбцах треугольника, как представлено на фиг. 5.For integrity control

blocks of data to be protected, hash codes H _i,k , H _k,j (i=j=0,1,…,k-1) are added to each row and column of the triangle, calculated from the set of data blocks Mjj located in corresponding rows and columns of the triangle, as shown in FIG. 5.

In accordance with the hashing scheme (Fig. 5), we get an array:

блоков данных, преобразованный в массив размером

, будет называться треугольной системой хэш-кодов. Для контроля целостности

блоков данных в треугольной системе хэш-кодов требуется вычислить k+1 хэш-кодов.The original triangle containing

blocks of data, converted to an array of size

, will be called the triangular hash code system. For integrity control

blocks of data in a triangular hash code system, it is required to calculate k+1 hash codes.

Data integrity control, as well as the localization of a data block with integrity violation, is carried out by means of a hashing network.

On the basis of the hashing network for each block of data to be protected, we will obtain groups of reference hash codes that are unique in composition and used when detecting and locating a block of data with integrity violation.

Detection of a block of data with a violation of integrity is performed by comparing the values of the reference hash codes previously calculated from it and the hash codes calculated when requesting its use. The discrepancy between the compared hash codes allows us to conclude that an error has occurred and determine its syndrome. Under the error syndrome, we mean the binary number obtained by writing the symbol "0" for each performed check for the compliance of the values of the calculated and reference hash code and the symbol "1" if the compared values do not match. To do this, based on the hashing network, a table of error syndromes is compiled, in which

- the presence of one "1" in the corresponding line will indicate a violation of the integrity of the reference hash code;

- the presence of two "1" in the corresponding line of the table will indicate a violation of the integrity of one data block M _i,j to be protected;

- the presence of three or more "1" in the corresponding line will indicate a violation of the integrity of two or more data blocks M _i,j to be protected, as well as another (the occurrence of an undetectable error).

Example 1 A hashing network for a triangular hash code system with triangle size k=3 is shown in FIG. 6.

Based on the hash network (FIG. 6), table 1 is compiled, where "[⋅]" denotes a localized block of data M _i,j , or a reference hash code (H _i,k or H _k,j ) with integrity violation.

To control the integrity of the reference hash codes, it is necessary to calculate the hash code:

обозначает операцию конкатенации (объединения).and place it in the resulting system of hash codes (Fig. 7); symbol

denotes the operation of concatenation (union).

In this case, the array (1) will take the form:

, вычисляемого при запросе на использование данных, подлежащих защите.To control the integrity of the reference hash codes, the hash code value H _k,k is compared with the hash code value

, calculated when requesting the use of data to be protected.

Based on the results of the comparison, we conclude:

;- about the absence of violation of the integrity of the reference hash codes, when

;

.- about the violation of the integrity of the reference hash codes, when

.

Claims (1)

A method for controlling the integrity of multidimensional data arrays based on the rules for constructing triangular codes, which consists in the fact that the detection and localization of a data block M _i (i=1,2,…,k) with signs of integrity violation is carried out by calculating a system of hash codes formed from hash codes calculated from a set of k data blocks M ₁ , M ₂ , ..., M _k , and comparing its values with the values of the reference system of hash codes, characterized in that the data blocks M _i,j (i=j=0, 1,…,k-1) are located in a triangle of size

, to each row and column of which reference hash codes H _i,k , H _k,j (i=j=0,1,…,k-1) are added, which are calculated from the set

data blocks M _ij; located in the corresponding rows and columns of the triangle, while to control the integrity of the reference hash codes H _i,k , H _k,j , the hash code H _k,k is calculated, the value of which is compared with the value of the hash code

, calculated when requesting the use of data to be protected.

Images