The DES standard is designed to protect against unauthorized access to sensitive, but unclassified information in US government and commercial organizations. The algorithm underlying the standard spread quickly enough, and already in 1980 was approved by the US National Institute of Standards and Technology. From that moment on, DES became a standard not only in name but in fact. There are software and specialized microcomputers designed for encryption and decryption of information in data transmission networks.
DES is by far the most common algorithm used in commercial information security systems. Moreover, the implementation of the DES algorithm in such systems becomes a sign of good form.
The main advantages of the DES algorithm:
· Only one key 56 bits long is used;
· Having encrypted a message with one package, you can use any other to decrypt;
· The relative simplicity of the algorithm provides a high speed of information processing;
· Sufficiently high stability of the algorithm.
DES encrypts 64-bit blocks of data using a 56-bit key. Decryption in DES is the reverse operation of encryption and is performed by repeating encryption operations in reverse order (despite the seeming obviousness, this is not always done. Later we will consider ciphers in which encryption and decryption are performed using different algorithms).
The encryption process consists of an initial bit swap of a 64-bit block, sixteen encryption cycles, and finally a reverse bit swap (Fig. 1).
It should be noted right away that ALL tables given in this article are STANDARD, and therefore should be included in your implementation of the algorithm unchanged. All permutations and codes in the tables were selected by the developers in such a way as to make the decryption process as difficult as possible by guessing the key. The structure of the DES algorithm is shown in Fig. 2.
Figure: 2.
Let the next 8-byte block T be read from the file, which is transformed using the initial permutation IP matrix (Table 1) as follows: bit 58 of the T block becomes bit 1, bit 50 - bit 2, etc., which will result in : T (0) \u003d IP (T).
The resulting bit sequence T (0) is divided into two sequences of 32 bits each: L (0) - left or most significant bits, R (0) - right or least significant bits.
Table 1: IP Initial Permutation Matrix
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Then encryption is performed, consisting of 16 iterations. The result of the i-th iteration is described by the following formulas:
R (i) \u003d L (i-1) xor f (R (i-1), K (i)),
where xor is the EXCLUSIVE OR operation.
The function f is called the encryption function. Its arguments are the 32-bit sequence R (i-1), obtained at the (i-1) th iteration, and the 48-bit key K (i), which is the result of transforming the 64-bit key K. In detail, the encryption function and the algorithm for obtaining keys K (i) is described below.
At the 16th iteration, the sequences R (16) and L (16) (without permutation) are obtained, which are concatenated into a 64-bit sequence R (16) L (16).
Then, the bit positions of this sequence are permuted in accordance with the matrix IP -1 (Table 2).
Table 2: IP -1 reverse permutation matrix
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
The matrices IP -1 and IP are related as follows: the value of the 1st element of the IP -1 matrix is \u200b\u200b40, and the value of the 40th element of the IP matrix is \u200b\u200b1, the value of the 2nd element of the IP -1 matrix is \u200b\u200b8, and the value of the 8th the element of the IP matrix is \u200b\u200bequal to 2, etc.
The process of decrypting data is the inverse of the encryption process. All steps must be performed in reverse order. This means that the decrypted data is first rearranged in accordance with the IP-1 matrix, and then the same actions are performed on the R (16) L (16) bit sequence as in the encryption process, but in reverse order.
The iterative decryption process can be described by the following formulas:
R (i-1) \u003d L (i), i \u003d 1, 2, ..., 16;
L (i-1) \u003d R (i) xor f (L (i), K (i)), i \u003d 1, 2, ..., 16.
At the 16th iteration, the sequences L (0) and R (0) are obtained, which are concatenated into a 64-bit sequence L (0) R (0).
The bit positions of this sequence are then rearranged according to the IP matrix. The result of such a permutation is the original 64-bit sequence.
Now consider the encryption function f (R (i-1), K (i)). It is shown schematically in Fig. 3.
Figure: 3.
The following matrix functions are used to calculate the value of the function f:
E - expansion of a 32-bit sequence to 48-bit,
S1, S2, ..., S8 - converting a 6-bit block to a 4-bit one,
P - permutation of bits in a 32-bit sequence.
The expansion function E is defined in Table. 3. According to this table, the first 3 bits of E (R (i-1)) are bits 32, 1, and 2, and the last are 31, 32, and 1.
Table 3: Expansion function E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
The result of the function E (R (i-1)) is a 48-bit sequence, which is added modulo 2 (operation xor) with a 48-bit key K (i). The result is a 48-bit sequence, which is split into eight 6-bit blocks B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8). I.e:
E (R (i-1)) xor K (i) \u003d B (1) B (2)… B (8).
Functions S1, S2, ..., S8 are determined by table. 4.
Table 4
To table. 4. additional clarification required. Let the 6-bit block B (j) \u003d b1b2b3b4b5b6 enter the input of the matrix function Sj, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 is the column number. The result of Sj (B (j)) is a 4-bit element located at the intersection of the specified row and column.
For example, B (1) \u003d 011011. Then S1 (B (1)) is located at the intersection of row 1 and column 13. Column 13 of row 1 is set to 5. So S1 (011011) \u003d 0101.
Applying the selection operation to each of the 6-bit blocks B (1), B (2), ..., B (8), we obtain a 32-bit sequence S1 (B (1)) S2 (B (2)) S3 (B ( 3))… S8 (B (8)).
Finally, to get the result of the encryption function, the bits of this sequence must be swapped. For this, the permutation function P is used (Table 5). In the input sequence, the bits are swapped so that bit 16 becomes bit 1, bit 7 becomes bit 2, and so on.
Table 5: Transfer function P
In this way,
f (R (i-1), K (i)) \u003d P (S1 (B (1)),… S8 (B (8)))
To complete the description of the data encryption algorithm, it remains to give an algorithm for obtaining 48-bit keys K (i), i \u003d 1 ... 16. At each iteration, a new key value K (i) is used, which is calculated from the initial key K. K is a 64-bit block with eight parity bits located at positions 8,16,24,32,40,48,56, 64.
To remove the control bits and permute the rest, the function G of the initial key preparation is used (Table 6).
Table 6
Initial key preparation matrix G
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
The transformation result G (K) is split into two 28-bit blocks C (0) and D (0), and C (0) will consist of bits 57, 49, ..., 44, 36 of the key K, and D (0) will be consist of bits 63, 55, ..., 12, 4 of the key K. After determining C (0) and D (0), C (i) and D (i), i \u003d 1 ... 16, are recursively determined. To do this, apply a cyclic left shift by one or two bits, depending on the iteration number, as shown in table. 7.
Table 7. Shift table for key calculation
|
Iteration number |
Shift (bit) |
The resulting value is again "mixed" in accordance with the matrix H (Table 8).
Table 8: Key Post-Processing Matrix H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Key K (i) will consist of bits 14, 17, ..., 29, 32 of the sequence C (i) D (i). In this way:
K (i) \u003d H (C (i) D (i))
The block diagram of the key calculation algorithm is shown in Fig. 4.
Figure: 4.
Recovering the original text is carried out using this algorithm, but first you use the key K (15), then K (14), and so on. Now it should be clear to you why the author strongly recommends using the given matrices. If you start self-righteous, you must get a very secret cipher, but you yourself will not be able to reveal it later!
Algorithm DES
The main advantages of the DES algorithm:
· Only one key 56 bits long is used;
· Having encrypted a message with one package, you can use any other to decrypt;
· The relative simplicity of the algorithm provides a high speed of information processing;
· Sufficiently high stability of the algorithm.
DES encrypts 64-bit blocks of data using a 56-bit key. Decryption in DES is the reverse operation of encryption and is performed by repeating encryption operations in reverse order (despite the seeming obviousness, this is not always done. Later we will consider ciphers in which encryption and decryption are performed using different algorithms).
The encryption process consists of an initial bit swapping of a 64-bit block, sixteen encryption cycles, and finally, a reverse bit swap (Fig. 1).
It should be noted right away that ALL tables given in this article are STANDARD, and therefore should be included in your implementation of the algorithm unchanged. All permutations and codes in the tables were selected by the developers in such a way as to make the decryption process as difficult as possible by guessing the key. The structure of the DES algorithm is shown in Figure 2.
Fig. 2. DES encryption algorithm structure
Let the next 8-byte block T be read from the file, which is transformed using the IP initial permutation matrix (Table 1) as follows: bit 58 of the T block becomes bit 1, bit 50 becomes bit 2, etc., which will result in : T (0) \u003d IP (T).
The resulting bit sequence T (0) is divided into two sequences of 32 bits each: L (0) - left or most significant bits, R (0) - right or least significant bits.
Table 1: IP Initial Permutation Matrix
58 50 42 34 26 18 10 02
60 52 44 36 28 20 12 04
62 54 46 38 30 22 14 06
64 56 48 40 32 24 16 08
57 49 41 33 25 17 09 01
59 51 43 35 27 19 11 03
61 53 45 37 29 21 13 05
63 55 47 39 31 23 15 07
Then encryption is performed, consisting of 16 iterations. The result of the i-th iteration is described by the following formulas:
R (i) \u003d L (i-1) xor f (R (i-1), K (i)),
where xor is the EXCLUSIVE OR operation.
The function f is called the encryption function. Its arguments are the 32-bit sequence R (i-1) obtained at the (i-1) th iteration, and the 48-bit key K (i), which is the result of transforming the 64-bit key K. In detail, the encryption function and the algorithm for obtaining keys K (i) is described below.
At the 16th iteration, the sequences R (16) and L (16) (without permutation) are obtained, which are concatenated into a 64-bit sequence R (16) L (16).
Then the bit positions of this sequence are rearranged in accordance with the matrix IP -1 (Table 2).
Table 2: IP -1 reverse permutation matrix
40 08 48 16 56 24 64 32
39 07 47 15 55 23 63 31
38 06 46 14 54 22 62 30
37 05 45 13 53 21 61 29
36 04 44 12 52 20 60 28
35 03 43 11 51 19 59 27
34 02 42 10 50 18 58 26
33 01 41 09 49 17 57 25
The matrices IP -1 and IP are related as follows: the value of the 1st element of the IP -1 matrix is \u200b\u200b40, and the value of the 40th element of the IP matrix is \u200b\u200b1, the value of the 2nd element of the IP -1 matrix is \u200b\u200b8, and the value of the 8th the element of the IP matrix is \u200b\u200bequal to 2, etc.
The process of decrypting data is the inverse of the encryption process. All steps must be performed in reverse order. This means that the decrypted data is first rearranged in accordance with the IP-1 matrix, and then the same actions are performed on the R (16) L (16) bit sequence as in the encryption process, but in reverse order.
The iterative decryption process can be described by the following formulas:
R (i-1) \u003d L (i), i \u003d 1, 2, ..., 16;
L (i-1) \u003d R (i) xor f (L (i), K (i)), i \u003d 1, 2, ..., 16.
At the 16th iteration, the sequences L (0) and R (0) are obtained, which are concatenated into a 64-bit sequence L (0) R (0).
The bit positions of this sequence are then rearranged according to the IP matrix. The result of such a permutation is the original 64-bit sequence.
Now consider the encryption function f (R (i-1), K (i)). It is shown schematically in Fig. 3.
Fig. 3. Calculation of the function f (R (i-1), K (i))
The following matrix functions are used to calculate the value of the function f:
E - expansion of a 32-bit sequence to 48-bit,
S1, S2, ..., S8 - convert a 6-bit block to a 4-bit one,
P - permutation of bits in a 32-bit sequence.
The expansion function E is defined in Table 3. According to this table, the first 3 bits of E (R (i-1)) are bits 32, 1, and 2, and the last are 31, 32, and 1.
Table 3: Expansion function E
32 01 02 03 04 05
04 05 06 07 08 09
08 09 10 11 12 13
12 13 14 15 16 17
16 17 18 19 20 21
20 21 22 23 24 25
24 25 26 27 28 29
28 29 30 31 32 01
The result of the function E (R (i-1)) is a 48-bit sequence, which is added modulo 2 (operation xor) with a 48-bit key K (i). The result is a 48-bit sequence, which is split into eight 6-bit blocks B (1) B (2) B (3) B (4) B (5) B (6) B (7) B (8). I.e:
E (R (i-1)) xor K (i) \u003d B (1) B (2) ... B (8).
The functions S1, S2, ..., S8 are defined in Table 4.
Table 4
Table 4. further clarification is required. Let the 6-bit block B (j) \u003d b1b2b3b4b5b6 enter the input of the matrix function Sj, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 is the column number. The result of Sj (B (j)) is a 4-bit element located at the intersection of the specified row and column.
For example, B (1) \u003d 011011. Then S1 (B (1)) is located at the intersection of row 1 and column 13. Column 13 of row 1 is set to 5. So S1 (011011) \u003d 0101.
Applying the selection operation to each of the 6-bit blocks B (1), B (2), ..., B (8), we obtain a 32-bit sequence S1 (B (1)) S2 (B (2)) S3 ( B (3)) ... S8 (B (8)).
Finally, to get the result of the encryption function, the bits of this sequence must be swapped. For this, the permutation function P is used (Table 5). In the input sequence, the bits are swapped so that bit 16 becomes bit 1, bit 7 becomes bit 2, and so on.
Table 5: Transfer function P
In this way,
f (R (i-1), K (i)) \u003d P (S1 (B (1)), ... S8 (B (8)))
To complete the description of the data encryption algorithm, it remains to give an algorithm for obtaining 48-bit keys K (i), i \u003d 1 ... 16. At each iteration, a new key value K (i) is used, which is calculated from the initial key K. K is a 64-bit block with eight parity bits located at positions 8,16,24,32,40,48,56, 64.
To remove the control bits and permute the rest, the function G of the initial key preparation is used (Table 6).
Table 6
Initial key preparation matrix G
57 49 41 33 25 17 09
01 58 50 42 34 26 18
10 02 59 51 43 35 27
19 11 03 60 52 44 36
63 55 47 39 31 23 15
07 62 54 46 38 30 22
14 06 61 53 45 37 29
21 13 05 28 20 12 04
The result of the transformation G (K) is divided into two 28-bit blocks C (0) and D (0), and C (0) will consist of bits 57, 49, ..., 44, 36 of the key K, and D (0 ) will consist of bits 63, 55, ..., 12, 4 of the key K. After defining C (0) and D (0), C (i) and D (i), i \u003d 1 ... 16, are recursively defined. To do this, apply a cyclic left shift by one or two bits, depending on the iteration number, as shown in Table 7.
Table 7
Shift table for calculating the key
| Iteration number | Shift (bit) |
| 01 | 1 |
| 02 | 1 |
| 03 | 2 |
| 04 | 2 |
| 05 | 2 |
| 06 | 2 |
| 07 | 2 |
| 08 | 2 |
| 09 | 1 |
| 10 | 2 |
| 11 | 2 |
| 12 | 2 |
| 13 | 2 |
| 14 | 2 |
| 15 | 2 |
| 16 | 1 |
The resulting value is again "mixed" in accordance with the matrix H (Table 8).
Table 8: Key Post-Processing Matrix H
14 17 11 24 01 05
03 28 15 06 21 10
23 19 12 04 26 08
16 07 27 20 13 02
41 52 31 37 47 55
30 40 51 45 33 48
44 49 39 56 34 53
46 42 50 36 29 32
Key K (i) will consist of bits 14, 17, ..., 29, 32 of the sequence C (i) D (i). In this way:
K (i) \u003d H (C (i) D (i))
The block diagram of the key calculation algorithm is shown in Fig. 4.
Fig. 4. Block diagram of the algorithm for calculating the key K (i)
Restoration of the original text is carried out using this algorithm, but first you use the key
K (15), then K (14) and so on. Now it should be clear to you why the author strongly recommends using the given matrices. If you start self-righteous, you must get a very secret cipher, but you yourself will not be able to reveal it later!
DES operation modes
For the most complete satisfaction of all the requirements for commercial encryption systems, several modes of operation of the DES algorithm are implemented. The most widespread modes are:
· Electronic codebook (Electronic Codebook) - ECB;
· Chain of digital blocks (Cipher Block Chaining) - CBC;
· Digital feedback (Cipher Feedback) - CFB;
· External feedback (Output Feedback) - OFB.
In this mode, the source file M is split into 64-bit blocks (8 bytes each): M \u003d M (1) M (2) ... M (n). Each of these blocks is encrypted independently using the same encryption key (Figure 5). The main advantage of this algorithm is its ease of implementation. The disadvantage is the relatively weak resistance against skilled cryptanalysts.
More than 30 years have passed since the adoption of DES as the US encryption standard. DES is the encryption algorithm with the richest and most interesting history.
Algorithm creation history
One of the world's most famous cryptologists, Bruce Schneier, in his famous book "Applied Cryptography", described the problems of users of information security tools in the early 70s. XX century (of course, we are talking about users on the other side of the "iron curtain"):
P there was no generally accepted standard for data encryption, or just widely used algorithms for protecting information, so there was no question of compatibility between various software or hardware encryption tools;
Almost any encryption tool was a "black box" with rather obscure content: what encryption algorithm is used, how cryptographically strong it is, is it correctly implemented, is it correctly created, stored, used encryption keys, are there any undocumented features inserted by the developers in the tool, and etc. - all this very important information was not available for the vast majority of buyers of cryptographic funds.
This problem is attended by the National Bureau of Standards (NBS) USA. As a result, in 1973 the first open competition for an encryption standard was announced. NBS was ready to investigate candidate algorithms meeting the following criteria to select a standard:
The algorithm must be cryptographically strong;
The algorithm must be fast;
The structure of the algorithm should be clear and clear;
The strength of encryption should depend only on the key; the algorithm itself should not be secret;
The algorithm should be easily applicable for a variety of purposes;
The algorithm should be easily implemented in hardware on the existing element base.
It was assumed that interested organizations or specialists would send to NBS detailed specifications of algorithms sufficient for their implementation, that is, without any "white spots". The algorithm was also supposed to be certified by NBS for general use, all patent and export restrictions would be removed from it, as a result of which such a standard would have to solve all the compatibility problems of encryption tools. In addition, NBS took over the functions of certification of encryption tools - that is, the "black boxes" should have become a thing of the past.
In fact, there was only one candidate algorithm: it was the Lucifer encryption algorithm developed by CMM. (see section 3.31). For two years, the algorithm was refined:
First, NBS, together with the US National Security Agency (NSA, NSA - National Security Agency), carried out a thorough analysis of the algorithm, which resulted in its quite significant reworking;
Secondly, comments and criticisms from all interested organizations and individuals were accepted for consideration.
As a result of joint activities of IBM, NBS and NSA in January 1977 DES was published as a US standard (the latest version of this standard is in the document) for data encryption algorithm (except for high-security information). The DES algorithm was patented by YM, but NBS received, in fact, a free and unlimited license to use this algorithm. An alternative, but less commonly used name for the algorithm is DEA (Data Encryption Algorithm).
Main characteristics and structure of the algorithm
DES encrypts information in blocks of 64 bits using a 64-bit encryption key that uses only 56 bits (the key expansion procedure is described in detail below).
Information encryption is performed as follows (Fig. 3.56):
1. Above a 64-bit data block, an initial permutation is performed according to table. 3.16.
Table 3.16
The table is interpreted as follows: the value of the input bit 58 (hereinafter, all bits are numbered from left to right, starting from 1) is placed in the output bit 1, the value of the 50th bit - in bit 2, and so on.
2. The result of the previous operation is divided into 2 sub-blocks of 32 bits each (by
fig. 3.56 marked A 0 and B 0), over which 16 rounds are made
the following transformations:
As mentioned above, DES uses only 56 bits of the 64-bit encryption key. Every 8th bit is discarded and is not used in any way in the algorithm, and the use of the remaining bits of the encryption key in the implementations of the DES algorithm is not limited by the standard. The procedure for extracting 56 significant bits of a 64-bit key in Fig. 3.59 is designated as E. In addition to extraction, this procedure also performs a key bit permutation according to Table. 3.19 and 3.20.
Table 3.19
Table 3.20
As a result of the permutation, two 28-bit values \u200b\u200bC and D are formed. Table 3.19 defines the sample of key bits for C, table. 3.20 - for D.
Then 16 rounds of transformations are performed, each of which gives one of the keys of the rounds K t. In each round of the key expansion procedure, the following actions are performed:
1. Current values \u200b\u200bof C and D are cyclically shifted left by a variable number of bits P. For rounds 1, 2, 9 and 16 P \u003d 1, the rest of the rounds are cycled by 2 bits.
2.C and D are concatenated into a 56-bit value, to which the contraction permutation CP is applied, which results in a 48-bit round key K (. The contraction permutation is performed according to Table 3.21.
Table 3.21
When decrypting data, you can use the same key expansion procedure, but apply the round keys in reverse order. There is another option: in each round of the key expansion procedure, instead of cyclic left shift, perform a cyclic right shift by n bits, where rc '\u003d 0 for the first round, and' \u003d 1 for rounds 2, 9, 16 and n \u003d 2 for the rest of the rounds ... Such a key expansion procedure will immediately give the round keys necessary for decryption.
It should be said that the ability to perform key expansion "on the fly" (especially if this possibility exists both during encryption and decryption) is considered an advantage of encryption algorithms, since in this case the key expansion can be performed in parallel with encryption and not waste memory on storing the keys of others rounds other than the current one.
DES (Data Encryption Standart) - Symmetric encryption algorithm, in which one key is used for both encryption and decryption of data. DES was developed by IBM and approved by the US government in 1977 as an official standard (FTPS 46-3). DES has 64-bit blocks and a 16-round Feistel network structure; it uses a 56-bit key for encryption. The algorithm uses a combination of non-linear (S-boxes) and linear (permutations E, IP, IP-1) transformations. Several modes are recommended for DES:Block cipher
The input data for the block cipher are an n-bit block and a k-bit key. At the output, after applying the encryption transformation, an n-bit encrypted block is obtained, and insignificant differences in the input data usually lead to a significant change in the result. Block ciphers are implemented by repeatedly applying some basic transformations to blocks of source text.Basic conversions:
Feistel Network Transforms
This is a transformation over vectors (blocks) representing the left and right halves of the shift register. DES uses forward Feistel transform in encryption (see Figure 1) and reverse Feistel transform to decryption (see Figure 2).
DES encryption scheme
The original text is a block of 64 bits. The cipher text is a block of 64 bits.
The encryption process consists of an initial permutation, 16 encryption cycles, and a final permutation.
Consider a detailed diagram of the DES algorithm:
L i R i \u003d 1,2 \\ ldots. Left and right halves of a 64-bit block L i R i
k i - 48 bit keys
f - encryption function
IP - initial permutation
IP -1 is the final permutation. 
According to the table, the first 3 bits of the resulting IP (T) block after the initial permutation of IP are bits 58, 50, 42 of the input block T, and its last 3 bits are bits 23, 15, 7 of the input block. Further, the 64-bit IP (T) block participates in 16-cycles of the Feistel transform.
16 cycles of Feistel transform:
Split IP (T) into two parts L 0, R 0, where L 0, R 0 - respectively 32 most significant bits and 32 least significant bits of the block T0 IP (T) \u003d L 0 R 0
Let T i -1 \u003d L i -1 R i -1 result of (i-1) iteration, then the result of the i-th iteration T i \u003d L i R i is determined:
L i \u003d R i - 1 The left half of L i is equal to the right half of the previous vector L i - 1 R i - 1. And the right half of R i is the bit addition of L i - 1 and f (R i - 1, k i) modulo 2.
In the 16-cycle Feistel transform, the function f plays the role of encryption. Let's consider the function f in detail.
The arguments to f are 32 bit vector R i - 1, 48 bit key k i, which are the result of transforming the 56 bit original cipher key k.
To calculate the function f, the expansion function E, the transformation S, consisting of 8 transformations of S-boxes, and the permutation P. are used.
Function E expands 32 bit vector R i - 1 to 48 bit vector E (R i - 1) by duplicating some of the bits from R i - 1, while the order of bits of vector E (R i - 1) is shown in Table 2. 
The first three bits of vector E (R i - 1) are bits 32, 1, 2 of vector R i -1. Table 2 shows that bits 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 are duplicated. The last 3 bits of vector E (Ri - 1) are bits 31, 32, 1 of vector R i - 1. The block E (R i -1) obtained after the permutation is added modulo 2 with the keys k i and then represented as eight consecutive blocks B 1, B 2, ... B 8.
E (R i - 1) \u003d B 1 B 2 ... B 8
Each B j is a 6-bit block. Further, each of the blocks B j is transformed into a 4-bit block B "j using transformations S j. The transformations S j are determined by Table 3. Suppose that B 3 \u003d 101111 and we want to find B" 3. The first and last bits of B 3 are binary notation of the number a, 0 The value of the function f (R i - 1, ki) (32 bits) is obtained by permutation P applied to 32 bit block B "1 B" 2 ... B "8. P is given by Table 4. 
f (R i - 1, k i) \u003d P (B "1 B" 2 ... B "8)
According to table 4, the first four bits of the resulting vector after the action of the function f are bits 16, 7, 20, 21 of vector B "1 B" 2 ... B "8
Generating keys k i.
Keys k i are obtained from the initial key k (56 bits \u003d 7 bytes or 7 characters in ASCII) in this way. Eight bits found in positions 8, 16, 24, 32, 40, 48, 56, 64 are added to the key k so that each byte contains an odd number of ones. This is used to detect errors in key exchange and storage. Then permute the extended key (except for the added bits 8, 16, 24, 32, 40, 48, 56, 64). This permutation is defined as in Table 5. 
This permutation is defined by two blocks C 0 and D 0 of 28 bits each. The first 3 bits of C 0 are bits 57, 49, 41 of the extended key. And the first three bits of D 0 are bits 63, 55, 47 of the extended key. C i, D i i \u003d 1,2,3 ... are obtained from C i - 1, D i - 1 by one or two left cyclic shifts according to table 6. 
Key k i, i \u003d 1, ... 16 consists of 48 bits selected from the bits of the vector C i D i (56 bits) according to Table 7. The first and second bits k i are bits 14, 17 of the vector C i D i 
The final permutation IP - 1 acts on T 16 and is used to restore position. It is the reverse of IP permutation. The final permutation is determined by Table 8. 
DES usage modes DES can be used in four modes.
Which ANSI calls the data encryption algorithm DEA (Data Encryption Algorithm), and ISO - DEA-1, has become a world standard in 20 years. Over the years of its existence, it has withstood the onslaught of various attacks and, under certain restrictions, is still considered cryptographic resistant.
DES is a block cipher that encrypts data in 64-bit blocks. At one end of the algorithm, a 64-bit block of plaintext is entered, and at the other end, a 64-bit block of ciphertext comes out. DES is a symmetric algorithm: the same algorithm and key are used for encryption and decryption (except for minor differences in key usage). The key length is 56 bits. (The key is usually represented as a 64-bit number, but every eighth bit is used for parity and is ignored. The parity bits are the least significant bits of the key bytes.) The key, which can be any 56-bit number, can be changed at any time.
Crypto resistance is completely determined by the key. The fundamental building block of DES is the combination of permutations and permutations. DES consists of 16 cycles.
General view of the conversion cycle:
If L i and R i are the left and right halves obtained as a result of the i -th iteration, K i is a 48-bit key for cycle i, and f is a function that performs all substitutions, permutations and XOR with a key, then one conversion cycle can be represented as:
Taking into account the substitution F i (*) and the permutation T (*), the transformation cycle can be represented as it is done in Fig.
It is seen that each DES cycle is a compositional cipher with two successive transformations - the substitution F i (*) and the permutation T (*) (except for the last, sixteenth cycle, where the permutation is omitted).
Substitution:
(L i, R i) \u003d (R i −1, L i −1) ⊕ f (R i −1, K)
is an involution, since
F i (F i (L i −1, R i −1)) \u003d F i (R i −1, L i −1) ⊕ (f (R i −1, K i))) \u003d (R i - 1, L i −1 ⊕ (f (R i −1, K i)) ⊕ (f (R i −1, K i))) \u003d (L i −1, R i −1)
And the substitution
T (L i ′, R i ′) \u003d (R i ′, L i ′),
is also an involution, since
T (T (L i ′, R i ′)) \u003d T (R i ′, L i ′) \u003d L i ′, R i ′
If we denote the initial and final permutations as (IP) and (IP) - 1, then the direct DES transformation (encryption) implements the function:
DES \u003d (IP) F 1 TF 2 T… F 15 TF 16 (IP) - 1,
and the reverse DES transform (decryption) implements the function:
DES - 1 \u003d (IP) −1 F 16 TF 15 T… F 2 TF 1 (IP).
Thus, DES is a Feistel cipher and is designed to fulfill a useful property: the same algorithm is used for encryption and decryption. The only difference is that the keys must be used in reverse order.
That is, if the keys K 1, K 2, K 3, ..., K 16 were used for encryption, then the decryption keys will be K 16, K 15, K 14, ..., K 1. The algorithm uses only standard 64-bit number arithmetic and logical operations, so it can be easily implemented in hardware.
DES operates on a 64-bit plaintext block. After the initial permutation, the block is split into right and left halves of 32 bits each. Then 16 transforms are performed (function f), in which the data is combined with the key. After the sixteenth cycle, the right and left halves are combined, and the algorithm ends with a final permutation (inverse to the original). On each cycle (see Fig.), The key bits are shifted, and then 48 bits are selected from the 56 key bits. The right half of the data is expanded to 48 bits using a spreading permutation, XORed with 48 bits of the shifted and permuted key, traverses 8 S-boxes to form 32 new bits, and is rearranged again. These four operations are performed by function f.
Then the result of the function f is concatenated with the left half using another XOR. As a result of these actions, a new right half appears, and the old right half becomes a new left half. These steps are repeated 16 times, forming 16 DES cycles.
Russian standard - GOST 28147-89
GOST 28147-89 is a block cipher with a 256-bit key and 32 conversion cycles, operating in 64-bit blocks. The cryptoalgorithm also uses an additional key, which is discussed below. For encryption, the plaintext is first split into the left and right halves of the L and R. On the i -th cycle, subkey K i is used:
L i \u003d R i −1,
R i \u003d L i −1 ⊕ (f (R i −1, K i)).
Function f is implemented as follows. First, the right half and the i -th subkey are added modulo 2 32. The result is split into eight 4-bit subsequences, each of which goes to the input of its own S-box. GOST uses eight different S-boxes, the first 4 bits go into the first S-box, the second 4 bits go into the second S-box, etc. Each S-box is a permutation of numbers from 0 to 15. For example, an S-box may look like: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. In this case, if the input of the S-box is 0, then the output is 7. If the input is 1, the output is 10, etc. All eight S-boxes are different, they are in fact additional key material. The outputs of all eight S-boxes are concatenated into a 32-bit word, then the entire word is cyclically shifted left 11 bits. Finally, the result is XORed with the left half to create a new right half, and the right half becomes the new left half. To generate subkeys, the original 256-bit key is split into eight 32-bit blocks: k 1, k 2, ..., k 8. Each cycle uses its own subkey. Decryption is performed in the same way as encryption, but the order of the k i subkeys is inverted. The standard does not define how S-boxes are generated.
Key differences between DES and GOST
The main differences between DES and GOST are as follows:
- DES uses a complex procedure to generate subkeys from keys. In GOST, this procedure is very simple;
- dES has a 56-bit key, and GOST has a 256-bit key. If we add secret permutations of S-boxes, then the total amount of GOST secret information will be approximately 610 bits;
- dES S-boxes have 6-bit inputs and 4-bit outputs, and GOST S-boxes have 4-bit inputs and outputs. Eight S-boxes are used in both algorithms, but the GOST S-box is equal to a quarter of the DES S-box;
- dES uses an irregular permutation called a P-box, and GOST uses an 11-bit circular left shift;
- dES has 16 cycles, and GOST - 32.
A force attack on GOST is absolutely hopeless. GOST uses a 256-bit key, and if the secret S-boxes are taken into account, the key length will be even greater. GOST appears to be more robust to differential and linear cryptanalysis than DES. Although random GOST S-boxes, with some choice, do not guarantee high cryptographic strength compared to fixed DES S-boxes, their secrecy increases the GOST resistance to differential and linear cryptanalysis. In addition, the effectiveness of these cryptanalytic methods depends on the number of transformation cycles - the more cycles, the more difficult cryptanalysis is. GOST uses twice as many cycles as DES, which may lead to inconsistencies in differential and linear cryptanalysis.
GOST does not use the extension permutation in DES. Removing this permutation from DES weakens it by reducing the avalanche effect; it is reasonable to assume that the absence of such an operation in GOST negatively affects its cryptographic strength. From the point of view of cryptographic strength, the arithmetic addition operation used in GOST is no worse than the XOR operation in DES.
The main difference seems to be the use of cyclic shift in GOST instead of permutation. The DES permutation increases the avalanche effect. In GOST, a change in one input bit affects one S-block of one conversion cycle, which then affects two S-blocks of the next cycle, then three blocks of the next cycle, etc. It takes eight cycles before changing one input bit affects every bit of the result; DES only needs five cycles. However, GOST consists of 32 cycles, and DES only 16.
The GOST developers tried to achieve a balance between cryptographic strength and efficiency. Taking Feistel's construction as a basis, they developed a cryptoalgorithm that is better suited for software implementation than DES. To increase the cryptographic strength, an extra-long key was introduced and the number of cycles was doubled. However, the question of whether the efforts of the developers were crowned with the creation of a more cryptographic algorithm than DES remains open.
Vorobieva E., Lukyanova A.
