RU2140709C1 - Process of cryptographic conversion of blocks of digital data - Google Patents

Abstract

FIELD: electric communication, computer engineering, cryptographic methods and devices to cipher digital data. SUBSTANCE: salient feature of process lies in breaking of data block into N≥2 subblocks and in conversion of subblocks by one conversion operation as minimum by turns. This conversion depends on value of input block. Substitution operation realized with k bits of subblock, where 8≤k≤16 is used as operation depending on value of input block. Substitution operations are set by substitution table which number T≥2. Secrete substitution tables are used as substitution tables. In addition binary vector V is formed and substitution table for implementation of substitution operation is chosen by value of vector V. Vector is formed on present step of conversion depending on its value on preceding step of conversion and on value of one of subblocks. EFFECT: increased cryptographic resistance. 2 cl, 3 dwg

Description

 The invention relates to the field of telecommunications and computer technology, and more particularly to the field of cryptographic methods and devices for encrypting messages (information).

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;
- cryptographic conversion is the conversion of digital information that provides the influence of one bit of the source data on many bits of the output data, for example, to protect information from unauthorized reading, the formation of a digital signature, and the generation of a modification detection code; One of the important types of cryptographic transformations is one-way conversion, hashing and encryption;
- hashing information is some way of generating the so-called hash code, the size of which is fixed (usually 128 bits) for messages of any size; widely used hashing methods based on iterative hash functions using block mechanisms of cryptographic information conversion [see Lai X., Massey JL Hash Functions Based on Block Ciphers / Workshop on the Theory and Applications of Cryptographic Techniques. EUROCRYPT'92. Hungary, May 24-28, 1992. Proceedings. P. 53-66.].

- encryption is a process of converting information that depends on the secret key and converts the source text into ciphertext, which is a pseudo-random sequence of characters from which it is practically impossible to obtain information without knowing the secret key;
- decryption is the opposite of the encryption process; 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 unit bits, for example 101101011; the specific structure of the binary vector can be interpreted as a binary number, if we assume that the position of each bit corresponds to a binary digit, i.e. a binary vector can be associated with a numerical value, which is determined uniquely by the structure of the binary vector;
- cryptanalysis - a method of calculating a secret key to obtain unauthorized access to encrypted information or developing a method that provides access to encrypted information without calculating a secret key;
- one-way conversion is the conversion of an L-bit input data block to an L-bit output data block, which makes it easy to calculate the output block from the input block, and computing an input block that would be converted to a randomly selected output block is an almost impossible task;
- a one-way function is a function whose value is easily calculated by a given argument, however, calculating an argument from a given function value is a computationally difficult task; one-way functions are implemented as a sequence of procedures for one-way conversion of some input block (argument), the output value of which is taken as the value of the function;
- 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 the cryptogram with knowledge of the conversion algorithm, but without the value of the secret key; in the case of one-sided transformations, cryptographic strength is understood as the complexity of calculating the input value of a block from its output value;
- cyclic shift operations depending on the converted sub-blocks or depending on the binary vector — these are cyclic shift operations by the number of bits specified by the value of the sub-block or the value of the binary vector; operations of cyclic shift to the left (right) are indicated by the sign "<<<"("<<<"), for example, the entry B ₁ <<< B ₂ denotes the operation of cyclic left shift of the subunit B ₁ by the number of bits equal to the value of the binary vector B ₂ ; similar operations are basic for the RC5 cipher;
- a single operation is an operation performed on one operand (data block or binary vector); the value of a subblock after performing some given unary operation depends only on its initial value; examples of single operations are cyclic shift operations;
- a double operation is an operation performed on two operands; the result of performing some given double operation depends on the value of each operand; examples of double operations are the operations of addition, subtraction, multiplication, etc.

 Known methods for block data encryption, see for example the US standard DES [National Bureau of Standards. Data Encryption Standard. Federal Information Processing Standards Publication 46, January 1977; see also: S. Maftik. Protection mechanisms in computer networks. - M., Mir, 1993. S. 42-47]. In this method, the encryption of data blocks is performed by generating a secret key, dividing the converted data block into two subblocks L and R and alternating the latter by performing bitwise summing operations modulo two on the subblock L and a binary vector that is formed as the output value of some function F from values of the sub-block R. After that, the blocks are rearranged. The function F 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 of mass application.

The closest in technical essence to the claimed method of cryptographic conversion of L-bit input blocks of digital data to L-bit output blocks is the method implemented in the RC5 cipher described in [R.Rivest, The RC5 Encryption Algorithm / Fast Software Encryption, Second International Workshop Proceedings (Leuven, Belgium, December 14-16, 1994), Lecture Notes in Computer Science, v. 1008, Springer-Verlag, 1995, pp. 86-96]. The prototype method includes forming a secret key in the form of a set of subkeys, splitting the input data block into subblocks A and B, and alternately converting the subblocks. Subunits are converted by performing single and double operations on them. As two-place operations, the modulo 2 ⁿ addition operations are used, where n = 8, 16, 32, 64, and the bitwise summing operation is modulo 2. The operation of cyclic left shift is used as a single-seat operation, and the number of bits by which the converted subunit is shifted on the value of another subblock, this determines the dependence of the cyclic shift operation at the current step of transforming the subblock on the initial value of the input data block. Two-seat operation is performed on a sub-block and a sub-block, as well as on two sub-blocks. A characteristic of the prototype method is the use of a cyclic shift operation, depending on the value of the input block.

A subunit, for example subunit B, is transformed in the following way. The bitwise summing operation is performed modulo 2 over subblocks A and B and the value obtained after performing this operation is assigned to subblock B. This is written as the ratio B ← _ B⊕V, where the sign “← _” denotes the assignment operation and the sign “⊕” denotes a bitwise summing operation modulo 2. After that, a cyclic shift operation is performed on subblock B by the number of bits equal to the value of subblock A: B ← _ B ≪ <A. Then, a summation modulo 2 ⁿ summation operation is performed on the subblock and one of the connections S, where n is the length of the subunit bit: B ← _ B + S mod 2 ^n. After that, block A is similarly converted. Several such steps are taken to convert both sub-blocks.

 This method provides a high encryption speed when implemented in the form of a computer program. However, the prototype method has drawbacks, namely, with a software implementation for a computer with a 32-bit microprocessor, it does not provide high resistance of cryptographic data conversion to differential and linear cryptanalysis [Kaliski B. S., Yin Y.L. On Differential and Linear Cryptanalysis of the RC5 Encryption Algorithm. Advances in Cryptology - CRYPTO '95 Proceedings, Springer-Verlag, 1995, pp. 171-184]. This drawback is due to the fact that the efficiency of using operations depending on the converted data to complicate the known cryptanalysis methods is reduced by the fact that the cyclic shift operations cause a weakly pronounced effect of dissipating the influence of the original structure of the subunit on the structure of the subunit after performing the cyclic shift operation.

 The basis of the invention is to develop a method of cryptographic conversion of digital data blocks, in which the input data is converted in such a way that the operation, depending on the converted block, provides an enhancement of the dispersion effect of the original structure of the subunit on the structure of the subunit after performing this operation, due to which resistance to differential and linear cryptanalysis is increased.

 The problem is achieved in that in the method of cryptographic conversion of digital data blocks, which consists in dividing the data block into N ≥ 2 sub-blocks, alternately converting the sub-blocks by performing at least one conversion operation on the sub-block, which depends on the value of the input block, new according to the invention is that, as an operation depending on the value of the input block, a substitution operation is performed performed on k binary digits of the subblock, where 8 ≤ k ≤ 16, and the operations permutations are defined by permutation tables, the number of which is T ≥ 2.

 Thanks to this solution, the effect of dispersing the influence of the original structure of the subblock on the structure of the subblock after an operation that depends on the data to be converted is enhanced, thereby increasing the resistance of the cryptographic transformation to differential and linear cryptanalysis.

 Also new is that secret lookup tables are used as lookup tables.

 Thanks to this solution, an additional increase in cryptographic resistance to differential and linear cryptanalysis is provided.

 It is also new that a binary vector V is additionally formed, and for performing a substitution operation by the value of V, a substitution table is selected, and the binary vector at the current conversion step is formed depending on its value in the previous conversion step and on the value of one of the subunits.

 Thanks to this solution, an additional increase in cryptographic resistance to attacks based on failures of the encryption device is provided.

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

 In FIG. 1 presents a generalized scheme of cryptographic conversion according to the claimed method.

 In FIG. 2 shows an encryption scheme corresponding to example 1.

 In FIG. 3 shows a one-way conversion scheme corresponding to example 2.

The invention is illustrated by a generalized scheme of cryptographic conversion of data blocks based on the proposed method, which is presented in FIG. 1, where: B is the block to be transformed, b ₁ , b ₂ , ..., b _n are the converted subblocks, S is the operation block that performs the substitution operation on the subblocks, f is the operational block that performs the formation of the binary vector, v ₀ is the initial binary vector value. The solid line corresponds to the transfer of the converted subunits, the dotted line to the transmission of the binary vector.

 The input block of digital data is divided into N ≥ 2 subblocks. Subblocks are converted one by one by changing them using the operation block S. which uses the binary vector value in the transformations, which determines the dependence of the output value of the converted subblock on the value of the binary vector. The operation unit f uses the value of the subblock transformed in the previous step to perform the binary vector transform, i.e. the operation unit f forms a binary vector according to the structure of one of the converted subunits and according to the value of the binary vector that it had at the previous step of the transformation of the subunit. Block S performs a lookup table using a lookup table selected depending on the value of the binary vector. (For example, the binary vector is formed in accordance with the analytical relation V = (V '+ b') mod T, where V 'is the value of the binary vector at the previous conversion step, b' is the output value of the subblock converted at the previous conversion step, T - the number of used lookup tables. Then, the lookup operation is performed using table number V). The formation of a binary vector depending on one of the converted subunits determines the dependence of the substitution operation on the converted data.

 The implementation of substitution over the subunit will be called one step of changing the subunit. The execution of the conversion procedures specified by the function f over the binary vector will be called the step of generating the binary vector. The subblock conversion step includes a binary vector generation step and a subblock change step. The conversion steps are performed sequentially on all sub-blocks, after which the sub-blocks are rearranged. In special cases, the implementation of the proposed method, the permutation of the subunits may not be used. Performing N steps for changing a subblock, N steps for generating a binary vector, and permuting subblocks shown in FIG. 1, make up one round of conversion. The value of the binary vector after the Nth step of generating the binary vector serves as the initial value of the binary vector for the next round of conversion when constructing one-sided transformation functions of digital data blocks. When building ciphers, the initial value of the binary vector for each round is formed depending on the secret key.

An important element is the implementation of a binary vector dependent substitution operation on a subblock. This type of substitution can be used when setting many different substitution tables, each of which is assigned a serial number and to perform the substitution operation on the subblock, use the table whose number is selected depending on the value of V, for example, if 32 substitution tables are used, then the table number can be calculated by the formula v = V mod 2 ⁵ . The meaning of choosing a lookup table that is used to perform a lookup operation on a subblock at the current step, according to a specially generated binary vector, is to make the lookup table selection undefined for each step of the subblock conversion, which increases the strength of the cryptographic conversion.

By the formation of a binary vector we mean a record, for example, in a register or memory cell of a computing device of a certain sequence of single or zero bits. By the formation of a binary vector depending on its structure in the previous step of converting a subblock using a binary vector, we mean defining the dependence of the current value of the generated binary vector on the value that the binary vector had at the previous step in the formation of the data subblock. For example, let subblock B _i be converted using the value of binary vector V. Before using the binary vector at some other transformation step, for example, subblock B _{j, the} binary vector can be formed in accordance with the expression V ← _ V + Q _b , where b = B _i mod 2 ¹¹ - the number of the subkey, calculated depending on the value of the sub-block B _i .

где N = 2^k.Let the substitution operations be performed on subblocks of digital data of length k bits, where k is an integer. Then, to specify a substitution operation that converts a k-bit input subunit into a k-bit output subunit, a table containing two rows of numbers is required:

where N = 2 ^k .

In this table, the bottom line contains all the possible values of the k-bit block exactly once, but in an arbitrary order. The sequence of numbers in the bottom line determines a specific variant of the lookup table, and therefore a specific version of the lookup operation performed using this table. The substitution operation is as follows. A number is selected on the top line that is equal to the value of the input block. The value under this number in the bottom line is taken as the output block. Thus, the substitution table can be placed in the main memory of the computer as a sequential record of k-bit computer words located in cells with addresses w ₀ , w ₁ , w ₂ , ..., w _N-1 . In this case, the value of the input block b is used to calculate the address w ₀ + b of the word, which is taken as the output block. This way of representing a lookup table requires a memory size of kN bits.

We select the number of lookup tables equal to 2 ^L (the amount of required memory will be 2 ^L kN bits), and place the lookup tables continuously one after another. As the address of the table with number v, we take the value of the address w _{0 of} its first k-bit word. Let the address of the table with number 0 be s. In this case, the address of the lookup table with an arbitrary number v is s + vN. If a binary vector is specified that determines the number of the current lookup table v and the current input subblock for performing the lookup operation, then it is performed by replacing the current input block with a k-bit word located at s + vN + b, where b is the value of the subblock above which The current substitution operation is in progress. Using this relation, it is easy to specify the choice of a lookup table with number v and perform lookup over a subblock with value b. In the case considered, setting the dependence of the lookup tables on the value of the binary vector and performing the lookup operation is carried out by the microprocessor very quickly when choosing the appropriate values of the parameters L and k, for example, with L = 5 and k = 8. With the specified parameters, 8 KB of RAM is required to place the lookup tables , which is acceptable, since modern computers have a RAM volume many orders of magnitude greater than this value (from 1 to 64 MB or more).

 The possibility of technical implementation of the proposed method is illustrated by the following specific examples of its implementation.

 Example 1

где R - число раундов шифрования. На r-м раунде шифрования используется r-ая строка подключей.Let L = 5 and k = 8, i.e. 32 tables are given specifying the substitution operations on 8-bit data subunits. We will assume that the tables are known, i.e., a person trying to conduct cryptanalysis knows these tables. We will create a secret key, presented as a combination of 7R 8-bit subkeys

where R is the number of rounds of encryption. On the rth round of encryption, the rth row of subkeys is used.

а обратная подстановка задается таблицей

где строка (Z₀, Z₁, Z₂, ..., Z₂₅₅) получается как верхняя строка после упорядочения столбцов предыдущей таблицы в порядке возрастания чисел в нижней строке.Denote the used lookup tables as follows: T ₀ , T ₁ , T ₂ ,. . . , T ₃₁ , and the substitution operation defined by the table T _v as S _v , where v = 0,1,2,. . ., 31. The permutation tables T ₀ , T ₁ , T ₂ , ..., T ₁₅ can be chosen arbitrarily, and the tables T ₁₆ , T ₁₇ , ..., T ₃₁ are taken so that the permutation operations S _v and S _31-v are mutually inverse. The last condition is satisfied if the pairs of tables T ₁₆ and T ₁₅ ; T ₁₇ and T ₁₄ ; T ₁₈ and T ₁₃ ; ...; T ₃₁ and T ₀ will specify mutually inverse substitution operations. For a set of arbitrary substitution tables T ₀ , T ₁ , T ₂ , ..., T ₁₅ it is easy to compile tables corresponding to the inverse substitution operations. For example, for the lookup operation specified by the following table

and the reverse substitution is set by the table

where the row (Z ₀ , Z ₁ , Z ₂ , ..., Z ₂₅₅ ) is obtained as the top row after ordering the columns of the previous table in ascending order of numbers in the bottom row.

In FIG. 2 shows a diagram of a first round of encryption. In FIG. 2, the solid vertical line corresponds to the transmission of 8-bit subblocks of data, the dashed line corresponds to the transmission of 5-bit subblocks, the horizontal solid line corresponds to the transmission of 8-bit subblock. The bitwise summing operation modulo two is indicated by the symbol "⊕", v denotes the number of the selected lookup table, block S denotes the lookup operation, k ₁₁ , k ₁₂ ,. .., k ₁₇ - plug used in the first round. The arrows on the lines indicate the direction of signal transmission. Example 1 corresponds to the encryption of 64-bit digital data blocks. Encryption is performed in the following way. The input block is divided into 8 subblocks b ₀ , b ₁ , b ₂ , ..., b _{7 of} size 8 bits each. After that form the binary vector v, which has the value of 5 least significant bits of the subblock b ₀ : v ← _ b ₀ mod 2 ⁵ . Then, the bitwise summing operation modulo 2 is performed on the subblock b ₁ and the b ₁₁ subkey and the output value of this operation is assigned to the b ₁ block, which can be written analytically as follows: b ₁ ← _ b ₁ ⊕r ₁₁ . Then, according to the lookup table with number v, the lookup operation is performed on the subblock b ₁ : b ₁ ← _ S _v (b ₁ ). Then, according to the value of b ₁ , the binary vector v is formed: v ← _ v⊕ (b ₁ mod 2 ⁵ ), and the new value of the binary vector depends on its previous value. After that, the subblock b _{2 is} converted: b ₂ ← _ b ₂ ⊕k ₁₂ and then b ₂ ← _ S _v (b ₂ ).
Similarly perform the conversion of the subblocks b ₃ , b ₄ , b ₅ , b ₆ and b ₇ . At the last step of each encryption round, the sub-blocks are rearranged in the reverse order, i.e. the b ₇ and b ₀ , b ₆ and b ₁ , b ₅ and b ₂ , b ₄ and b ₃ blocks are interchanged in pairs.

 The second round is performed similarly, except that instead of the first row of subkeys, the second row of subkeys is used. Then the third round of encryption is performed using the third row of subkeys, etc. In total, R rounds of encryption are performed, where R = 4. In software implementation, this example implementation of the proposed method provides an encryption speed of about 25 Mbps for the Pentium / 200 microprocessor. If necessary, a different number of rounds can be set, for example, R = 2,3,5,6.

 Example 1 is described by the following specific algorithm.

 Algorithm 1.

Input: 64-bit digital data input block, represented as a concatenation of 8-bit subblocks b ₀ | b ₁ | b ₂ | b ₃ | b ₄ | b ₅ | b ₆ | b ₇ , where the sign "|" denotes a concatenation operation.

 1. Set the number of rounds of encryption R = 4 and the counter of the number of rounds r = 1.

 2. Set the counter i = 1.

3. Generate the binary vector v: v ← _ b _i-1 mod 2 ⁵ .

4. Convert subblock b ₁ : b _i ← _ b _i ⊕k _ri , b _i ← _ S _v (b _i ), where the substitution operation S _v is performed using the substitution table with number v.

5. Generate the binary vector v: v ← _ v⊕ (b ₁ mod 2 ⁵ ).

 6. If i ≠ 7, then increment i ← _ i + 1 and go to step 4.

 7. If r ≠ R, then increment r ← _ r + 1. Otherwise STOP.

 8. Rearrange the subunits in the reverse order and go to step 3.

 Output: 64-bit ciphertext block.

 In this example, it can be seen that the number of the used lookup table depends on the blocks being converted and is not predetermined for the current conversion step, i.e. the substitution operation is not known in advance for all transformation steps. It is determined by a secret key and a block of converted data. Decryption is carried out similarly and is described by the following algorithm.

 Algorithm 2.

Input: 64-bit ciphertext input block b ₀ | b ₁ | b ₂ | b ₃ | b ₄ | b ₅ | b ₆ | b ₇ .
1. Set the number of rounds of encryption R = 4 and the counter of the number of rounds r = 1.

 2. Set the counter i = 1.

3. Generate the binary vector v: v ← _ b _i-1 mod 2 ⁵ .

4. Save the value of b ₁ in the variable g: g ← _ b _i . Convert subblock b ₁ : b _i ← _ S _31-v (b _i ), b _i ← _ b _i ⊕k _r′i , where r '= 5-r.

5. Generate the binary vector v: v ← _ v⊕ (g mod 2 ⁵ ).

 6. If i ≠ 7, then increment i ← _ i + 1 and go to step 4.

 7. If r ≠ R, then increment r ← _ r + 1. Otherwise STOP.

 8. Rearrange the subunits in the reverse order and go to step 3.

 Output: 64-bit block of source text.

 The above encryption and decryption algorithms can be easily modified to convert data blocks of a different size, for example 125 and 256 bits.

 Example 2

This example relates to the construction of a one-way function based on the claimed method of cryptographic conversion. As in example 1, it is assumed to use 32 lookup tables T ₀ , T ₁ , T ₂ , ..., T ₃₁ . Substitution tables are assumed to be known and private keys are not used. The one-way function is defined by algorithm 4. The sequence of operations for converting data subblocks for one round of transformation is shown in FIG. 2.

 Algorithm 3.

Input: A 64-bit input data block, represented as a concatenation of 8-bit subblocks b ₀ | b ₁ | b ₂ | ... | b ₇ .
1. Set the number of conversion rounds R = 8, the counter of the number of rounds r = 1 and the initial value of the binary vector v = 13.

 2. Set the counter i = 1.

3. Generate the binary vector v: v ← _ v⊕ (b _i-1 mod 2 ⁵ ).

b_i-1 ←_ S_v(b_i-1).
6. Если i ≠ 8, то прирастить i ←_ i+1 и перейти к п. 3.4. Convert subblock b _i-1 :

b _i-1 ← _ S _v (b _i-1 ).
6. If i ≠ 8, then increment i ← _ i + 1 and go to step 3.

7. Rearrange the subblocks b ₀ , b ₁ , ..., b ₇ , in the reverse order.

 7. If r ≠ R, then increment r ← _ r + 1 and go to step 2. Otherwise, STOP.

Output: 64-bit value of a one-way function specified by concatenation of converted subunits b ₀ | b ₁ | b ₂ | ... | b ₇ .
Similarly, a one-way function can be constructed for converting 128-bit data blocks, which can be used to hash data.

 Example 3

 This example is similar to example 1, and the only difference is that the 32 substitution tables used are secret, for example, they are formed depending on the secret key. This option is easily implemented when using a computer to encrypt data by creating lookup tables using a special program when entering a secret key into the encryption module. The formation of secret tables can be implemented, for example, by modifying the known (predefined) lookup tables by block encryption with the secret key of the elements of the bottom row of known tables (since the block encryption transformation is a lookup, the modified tables will also be lookup tables).

 Example 4

This example is also similar to example 1. The difference is that the digital data block is divided into 16-bit subunits and 32 lookup tables are used, corresponding to the value k = 16, i.e. they specify the substitution operation over 16 bits of the converted subunits. The amount of RAM required to accommodate one table is 2 ^k k bits = 128 KB. To accommodate 32 tables, 4 MB is required, which can be provided by modern computers of mass application. The following two options can be used for writing substitution tables to the computer main memory: (1) known tables are stored on magnetic information carriers and are copied to the main memory when the encryption module is started; (2) tables are generated by a special program that runs when the encryption module is started. In the second case, the formation of lookup tables can be carried out depending on the secret key, which allows the use of secret lookups over 16-bit subblocks for data encryption.

 The above examples show that the proposed method of cryptographic transformations of digital data blocks is technically feasible and allows us to solve the problem.

 The inventive method can be implemented, for example, on personal computers and provides the ability to create on its basis high-speed encryption software modules and replace expensive specialized encryption equipment for personal computers equipped with a high-speed encryption software system.

Claims (3)

 1. The method of cryptographic conversion of digital data blocks, which consists in dividing the data block into N ≥ 2 subblocks, sequentially converting the subblocks by performing at least one conversion operation on the subblock, which depends on the value of the input block, characterized in that as an operation that depends of the value of the input block, a substitution operation is performed that is performed on k binary digits of the subblock, where 8 ≤ k ≤ 16, and the substitution operations are specified by the substitution tables, the number of which is T ≥ 2 .  2. The method according to claim 1, characterized in that secret lookup tables are used as lookup tables.  3. The method according to claim 1, characterized in that they additionally form a binary vector V and select a lookup table for performing a substitution operation by the value of V, the binary vector at the current conversion step being formed depending on its value in the previous conversion step and on the value of one from subunits.

Images