RU2806539C1 - Method for forming crypto-code constructions in conditions of reducing dimensionality of control space and restoring integrity of structured data arrays - Google Patents

Abstract

FIELD: information technology.

SUBSTANCE: invention can be used to ensure the integrity of information when constructing crypto-code structures in data storage systems under the conditions of a forced reduction in the dimension of the control space and restoring the integrity of structured data arrays. The technical result is achieved by performing structural-parametric synthesis, as a result of which the structure of the structure is determined and the values of the parameters of its constituent elements are found, which consists in reducing the dimension of the control space to a minimum number of hash codes and restoring the integrity of structured data arrays without moving to a data space with a smaller dimensionality, which will ensure the integrity of the data to be protected.

EFFECT: ensuring data integrity.

1 cl, 3 dwg

Description

Field of technology to which the invention relates

The proposed invention relates to information technology and can be used to ensure the integrity of information when constructing crypto-code structures in data storage systems under conditions of forced reduction in the dimension of the control space and restoration of the integrity of structured data arrays.

State of the art

a) Description of analogues

There are known methods for constructing cryptographic structures for monitoring the integrity of structured data arrays through the use of cryptographic hash functions (Invention Patent RUS No. 2730365, 08.21.2020; Invention Patent RUS No. 2758194, 10.26.2021; Invention Patent RUS No. 2759240, 11.11.2021 ; Patent for invention RUS No. 2771146, 04/27/2022; Patent for invention RUS No. 2771209, 04/28/2022; Patent for invention RUS No. 2771236, 04/28/2022; Patent for invention RUS No. 2771273, 04/29/2022; Patent for invention RUS No. 2774099, 06/15/2022; Shannon, K. Works on information theory and cybernetics / K. Shannon. - M.: Foreign Literature Publishing House, 1963. -829 pp.; Schneier, B. Secrets and lies. Data security in digital world / B. Schneier. - St. Petersburg: Peter, 2003. - 367 pp.).

The disadvantages of these methods are:

- inability to restore data integrity;

- lack of ability to control data integrity with a forced reduction in the dimension of space for monitoring the integrity of structured data arrays.

There are known methods for constructing code structures for restoring the integrity of structured data arrays through the use of error-correcting codes (Invention Patent RUS No. 2680033, 02/14/2019; Invention Patent RUS No. 2680350, 02/19/2019; Invention Patent RUS No. 2758943, 11/03/2021 ; Patent for invention RUS No. 2771238, 04/28/2022; Morelos-Zaragoza, R. The art of noise-resistant coding. Methods, algorithms, application / R. Morelos-Zaragoza; translation from English by V.B. Afanasyev. - M.: Technosphere, 2006. - 320 pp.; Hemming, R.V. Coding theory and information theory / R.V. Hemming; translation from English - M.: “Radio and Communications”, 1983. - 176 pp.). The disadvantages of these methods are:

- data integrity control is performed with a probability determined for the error-correcting code used;

- inability to restore the integrity of data when the dimensionality of the space is forced to be reduced to restore the integrity of structured data arrays.

There are known methods based on the construction of crypto-code structures for monitoring and restoring the integrity of structured data arrays through the use of cryptographic methods and methods of reliability theory (Patent for invention RUS No. 2680739, 02.26.2019; Patent for invention RUS No. 2696425, 02.08.2019; Patent for invention RUS No. 2707940, 02.12.2019).

The disadvantages of these methods are:

- monitoring and restoration of data integrity is performed for the initially defined data structure to be stored;

- lack of ability to control and restore data integrity with a forced reduction in the dimension of the control space and restore the integrity of structured data arrays.

b) Description of the closest analogue (prototype)

The closest in technical essence to the claimed invention (prototype) is a method for monitoring and restoring the integrity of multidimensional data arrays, in which a crypto-code structure is built to monitor and restore the integrity of data presented in the form of multidimensional structured data arrays of dimension k (Fig. 1), from the elements of which reference hash codes are first calculated through the use of a hash function, the values of which are subsequently compared, when monitoring data integrity, with the values of hash codes calculated from the data blocks being checked when requesting their use. From the received hash codes, as well as from elements of multidimensional structured data arrays, redundant blocks are calculated using the mathematical apparatus of error-correcting codes to ensure the possibility of restoring data integrity (Alimanov P.E., Dichenko S.A., Samoilenko D.V., Finko O.A. [et al.]. A method for monitoring and restoring the integrity of multidimensional data arrays // Patent for invention RUS No. 2771208, 04/28/2022).

The disadvantage of this known method is the inability to ensure data integrity when forced to reduce the dimension of the control space and restore the integrity of structured data arrays.

Disclosure of the Invention

a) The technical result to be achieved by the invention

The purpose of the present invention is to develop a method for constructing crypto-code structures for monitoring and restoring the integrity of structured data arrays, allowing to ensure data integrity while forcing a reduction in the dimension of the control space and restoring the integrity of structured data arrays.

b) Set of essential features

This goal is achieved by the fact that in the known method of monitoring and restoring the integrity of multidimensional data arrays, which consists in the fact that crypto-code structures for monitoring and restoring data integrity are built on the basis of data arrays of dimension k, consisting of data blocks, to which, in order to be able to detect signs integrity violation, the hash function h is used, while the calculated hash codes are placed in free blocks of the array and are reference values, the values of which, when requesting the use of data, are compared with the values of hash codes calculated from the data blocks being checked, when restoring the integrity of the data blocks, to be protected, as well as the reference hash codes calculated from them, are interpreted as elements of GF(2 ^t ) and are the smallest polynomial residues, while the resulting data array is considered as a single superblock of modular polynomial code, over which an expansion operation is performed by introducing nk redundant bases, for which the corresponding excess residues are calculated, additionally introduced for error correction, in the event of which the restoration of data blocks without compromising the unambiguity of their representation is carried out by reconfiguring the system by excluding from the calculations a data block with signs of integrity violations, in the presented method for constructing a crypto- code structures for monitoring and restoring the integrity of structured data arrays, a structural-parametric synthesis is performed, as a result of which the structure of the structure is determined and the values of the parameters of its constituent elements are found, the number of control blocks will be determined by the required detecting and correcting abilities of the error-correcting code used, and the order of synthesis is in reducing the dimensionality of the control space to a minimum number of hash codes and restoring the integrity of structured data arrays without moving to a data space with a lower dimensionality, which allows for control and restoration of data integrity through the use of (θ-1)-dimensional cryptographic and code transformations performed in θ-dimensional data space, with the calculation of the minimum number of hash codes for this.

A comparative analysis of the claimed solution and the prototype shows that the proposed method differs from the known one in that the set goal is achieved by performing structural-parametric synthesis, as a result of which the structure of the structure is determined and the values of the parameters of its constituent elements are found, which consists in reducing the dimension of the control space to the minimum number of hash codes and restoring the integrity of structured data arrays without moving to a data space with a lower dimension, which will ensure the integrity of the data to be protected.

In conditions of significant degradation of data storage systems, leading to the need to calculate the minimum number of hash codes, the structural-parametric synthesis of crypto-code structures is defined and can be described by means of the ϕ-function, which will make it possible at time t to ensure the integrity of the data to be protected. What is new is that to build crypto-code control structures and restore the integrity of structured data arrays, a structural-parametric synthesis is performed, which consists in reducing the dimension of the control space to a minimum number of hash codes and restoring the integrity of structured data arrays without moving to a data space with a lower dimensionality . What is new is that control and restoration of data integrity is ensured through the use of θ-1-dimensional cryptographic and coding transformations performed in the θ-dimensional data space, with the calculation of a minimum number of hash codes for this.

c) Cause-and-effect relationship between the characteristics and the technical result Thanks to the new set of essential characteristics, the method implements the ability to:

- building crypto-code control structures and restoring the integrity of structured data arrays by performing structural-parametric synthesis, which consists in reducing the dimensionality of the control space to a minimum number of hash codes and restoring the integrity of structured data arrays without moving to a data space with a lower dimensionality;

- ensuring the integrity of the data to be protected by monitoring and restoring data integrity through the use of - 1-dimensional cryptographic and coding transformations performed in the θ-dimensional data space, with the calculation of the minimum number of hash codes for this.

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

The analysis of the level of technology 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 that the claimed method complies with the patentability condition of “novelty”.

The results of a search for known solutions in this and related fields of technology in order to identify features that coincide with the features of the claimed object that are distinctive from the prototype, showed that they do not follow explicitly from the prior art. The prior art also does not reveal the knowledge of distinctive essential features that determine the same technical result that was achieved in the claimed method. Therefore, the claimed invention meets the patentability requirement of “inventive step”.

Brief description of drawings

The claimed method is illustrated by drawings, which show:

fig. 1 is a diagram illustrating the general view of a crypto-code design for monitoring and restoring the integrity of multidimensional data arrays;

fig. 2 is a diagram illustrating the performance of 2-dimensional cryptographic and code transformations;

fig. 3 is a diagram illustrating the performance of 1-dimensional cryptographic and code transformations on elements of a structured data array presented in a 2-dimensional data space.

Carrying out the invention

Structural-parametric synthesis is understood as a process as a result of which the structure of an object is determined and the values of the parameters of its constituent elements are found, so that the conditions of the synthesis task are satisfied (Volkov, V.A. System analysis for system-parametric synthesis / V.A. .Volkov, S.M. Chudinov // Scientific bulletins of Belgorod State University. Series: Economics. Informatics. - 2012. - No. 19 (138). - P. 153-157).

To obtain, as a result of the synthesis, crypto-code structures that make it possible to ensure the integrity of data in the event of a forced change in the required detecting and correcting abilities caused by the destructive influences of an attacker and disturbances in the operating environment, aggregation of the corresponding cryptographic and code transformations is performed both in the space of structures and parameters of the object under consideration .

Under conditions of destructive influences from an attacker and disturbances in the operating environment when storing information, it is possible that it may be distorted and (or) destroyed, that is, its integrity may be violated. Violation of the integrity of structured data arrays, in turn, will be characterized by the appearance of errors in data blocks, that is, a discrepancy between the data sent for storage and the data when requesting their use. A violation of the integrity of a single data block contained in a structured data array is understood as the occurrence of a 1-fold error; accordingly, the occurrence of a g-fold error will be characterized by a violation of the integrity of q data blocks.

Cryptographic transformations performed when constructing crypto-code structures are based on the use of a cryptographic hash function (Knuth, D.E. The Art of Computer Programming. Volume 3 sorting and searching / D.E. Knut. - M.: Mir, 1978. - 824 pp.). The application of a hash function to structured data arrays makes it possible to detect with cryptographic reliability a data block or a set of data blocks with signs of integrity violations.

A hash function h is a function that maps data M ∈{0,1}* into hash codes

Where - arbitrary data block size, - fixed block size with hash code , and satisfying the following properties:

- based on the calculated hash value difficult to calculate source data mapped to this value;

- for given initial data difficult to calculate other input data , mapped to the same hash value, that is

h(M ₁ )=h(M ₂ ), where

- it is difficult to calculate any pair of initial data (M ₁ ,M ₂ ), where t = 1.2 mapped to the same hash value, that is

Under the hash code refers to the string of bits that is the output result of the hash function h.

Strings of bits that the hash function h maps to a hash code will be called a data block

In turn, restoring the integrity of structured data arrays is ensured through the use of the mathematical apparatus of error-correcting codes.

Error-correcting code (correcting code, error-correcting code) is a code designed to detect and correct errors. The main technique is adding specially structured redundant information to useful data when writing (transmitting), and using such redundant information when reading (receiving) to detect and correct errors. The number of errors that can be corrected is limited and depends on the specific code used (Bleikhut, R. Theory and practice of error-control codes / R. Bleikhut; translation from English by I.I. Grushko, V.M. Blinovsky; ed. K.Sh. Zigangirova. - M.: Mir, 1986. - 576 p.).

The procedure for structural-parametric synthesis of crypto-code control structures and restoration of the integrity of structured data arrays, based on the aggregation of cryptographic and code transformations, will be explained using systematic codes (codes in which the bits can be divided into information and control, and the control bits occupy the same and the same positions in code combinations). They are denoted by (n, k;)-codes, where n is the length of the code combination, k is the information part. In this case, the mathematical apparatus of error-correcting codes will be described using the coding function, which is denoted f.

The encoding function f is understood as a function that maps information blocks of data (target information) contained in a structured data array into control (redundant) blocks:

where M _k - information blocks of data contained in a 1-dimensional structured data array (special case); M _r - control (redundant) blocks; k=0.1,…, k = 1; ρ=k, …, n-1.

The number of control (redundant) blocks will be determined by the required detection and correction capabilities of the error-correcting code used.

The use of error-correcting codes provides the possibility of flexible introduction of redundancy for restoration (control and recovery - in cases where the use of a hash function does not allow detection and (or) localization of data blocks with signs of integrity violation) of the integrity of structured data arrays in destructive conditions influences of an attacker and disturbances in the operating environment.

At the same time, to ensure the possibility of applying cryptographic and code transformations to elements of structured data arrays to control and restore their integrity, the interpretation of the data blocks contained in them will be different. To ensure the ability to perform transformations with elements of an arbitrary structured data array that are identical to the transformations used in constructing error-correcting codes, it is necessary to interpret data blocks M as:

- non-negative integers, represented, for example, in the binary number system:

Where

- elements of the extended field GF (2 ^t ):

where ϖ is a dummy variable;

With this interpretation, it is possible to perform transformations with elements of a structured data array that are identical to those that are used, in particular, when performing the expansion operation to construct codes for a system of residual classes: modular codes, modular polynomial codes, etc.

Interpreting data blocks as vectors:

Where g=1,2, …, τ, makes it possible to perform transformations with them that are identical to those used in various cryptographic algorithms, for example, when generating and verifying an electronic signature, applying a hashing function, etc.

In case of significant degradation of data storage systems under conditions of destructive influences of an attacker and disturbances of the operating environment, to ensure data integrity through crypto-code structures, it is proposed to reduce the dimensionality of the control space to a minimum number of hash codes and restore the integrity of structured data arrays without moving to a data space with a lower dimensionality . In this case, control and restoration of the integrity of structured data arrays will be performed through the use of cryptographic and code transformations in a space with a lower dimensionality in relation to the dimensionality of the data space.

For a structured data array M[k,k], presented in a 2-dimensional data space, the structural-parametric synthesis of crypto-code structures can be performed in the following order:

- cryptographic transformations will be performed along one axis with the calculation of one hash code from the elements of the array M[k,k], interpreted as vectors:

- on the other axis - code transformations over array elements M[k,k], interpreted as non-negative integers:

As a result, the dimensionality of the cryptographic and code transformations illustrated in FIG. 2, with the same dimension of the data space in which the original structured data array M[k,k] is represented, and 1-dimensional cryptographic (with the calculation of the minimum number of hash codes) and code transformations in the 2-dimensional data space will be performed (Fig. 3).

Let us obtain a crypto-code design for monitoring and restoring the integrity of a 2-dimensional structured data array, represented by the array:

The rules for constructing a crypto-code structure, represented by the resulting array, are determined and can be described using a ϕ-function of the following form:

where the symbol "1D" denotes that 1-dimensional cryptographic and encoding transformations are performed on elements of a structured data array represented in a 2-dimensional data space ("2D");

The result of cryptographic control of the integrity of structured data arrays will be the detection not of a separate single block of data (1-fold error), but of a separate line containing blocks of data with signs of integrity violation. Further localization and restoration of the integrity of data blocks will be performed along the columns of the structured data array M[k,k] through the use of the mathematical apparatus of the error-correcting code used, due to its detecting and correcting abilities.

Thus, the presented synthesis procedure allows us to build crypto-code structures for monitoring and restoring the integrity of structured data arrays, which make it possible to ensure data integrity while forcing the dimensionality of the control space to be reduced to a minimum number of hash codes and restore the integrity of structured data arrays. When data storage systems are degraded, the dimension of the parameter vector (the number of calculated hash codes and control (redundant) blocks) is unknown in advance and will be determined after determining the structure of the resulting crypto-code structure.

Claims (1)

A method for forming crypto-code structures in the conditions of reducing the dimension of the control space and restoring the integrity of structured data arrays, which consists in the fact that crypto-code structures for monitoring and restoring data integrity are built on the basis of data arrays of dimension k, consisting of data blocks, to which, in order to be able to to detect signs of integrity violation, the hash function h is used, while the calculated hash codes are placed in free blocks of the array and are reference values, the values of which, when requesting to use data, are compared with the values of hash codes calculated from the data blocks being checked, when restoring the integrity of the blocks data to be protected, as well as the reference hash codes calculated from them are interpreted as elements of GF(2 ^t ) and are the smallest polynomial residues, while the resulting data array is considered as a single superblock of modular polynomial code, over which an expansion operation is performed by introducing nk redundant bases for which the corresponding excess deductions are calculated, additionally introduced for error correction, in the event of which the restoration of data blocks without compromising the unambiguity of their representation is carried out by reconfiguring the system by excluding from the calculations a data block with signs of integrity violations, characterized in that for construction crypto-code structures for monitoring and restoring the integrity of structured data arrays, a structural-parametric synthesis is performed, as a result of which the structure of the structure is determined and the values of the parameters of its constituent elements are found, the number of control blocks will be determined by the required detecting and correcting abilities of the error-correcting code used, while the order synthesis consists in reducing the dimensionality of the control space to a minimum number of hash codes and restoring the integrity of structured data arrays without moving to a data space with a lower dimensionality, which allows for control and restoration of data integrity through the use of (θ-1)-dimensional cryptographic and code transformations, executed in θ-dimensional data space, with the calculation of a minimum number of hash codes for this.