RU2808760C1 - Method for control and restoration of data integrity based on number theoretic transformations in the complex plane - Google Patents

Abstract

FIELD: storage systems.

SUBSTANCE: invention relates to methods for monitoring and restoring data integrity in storage systems. Technical result is achieved by converting data to be protected from changes under the destructive influences of an attacker and disturbances in the operating environment into many elements of the form A = a + bi, which will be complex numbers A, and modulo complex m = p+ qi, whose norm is N = p ² + q ² , and p and q are relatively prime numbers, each complex integer A is comparable to one and only one residue from the series 0.1,… , N-1, with each complex least residue x + yi modulo m = p + qi corresponds to the real residue h modulo N = p ² +q ² , which can be calculated according to the following expression: x + y(uq – vp) ≡ h(mod N), where u and v such that up + vq = 1, moreover, in order to monitor the integrity of data, as well as its restoration, it is necessary to store only those complex deductions whose range of real and imaginary parts is the largest A = a + bi.

EFFECT: reducing the amount of memory required to monitor and restore data integrity.

1 cl, 2 tbl, 6 dwg

Description

Field of technology to which the invention relates

The proposed invention relates to information technology and can be used to monitor the integrity of data in storage systems under conditions of destructive influences of an attacker and disturbances in the operating environment.

State of the art

a) Description of analogues

There are known methods for monitoring data integrity through the use of cryptographic methods: key hashing, electronic signature means (Patent for invention RUS No. 2680033, 02/14/2019; Patent for invention RUS No. 2680350, 02/19/2019; Patent for invention RUS No. 2680739, 02/26/2019 ; Patent for invention RUS No. 2696425, 08/02/2019; Patent for invention RUS No. 2707940, 02.12.2019; Patent for invention RUS No. 2726930, 07.16.2020; Patent for invention RUS No. 2730365, 08.21.2020; Patent for invention RUS No. 2758194, 10.26.2021; Patent for invention RUS No. 2758943, 03.11.2021; Patent for invention RUS No. 2759240, 11.11.2021; Patent for invention RUS No. 2771146, 04.27.2022; Patent for invention RUS No. 2771208, 04/28/2022; Patent for invention RUS No. 2771209, 04/28/2022; Patent for invention RUS No. 2771236, 04/28/2022; Patent for invention RUS No. 2771238, 04/28/2022; Patent for invention RUS No. 2771273, 04/29/2022; Patent for invention RUS No. 27 74099 , 06/15/2022; Patent for invention RUS No. 2785484, 12/08/2022; Patent for invention RUS No. 2785800, 12/13/2022; Patent for invention RUS No. 2786617, 12/22/2022; Patent for invention RUS No. 2793782, 04/06/2023; Shannon, K. Works on information theory and cybernetics / K. Shannon. - M.: Foreign Literature Publishing House, 1963. -829 p.; Schneier, B. Secrets and lies. Data security in the digital world / B. Schneier. - St. Petersburg: Peter, 2003. - 367 p.), for which two generalized schemes for calculating hash function values are typical: for each subblock in a data block and for the whole data block.

The disadvantages of these methods are:

- high redundancy when monitoring the integrity of the sequence of subblocks of a small data block (when calculating a separate hash function value for each subblock of a data block);

- inability to detect and localize corrupted subblocks of a data block (when hashing an entire data block and obtaining one common hash function value);

- the need to store all control information (hash function values), calculated to ensure the possibility of guaranteed (without taking into account collisions) data integrity control.

There are known ways to control data integrity through the use of non-cryptographic methods: error-correcting codes (Morelos-Zaragoza, R. The art of error-correcting 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 Communication", 1983. - 176 pp.) .

The disadvantages of these methods are:

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

- the need to store all control information (redundant blocks), calculated to ensure the possibility of guaranteed control of data integrity.

b) Description of the closest analogue (prototype)

The closest in technical essence to the claimed invention (prototype) is a method for monitoring the integrity of multidimensional data arrays based on the rules for constructing the Reed-Solomon code (Invention Patent RUS No. 2785862, 12/14/2022), which provides the ability to detect and localize two or more subblocks block of data with signs of integrity violation without calculation and introduction of high redundancy of control information for this purpose (Fig. 1).

The disadvantage of this known method is the need to store all control information calculated to ensure the possibility of detecting and localizing two or more subblocks of a data block with signs of integrity violation.

Disclosure of the Invention

a) The technical result to which the invention is aimed. The purpose of the present invention is to develop a method for monitoring and restoring data integrity, in which the storage of all calculated control information is not required to enable detection and localization of data blocks with signs of integrity violations.

b) Set of essential features

This goal is achieved by the fact that in the known method of data integrity monitoring, which consists in the fact that in order to ensure the possibility of detecting and localizing data with signs of integrity violation, the initial array is divided into data blocks of a fixed length, with which transformations are subsequently performed, in the presented method with data blocks M _j , where j=1, 2, ..., n, subject to protection from changes, perform transformations, as a result of which many elements of the form are obtained where a and b are real numbers, the symbol g is an imaginary unit, which makes it possible to introduce the operations of comparison, addition and multiplication on the set of these elements, and the elements of the specified type with the introduced operations will be complex numbers A, and modulo complex whose norm is and p and q are coprime numbers, each integer complex number A will be comparable to one and only one residue from the series 0, 1 ..., N-1, with each complex least residue modulo associate the real residue h modulo which is calculated according to the following expression Where And such that to carry out data integrity monitoring, providing the ability to detect and localize data blocks with signs of integrity violations, using the fundamental Gauss theorem, an isomorphism is established between sets of real and complex numbers, while the array M, which includes the data sent for storage, and the array G received when requested to use it, they are presented in the form of matrices And with many elements like at the same time, the norm is determined, which must be greater than the maximum element in the original array M, redundant blocks are formed, represented by matrices S and D, while block S is the sum of the elements of the matrix rows block D composes the sums of the matrix diagonal elements detection and localization of data blocks with signs of integrity violations is performed by subtracting matrix elements from the elements of redundant blocks represented by matrices S and D based on the calculation results, a decision is made about the absence of signs of data integrity violation, or the opposite, in this case, data blocks with signs of integrity violation will be located at the intersection of identified lines and diagonals; to restore the integrity of localized data blocks with signs of its violation, the result is added to the identified erroneous elements the difference between the rows of the redundant block represented by the matrix S and the matrix Moreover, to ensure this possibility, it is necessary to store only those complex residues whose range of real and imaginary parts is the largest.

A comparative analysis of the claimed solution with the prototype shows that the proposed method differs from the known one in that the set goal is achieved by converting data to be protected from changes under the conditions of destructive influences of an attacker and disturbances of the operating environment into many elements of the form which are complex numbers A, and modulo complex , whose norm is and p and q are coprime numbers, each complex integer A is comparable to one and only one residue from the series 0, 1, ..., N - 1, and each complex least residue modulo corresponds to the real residue h modulo which can be calculated according to the following expression Where And such that Moreover, in order to monitor data integrity, as well as its restoration, the storage of all calculated control information is not required.

The integrity of data blocks is checked by subtracting matrix elements from the elements of redundant blocks represented by matrices S and D Moreover, in the event of an integrity violation, data blocks with signs of its violation will be located at the intersection of the row and diagonal in which the error is present. To restore the integrity of a detected and localized data block with signs of its violation, it is necessary to add to the erroneous element the result of the difference between the rows of the redundant block represented by the matrix S, and matrices which will allow at time t, under conditions of destructive influences of an attacker and disturbances in the operating environment, to ensure data protection from changes. What is new is that in the proposed method, data blocks M _j , where j = 1, 2, ..., n, to be protected from changes, are converted into a set of elements of the form where a and b will be real numbers, the symbol g will be an imaginary unit, which allows you to introduce the operations of comparison, addition and multiplication on the set of these elements, and the elements of the specified type with the introduced operations will be complex numbers A, and modulo complex whose norm is and p and q are coprime numbers, each complex integer A is comparable to one and only one residue from the series 0, 1, ..., N - 1, and each complex least residue modulo corresponds to the real residue h modulo which can be calculated according to the following expression Where And such that What is new is that to ensure the possibility of monitoring the integrity of data to be protected, by means of the fundamental Gauss theorem, an isomorphism is established between sets of real and complex numbers, while the array M, which includes the data sent for storage, and the array G, received upon request for its use is represented in the form of matrices And with many elements like at the same time, the norm is determined, which should be greater than the maximum element in the original array M, redundant blocks S and D are formed, and block S will be the sum of the elements of the matrix rows block D will be the sum of the elements of the diagonals of the matrix What is new is that in the proposed method, detection and localization of data blocks with signs of integrity violations is performed by subtracting matrix elements from the elements of redundant blocks represented by matrices S and D Based on the calculation results, a decision is made about the absence of a violation of the integrity of data blocks, or the opposite, in this case, data blocks with signs of integrity violation will be located at the intersection of identified lines and diagonals, to restore the integrity of detected and localized data blocks with signs of its violation to the identified erroneous elements add the result of the difference between the rows of the redundant block represented by the matrix S and the matrix What is new is that to ensure the possibility of detecting and localizing data blocks with signs of integrity violations, it is necessary to store only those complex residues whose range of real and imaginary parts is the largest. c) Cause-and-effect relationship between features and technical result Thanks to a new set of essential features, the method implements the following capabilities:

- control and restoration of data integrity based on number-theoretic transformations in the complex plane;

- detection and localization of data blocks with signs of integrity violation, which does not require storage of all calculated control information.

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 a method for monitoring the integrity of multidimensional data arrays based on the rules for constructing the Reed-Solomon code; fig. 2 is a diagram illustrating the developed method for monitoring and restoring data integrity based on number-theoretic transformations in the complex plane;

fig. 3 - diagram illustrating the complete system of least complex deductions for the norm N=25 and module

fig. 4 is a diagram illustrating the smallest and largest residues in geometric representation;

fig. 5 is a diagram illustrating the order of following along the ordinate axis;

fig. 6 is a diagram illustrating selected storage deductions.

Carrying out the invention

Data that must be protected from changes during storage, presented in the form of blocks M _j (j=1, 2, ..., n), must be converted into a set of elements of the form:

where a and b are real numbers, i is a symbol called the imaginary unit. In this case, the following operations can be entered on the set of these symbols:

- comparison: (if and only if );

- addition:

- multiplication:

In this case, elements of the specified type with the introduced operations will be complex numbers. The operations of addition and multiplication introduced on the set of complex numbers will have the following properties:

- commutativity of addition:

- addition associativity:

- commutativity of multiplication:

- associativity of multiplication:

- distributivity of addition and multiplication:

Real number will be the real part of the number represented in the complex plane, and the number b is its imaginary part.

If given a series of positive integers called the bases of the system, then a system in residual classes will be understood as a system in which a positive integer A is represented as a set of residues (residues) for selected bases:

In this case, the number xth digit a _x of the number A is the smallest positive remainder when dividing A by p _x .

The main number-theoretic basis of the system of residual classes is the theory of comparisons, in which two integers a and b are comparable modulo p if their difference is a multiple of p (divisible by p).

For comparison, the following notation is used:

Moreover, the complex number will be a multiple of a complex number if private is a complex number. In this case, the quotient will be an integer when

Where - norm of the number m.

Smallest number deduction modulo this number is called that the following relation holds:

or

Smallest residue of any complex number by complex module is determined based on a system of two real comparisons:

where r and r' are the smallest positive residues modulo N. All possible pairs of values r and r' can be determined by solving the comparison:

Where and k is such that t is an integer less

Using the following ratio:

The smallest deduction of the number A modulo m is calculated.

According to a given complex module whose norm is and for which p and q are coprime numbers, each complex integer is comparable to one and only one residue from the series: 0, 1, ..., N-1.

Thus, for each complex least deduction modulo corresponds to the real residue h modulo which can be calculated according to the following expression:

Where And such that

To detect and localize data blocks with signs of integrity violations (occurring errors), an isomorphism is established between the sets of real and complex numbers using the fundamental Gauss theorem.

In this case, two data sets are given:

- initial data array M, which includes data sent for processing and storage to an automated system, containing target information;

- array G, which includes data obtained after processing and storage in an automated system under conditions of destructive influences of an attacker and disturbances in the operating environment.

Using the fundamental theorem of Gauss, we represent the arrays M and G in the form of matrices with many elements of the form To do this, we define a norm that must be greater than the maximum element in the original array M.

The matrix corresponding to the original array M will take the following form:

where the matrix element is a complex number, that is

The matrix corresponding to array G will take the following form:

where the matrix element is a complex number, that is

Let's form redundant blocks, the first of which will be the sums of the elements of the matrix rows

the second block will be the sums of the elements of the matrix diagonals that is:

where S is the first redundant block, D is the second.

To detect and localize data blocks with signs of integrity violations (occurring errors), it is necessary to subtract matrix elements from the elements of redundant blocks represented by matrices S and D

- if the result is “O”, then the integrity of the data blocks has not been violated (no error);

- otherwise, a violation of the integrity of data blocks is confirmed (an error has occurred). In this case, the element (a block of data with signs of integrity violation) will be located at the intersection of the line and diagonal in which the error is present.

To restore the integrity of a detected and localized data block with signs of its violation (correction of an error), it is necessary to add to the erroneous element the result of the difference between the rows of matrices S and

A diagram illustrating the developed method of protecting data from changes in an automated system during their processing and storage is presented in Figure 2.

Example 1. Let’s assume that an image with its corresponding digital code (data array M) is sent to an automated system for processing and storage:

Moreover, when requesting its use after processing and storage under conditions of destructive influences of an attacker and disturbances of the operating environment, the following digital code (array G) is received at the output:

As a result of the destructive influences of the attacker and disturbances in the operating environment, information was distorted, that is, the integrity of data blocks to be protected was violated (an error occurred).

To detect and localize a block of data with signs of integrity violation (error), based on the fundamental Gauss theorem, we will write the arrays M and G in matrix form and reduce their elements to a complex form.

Let us choose the norm N=256 and the corresponding module

We get the matrix:

corresponding to the array M and the matrix corresponding to the array G:

Let's create redundant blocks:

To detect, localize and restore the integrity of data blocks with signs of its violation (detection, localization and correction of an error that has occurred), we will perform a line-by-line check:

hence there is an error in the first line;

therefore, there is an error in the second line;

hence there is an error in the third line,

and along the diagonals:

therefore there is no error;

therefore there is no error;

therefore, there is an error;

therefore, there is an error;

therefore there is no error.

Thus, the erroneous element is located at the intersection of the line and the diagonal, that is, during processing and storage in an automated image system, an error occurred in the elements

To correct an error that occurred during image processing and storage, you need to add the result of the line difference to the erroneous element:

We get

Let's convert it into real form:

and as a result we obtain a digital code (original array) corresponding to the one sent for storage (Fig. 2).

Example 2. Consider the system of least complex deductions for the norm N=25 and the module We will find the complete system of least complex residues using geometric construction. Let us mark a point M on the complex plane with coordinates (3; 4), construct a square on the side OM and list all the integer complex numbers,

located inside this square (Fig. 3). Thus, we obtain a complete system of complex deductions presented in Table 1.

Let's translate the information contained in the data subblocks M into complex form from the real one.

Let us calculate the real residue, which corresponds to the complex residue using the Gauss formula:

We'll find And from the expression

It turns out

Where does the complex deduction come from? according to the Gauss formula for norm N ₁ with modulus the following real deduction will correspond:

Where

Then we will find real residues that correspond to complex residues from the example. Norm N=25 and module We'll find And from the expression

We get where Let's substitute And into the Gaussian equation and we get:

Next we obtain real residues by substituting complex residues into the Gauss equation:

In a similar way, we will establish a correspondence between the remaining complex and real deductions (Table 2).

From Table 2 presented above, it is clear that there is a pattern in that the real deduction increases by one from left to right, starting from “-3+3i” (real deduction is equal to 1), ending with “2+4i” (real deduction is equal to 24) ( Fig. 4).

The order of following along the ordinate axis is formed as follows: 1) T/2, where T is the number of smallest deductions along the ordinate axis from 0 to the border of the square; 2) T; 3) T/2 - 1; 4) T - 1; 5) T/2 - 2; 6) T - 2.

In the example under consideration, the order along the ordinate axis is as follows: 3i, 6i, 2i, 5i, 1i, 4i (Fig. 5). This property of the geometric representation allows, without calculations, according to expression (1), to determine the real residue and the corresponding complex residue.

Thus, transformations of the form allow you to represent the data of the array M as real residues h modulo m and, accordingly, complex residues isomorphic to them.

Let's assume that we have a data array, which in its geometric interpretation represents a square, the number of smallest residues of which is equal to N-1, with N=1000. This will lead to the consumption of a large amount of memory, and, as a result, a large amount of time for monitoring data integrity. In turn, the developed method allows you to store only those complex residues (also known as real residues) whose range of real and imaginary parts is the largest. In this case (see example 2) these will be real components (-3, -2, -1, 0, 1, 2) and imaginary parts (Fig. 6).

This way, fewer memory cells can be wasted. Let’s assume that in the presented case, 24 memory cells (24 residues) are occupied, but since only part of the residues are stored, there will be 11 cells in total. Accordingly, with large sizes of the geometric representation of the smallest residues, the amount of data not reserved for storage will be much less. From all of the above, it follows that in the developed method for monitoring data integrity, in order to ensure the possibility of detecting and localizing data blocks with signs of integrity violations, the storage of all calculated control information is not required.

Claims (1)

A method for monitoring and restoring data integrity based on number-theoretic transformations in the complex plane, which consists in the fact that in order to ensure the possibility of detecting and localizing data with signs of integrity violation, the initial array is divided into data blocks of a fixed length, with which transformations are subsequently performed, differing in , that with data blocks M _j , where j = 1, 2, ..., n, subject to change protection, transformations are performed, as a result of which a set of elements of the form A = a + bi is obtained, where a and b are real numbers, symbol i is an imaginary unit, which allows us to introduce the operations of comparison, addition and multiplication on the set of these elements, and the elements of the specified type with the introduced operations will be complex numbers A, and modulo m=p+qi, the norm of which is N = p ² + q ² , and p and q are relatively prime numbers, each integer complex number A will be comparable to one and only one residue from the series 0, 1, ..., N-1, and each complex minimum residue x+yi modulo m =p+qi correspond to the real residue h modulo N=p ² +q ² , which is calculated according to the following expression x+y(uq-vp)≡h(modN), where u and v are such that up+vq= 1, to carry out data integrity monitoring, providing the ability to detect and localize data blocks with signs of integrity violations, using the fundamental Gauss theorem, an isomorphism is established between sets of real and complex numbers, while the array M, which includes the data sent for storage, and the array G , received upon request for its use, is presented in the form of matrices A _complex and B _complex with a set of elements of the form a + bi, while determining the norm, which must be greater than the maximum element in the original array M, forming redundant blocks represented by matrices S and D , while block S constitutes the sums of row elements of matrix A _complex , block D constitutes the sums of diagonal elements of matrix A _complex , detection and localization of data blocks with signs of integrity violations is performed by subtracting elements of matrix B from the elements of redundant blocks represented by matrices S and D _complex , based on the calculation results, a decision is made about the absence of signs of data integrity violation, or the opposite, in this case, data blocks with signs of integrity violation will be located at the intersection of identified lines and diagonals, to restore the integrity of localized data blocks with signs of its violation, to the identified erroneous ones elements are added the result of the difference between the rows of the redundant block, represented by the matrix S, and the matrix B _complex , and to ensure this possibility it is necessary to store only those complex residues whose range of real and imaginary parts is the largest.