The most common and best known algorithm symmetric encryption is an DES (Data Encryption Standard). The algorithm was developed in 1977, and in 1980 NIST (National Institute of Standards and Technology, USA) was adopted as a standard.
DES is classical network Feishtel with two branches. The data is encrypted in 64-bit blocks using a 56-bit key. The algorithm converts a 64-bit input to a 64-bit output in several rounds. The key length is 56 bits. The encryption process consists of four steps. The first step is to perform an initial permutation (IP) of the 64-bit plaintext (whitening), during which the bits are reordered according to standard table. The next stage consists of 16 rounds of the same function, which uses the shift and substitution operations. At the third stage, the left and right halves of the output of the last (16th) iteration are swapped. Finally, at the fourth stage, the IP-1 permutation of the result obtained at the third stage is performed. The IP-1 permutation is the inverse of the initial permutation.
Fig.4. DES algorithm
The figure shows a method that uses a 56-bit key. Initially, the key is fed to the input of the permutation function. Then, for each of the 16 rounds, the subkey K i is the combination of a left cyclic shift and a permutation. The permutation function is the same for each round, but the subkeys K i for each round are different due to repeated shifting of the key bits.
The initial permutation and its inverse are determined by a standard table. If M is arbitrary 64 bits, then X = IP(M) - permuted 64 bits. If we apply the inverse permutation function Y = IP-1 (X) = IP-1 (IP(M)), we get the original bit sequence.
Description of round des
Consider the sequence of transformations used in each round.
Fig.5. Illustration of a round of the DES algorithm
A 64-bit input block goes through 16 rounds, while at each iteration an intermediate 64-bit value is obtained. The left and right parts of each intermediate value are treated as separate 32-bit values, denoted L and R. Each iteration can be described as follows:
R i = L i -1 F(R i -1 , K i)
Thus, the output of the left half of L i is equal to the input of the right half of R i-1 . The output of the right half of R i is the result of XORing L i-1 and a function F depending on R i-1 and K i .
Let's consider the function F in more detail. R i , which is fed to the input of the function F, has a length of 32 bits. First, R i is expanded to 48 bits using a table that defines a permutation plus an expansion of 16 bits. The expansion goes like this. The 32 bits are split into groups of 4 bits and then expanded to 6 bits by appending the extreme bits from two adjacent groups. For example, if part of the input message
Efgh ijkl mnop . . .
then the result of the expansion is the message
Defghi hijklm lmnopq . . .
The resulting 48-bit value is then XORed with the 48-bit subkey K i . The resulting 48-bit value is then fed into the substitution function, resulting in a 32-bit value.
The substitution consists of eight S-boxes, each of which receives 6 bits as input and produces 4 bits as output. These transformations are defined by special tables. The first and last bits of the S-box input value determine the row number in the table, the middle 4 bits determine the column number. The intersection of a row and a column defines a 4-bit output. For example, if the input is 011011, then the row number is 01 (row 1) and the column number is 1101 (column 13). The value in row 1 and column 13 is 5, i.e. the output is 0101.
Next, the resulting 32-bit value is processed using a permutation P, the purpose of which is to reorder the bits as much as possible so that in the next round of encryption, with a high probability, each bit is processed by a different S-box.
The key for a single round K i consists of 48 bits. The keys K i are obtained by the following algorithm. The 56-bit key used as input to the algorithm is first permuted according to the Permuted Choice 1 (PC-1) table. The resulting 56-bit key is divided into two 28-bit parts, denoted as C0 and D0, respectively. On each round, C i and D i are independently rotated to the left by 1 or 2 bits, depending on the round number. The resulting values are the input of the next round. They are also an input to Permuted Choice 2 (PC-2), which produces a 48-bit output value that is the input of the function F(R i-1 , K i).
The decryption process is similar to the encryption process. The algorithm uses ciphertext as input, but the keys K i are used in reverse order. K 16 is used on the first round, K 1 is used on the last round. Let the output of the i-th encryption round be L i ||R i . Then the corresponding input of the (16-i)th round of decryption will be R i ||L i .
After the last round of the decryption process, the two halves of the output are swapped so that the input of the final permutation IP-1 is R 16 ||L 16 . The output of this stage is plain text.
- tutorial
Hey %username%!
Many people know that the default standard in the field of symmetric encryption long time was considered DES algorithm. The first successful attack on this indestructible algorithm was published in 1993, 16 years after it was adopted as a standard. The method, which the author called linear cryptanalysis, in the presence of 2 47 pairs of plain/ciphertexts, allows to open the secret key of the DES cipher in 2 43 operations.
Under the cut, I will try to summarize the main points of this attack.
Linear cryptanalysis
Linear cryptanalysis is a special kind of attack on symmetrical ciphers, aimed at recovering an unknown encryption key, from known open messages and their corresponding ciphertexts.AT general case attack based on linear cryptanalysis is reduced to the following conditions. The attacker has big amount plaintext/ciphertext pairs obtained using the same encryption key K. The goal of the attacker is to recover part or all of the key K.
First of all, the attacker examines the cipher and finds the so-called. statistical analog, i.e. an equation of the following form, which holds with probability P ≠ 1/2 for an arbitrary public/private text pair and a fixed key:
P I1 ⊕ P I2 ⊕… ⊕ P Ia ⊕ C I1 ⊕ C I2 ⊕… ⊕ C Ib = K I1 ⊕ K I2 ⊕… ⊕ K Ic (1)
,
where P n , C n , K n are the n-th bits of the text, ciphertext and key.
After such an equation is found, the attacker can recover 1 bit of information about the key using the following algorithm
Algorithm 1
Let T be the number of texts for which the left side of equation (1) is 0, then
If T>N/2, where N is the number of known plaintexts.
Assume that K I1 ⊕ K I2 ⊕… ⊕ K Ic = 0 (when P>1/2) or 1 (when P<1/2).
Otherwise
Assume that K I1 ⊕ K I2 ⊕… ⊕ K Ic = 1 (when P>1/2) or 0 (when P<1/2).
Obviously, the success of the algorithm directly depends on the value of |P-1/2| and on the number of available plaintext/privatetext pairs N. The more the probability P of equality (1) differs from 1/2, the smaller the number of plaintexts N needed for an attack.
There are two problems that need to be solved for the successful implementation of the attack:
- How to find an effective equation of the form (1).
- How to get more than one bit of information about the key using such an equation.
Description of DES
But first, let's briefly describe how the algorithm works. Enough has been said about DES. A full description of the cipher can be found on Wikipedia. However, to further explain the attack, we need a number of definitions that are best introduced beforehand.So, DES is a block cipher based on the Feistel network. The cipher has a block size of 64 bits and a key size of 56 bits. Consider the encryption scheme of the DES algorithm. 
As can be seen from the figure, the following operations are performed on the text during encryption:
- Initial bit swap. At this stage, the bits of the input block are shuffled in a certain order.
- After that, the shuffled bits are split into two halves, which are fed to the input of the Feistel function. For standard DES, the Feistel network includes 16 rounds, but there are other variants of the algorithm.
- The two blocks obtained in the last round of transformation are combined and another permutation is performed on the resulting block.
On each round of the Feistel network, the least significant 32 bits of the message are passed through the function f: 
Consider the operations performed at this stage:
- The input block is passed through an extension function E, which converts the 32-bit block into a 48-bit block.
- The resulting block is added to the round key K i .
- The result of the previous step is split into 8 blocks of 6 bits each.
- Each of the resulting blocks B i is passed through a substitution function S-Box i , which replaces a 6-bit sequence with a 4-bit block.
- The resulting 32-bit block is passed through the permutation P and returned as the result of the function f.
Of greatest interest, from the point of view of cryptanalysis of the cipher, for us are S blocks, designed to hide the connection between the input and output data of the function f. To successfully attack DES, we first construct statistical counterparts for each of the S-boxes, and then extend them to the entire cipher.
Analysis of S blocks
Each S-box takes a 6-bit sequence as input, and a fixed 4-bit value is returned for each such sequence. Those. There are a total of 64 input and output options. Our task is to show the relationship between the input and output data of S blocks. For example, for the third S-box of the DES cipher, the 3rd bit of the input sequence is equal to the 3rd bit of the output sequence in 38 cases out of 64. Therefore, we found the following statistical analogue for the third S-box:S 3 (x) = x, which is fulfilled with probability P=38/64.
Both sides of the equation represent 1 bit of information. Therefore, if the left and right parts were independent of each other, the equation would have to be fulfilled with a probability equal to 1/2. Thus, we have just demonstrated the relationship between the inputs and outputs of the 3rd S-box of the DES algorithm.
Consider how you can find a statistical analogue of the S-box in the general case.
For an S-box S a , 1 ≤ α ≤ 63 and 1 ≤ β ≤ 15, the value NS a (α, β) describes how many times out of 64 possible XORs of the input bits of S a overlaid on the bits α are equal to the XOR of the output bits overlaid on the bits β, i.e.:
where symbol is a logical AND.
The values of α and β for which NS a (α, β) differs most from 32 describe the most efficient statistical analog of the S-box S a .
The most efficient analog was found in the 5th S-box of the DES cipher for α = 16 and β = 15 NS 5 (16, 15)=12. This means that the following equation is true: Z=Y ⊕ Y ⊕ Y ⊕ Y, where Z is the S-box input sequence and Y is the output sequence.
Or taking into account the fact that in the DES algorithm, before entering the S-box, the data are added modulo 2 with a round key, i.e. Z = X ⊕ K we get
X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, where X and Y are the input and output data of the function f without permutations.
The resulting equation is executed on all rounds of the DES algorithm with the same probability P=12/64.
The following table lists the effective, i.e. having the largest deviation from P=1/2, statistical analogues for each s-block of the DES algorithm. 
Building Statistical Analogs for Multiple DES Rounds
Let us now show how one can combine the statistical analogues of several rounds of DES and, as a result, obtain a statistical analogue for the entire cipher.To do this, consider a three-round version of the algorithm:
Let's apply the efficient statistical analogue of the 5th s-box to calculate certain bits of the value X(2).
We know that with a probability of 12/64, the f-function satisfies the equality X ⊕ Y ⊕ Y ⊕ Y ⊕ Y = K, where X is the second input bit of the 5th S-box, it is essentially the 26th bit of the sequence obtained after the expansion of the input bits. Analyzing the extension function, it can be established that the 17th bit of the X(1) sequence turns out to be in place of bit 26.
Similarly, Y,…, Y are essentially the 17th, 18th, 19th, and 20th bits of the sequence obtained before the P permutation. By examining the P permutation, we find that the Y,…, Y bits are actually bits Y(1), Y(1), Y(1), Y(1).
The key bit K involved in the equations is the 26th subkey bit of the first round K1 and then the statistical counterpart takes the following form:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Consequently, X(1) ⊕ K1 = Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1)(2) with probability P=12/64.
Knowing 3, 8, 14, 25 bits of the Y(1) sequence, you can find 3, 8, 14, 25 bits of the X(2) sequence:
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y(1) or taking into account equation (2)
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 (3) with a probability of 12/64.
Let's find a similar expression using the last round. This time we have the equation
X(3) ⊕ K3 = Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3).
Because
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
we get that
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3(4)
with a probability of 12/64.
Equating the right parts of equations (3) and (4) we obtain
СL ⊕ СL ⊕ СL ⊕ СL ⊕ X(3) ⊕ K3 = PL ⊕ PL ⊕ PL ⊕ PL ⊕ X(1) ⊕ K1 with probability (12/64) 2 +(1-12/64) 2 .
Taking into account the fact that X(1) = PR and X(3) = CR, we obtain a statistical analogue
СL ⊕ CR ⊕ PL ⊕ PR = K1 ⊕ K3 (5)
,
which is performed with probability (12/64) 2 +(1-12/64) 2 =0.7.
The statistical analog described above can be represented graphically as follows (bits in the figure are numbered from right to left and starting from zero): 
All bits on the left side of the equation are known to the attacker, so he can apply Algorithm 1 and find out the value of K1 ⊕ K3. Let us show how, using this statistical analog, it is possible to open not 1, but 12 bits of the encryption key K.
Attack on DES with known plaintext
Here is a way by which you can expand the attack and immediately get 6 bits of the subkey of the first round.When compiling equation (5), we took into account the fact that we do not know the value of F1(PR, K1). Therefore, we used its statistical analog K1 ⊕ PR.
Instead of the expression K1 ⊕ PR, we return the value F1(PR, K1) and obtain the following equation:
CL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , which will be executed with a probability of 12/64. The probability has changed since we left only the statistical analogue from the third round, all other values are fixed.
We have already determined above that the value of F1(PR, K1) is influenced by the input bits of the 5th S-box, namely the bits of the key K1 and the bits of the PR block. Let us show how, having only a set of open/closed texts, one can recover the value of K1. To do this, we use Algorithm 2.
Algorithm 2
Let N be the number of open/closed text pairs known before the attack. Then, to open the key, you need to do the following steps.
For (i=0; i<64; i++) do
{
For(j=0; j
if(СL j ⊕ CR j ⊕ PL j ⊕ F1(PR j , i)=0) then
T i =T i +1
}
}
As a probable sequence K1, such a value of i is taken for which the expression |T i -N/2| has the maximum value.
With a sufficient number of known plaintexts, the algorithm will most likely return the correct value of the six bits of the first round subkey K1. This is explained by the fact that if the variable i is not equal to K1, then the value of the function F1(PR j , K) will be random and the number of equations for such a value of i, at which the left side is equal to zero, will tend to N/2. If the subkey is guessed correctly, the left part will be equal to the fixed bit K3 with a probability of 12/64. Those. there will be a significant deviation from N/2.
Having received 6 bits of the K1 subkey, you can similarly open the 6 bits of the K3 subkey. All that is needed for this is to replace C with P and K1 with K3 in equation (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algorithm 2 will return the correct value of K3 because the decryption process of the DES algorithm is identical to the encryption process, just the sequence of keys is reversed. So on the first round of decryption, the key K3 is used, and on the last round, the key K1.
Having received 6 bits of subkeys K1 and K3, the attacker recovers 12 bits of the common key of the cipher K, because round keys are the usual permutation of the key K. The number of plaintexts needed for a successful attack depends on the probability of the statistical counterpart. To crack a 12-bit 3-round DES key, 100 public/private text pairs are enough. To crack a 12-bit 16-round DES key would require about 244 pairs of texts. The remaining 44 bits of the key are opened by the usual enumeration.
Algorithm DES
The main advantages of the DES algorithm:
Only one 56-bit key is used;
· after encrypting a message using one package, you can use any other to decrypt it;
Relative simplicity of the algorithm ensures high speed of information processing;
rather 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 the encryption operations in reverse order (despite the apparent obviousness, this is not always done. Later we will consider ciphers in which encryption and decryption are carried out using different algorithms).
The encryption process consists of an initial bit-swap of the 64-bit block, sixteen rounds of encryption, and finally a reverse bit-swap (Fig. 1).
It should be immediately noted 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 are selected by the developers in such a way as to make the decryption process as difficult as possible by selecting a key. The structure of the DES algorithm is shown in Figure 2.
Fig.2. The Structure of the DES Encryption Algorithm
Let the next 8-byte block T be read from the file, which is transformed using the initial permutation matrix IP (Table 1) as follows: bit 58 of block T becomes bit 1, bit 50 - bit 2, etc., which will result in : T(0) = IP(T).
The resulting bit sequence T(0) is divided into two sequences of 32 bits each: L(0) - left or high bits, R(0) - right or low 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) = 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 converting the 64-bit key K. The encryption function and the algorithm for deriving 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 positions of the bits of this sequence are rearranged in accordance with the matrix IP -1 (table 2).
Table 2: IP-1 Inverse 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 IP -1 and IP matrices are related as follows: the value of the 1st element of the IP -1 matrix is 40, and the value of the 40th element of the IP matrix is 1, the value of the 2nd element of the IP -1 matrix is 8, and the value of the 8th matrix element IP is 2, and so on.
The data decryption process is the inverse of the encryption process. All steps must be performed in reverse order. This means that the data to be decrypted is first rearranged according to the IP-1 matrix, and then the same operations 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) = L(i), i = 1, 2, ..., 16;
L(i-1) = R(i) xor f(L(i), K(i)), i = 1, 2, ..., 16 .
At the 16th iteration, 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 this 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 - extension of a 32-bit sequence to 48-bit,
S1, S2, ... , S8 - converting a 6-bit block to a 4-bit block,
P is a bit permutation in a 32-bit sequence.
The extension 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: Extension 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 that is added modulo 2 (xor operation) with the 48-bit key K(i). The result is a 48-bit sequence that is split into eight 6-bit blocks B(1)B(2)B(3)B(4)B(5)B(6)B(7)B(8). That is:
E(R(i-1)) xor K(i) = B(1)B(2)...B(8) .
Functions S1, S2, ... , S8 are defined in Table 4.
Table 4
To table.4. additional explanations are required. Let the input of the matrix function Sj be a 6-bit block B(j) = b1b2b3b4b5b6, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 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)=011011. Then S1(В(1)) is located at the intersection of row 1 and column 13. Column 13 of row 1 is set to 5. Hence, S1(011011)=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, you need to rearrange the bits of this sequence. For this, the permutation function P is used (Table 5). In the input sequence, the bits are reversed so that bit 16 becomes bit 1, bit 7 becomes bit 2, and so on.
Table 5: Permutation function P
Thus,
f(R(i-1), K(i)) = 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=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 rearrange the rest, the function G of the initial preparation of the key is used (Table 6).
Table 6
Matrix G of initial key preparation
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 K key, 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=1...16, are recursively defined. For this, a left cyclic shift is applied 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) |
| 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 Finishing 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
The key K(i) will consist of bits 14, 17, ..., 29, 32 of the sequence C(i)D(i). Thus:
K(i) = 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 according to this algorithm, but first you use the key
K(15), then - K(14) and so on. Now you should understand why the author strongly recommends using the above matrices. If you start going arbitrarily, you must get a very secret cipher, but you yourself will not be able to open it later!
Modes of Operation of the DES Algorithm
For the most complete satisfaction of all the requirements for commercial encryption systems, several modes of operation of the DES algorithm have been implemented. The most widely used modes are:
Electronic codebook (Electronic Codebook) - ECB;
a 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 divided into 64-bit blocks (8 bytes each): M = M(1)M(2)...M(n). Each of these blocks is encoded independently using the same encryption key (Figure 5). The main advantage of this algorithm is the ease of implementation. The disadvantage is relatively weak resistance against skilled cryptanalysts.
DES(Data Encryption Standard) - A symmetric encryption algorithm in which one key is used to both encrypt and decrypt 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-cycle Feistel network structure; it uses a 56-bit key for encryption. The algorithm uses a combination of non-linear (S-boxes) and linear (E, IP, IP-1 permutations) transformations. Several modes are recommended for DES:Block cipher
The input data for a block cipher is 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 minor differences in the input data, as a rule, lead to a significant change in the result. Block ciphers are implemented by repeatedly applying certain basic transformations to blocks of source text.Basic transformations:
Feistel Network Transforms
This is a transformation over vectors (blocks) representing the left and right halves of the shift register. The DES algorithm uses forward transformation by the Feistel network in encryption (see Fig. 1) and inverse transformation by the Feistel network into decryption (see Fig. 2).
DES encryption scheme
Source text - block 64 bits. The ciphertext is a 64-bit block.
The encryption process consists of an initial permutation, 16 encryption cycles and a final permutation.
Consider the detailed scheme of the DES algorithm:
L i R i =1,2\ldots.left and right halves of 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 IP permutation 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 block IP(T) participates in 16-cycles of the Feistel transformation.
16 cycles of the Feistel transformation:
Split IP(T) into two parts L 0 ,R 0 , where L 0 ,R 0 are respectively 32 high bits and 32 low bits of block T0 IP(T)= L 0 R 0
Let T i -1 = L i -1 R i -1 be the result of (i-1) iteration, then the result of the i-th iteration T i = L i R i is determined by:
L i = 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 bitwise addition of L i - 1 and f(R i - 1 , k i) modulo 2.
In the 16-cycles of the Feistel transform, the function f plays the role of encryption. Let us consider the function f in detail.
The arguments to function f are a 32 bit vector R i - 1 , a 48 bit key k i , which are the result of transforming the 56 bit original cipher key k.
To calculate the function f, the extension function E, the transformation S, consisting of 8 transformations of S-boxes, and the permutation P are used.
The function E extends the 32 bit vector R i - 1 to the 48 bit vector E(R i - 1) by duplicating some bits from R i - 1, while the bit order of the vector E(R i - 1) is specified in Table 2. 
The first three bits of the vector E(R i - 1) are bits 32, 1, 2 of the 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 the vector E(Ri - 1) are bits 31, 32, 1 of the 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 presented as eight consecutive blocks B 1 ,B 2 ,...B 8 .
E(R i - 1) = B 1 B 2 ...B 8
Each B j is a 6-bit block. Next, each of the blocks B j is transformed into a 4-bit block B" j using the transformations S j . The transformations S j are determined by table 3. Let's assume that B 3 = 101111 and we want to find B" 3 . The first and last digits of B 3 are the binary notation of the number a, 0 The value of the function f(R i - 1, k i) (32 bits) is obtained by permuting P applied to a 32-bit block B "1 B" 2 ...B" 8. Permutation P is given by table 4. 
f(R i - 1 ,k i) = 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 the vector B" 1 B" 2 ...B" 8
Generation of keys k i .
The keys k i are obtained from the initial key k (56 bits = 7 bytes or 7 characters in ASCII) in this way. Eight bits located at 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 a permutation is made for the extended key (except for the added bits 8, 16, 24, 32, 40, 48, 56, 64). Such a 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=1,2,3… are obtained from C i - 1 ,D i - 1 by one or two left cyclic shifts according to Table 6. 
The key k i , i=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 of 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 the position. It is the inverse of the IP permutation. The final permutation is determined by Table 8. 
Modes of using DES DES can be used in four modes.
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 quite quickly, and already in 1980 was approved by the US National Institute of Standards and Technology. From this point on, DES becomes a standard not only in name, but also in fact. There are software and specialized microcomputers designed to encrypt and decrypt information in data networks.
To date, DES is 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 taste.
The main advantages of the DES algorithm:
Only one 56-bit key is used;
· after encrypting a message using one package, you can use any other to decrypt it;
Relative simplicity of the algorithm ensures high speed of information processing;
rather 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 the encryption operations in reverse order (despite the apparent obviousness, this is not always done. Later we will consider ciphers in which encryption and decryption are carried out using different algorithms).
The encryption process consists of an initial bit-swap of the 64-bit block, sixteen rounds of encryption, and finally a reverse bit-swap (Figure 1).
It should be immediately noted 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 are selected by the developers in such a way as to make the decryption process as difficult as possible by selecting a key. The structure of the DES algorithm is shown in fig. 2.
Rice. 2.
Let the next 8-byte block T be read from the file, which is transformed using the initial permutation matrix IP (Table 1) as follows: bit 58 of block T becomes bit 1, bit 50 becomes bit 2, etc., which will result in : T(0) = IP(T).
The resulting bit sequence T(0) is divided into two sequences of 32 bits each: L(0) - left or high bits, R(0) - right or low 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) = 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 converting the 64-bit key K. In detail, the encryption function and the algorithm for deriving 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 positions of the bits of this sequence are rearranged in accordance with the matrix IP -1 (Table 2).
Table 2: IP-1 Inverse 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 IP -1 and IP matrices are related as follows: the value of the 1st element of the IP -1 matrix is 40, and the value of the 40th element of the IP matrix is 1, the value of the 2nd element of the IP -1 matrix is 8, and the value of the 8th matrix element IP is 2, and so on.
The data decryption process is the inverse of the encryption process. All steps must be performed in reverse order. This means that the data to be decrypted is first rearranged according to the IP-1 matrix, and then the same operations 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) = L(i), i = 1, 2,…, 16;
L (i-1) = R(i) xor f (L(i), K(i)), i = 1, 2,…, 16.
At the 16th iteration, 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 this 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.
Rice. 3.
The following matrix functions are used to calculate the value of the function f:
E - extension of a 32-bit sequence to 48-bit,
S1, S2,…, S8 - 6-bit to 4-bit block conversion,
P is a bit permutation in a 32-bit sequence.
The extension 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: Extension 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 that is added modulo 2 (xor operation) with the 48-bit key K(i). A 48-bit sequence is obtained, which is divided into eight 6-bit blocks B(1) B(2) B(3) B(4) B(5) B(6) B(7) B(8). That is:
E (R(i-1)) xor K(i) = B(1) B(2)… B(8).
Functions S1, S2, ..., S8 are defined in Table. 4.
Table 4
To table. 4. Additional explanations are required. Let the input of the matrix function Sj be a 6-bit block B(j) = b1b2b3b4b5b6, then the two-bit number b1b6 indicates the row number of the matrix, and b2b3b4b5 the column number. The result of Sj (B(j)) will be a 4-bit element located at the intersection of the specified row and column.
For example, B(1)=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)=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, you need to rearrange the bits of this sequence. For this, the permutation function P is used (Table 5). In the input sequence, the bits are reversed so that bit 16 becomes bit 1, bit 7 becomes bit 2, and so on.
Table 5: Permutation function P
Thus,
f (R(i-1), K(i)) = 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=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 rearrange the rest, the function G of the initial preparation of the key is used (Table 6).
Table 6
Matrix G of initial key preparation
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), where 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 C(0) and D(0) are determined, C(i) and D(i), i=1…16, are determined recursively. For this, a left cyclic shift is applied by one or two bits, depending on the iteration number, as shown in Table 1. 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 Finishing 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
The key K(i) will consist of bits 14, 17,…, 29, 32 of the sequence C(i) D(i). Thus:
K(i) = H (C(i) D(i))
The block diagram of the key calculation algorithm is shown in fig. 4.
Rice. 4.
Restoration of the original text is carried out according to this algorithm, but first you use the key K(15), then K(14) and so on. Now you should understand why the author strongly recommends using the above matrices. If you start going arbitrarily, you must get a very secret cipher, but you yourself will not be able to open it later!
