Block cipher standards. DES and AES encryption algorithms

Which ANSI calls the data encryption algorithm DEA (Data Encryption Algorithm), and ISO calls it DEA-1, has become a world standard in 20 years. Over the years of its existence, it has withstood the onslaught of various attacks and, with certain restrictions, is still considered crypto-resistant.

DES is a block cipher that encrypts data in 64-bit blocks. A 64-bit block of plaintext is input at one end of the algorithm, and a 64-bit ciphertext block is output at the other end. DES is symmetric algorithm: Encryption and decryption use the same algorithm and key (except for slight differences in key usage). The key length is 56 bits. (A key is typically represented as a 64-bit number, but every eighth bit is used for parity and is ignored. The parity bits are the least significant bits of the key bytes.) The key, which can be any 56-bit number, can be changed at any time.

Cryptographic strength is completely determined by the key. The fundamental building block of DES is the combination of substitutions and permutations. DES consists of 16 cycles.

General view of the conversion cycle:

If L i and R i are the left and right halves resulting from the ith iteration, K i is the 48-bit key for loop i, and f is a function that performs all substitutions, permutations, and XORs on the key, then one conversion loop can be represented as:

Taking into account the substitution F i (*) and the permutation T (*), the transformation cycle can be represented as shown in Fig.

It can be seen that each DES cycle is a composition cipher with two sequential transformations - substitution F i (*) and permutation T (*) (with the exception of the last, sixteenth cycle, where the permutation is omitted).

Substitution:

(L i , R i) = (R i −1 , L i −1) ⊕ f (R i −1 , K)

is an involution, since

F i (F i (L i −1 , R i −1)) = F i (R i −1 , L i −1) ⊕ (f (R i −1 , K i))) = (R i − 1 , L i −1 ⊕(f (R i −1 , K i)) ⊕ (f (R i −1 , K i))) = (L i −1 , R i −1)

And substitution

T (L i ′, R i ′) = (R i ′, L i ′),

is also an involution, since

T (T (L i ′, R i ′)) = T (R i ′, L i ′) = L i ′, R i ′

If we denote the initial and final permutations as (IP) and (IP) − 1, then the direct DES transformation (encryption) implements the function:

DES = (IP) F 1 TF 2 T … F 15 TF 16 (IP) − 1 ,

and the reverse DES transformation (decryption) implements the function:

DES − 1 = (IP) −1 F 16 TF 15 T … F 2 TF 1 (IP).

Thus, DES is a Feistel cipher and is designed to perform useful property: The same algorithm is used for encryption and decryption. The only difference is that the keys must be used in reverse order.

That is, if the keys K 1, K 2, K 3, ..., K 16 were used during encryption, then the decryption keys will be K 16, K 15, K 14, ..., K 1. The algorithm uses only standard 64-bit arithmetic and logical operations, so it can be easily implemented in hardware.

DES operates on a 64-bit plaintext block. After the initial shuffling, the block is split into right and left halves of 32 bits each. Then 16 transformations (function f) are performed in which the data is combined with the key. After the sixteenth cycle, the right and left halves are combined, and the algorithm ends with a final permutation (the reverse of the original). At each cycle (see figure), the key bits are shifted, and then 48 bits are selected from the 56 key bits. The right half of the data is expanded to 48 bits using expansion permutation, XORed with the 48 bits of the shifted and permuted key, passed through 8 S-boxes to form 32 new bits, and permuted again. These four operations are performed by the f function.

The result of f is then combined with the left half using another XOR. As a result of these actions, a new right half appears, and the old right becomes a new left half. These steps are repeated 16 times, resulting in 16 DES cycles.

Russian standard - GOST 28147-89

GOST 28147-89 is a block cipher with a 256-bit key and 32 conversion cycles, operating on 64-bit blocks. The crypto algorithm also uses an additional key, which is discussed below. For encryption, the plaintext is first split into left and right halves L and R. On the i-th cycle, the subkey K i is used:

L i = R i −1 ,
R i = L i −1 ⊕ (f (R i −1 , K i)).

The function f is implemented as follows. First, the right half and the i-th subkey are added modulo 2 32. The result is divided into eight 4-bit subsequences, each of which is input to its own S-box. GOST uses eight different S-boxes, the first 4 bits go into the first S-box, the second 4 bits into the second S-box, etc. Each S-box is a permutation of numbers from 0 to 15. For example, S-box might look like: 7,10,2,4,15,9,0,3,6,12,5,13,1,8,11. In this case, if the input of the S-box is 0, then the output is 7. If the input is 1, the output is 10, etc. All eight S-boxes are different, they are actually additional key material. The outputs of all eight S-boxes are combined into a 32-bit word, then the entire word is rotated left by 11 bits. Finally, the result is XORed with the left half to create a new right half, and the right half becomes the new left half. To generate subkeys, the original 256-bit key is divided into eight 32-bit blocks: k 1, k 2, ..., k 8. Each cycle uses its own subkey. Decryption is performed in the same way as encryption, but the order of the subkeys k i is inverted. The standard does not specify how S-boxes are generated.

Main differences between DES and GOST

The main differences between DES and GOST are as follows:

• DES uses a complex procedure to generate subkeys from keys. In GOST this procedure is very simple;
• in DES there is a 56-bit key, and in GOST it is 256-bit. If we add secret permutations of S-boxes, then the total volume of GOST secret information will be approximately 610 bits;
• DES S-boxes have 6-bit inputs and 4-bit outputs, while GOST S-boxes have 4-bit inputs and outputs. Both algorithms use eight S-boxes, but the size of the GOST S-box is equal to a quarter of the size of the DES S-box;
• DES uses irregular permutations called P-block, while GOST uses an 11-bit cyclic left shift;
• in DES there are 16 cycles, and in GOST - 32.

A forceful attack on GOST is absolutely futile. GOST uses a 256-bit key, and if you take into account secret S-boxes, the key length will be even greater. GOST appears to be more resistant to differential and linear cryptanalysis than DES. Although random GOST S-boxes, given some choice, do not guarantee high cryptographic strength compared to fixed DES S-boxes, their secrecy increases GOST's resistance to differential and linear cryptanalysis. In addition, the effectiveness of these cryptanalytic methods depends on the number of conversion cycles - the more cycles, the more difficult the cryptanalysis. GOST uses twice as many cycles as DES, possibly causing differential and linear cryptanalysis to fail.

GOST does not use the extension permutation existing in DES. Removing this permutation from DES weakens it by reducing the avalanche effect; It is reasonable to assume that the absence of such an operation in GOST has a negative impact on its cryptographic strength. From the point of view of cryptographic strength, the arithmetic addition operation used in GOST is no worse than the XOR operation in DES.

The main difference seems to be the use of cyclic shift instead of permutation in GOST. Rearranging DES increases the avalanche effect. In GOST, changing one input bit affects one S-box of one conversion cycle, which then affects two S-boxes of the next cycle, then three blocks of the next cycle, etc. It takes eight cycles before changing one input bit affects every bit of the output; in DES this requires only five cycles. However, GOST consists of 32 cycles, and DES only of 16.

The developers of GOST tried to achieve a balance between cryptographic strength and efficiency. Using Feistel's design as a basis, they developed a cryptographic algorithm that is better suited for software implementation than DES. To increase cryptographic strength, an extra-long key was introduced and the number of cycles was doubled. However, the question of whether the efforts of the developers were crowned with the creation of a more cryptographic algorithm than DES remains open.

Vorobyova E., Lukyanova A.

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

In general, an attack based on linear cryptanalysis boils down to the following conditions. The attacker has a large number 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. 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 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 clear 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.

Description of DES

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

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

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 a probability of 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.

Algorithm DES

The main advantages of the DES algorithm:

· only one key with a length of 56 bits is used;

· having encrypted a message using one package, you can use any other to decrypt it;

· the relative simplicity of the algorithm ensures high speed of information processing;

· sufficiently high stability of the algorithm.

DES encrypts 64-bit blocks of data using a 56-bit key. Decryption in DES is the reverse operation of encryption and is performed by repeating encryption operations in reverse order (despite the apparent obviousness, this is not always done. Later we will look at ciphers in which encryption and decryption are carried out using different algorithms).

The encryption process consists of an initial permutation of the bits of a 64-bit block, sixteen encryption cycles and, finally, a reverse permutation of the bits (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 Fig. 2.

Fig.2. 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 becomes bit 2, etc., which will give the result : T(0) = IP(T).

The resulting bit sequence T(0) is divided into two sequences of 32 bits each: L(0) - left or high-order bits, R(0) - right or low-order 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 obtaining keys K(i) is described below.

At the 16th iteration, the sequences R(16) and L(16) (without permutation) are obtained, which are concatenated into a 64-bit sequence R(16)L(16).

Then the positions of the bits of this sequence are rearranged in accordance with the matrix IP -1 (Table 2).

Table 2: Inverse permutation matrix IP -1

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 IP matrix element is equal to 2, etc.

The process of data decryption is inverse to the encryption process. All steps must be performed in reverse order. This means that the decrypted data is first rearranged according to the IP-1 matrix, and then the same actions are performed on the sequence of bits R(16)L(16) 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, the sequences L(0) and R(0) are obtained, which are concatenated into a 64-bit sequence L(0)R(0).

The bit positions of this sequence are then rearranged according to the IP matrix. The result of such a permutation is the original 64-bit sequence.

Now consider the encryption function f(R(i-1),K(i)). It is shown schematically in Fig. 3.

Fig.3. Calculation of function f(R(i-1), K(i))

To calculate the value of the function f, the following matrix functions are used:

E - extension of a 32-bit sequence to 48-bit,

S1, S2, ..., S8 - conversion of a 6-bit block into a 4-bit one,

P - permutation of bits in a 32-bit sequence.

The expansion function E is defined in Table 3. According to this table, the first 3 bits of E(R(i-1)) are bits 32, 1 and 2, and the last are 31, 32 and 1.

Table 3: 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 resulting 48-bit sequence 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. further clarification is 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. In column 13 of row 1 the value is 5. This means S1(011011)=0101.

Applying the selection operation to each of the 6-bit blocks B(1), B(2), ..., B(8), we obtain the 32-bit sequence S1(B(1))S2(B(2))S3( B(3))...S8(B(8)).

Finally, to obtain the result of the encryption function, the bits of this sequence must be rearranged. For this purpose, the permutation function P is used (Table 5). In the input sequence, the bits are rearranged 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 present the 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 control bits and rearrange the rest, function G of the initial key preparation 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 key K, and D(0 ) will consist of bits 63, 55, ..., 12, 4 of key K. After defining C(0) and D(0), C(i) and D(i), i=1...16, are recursively determined. To do this, apply a cyclic shift to the left by one or two bits, depending on the iteration number, as shown in Table 7.

Table 7

Shift table for key calculation

The resulting value is again “mixed” in accordance with the matrix H (Table 8).

Table 8: Key Completion 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)

Restoring the original text is carried out using this algorithm, but first you use the key

K(15), then K(14) and so on. Now you should understand why the author insistently recommends using the given matrices. If you go rogue, you might end up with a very secret code, but you won't be able to crack it yourself!

Operating modes of the DES algorithm

To most fully meet all the requirements for commercial encryption systems, several modes of operation of the DES algorithm are implemented. The most widely used modes are:

· electronic codebook (Electronic Codebook) - ECB;

· chain of digital blocks (Cipher Block Chaining) - CBC;

· digital feedback (Cipher Feedback) - CFB;

· external feedback (Output Feedback) - OFB.

In this mode, the source file M is divided into 64-bit blocks (8 bytes each): M = M(1)M(2)...M(n). Each of these blocks is encrypted independently using the same encryption key (Fig. 5). The main advantage of this algorithm is its ease of implementation. The disadvantage is that it is relatively weak against skilled cryptanalysts.

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 a data encryption algorithm (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 (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 n= 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.

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.

Next, the resulting 32-bit value is 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.