Des key what. DES and AES encryption algorithms

• Tutorial

Hello %username%!
Many people know that the default standard in the field symmetric encryption for a long time was considered DES algorithm. The first successful attack on this unkillable 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, makes it possible to crack The secret key DES cipher in 2 43 operations.
Below the cut I will try to briefly outline the main points of this attack.

Linear cryptanalysis

Linear cryptanalysis is a special type of attack on symmetric ciphers, aimed at recovering an unknown encryption key from known open messages and their corresponding ciphertexts.

IN general case An attack based on linear cryptanalysis boils down to the following conditions. The attacker has big amount plaintext/ciphertext pairs obtained using the same encryption key K. The attacker's goal is to recover part or all of the key K.

First of all, the attacker examines the cipher and finds the so-called statistical analogue, i.e. the equation the following type, which executes 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.
Once such an equation is found, the attacker can recover 1 bit of key information using the following algorithm

Algorithm 1
Let T be the number of texts for which left side equation (1) equals 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).
It is obvious that the success of the algorithm directly depends on the value of |P-1/2| and on the number of available open/closed text pairs N. The more the probability P of equality (1) differs from 1/2, the less number of open texts N is needed for the attack.

There are two problems that need to be solved for the attack to be successful:

• How to find an effective equation of the form (1).
• How to use this equation to get more than one bit of information about the key.

Let's consider the solution to these issues using the DES cipher as an example.

Description of DES

But first, let's briefly describe how the algorithm works. Enough has already been said about DES. A full description of the cipher can be found on Wikipedia. However, to further explain the attack we will need a number of definitions that are best introduced in advance.

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. Let's consider the encryption scheme of the DES algorithm.

As can be seen from the figure, when encrypting text, the following operations are performed:

1. Initial bit permutation. At this stage, the bits of the input block are shuffled in a certain order.
2. After this, the mixed 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 other variants of the algorithm exist.
3. The two blocks obtained in the last round of transformation are combined and another permutation is performed on the resulting block.

In each round of the Feistel network, the least significant 32 bits of the message are passed through the function f:

Let's look at the operations performed at this stage:

1. The input block is passed through the extension function E, which converts a 32-bit block into a 48-bit block.
2. The resulting block is added to the round key K i .
3. The result of the previous step is divided into 8 blocks of 6 bits each.
4. Each of the received blocks B i is passed through the substitution function S-Box i , which replaces the 6-bit sequence with a 4-bit block.
5. The resulting 32-bit block is passed through the permutation P and returned as the result of function f.

Of greatest interest to us from the point of view of cipher cryptanalysis are S blocks, designed to hide the connection between the input and output data of the function f. To successfully attack DES, we will first construct statistical analogues for each of the S-boxes, and then extend them to the entire cipher.

S block analysis

Each S-box takes a 6-bit sequence as input, and for each such sequence a fixed 4-bit value is returned. 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 out of 64 cases. 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 sides were independent of each other, the equation would have to be satisfied with a probability of 1/2. Thus, we have just demonstrated the relationship between the input and output of the 3rd S-box of the DES algorithm.

Let's consider how we 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 XOR input bits S a superimposed on the α bits are equal to the XOR output bits superimposed on the α bits β, i.e.:
where the symbol is logical AND.
The values ​​of α and β for which NS a (α, β) is most different from 32 describe the most efficient statistical analogue of the S-box S a .

The most effective analogue 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 holds: Z=Y ⊕ Y ⊕ Y ⊕ Y, where Z is the input sequence of the S-box and Y is the output sequence.
Or taking into account the fact that in the DES algorithm, before entering the S-box, the data is 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 taking into account permutations.
The resulting equation is executed on all rounds of the DES algorithm with the same probability P=12/64.
The following table shows a list of effective ones, i.e. having the greatest deviation from P=1/2, statistical analogues for each s-block of the DES algorithm.

Constructing statistical analogues for multiple rounds of DES

Let us now show how we can combine the statistical analogues of several rounds of DES and ultimately obtain a statistical analogue for the entire cipher.
To do this, consider a three-round version of the algorithm:

Let's use an efficient statistical analogue of the 5th s-box to calculate certain bits of the X(2) value.
We know that with probability 12/64 the equality holds in the f-function 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 expanding the input bits. By analyzing the expansion function, we can establish that the 26th bit is replaced by the 17th bit of the X(1) sequence.
Similarly, Y,..., Y are essentially the 17th, 18th, 19th and 20th bits of the sequence obtained before the permutation P. Examining the permutation P, we find that the bits Y,..., Y are actually bits Y(1), Y(1), Y(1), Y(1).
The key bit K involved in the equations is the 26th bit of the first round subkey K1 and then the statistical analogue takes the following form:
X(1) ⊕ Y(1) ⊕ Y(1) ⊕ Y1 ⊕ Y(1) = K1.
Hence, 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 sequence Y(1), you can find 3, 8, 14, 25 bits of the sequence X(2):
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) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ Y(3) ⊕ Y(3) ⊕ Y(3) ⊕ Y(3)
we get that
X(2) ⊕ X(2) ⊕ X(2) ⊕ X(2) = CL ⊕ CL ⊕ CL ⊕ CL ⊕ X(3) ⊕ K3(4) with a probability of 12/64.

Equating the right-hand sides of equations (3) and (4) we obtain
CL ⊕ CL ⊕ CL ⊕ CL ⊕ 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 executed with probability (12/64) 2 + (1-12/64) 2 =0.7.
The statistical analogue described above can be represented graphically as follows (bits in the figure are numbered from right to left and starting from zero):

All the 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's show how, using this statistical analogue, you can open not 1, but 12 bits of the encryption key K.

Attack on DES with Known Plaintext

Let us present a method by which you can expand the attack and immediately obtain 6 bits of the first round connect.
When composing 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.
Let us return the value F1(PR, K1) instead of the expression K1 ⊕ PR and obtain the following equation:
СL ⊕ CR ⊕ PL ⊕ F1(PR, K1) = K3 (6) , which will be executed with probability 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 key bits K1 and the bits of the PR block. Let's show how, having only a set of open/closed texts, you can restore the value of K1. To do this, we will 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 take 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, a value of i is taken such that the expression |T i -N/2| has the maximum value.

Given a sufficient number of known plaintexts, the algorithm will have a high probability of returning 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 for which the left side is equal to zero will tend to N/2. If the subkey is guessed correctly, the left side will be equal to the fixed bit K3 with probability 12/64. Those. there will be a significant deviation from N/2.

Having received 6 bits of subkey K1, you can similarly open 6 bits of subkey K3. All you need to do is replace C with P and K1 with K3 in equation (6):
PL ⊕ PR ⊕ CL ⊕ F3(CR, K3) = K1.
Algorithm 2 will return the correct K3 value because the decryption process of the DES algorithm is identical to the encryption process, just the key sequence is reversed. So in the first round of decryption the key K3 is used, and in the last round the key K1 is used.

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 required for a successful attack depends on the probability of the statistical analogue. To crack a 12-bit 3-round DES key, 100 public/private text pairs are sufficient. To open 12 bits of a 16-round DES key, about 2 44 pairs of texts will be required. The remaining 44 bits of the key are opened using normal brute force.

The most common and best known symmetric encryption algorithm is DES (Data Encryption Standard). The algorithm was developed in 1977 and was adopted by NIST (National Institute of Standards and Technology, USA) as a standard in 1980.

DES is a classical Feishtel network with two branches. Data is encrypted in 64-bit blocks using a 56-bit key. The algorithm converts a 64-bit input into a 64-bit output over several rounds. The key length is 56 bits. The encryption process consists of four stages. The first step is an initial permutation (IP) of the 64-bit source text (whitening), during which the bits are reordered according to a 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, the fourth stage performs an IP-1 permutation of the result obtained in the third stage. 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 supplied to the input of the permutation function. Then, for each of the 16 rounds, the subkey K i is a combination of left circular shift and permutation. The permutation function is the same for each round, but the subkeys K i for each round are different due to the repeated shifting of the key bits.

The initial permutation and its inversion are determined by a standard table. If M is arbitrary 64 bits, then X = IP(M) is the rearranged 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

Let's look at the sequence of transformations used in each round.

Fig.5. Illustration of a round of the DES algorithm

A 64-bit input block passes through 16 rounds, with each iteration producing an intermediate 64-bit value. The left and right sides 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 L i is equal to the input of the right half R i-1. The output of the right half of R i is the result of applying an XOR operation to L i-1 and a function F depending on R i-1 and K i .

Let's look at function F in more detail. R i , which is supplied to the input of function F, has a length of 32 bits. First, R i is expanded to 48 bits using a table that specifies the permutation plus the 16-bit expansion. The expansion occurs as follows. The 32 bits are split into groups of 4 bits and then expanded to 6 bits by adding the outermost 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, which results in a 32-bit value.

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 determines the 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.

The resulting 32-bit value is then processed using permutation P, the purpose of which is to reorder the bits as much as possible so that in the next round of encryption, each bit is likely to be processed by a different S-box.

The key for an individual round K i consists of 48 bits. Keys K i are obtained using the following algorithm. For the 56-bit key used as input to the algorithm, a permutation is first performed in accordance with 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. At each round, C i and D i are independently cyclically shifted to the left by 1 or 2 bits, depending on the round number. The resulting values ​​are the input for the next round. They are also the input to Permuted Choice 2 (PC-2), which produces a 48-bit output value that is the input to the function F(R i-1, K i).

The decryption process is similar to the encryption process. The input to the algorithm is ciphertext, 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 decryption round 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 plaintext.

More than 30 years have passed since the adoption of the DES algorithm as the US encryption standard. DES is an encryption algorithm with the richest and most interesting history.

History of the creation of the algorithm

One of the most famous cryptologists in the world, Bruce Schneier, in his famous book “Applied Cryptography” described the problems of users of information security tools in the early 70s. XX century (naturally, we are talking about users on the other side of the Iron Curtain):

There was neither a generally accepted standard for data encryption nor simply widely used information security algorithms, so compatibility between different software or hardware encryption tools was out of the question;

Almost any encryption tool was a “black box” with rather unclear contents: what encryption algorithm is used, how cryptographically strong it is, whether it is implemented correctly, whether encryption keys are created, stored, and used correctly, whether the tool contains undocumented capabilities inserted by developers and etc. - all this very important information was inaccessible to the vast majority of buyers of cryptographic funds.

The National Bureau of Standards (NBS) of the USA was concerned with this problem. As a result, in 1973, the first ever open competition for an encryption standard was announced. NBS was willing to examine candidate algorithms that met the following criteria in order to select a standard:

The algorithm must be cryptographically strong;

The algorithm must be fast;

The structure of the algorithm must be clear and precise;

The strength of encryption should depend only on the key; the algorithm itself should not be secret;

The algorithm should be easily applicable for various purposes;

The algorithm should be easily implemented in hardware using existing hardware components.

It was assumed that interested organizations or specialists would send to NBS detailed specifications of algorithms sufficient for their implementation, i.e., without any “blind spots.” It was also assumed that the algorithm would be certified by the NBS for general use, and all patent and export restrictions would be removed from it, as a result of which such a standard would have to solve all encryption compatibility problems. In addition, NBS took on the functions of certifying encryption tools - that is, “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 ShM (see section 3.31). Over the course of two years, the algorithm was refined:

Firstly, NBS, together with the National Security Agency (NSA, National Security Agency) of the United States, carried out a thorough analysis of the algorithm, which resulted in its fairly significant revision;

Secondly, comments and criticisms from all interested organizations and individuals were taken into account.

As a result of joint efforts by IBM, NBS and the NSA, DES was published in January 1977 as a US standard (the latest version of this standard is in the document) for an algorithm for encrypting data (except for highly sensitive information). The DES algorithm was patented by YuM, 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

The DES algorithm encrypts information in 64-bit blocks using a 64-bit encryption key that uses only 56 bits (the key expansion procedure is described in detail below).

Encryption of information is performed as follows (Fig. 3.56):

1. An initial permutation is performed on a 64-bit data block according to table. 3.16.

Table 3.16

The table is interpreted as follows: the value of input bit 58 (hereinafter all bits are numbered from left to right, starting from 1) is placed in output bit 1, the value of bit 50 is placed in bit 2, etc.

2. The result of the previous operation is divided into 2 subblocks of 32 bits each (per

rice. 3.56 marked A 0 and B 0), over which 16 rounds are performed

the following transformations:

As mentioned above, out of a 64-bit encryption key, the DES algorithm uses only 56 bits. 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 implementations of the DES algorithm is in no way limited by the standard. The procedure for extracting the 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 rearrangement of the key bits according to Table. 3.19 and 3.20.

Table 3.19

Table 3.20

As a result of the permutation, two 28-bit values ​​C and D are formed. Table 3.19 defines the selection of key bits for C, table. 3.20 - for D.

Then 16 rounds of transformations are performed, each yielding one of the round keys K t . In each round of the key expansion procedure, the following actions are performed:

1. Current values ​​of C and D cyclically shifted left by a variable number of bits P. For rounds 1, 2, 9 and 16 P= 1, in the remaining rounds a cyclic shift of 2 bits is performed.

2. C and D are combined into a 56-bit value, to which the compression permutation CP is applied, the result of which is a 48-bit round key K (. The compression 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 a cyclic shift to the left, perform a cyclic shift to the right by n bits, where rc' = 0 for the first round, u' = 1 for rounds 2, 9, 16 and n = 2 for the remaining rounds . This key expansion procedure will immediately provide the round keys needed for decryption.

It is worth saying 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.

Annotation: One of the most famous private key cryptographic systems is DES – Data Encryption Standard. This system was the first to receive the status of a state standard in the field of data encryption. And although the old American standard DES has now lost its official status, this algorithm still deserves attention when studying cryptography. This lecture also explains what double DES is, a meet-in-the-middle attack, and how to mitigate it. This lecture also briefly discusses the new US standard for block ciphers, the Rijndael algorithm.

Purpose of the lecture: introduce the student to the basic information about the DES encryption algorithm.

Basic information

One of the most famous private key cryptographic systems is DES – Data Encryption Standard. This system was the first to receive the status of a state standard in the field of data encryption. It was developed by IBM specialists and came into force in the USA in 1977. Algorithm DES widely used for storing and transmitting data between various computer systems; in postal systems, electronic drawing systems and electronic interchange commercial information. Standard DES was implemented both in software and in hardware. Enterprises from different countries have launched mass production of digital devices using DES for data encryption. All devices underwent mandatory certification for compliance with the standard.

Despite the fact that this system has not had the status of a government standard for some time, it is still widely used and deserves attention when studying block ciphers with a private key.

Key length in the algorithm DES is 56 bits. It is with this fact that the main controversy regarding the ability to DES resist various attacks. As you know, any block cipher with a private key can be cracked by trying all possible key combinations. With a key length of 56 bits, 2 56 different keys are possible. If a computer searches through 1,000,000 keys in one second (which is approximately equal to 2 20), then it will take 2 36 seconds or a little over two thousand years to search through all 2 56 keys, which, of course, is unacceptable for attackers.

However, more expensive and faster computing systems are possible than Personal Computer. For example, if it is possible to combine a million processors for parallel calculations, then the maximum key selection time is reduced to approximately 18 hours. This time is not too long, and a cryptanalyst equipped with such expensive equipment can easily break DES-encrypted data in a reasonable amount of time.

At the same time, it can be noted that the system DES It can be used in small to medium-sized applications to encrypt data of little value. For encrypting data of national importance or having significant commercial value, the system DES should of course not be used at present. In 2001, after a specially announced competition, a new block cipher standard was adopted in the United States, called AES (Advanced Encryption Standard), which was based on the cipher Rijndael, developed by Belgian specialists. This cipher is discussed at the end of the lecture.

Main settings DES: block size 64 bits, key length 56 bits, number of rounds – 16. DES is a classical Feishtel network with two branches. The algorithm converts a 64-bit input data block into a 64-bit output block over several rounds. Standard DES built on the combined use of permutation, replacement and gamma. The encrypted data must be in binary form.

Encryption

General structure DES shown in Fig. 4.1. The process of encrypting each 64-bit block of raw data can be divided into three stages:

1. initial preparation of a data block;
2. 16 rounds of the "main cycle";
3. final processing of a data block.

At the first stage it is carried out initial permutation 64-bit source block of text, during which the bits are rearranged in a specific way.

At the next (main) stage, the block is divided into two parts (branches) of 32 bits each. The right branch is transformed using some function F and the corresponding partial key, obtained from the main encryption key using a special key conversion algorithm. Then data is exchanged between the left and right branches of the block. This is repeated in a cycle 16 times.

Finally, the third stage rearranges the result obtained after sixteen steps of the main loop. This permutation is the inverse of the initial permutation.

Rice. 4.1.

Let's take a closer look at all the stages of cryptographic conversion according to the standard DES.

In the first stage, the 64-bit source data block undergoes an initial permutation. In the literature, this operation is sometimes called “whitening”. During the initial permutation, the bits of the data block are rearranged in a certain way. This operation adds some "chaotic" nature to the original message, reducing the possibility of using cryptanalysis using statistical methods.

Simultaneously with the initial permutation of the data block, an initial permutation of the 56 bits of the key is performed. From Fig. 4.1. It can be seen that in each of the rounds the corresponding 48-bit partial key K i is used. Keys K i are obtained using a specific algorithm, using each of the bits of the initial key several times. In each round, the 56-bit key is divided into two 28-bit halves. The halves are then shifted left one or two bits depending on the round number. After the shift, 48 of the 56 bits are selected in a certain way. Since this not only selects a subset of bits, but also changes their order, this operation is called “compression permutation.” Its result is a set of 48 bits. On average, each bit of the original 56-bit key is used in 14 of the 16 subkeys, although not all bits are used the same number of times.

Next, the main transformation cycle is performed, organized using the Feishtel network and consisting of 16 identical rounds. In this case, in each round (Fig. 4.2) an intermediate 64-bit value is obtained, which is then processed in the next round.

Rice. 4.2.

The left and right branches of each intermediate value are treated as separate 32-bit values, denoted L and R .

First, the right side of the block R i is expanded to 48 bits using a table that specifies the permutation plus the expansion by 16 bits. This operation matches the size of the right half to the size of the key to perform an XOR operation. In addition, by performing this operation, the dependence of all bits of the result on the bits of the source data and the key increases faster (this is called the “avalanche effect”). The stronger the avalanche effect when using one or another encryption algorithm, the better.

After performing the expansion permutation, the resulting 48-bit value is XORed with the 48-bit subkey K i . Then the resulting 48-bit value is fed to the input of the substitution block S (from the English. Substitution - substitution), result which is a 32-bit value. The substitution is performed in eight substitution blocks or eight S-boxes. When executed, DES looks quite complicated on paper, let alone its software implementation! Develop a correctly and optimally functioning program fully in accordance with DES, probably, only experienced programmers can do it. Some difficulties arise when implementing software, for example, initial permutation or permutation with expansion. These difficulties are related to what was originally planned to be implemented DES hardware only. All operations used in the standard are easily performed by hardware units, and no implementation difficulties arise. However, some time after the publication of the standard, software developers decided not to stand by and also take up the creation of encryption systems. Further DES was implemented both in hardware and software.