What is the main disadvantage of des. DES and AES encryption algorithms

symmetric keys .

IBM's proposed modification of the project, called Lucifer, was adopted as DES. DES were published in draft form in Federal Register in March 1975 as Federal Information Processing Standard (FIPS – Federal Information Processing Standard).

Upon publication, the sketch was severely criticized for two reasons. First, there was criticism of the questionably small key length (only 56 bits), which could make the cipher vulnerable to brute force attacks.

The second reason: critics were concerned about some hidden design of the internal structure of DES. They suspected that some part of the structure (S-boxes) might have hidden loophole

, which will allow you to decrypt messages without a key. IBM designers subsequently reported that the internal structure had been modified to prevent cryptanalysis. DES was finally published as FIPS 46 in the Federal Register in January 1977. However, FIPS declared DES as a standard for use in unofficial applications . DES was the most widely used block cipher With symmetric keys , starting from its publication. NIST later proposed new standard

(FIPS 46-3), which recommends the use of triple DES (triple-repeated DES cipher) for future applications. As we will see later in lectures 9-10, the newer AES standard is expected to replace DES.

General provisions

As shown in Fig. 8.1. DES - block cipher.

Rice. 8.1. On the side DES encryption accepts 64-bit original text

and produces 64-bit ciphertext; On the decryption side, DES takes a 64-bit ciphertext and produces a 64-bit plaintext. Both sides use the same 56-bit key for encryption and decryption.

8.2. DES structure

Let's look at encryption first and then decryption. The encryption process consists of two permutations (P-blocks) - called start and end permutations - and sixteen Feistel rounds. Each round uses a different generated 48-bit key. The generation algorithm will be discussed later in this lecture. Figure 8.2 shows the elements of a DES cipher on the encryption side.

Figure 8.3 shows the initial and final permutations (P-blocks). Each of the permutations takes a 64-bit input and rearranges its elements according to a given rule. We have shown only a small number of input ports and corresponding output ports. These permutations are direct permutations without keys, which are inverses of each other. For example, in the initial permutation, the 58th bit of the input goes to the first bit of the output. Similarly, in the final permutation, the first input bit goes to the 58th output bit. In other words, if there is no round between these two permutations, the 58th bit supplied to the input of the initial permutation device will be delivered to the 58th output by the final permutation.

Rice. 8.2.

Rice. 8.3.

The permutation rules for this P-box are shown in Table 8.1. The table can be represented as a 64-element array. Note that we discussed working with the table; the value of each element determines the number of the input port, and the serial number (index) of the element determines the number of the output port.

Table 8.1.

Table of initial and final permutations								Initial permutations
58	50	42	34	26	18	10	02	40	08	48	16	56	24	64	32
60	52	44	36	28	20	12	04	39	07	47	15	55	23	63	31
62	54	46	38	30	22	14	06	38	06	46	14	54	22	62	30
64	56	48	40	32	24	16	08	37	05	45	13	53	21	61	29
57	49	41	33	25	17	09	01	36	04	44	12	52	20	60	28
59	51	43	35	27	19	11	03	35	03	43	11	51	19	59	27
61	53	45	37	29	21	13	05	34	02	42	10	50	18	58	26
63	55	47	39	31	23	15	07	33	01	41	09	49	17	57	25

Finite permutations

• These two permutations have no meaning for cryptography in

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

The DES algorithm is quite suitable for both encryption and authentication of data. It allows 64-bit plaintext input to be directly converted to 64-bit ciphertext output, but data is rarely limited to 64 bits.

To use the DES algorithm to solve a variety of cryptographic problems, four operating modes have been developed:

· electronic code book ECB (Electronic Code Book);

· concatenation of CBC cipher blocks (Cipher Block Chaining);

· CFB (Cipher Feed Back) ciphertext feedback;

· feedback on the output OFB (Output Feed Back).

"Electronic code book" mode

A long file is divided into 64-bit segments (blocks) of 8 bytes. Each of these blocks is encrypted independently using the same encryption key (Fig. 3.6).

The main advantage is ease of implementation. Disadvantage: Relatively weak resistance against skilled cryptanalysts. Due to the fixed nature of encryption, with a limited block length of 64 bits, "dictionary" cryptanalysis is possible. A block of this size may be repeated in a message due to the high redundancy in natural language text.

Figure 3.6 – Scheme of the DES algorithm in electronic codebook mode

This causes identical blocks of plaintext in a message to be represented by identical blocks of ciphertext, giving the cryptanalyst some information about the contents of the message.

"Chaining Cipher Blocks" mode

In this mode, the source file M is divided into 64-bit blocks: M = M 1 M 2 ...M n. The first block M 1 is added modulo 2 with a 64-bit initial vector IV, which changes daily and is kept secret (Fig. 3.7). The received amount is then encrypted using a DES key known to both the sender and recipient of the information. The resulting 64-bit cipher C 1 is added modulo 2 with the second block of text, the result is encrypted and a second 64-bit cipher C 2 is obtained, etc. The procedure is repeated until all blocks of text have been processed.

Thus, for all i = 1…n (n is the number of blocks), the encryption result C i is determined as follows: C i =

DES (М i  C i –1), where С 0 = IV is the initial value of the cipher, equal to the initial vector (initialization vector).

Obviously, the last 64-bit ciphertext block is a function of the secret key, the seed vector, and each bit

Figure 3.7 – Scheme of the DES algorithm in cipher block chaining mode

plaintext regardless of its length. This block of ciphertext is called a message authentication code (MAC).

The CAS code can be easily verified by the recipient, who has the secret key and the seed vector, by repeating the procedure performed by the sender. An outsider, however, cannot generate a UAS that is perceived as genuine by the recipient to add to a false message, or separate the UAS from a true message for use with a modified or false message.

The advantage of this mode is that it does not allow errors to accumulate during transmission.

Block M i is a function of only C i –1 and C i . Therefore, a transmission error will result in the loss of only two blocks of source text.

"Cypher feedback" mode

In this mode, the block size may differ from 64 bits (Fig. 3.8). The file to be encrypted (decrypted) is read in successive blocks of k bits in length (k=1...64).

The input block (64-bit shift register) first contains a right-aligned initialization vector.

Suppose that as a result of dividing into blocks, we received n blocks of length k bits each (the remainder is appended with zeros or spaces). Then for any i=1…n ciphertext block

С i = M i  P i –1 ,

where P i–1 denotes the k most significant bits of the previous encrypted block.

The shift register is updated by removing its highest k bits and writing C i to the register. Recovering encrypted data is also relatively simple: P i –1 and C i are calculated in a similar way and

М i = С i  Р i –1 .

Figure 3.8 – Scheme of the DES algorithm in ciphertext feedback mode

Output feedback mode

This mode also uses a variable block size and a shift register that is initialized in the same way as in CFB mode, namely, the input block first contains an initialization vector IV, aligned to the right (Fig. 3.9). In this case, for each data encryption session, it is necessary to use a new initial state of the register, which must be sent over the channel in clear text.

M = M 1 M 2 ... M n.

For all i = 1… n

C i = M i  P i ,

where Р i are the highest k bits of the DES operation (С i –1).

The difference from the ciphertext feedback mode is the method of updating the shift register.

This is done by discarding the highest k bits and adding P i to the right.

Figure 3.9 – Scheme of the DES algorithm in output feedback mode

3.3. Areas of application of the DES algorithm

Each of the considered modes (ECB, CBC, CFB, OFB) has its own advantages and disadvantages, which determines the areas of their application.

The ECB mode is well suited for key encryption: the CFB mode is usually intended for encryption of individual characters, and the OFB mode is often used for encryption in satellite communications systems.

The CBC and CFB modes are suitable for data authentication. These modes allow you to use the DES algorithm to:

· interactive encryption when exchanging data between the terminal and the host computer;

· encryption of a cryptographic key in the practice of automated key distribution;

· encryption of files, mail, satellite data and other practical tasks.

Initially, the DES standard was intended for encryption and decryption of computer data. However, its application has been generalized to authentication.

In automatic data processing systems, there is no way for a human to review the data to determine whether any changes have been made to it. With the huge amounts of data flowing through modern processing systems, browsing would take too much time. In addition, data redundancy may not be sufficient to detect errors. Even in cases where human review is possible, the data may be changed in ways that make it very difficult for humans to detect the changes. For example, “do” can be replaced with “do not”, “$1900” with “$9100”. Without additional information, a person viewing it can easily mistake the altered data for genuine data. Such dangers may exist even when data encryption is used. Therefore, it is desirable to have an automatic means of detecting intentional and unintentional data changes.

Ordinary error detection codes are unsuitable because if the algorithm for generating the code is known, the adversary can generate the correct code after making changes to the data. However, using the DES algorithm, it is possible to generate a cryptographic checksum that can protect against both accidental and intentional but unauthorized changes to data.

This process describes the standard for computer data authentication (FIPS 113). The essence of the standard is that data is encrypted in ciphertext feedback mode (CFB mode) or in cipher block concatenation mode (CBC mode), resulting in a final cipher block that is a function of all the plaintext bits. The message, which contains the plaintext, can then be transmitted using the calculated final cipher block, which serves as a cryptographic checksum.

The same data can be protected using both encryption and authentication. Data is protected from access by encryption, and changes are detected through authentication. The authentication algorithm can be applied to both plaintext and ciphertext. In financial transactions, where in most cases both encryption and authentication are implemented, the latter also applies to open

mu text.

Encryption and authentication are used to protect data stored in a computer. In many computers, passwords are encrypted irreversibly and stored in the machine's memory. When a user accesses the computer and enters a password, the latter is encrypted and compared with the stored value. If both encrypted values ​​are the same, the user gains access to the machine, otherwise it is denied.

Often, an encrypted password is generated using the DES algorithm, with the key equal to the password and the plaintext equal to the user identification code.

Using the DES algorithm, you can also encrypt computer files for storage.

One of most important applications algorithm DES is protection of electronic payment system (EPS) messages during transactions with a wide clientele and between banks.

The DES algorithm is implemented in ATMs, point-of-sale terminals, workstations, and mainframe computers. The range of data it protects is very wide - from payments of $50 to transfers of many millions of dollars. The flexibility of the core DES algorithm allows it to be used in a wide variety of electronic payment system applications.

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, substitution and gamma. The encrypted data must be in binary form.

Encryption

General structure DES shown in Fig.

1. 4.1. The process of encrypting each 64-bit block of raw data can be divided into three stages:
2. initial preparation of a data block;
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.

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.