RU2186466C2 - Method for iterative encryption of digital data blocks - Google Patents

Abstract

FIELD: electric communications and computer engineering; data encryption methods. SUBSTANCE: method involves private key generation, data block division into two subblocks, and execution of R≥2 encryption, these operations including conversion of first sub-block by means of sequence of L₁, L₂,..., L_n operations, where n > 1, and conversion of second sub-block by means of sequence of H₁, H₂,...,H_m operations, where m > 1; at least one of L₁, L₂,..., L_n, H₁, H₂,..., H_m operations is controlled operation and control vector is generated prior to this operation; during execution of at least one of L₁, L₂,..., L_n, H₁, H₂,..., H_m operations use is made of one of sub-keys ; m is even number and n is odd number; in addition sub-blocks are re- arranged in all encryption rounds except for last one upon execution of L_n and H_m operation; H_i operations are reverse to H_m-i+1 operations, where 1≤i≤m/2; L_n-j+1, where 1≤j≤(n-1)/2 ones; two-place reversible controlled operation is used as L_(n-1)/2+1 operation and before its execution control vector is generated depending on second block. EFFECT: enhanced resistance to differential cryptanalysis. 4 cl, 2 dwg

Description

 The invention relates to the field of telecommunications and computer technology, and more particularly to the field of encryption methods and cryptographic devices for protecting information transmitted through communication channels or stored in computer systems.

In the aggregate of the features of the proposed method, the following terms are used:
- the secret key is binary information known only to a legitimate user;
- subkey - part of the secret key;
- encryption is the process of converting information that depends on the secret key and converts the source text into ciphertext (cryptogram), which is a pseudo-random sequence of characters from which obtaining information without knowing the secret key is practically impossible;
- decryption is the reverse process of encryption; decryption provides recovery of information from the cryptogram with the knowledge of the secret key;
- the cipher is a set of elementary steps for converting input data using a secret key; the cipher can be implemented as a computer program or as a separate device;
- a binary vector is a sequence of zero and one bits, for example (101101011); a binary vector is interpreted as a binary number, i.e. a binary vector can be matched with a numerical value;
- cryptanalysis - a method of calculating a secret key to obtain unauthorized access to encrypted information;
- cryptographic strength is a measure of the reliability of encrypted information protection and represents the complexity, measured in the number of elementary operations that must be performed to recover information from a cryptogram with knowledge of the conversion algorithm, but without knowledge of the secret key;
- a single operation is an operation performed on a binary vector; the binary vector generated at the output of a unary operation depends only on the input binary vector; examples of single operations are cyclic shift operations;
- two-place operation is an operation performed on two operands; the result of some given two-place operation depends on the value of each operand; examples of double operations are the operations of addition, subtraction, multiplication, etc.

- the operand is a binary vector over which a two-place or one-place operation is performed;
- a controlled two-place operation is an operation performed on two operands under the control of a binary vector called a control vector; the result of some controlled two-place operation with a fixed control vector depends on the value of each operand, and for fixed values of the operands, on the value of the control vector; examples of the implementation of controlled double operations are described in patent 2140716 [Moldovyan A.A., Moldovyan N.A., Moldovyan P.A. The method of cryptographic conversion of digital data blocks // RF Patent 2140716, IPC ⁶ H 04 L 9/28, BI 30 from 10.27.1999]; in the formulas, the controlled two-place operation will be denoted by the record Z: = Q _V (A, B), where A, B are operands, V is the control vector, Z is the binary vector resulting from the execution of the controlled two-place operation Q _V ;
- modification of the controlled two-seater operation - a two-seater operation corresponding to the conversion of two operands with a fixed value of the control vector;
- controlled permutation - this is an operation performed on one operand under the control of a binary vector called a control vector and consisting in the permutation of the bits of the operand depending on the value of the control vector; examples of the implementation of controlled permutations are described in patent 2140714 [Alekseev L.E., Belkin T.G., Moldovyan A.A., Moldovyan N.A. The method of iterative encryption of data blocks // RF Patent 2140714, IPC ⁶ N 04 L 9/20, BI 30 from 10.27.1999]; in the formulas, the controlled permutation will be denoted by the record P _V , and the transformation of the operand B by performing a controlled permutation on it by the record B: = P _V (B), where V is the control vector; controlled permutation is a special case of controlled single operation;
- modification of controlled permutation - a fixed permutation of the bits of the operand corresponding to a given value of the control vector;
- inverse controlled permutation (with respect to some given controlled permutation) is a permutation, all modifications of P _V ^{-1 of} which are inverse with respect to modifications of the permutation P _V , i.e. for any given value of the control vector, the sequential execution of the operations P _V and P _V ^-1 on the binary vector B does not change the value of the latter, which can be analytically written as B = P _V ^-1 (P _V (B)) or B = P _V ( P _V ^-1 (B)); embodiments of two mutually inverse controlled permutations are described in RF patent 2140714.

is an inverse controlled two-place operation (with respect to some given controlled two-place operation, Q is such a controlled two-place operation (denoted as Q ^-1 ), which for any given value of the control vector V and any given value of the operand B satisfies the condition A = Q _V ^{- 1} (Z, B) if Z = Q _V (A, B); options for the implementation of two mutually inverse controlled two-place operations are described in [Guts N.D., Moldovyan A.A., Moldovyan N.A. oriented ciphers based on managed adders // Security issues inf rations, 2000, 1, pp. 8-15];
- the reversed controlled two-place operation Q * is such a controlled two-place operation that is controlled by a special invert bit e; different values of e specify two different variants of the controlled two-seater operation, and these variants are mutually inverse; for example, if, for e = 0, the operation Q ₍₀₎ is performed, and for e = 1, the operation Q ₍₁₎ , then for these controlled two-place operations we have the relation Q ₍₁₎ = Q ₍₀₎ ^-1 ; an implementation option of a reversed controlled two-seater operation is described in [Guts N.D., Moldovyan A.A., Moldovyan N.A. Flexible hardware-oriented ciphers based on managed adders // Issues of information security, 2000, 1, p. 8-15];
- controlled permutation involution is an operation of controlled permutation P, for which the controlled permutation inverse to it coincides with itself, i.e. P _V ^-1 = P _V for all possible values of the control vector; this means that for a controlled permutation involution the equality B = P _V (P _V (B)) holds for an arbitrary value V.

 Known methods for iterative encryption of digital data blocks, see, for example, the DES cipher [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc., New York, 1996, p. 270-277]. In this method, the data is divided into blocks, the encryption of which is performed by generating a secret key, dividing the converted data block into two subunits L and R and alternating the latter by performing bitwise summing operations modulo two over the subunit L and the binary vector, which is formed as the output value some function E on the value of the sub-block R. After this, the sub-blocks are rearranged. Function E in the specified method is implemented by performing permutation and substitution operations performed on the sub-block R. This method has a high conversion speed when implemented in the form of specialized electronic circuits. However, the known analogue method uses a small secret key (56 bits), which makes it vulnerable to cryptanalysis based on key selection. The latter is associated with the high computing power of modern computers.

Another well-known method of iterative encryption of discrete data blocks is the method described in the Russian standard for cryptographic data protection [USSR Standard GOST 28147-89. Information processing systems. Cryptographic protection. Cryptographic Transformation Algorithm]. This method includes generating an encryption key in the form of a sequence of 8 subkeys 32 bits long, splitting the input information presented as binary code into sections of 64 bit length, forming 64-bit data blocks on their basis, and converting the blocks under the control of the key encryption. Before conversion, each data block is divided into two 32-bit subunits A and B, which are converted one by one by performing 32 rounds of conversion (iterations). One round of conversion is as follows. Using subunit A and one of the subkeys, the 32-bit value of the round function E is calculated and the obtained value E (A) is superimposed on subunit B using the bitwise summing operation modulo two (⊕) in accordance with the formula B: = B⊕E (A) . The calculation of the round function is carried out in accordance with the following transformation steps. A binary vector F is formed from subunit A. The binary vector F is transformed by superimposing on it the current subkey K _i , which is fixed for a given round and called a round subkey, using the addition operation modulo 2 ³² (+) in accordance with the formula F: = ( R + K _i ) mod 2 ³² , where 1≤i≤8, after which the substitution operation (F: = S (F)) is performed on the binary vector F, then the operation of cyclic left shift by eleven bits, i.e. by eleven binary digits in the direction of the higher digits (F: = F <<< 11). After each round of encryption, with the exception of the last round, the subblocks are rearranged. The substitution operation is performed as follows. Binary vector F is divided into 8 binary vectors with a length of 4 bits. Each binary vector is replaced by a binary vector from the lookup table. Eight 4-bit vectors selected from the lookup table are combined into a converted 32-bit binary vector F.

 However, the analogue method has drawbacks, namely, the substitution operations are performed on binary vectors of small length (4 bits), which creates the prerequisites for attacking this cipher by differential cryptanalysis [B. Schneier, "Applied Cryptography", Second Eddition, John Wiley & Sons, Inc. , New York, 1996, p. 285-290]. Therefore, to ensure high resistance to differential cryptanalysis, a large number of encryption rounds are required, which reduces the encryption performance.

The closest in technical essence to the claimed method of iterative encryption of discrete data blocks is the method described in the patent of the Russian Federation 2141729 [Moldovyan A.A., Moldovyan N.A. The method of cryptographic conversion of binary data blocks // RF Patent 2141729, IPC ⁶ Н 04 L 9/00, BI 32 from 11/20/1999]. The prototype method includes generating a secret key, splitting a data block into two sub-blocks A and B, and converting the sub-blocks under the control of the encryption key by performing 16 rounds of conversion (iterations) on them. Each round includes the conversion of sub-blocks in turn, with at least two operations performed on each of them. In the particular case of the implementation of the prototype method (see example 1 with r = 1 in the description of patent 2141729), one round includes the following conversion steps:
1. Using the bitwise summing operation modulo two (⊕), a sub-block K _{1 is} superimposed on sub block A in accordance with the formula A: = A ⊕ K ₁ .
2. Using the addition operation modulo 2 ³² (+), a sub-block K _{2 is} superimposed on the sub-block B in accordance with the formula B: = B + K ₂ , where the “: =” sign denotes the assignment operation.

3. Subblock B is transformed in accordance with the expression B: = P _V (B), where P _V is the modification of the controlled permutation, V is the value of the control vector formed depending on the values of the subblock A and subkey K ₃ .

 4. On subunit A, subunit B is superimposed in accordance with the formula: A: = A + B.

5. The operation of controlled permutation A is performed over sub block A: = Р _V (A), where V is the value of the control vector generated depending on the values of sub block B and subkey K ₄ .

6. Subblock B is converted in accordance with the formula B: = B⊕A.
However, the prototype method has drawbacks, namely, when it is implemented in the form of electronic cryptographic devices, it is necessary to use two different electronic circuits to perform encryption and decryption, which complicates its implementation.

 The basis of the invention is the task of developing an iterative encryption of digital data blocks, in which the input data is converted in such a way that the encryption and decryption procedures can be carried out using the same electronic circuit, using plug-ins in reverse order when decrypting in relation to the order use of keys under encryption, which simplifies the circuitry implementation.

The problem is achieved in that in the method of iterative encryption of discrete data blocks, including generating a secret key, splitting the data block into two subblocks and performing R≥2 rounds of encryption, including converting the first subblock by performing a sequence of operations L ₁ , L ₂ , on it. .., L _n , where n> 1, and the transformation of the second subblock by performing a sequence of operations H ₁ , H ₂ , ..., H _{m on it} , where m> 1, new, according to the invention, is that m is an even number, n is an odd number and additionally, in the first (R-1) encryption rounds, after the operations L _n and H _{m are} performed, the sub-blocks are rearranged, and the operations H _i are inverse to the operations H _{m-i + 1} , where 1≤i≤m / 2, and operations L _j are inverse with respect to operations L _{n-j + 1} , where 1≤j≤ (n-1) / 2, and before the operation L _{(n-1) / 2 + 1} , a control vector is formed, and as operations L _{(n-1) / 2 + 1} uses a reversible controlled two-place operation.

Thanks to this solution, the execution of the sequence of operations L ₁ , L ₂ ,. . ., L _n and operations H ₁ , H ₂ , ..., H _m , defines the procedure for converting the data block as an involution, which makes it possible to decrypt the encrypted data block using the same electronic circuit that was used to encrypt it. This simplifies the circuitry implementation of the method of iterative encryption of discrete data blocks.

It is also new that, in addition to performing each operation L ₁ , L ₂ , ..., L _n , H ₁ , H ₂ , ..., H _m , a control vector is formed, and as operations L ₁ , L ₂ , ..., L _n , H ₁ , H ₂ , ..., H _m , controlled permutations and controlled two-place operations are used, and the inverse controlled two-place operation is used as the operation L _{(n-1) / 2 + 1} .

 Thanks to this solution, it provides increased resistance to differential cryptanalysis.

In addition, it is new that before performing the operation L _j , 1≤j≤n on the first subunit, the control vector is formed depending on the secret key and the current value of the second subunit, and before performing the operation H _i , 1≤i≤m on the second subblock, the control vector is formed depending on the secret key and the current value of the first subblock.

 Thanks to this solution, an additional increase in cryptographic strength and the possibility of reducing the number of encryption rounds is provided, which ensures an increase in the encryption speed.

 Below the essence of the claimed invention is explained in more detail by examples of its implementation with reference to the accompanying drawings.

 The generalized scheme of iterative encryption of data blocks based on the proposed method is represented by the encryption round structure shown in FIG. 1a, where A and B are sub-blocks of the data block to be converted.

Example 1
This example is shown in figb and explains the implementation of the method for the case of n = 5 and m = 4. The data block T has a length of 64 bits and is divided into two 32-bit subunits A and B. In FIG. 1b, the following notation is used:
P and P ^-1 are mutually inverse controlled permutations performed on 32-bit binary vectors and having a 64-bit control input;
π and π ^-1 are mutually inverse fixed permutations, i.e. such fixed permutations, the sequential execution of which on any operand does not change the value of the latter, i.e. the relations are: π (π ^-1 (A)) = A, and π ^-1 (π (A)) = A. Fixed permutations are easily implemented in electronic circuits and do not introduce delays in the data conversion process;
Q * is a reversible two-place operation with a 32-bit control input;
"-" - operation subtraction modulo 2 ³² .

Encryption in accordance with example 1 is as follows. The secret key is generated in the form of the following set of 32-bit round subkeys: K ₁ , K ₂ , ..., K ₁₆ and W ₁ , W ₂ , ...., W ₁₆ . The data block is divided into two subunits A = T div 2 ³² and B = T mod 2 ³² . Data block encryption is performed in accordance with the following algorithm.

 1. Set the counter for the number of encryption rounds r: = 1 and the value e = 1.

2. Place subwrite W _r on sub block A using the summation operation modulo 2 ³² :
A: = (A + W _r ) mod 2 ³² .

3. Place subkey K _r on subblock B using the bitwise summing operation modulo 2:
B: = B⊕K _r .
4. Generate a 64-bit control vector V: V = A | A, where the sign "|" denotes a concatenation operation.

5. Perform on a sub-block B operation controlled permutation:
B: = P _V (B).

6. Perform a fixed permutation operation on block A:
A: = π (A).
7. Form a control vector V depending on the subunit A and subkey K _r and W _r :
V = A⊕K _r ⊕W _r .
8. Place subunit A on subunit B using a reversible controlled two-seat operation
B: = Q $\genfrac{}{}{0ex}{}{\text{*}}{\text{V}}$ (B, A).
9. Perform reverse fixed permutation operation on block A:
A: = π ^-1 (A).
10. Generate a 64-bit control vector V: V = A | A from subunit A.
11. Perform on a sub-block B operation reverse controlled permutation:
B: = P _V ^-1 (B).

12. Place subkey K _r on sub block A using the subtraction operation modulo 2 ³² :
A: = (A-K _r ) mod 2 ³² .

13. Place subwrite W _r on subblock B using the bitwise summing operation modulo 2:
B: = B⊕W _r .
14. If r <16, then increment r: = r + 1, rearrange subblocks A and B (that is, take binary vector A as binary vector B, and binary vector B as binary vector A) and go to step 2.

 15. STOP.

The cryptogram block C is formed by combining the transformed binary vectors A and B: C = A | B. Decryption of the cryptogram block is carried out using the same algorithm, except that in the first step the value e = 0 is set and when performing steps 2, 7 and 13, the subkey K _{17-r is used} instead of the subkey W _r , and when performing steps 3, 7 and 12 - plug W _17-r instead of K _r . Bit e serves to reverse the controlled two-place operation Q * and to specify the sequence of use of round subkeys, i.e. the value of this bit sets the encryption mode (e = 1) or decryption (e = 0). Since encryption and decryption are performed using the same algorithm, both of these procedures can be performed using the same electronic circuit.

Example 2. Encryption of a 64-bit data block T
This example is illustrated in FIG. 2a and corresponds to the case n = 5 and m = 4 and the use of the reversed controlled two-place operation Q * as the operation L _{(n-1) / 2 + 1} . This example uses a reversible controlled two-place operation Q * with a 32-bit control input. Encryption in accordance with example 2 is as follows. The secret key is generated in the form of the following combination of 32-bit round subkeys: K ₁ , K ₂ ,. . ., K ₈ and W ₁ , W ₂ , ..., W ₈ . Split the data block T into two 32-bit subunits A and B. Then the data block is encrypted in accordance with the following algorithm.

 1. Set the counter for the number of encryption rounds r: = 1 and the value of the invert bit e = 1.

2. Place subkey K _r on sub block A in accordance with the formula:
A: = A⊕K _r .
3. Perform on a sub-block B operation of a fixed permutation:
B: = π (B).
4. By connecting W _r and using sub-block B to form a 64-bit control vector V: V = W _r | B.
5. Perform a controlled permutation operation on subunit A:
A: = P _V (A).

6. Place subwrite W _r on subblock B in accordance with the expression:
B: = (B + W _r ) mod 2 ³² .

7. Generate a 32-bit control vector V, depending on sub-block A and subkeys K _r and W _r in accordance with the expression:
V = (W _r + K _r ) ⊕ A.
8. Place subunit A on subunit B using a reversible controlled two-seat operation:
B: = Q $\genfrac{}{}{0ex}{}{\text{*}}{\text{V}}$ (B, A).
9. Place subkey K _r on subblock B in accordance with the expression:
B: = (BK _r ) mod 2 ³² .

10. By connecting K _r and using sub-block B to form a 64-bit control vector V: V = K _r | B.
11. Perform reverse controlled permutation operation on block A:
A: = P _V ^-1 (A).

12. Place subwrite W _r on sub-block A in accordance with the formula:
A: = A⊕W _r .
13. Perform the reverse fixed permutation operation on subblock B:
B: = π ^-1 (B).
14. If r <8, then increment r: = r + 1, rearrange subblocks A and B, and go to step 2.

 15. STOP.

As a result of the algorithm execution, the cryptogram block C = A | B is formed. Decryption of the cryptogram block is carried out using the same algorithm, except that in the first step the value e = 0 is set, and in steps 4, 6, 7 and 12, the subkey K _{9-r is used} instead of the subkey W _r and in steps 2 , 7, 9 and 10 - subkey W _9-r instead of subkey K _r .

Example 3
This example is illustrated in FIG. 2b, where Q is a controlled two-place operation with a 32-bit control input and Q ^-1 is the corresponding reverse controlled two-place operation with a 32-bit control input. Example 3 corresponds to the case n = 3 and m = 2 and the use of controlled permutation operations and controlled two-place operations as the operations L ₁ , L ₂ , ..., L _n , H ₁ , H ₂ , ..., H _m and the operations Q * as the operation L _{(n-1) / 2 + 1} .

Encryption in accordance with example 3 is as follows. The secret key is generated in the form of the following set of 32-bit round subkeys: K ₁ , K ₂ , ..., K ₁₆ and W ₁ , W ₂ , ...., W ₁₆ . Split the data block T into two 32-bit subunits A and B. The encryption of the data block is carried out in accordance with the following algorithm.

 1. Set r: = 1 and e = 1.

2. By connecting W _r and using sub-block A, form a 32-bit control vector V: V = W _r ⊕ A.
3. Place subkey K _r on sub-block B in accordance with the formula:
B: = Q _V (B, K _r ).

4. By connecting W _r and using sub-block B to form a 64-bit control vector V: V = W _r | B.
5. Perform a controlled permutation operation on subunit A:
A: = P _V (A).

6. Generate a control vector V depending on subunit A and subkey K _r and W _r :
V = (W _r + K _r ) ⊕ A.
7. Place subunit A on subunit B using the reversed controlled two-place operation Q *:
B: = Q $\genfrac{}{}{0ex}{}{\text{*}}{\text{V}}$ (B, A).
8. By connecting To _r and using sub-block B, generate a 64-bit control vector V: V = K _r | B.
9. Perform a reverse controlled permutation operation on subunit A:
A: = P _V ^-1 (A).

10. By connecting K _r and using sub-block A, form a 32-bit control vector V in accordance with the formula: V = K _r ⊕A.
11. Place subwire W _r on subblock B in accordance with the formula:
B: = Q _V ^-1 (B, W _r ).

 12. If r <16, then increment r: = r + 1, rearrange subblocks A and B, and go to step 2.

 13. STOP.

As a result of the algorithm execution, the cryptogram block C = A | B is formed. The cryptogram block is decrypted using the same algorithm, except that in the first step the inversion bit value is set to e = 0, and when performing steps 2, 4, 6 and 11, the K _17-r subkey is used instead of the W _r subkey, and when performing steps 3, 6, 8 and 10 - subwoofer W _17-r instead of subkey K _r . Such a change in the order of use of subkeys in electronic circuits can be easily set depending on the setting of the value of the invert bit e.

 The above examples show that the proposed method of iterative encryption of discrete data blocks is technically feasible and allows us to solve the problem.

Claims (4)

1. A method of iterative encryption of binary data blocks, including generating a secret key in the form of a set of subkeys, splitting a data block into two subblocks and performing R≥2 rounds of encryption, each of which consists in converting the first subblock by performing a sequence of operations L ₁ , L on it ₂ ,. . . , L _n , where n> 1, and the transformation of the second subblock by performing operations on it H ₁ , H ₂ ,. . . , H _m , where m> 1, and at least one of the operations L ₁ , L ₂ ,. . . , L _n , H ₁ , H ₂ ,. . . , H _m is a controlled operation and before performing this operation form a control vector, and when performing at least one of the operations L ₁ , L ₂ ,. . . , L _n , H ₁ , H ₂ ,. . . , H _m use one of the subkeys, characterized in that m is an even number, n is an odd number and, in addition to the last one, in all encryption rounds, after operations L _n and H _m , the sub-blocks are rearranged, and the operations H _i are inverse with respect to operations H _{m-i + 1} , where 1≤i≤m / 2, and operations L _j are inverse to operations L _{n-j + 1} , where 1≤j≤ (p-1) / 2, and operation as L _{(n-1) / 2 + 1} is used Reversal controlled two-place operation and before it is executed the control vector formed in dependence m the second block. 2. The method according to p. 1, characterized in that the values m = 2 and n = 3 are used as the operations H ₁ and H ₂ using controlled permutations, and as the operations L ₁ and L ₃ using controlled two-place operations performed on the first subblock and one of the subkeys. 3. The method according to p. 1, characterized in that as at least one of the operations H ₁ , H ₂ ,. . . , H _m use the fixed permutation operation. 4. The method according to p. 1, characterized in that as at least one of the operations L ₁ , L ₂ ,. . . , L _{(n-1) / 2} use the fixed permutation operation.

Images