2.3.2. Block Symmetric Encryption Algorithms

The Feistel scheme is used in DES, GOST 28147-89, FEAL, Blowfish, LOKI, CAST, and other cryptographic algorithms. Consider the practical implementation of a block cipher built on the Feystel network principle, using the example of TEA (Tiny Encrypton Algorithm) algorithm.

The TEA algorithm (Fig.2.6) was developed at the University of Cambridge and is a 64-round network of Festel, the block size is 64 bits, the size of the encryption key is 128 bits.

Fig.2.6. TEA algorithm operation scheme

Encryption algorithms that are more recognized among cryptographers use nonlinear operations in their conversion functions. For example, the DES (Data Encryption Standard) encryption algorithm, which until recently was a global encryption standard, uses table substitution operations in its generator function, which significantly complicates the procedure of linear cryptanalysis of this cipher. The scheme of the DES algorithm round is presented in fig. 2.7.
The advantage of the TEA algorithm is the ease of implementation, however, the absence of non-linear operations in the generator function has to be compensated by a large number of rounds. KEY0, KEY1, KEY2, KEY3 in Figure 2.6 are the round keys, which are obtained by simply dividing the encryption key into 4 parts. It should also be noted that TEA is an asymmetric algorithm, since the branches are mixed by ordinary arithmetic addition, therefore the decryption operation requires minor changes.

Each round of conversion involves a permutation of the right side of the block, with the 32-bit number being fed to the expander input, and 48-bit from it (some bits of the input number are copied to the output twice). After adding a key material to the key material, a tabular substitution is performed, which results in replacing the 48-bit input with a 32-bit output for 8 substitution tables (each S-substitution table replaces a 6-bit input with a 4-bit output). The output of the S-block enters the permutation block, where the bits are rearranged according to the laws determined by the special P-table. The round ends with the traditional Feystelle nets mixing the branches together. Due to the use of nonlinear transformation operations, it was possible to reduce the number of rounds to 16 with a key size of 56 bits.

Since the publication of the DES algorithm in 1977, it has been subjected to serious cryptanalysis. So, in particular, 4 weak DES keys were found that half of the possible 2 64 input blocks encode into themselves. A number of specific attacks on DES were also proposed, which in the 1980s allowed using a computer with a specialized architecture or distributed computing to conduct a successful attack on an algorithm for several hours. For the modern technological level, the time of cracking the DES cipher is several tens of minutes. In this regard, to ensure higher cryptographic strength, it is recommended to use triple DES encryption on three or two different keys. Such schemes are called EDE (encrypt-decrypt-encrypt) encryption. With two encryption keys, the plaintext block is first encrypted with the K 1 key, then decrypted with the K 2 key, and then encrypted again with the K 1 key . The size of the key space (the total number of possible encryption keys) in this case increases to 2 112 (for an ordinary DES - 2 56 ). When using three encryption keys, the plaintext block is first encrypted with the K 1 key, then decrypted with the K 2 key, and then encrypted with the K 3 key, which ensures the size of the key space is 2,168 .

Due to the insufficient length of the encryption key, as well as the orientation of the DES cipher to the hardware implementation (due to the large number of permutations used), the American National Institute of Standards in 1997 announced a competition for AES (Advanced Encryption Standard) cryptographic standard. In 2000, the Rijndael algorithm developed by Belgian cryptographers was announced the winner. Its distinguishing feature is that it is not built according to the Feystel network principle, but uses the unconventional structure of the KALST network.

The Rijndael algorithm represents a data block in the form of a two-dimensional byte array of 4x4, 4x6 or 4x8 (it is allowed to use several fixed sizes of the encrypted information block). All operations are performed with individual bytes of the array, as well as with independent columns and rows.

The Rijndael algorithm performs four transformations: BS (ByteSub) - tabular replacement of each byte of the array, SR (ShiftRow) - shift of the rows of the array. In this operation, the first line remains unchanged, while the remaining ones are cycled byte-by-byte by shifting left by a fixed number of bytes, depending on the size of the array. For example, for an array of 4X4, rows 2, 3, and 4 are shifted by 1, 2, and 3 bytes, respectively. Next, MC (MixColumn) is performed - an operation on independent columns of an array, when each column is multiplied by a fixed rule by a fixed matrix. And finally, AK (AddRoundKey) - adding a key. Each bit of the array is modulo 2 modulated with the corresponding bit of the round key, which, in turn, is calculated in a certain way from the encryption key. The number of encryption rounds in the Rijndael algorithm is variable (10, 12, or 14 rounds) and depends on the block size and encryption key (there are also several fixed sizes for the key).

The advantages of the Rijndael cipher is that it provides high encryption speed on all platforms: both in software and in hardware. It is distinguished by incomparably better paralleling of computations compared to other algorithms submitted for the AES competition. In addition, the requirements for resources for its work are minimal, which is important when using it in devices with limited computing capabilities.

The Russian standard block encryption is the GOST 28147-89 algorithm, built on the Feystel network structure. Its feature should recognize a large key size (256 bits), unpublished lookup tables, a large number of rounds (32 rounds).