DES cipher, Algorithm

DES (Data Encryption Standart) - A symmetric encryption algorithm in which one key is used, both for encrypting and decrypting data. DES was developed by IBM and approved by the US government in 1977 as an official standard (FTPS 46-3). DES has blocks of 64 bits and 16 cycle structure of the Feistel network, uses a key with a length of 56 bits for encryption. The algorithm uses a combination of non-linear (S-blocks) and linear (permutations E, IP, IP-1) transformations. For DES recommended several modes:
electronic codebook mode (ECB - Electronic Code Book),
Cipher Block Chaining (CBC),
ciphertext feedback mode (CFB - Cipher Feed Back),
Output Feed Back (OFB) mode.
Block cipher
The input data for the block cipher is a block of n bits and a k-bit key. At the output, after applying the encryption transform, an n-bit encrypted block is obtained, and minor differences in the input data usually lead to a significant change in the result. Block ciphers are implemented by repeatedly applying to the blocks of the source text of some basic transformations.
Basic transformations:
Complicated conversion on one local part of the block.
Simple conversion between parts of a block. Since the conversion is performed block by block, as a separate step, it is necessary to divide the source data into blocks of the required size. In this case, regardless of the format of the source data, be it text documents, images or other files, they must be interpreted in a binary form and only after that are they divided into blocks. All of the above can be done by software, as well as by devices.

Feistel Network Transformations
This transformation is over the vectors (blocks) representing the left and right halves of the shift register. The DES algorithm uses a direct network transformation of Feistel in encryption (see Fig. 1) and a reverse transformation of a network of Feistel in decryption (see Fig. 2).

DES encryption scheme

The source text is a 64 bit block.
The cipher text is a block of 64 bits.

The encryption process consists of an initial permutation, 16 cycles of encryption, and a final permutation.
Consider a detailed scheme of the DES algorithm:
LiRi = 1,2ldots. Left and right half of a 64-bit LiRi block
ki - 48 bit keys
f - encryption function
IP - initial permutation
IP-1 is the final permutation.

According to the table, the first 3 bits of the resultant IP block (T) after the initial IP permutation are bits 58, 50, 42 of the input block T, and its 3 last bits are bits 23, 15, 7 of the input block. Next, the 64-bit IP block (T) participates in a 16-cycle Feistel transformation.

- 16 Feistel transformation cycles:

Split IP (T) into two parts L0, R0, where L0, R0 - respectively 32 high bits and 32 low bits of the block T0 IP (T) = L0R0

Let Ti -1 = Li -1Ri -1 result (i-1) iteration, then the result of the i-th interaction Ti = LiRi is determined:

Li = Ri - 1

The left half of Li is equal to the right half of the previous vector Li - 1Ri - 1. And the right half of Ri is the bit addition of Li - 1 and f (Ri - 1, ki) modulo 2.

In 16-cycles of the Feistel transform, the function f plays the role of encryption. Let us consider in detail the function f.

The arguments of the function f are the 32 bit vector Ri - 1, 48 bit key ki, which are the result of the conversion of the 56 bit source key of the cipher k.

To calculate the function f, the function E is used, the transformation S, consisting of 8 S-block transformations, and the permutation P.

Function E expands 32 bit vector Ri - 1 to 48 bit vector E (Ri - 1) by duplicating some bits from Ri - 1, and the order of bits of vector E (Ri - 1) is specified in Table 2.

The first three bits of the vector E (Ri - 1) are bits 32, 1, 2 of the vector Ri -1. In Table 2 it can be seen that bits 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29, 32 are duplicated. The last 3 bits of the vector E (Ri - 1) are bits 31, 32, 1 of the vector Ri - 1. The block E obtained after the permutation (Ri -1) is added modulo 2 with the keys ki and then represented as eight consecutive blocks B1, B2, ... B8.
E (Ri - 1) = B1B2 ... B8
Each Bj is a 6-bit block. Next, each of the Bj blocks is transformed into a 4-bit B'j block using Sj transforms. The transformations of Sj are given in Table 3.

Suppose that B3 = 101111 and we want to find B'3. The first and last digits of B3 are the binary notation of the number a, 0 <= a <= 3, the middle 4 digits represent the number b, 0 <= b <= 15. The rows of table S3 are numbered from 0 to 3, the columns of table S3 are numbered from 0 to 15. The pair of numbers (a, b) defines the number found at the intersection of row a and columns b. The binary representation of this number gives B'3. In our case, a = 112 = 3, b = 01112 = 7, the number is determined by the pair (3.7) is 7, it follows B'3 = 0111.
The value of the function f (Ri - 1, ki) (32 bits) is obtained by rearranging P applied to the 32 bit block B'1B'2 ... B'8. The permutation P is given in table 4.

f (Ri - 1, ki) = P (B'1B'2 ... B'8)
According to Table 4, the first four bits of the result vector after the action of the function f are bits 16, 7, 20, 21 of the vector B'1B'2 ... B'8

Key generation ki.
The keys ki are obtained from the initial key k (56 bits = 7 bytes or 7 characters in ASCII) in this way. Eight bits that are in positions 8, 16, 24, 32, 40, 48, 56, 64 are added to the key k in such a way that each byte contains an odd number of ones. It is used to detect errors in the exchange and storage of keys. Then make a permutation for the extended key (except for the added bits 8, 16, 24, 32, 40, 48, 56, 64). Such a permutation is defined as in table 5.

This permutation is determined by two blocks C0 and D0 of 28 bits each. The first 3 bits of C0 are bits 57, 49, 41 of the extended key. And the first three bits of D0 are bits 63, 55, 47 of the extended key. Ci, Di i = 1,2,3 ... are obtained from Ci - 1, Di - 1 by one or two left cyclic shifts according to table 6.

The key ki, i = 1, ... 16 consists of 48 bits selected from the bits of the vector CiDi (56 bits) according to table 7. The first and second bits of ki are bits 14, 17 of the vector CiDi

The final permutation of IP - 1 acts on T16 and is used to restore the position. It is the inverse of the IP permutation. The final permutation is determined by table 8.

DES usage modes
DES can be used in four modes.
Electronic Code Book mode (Electronic Code Book): the usual use of DES as a block cipher (see Figure 7).

Cipher Block Chaining mode (see Fig.8). Each regular block Ci i> = 1, before encoding, is folded modulo 2 with the next plaintext block Mi + 1. Vector C0 is the initial vector, it changes daily and is kept secret.

The ciphertext feedback mode (CFB - Cipher Feed Back) (see Fig.9). In the CFB mode, a block “gamma” Z0, Z1, ... Zi = DESk (Ci - 1) is produced

. The initial vector C0 is kept secret.

Output Feed Back Mode (OFB) (see Figure 10). In OFB mode, a block "gamma" Z0, Z1, ...

, i> = 1

The ECB mode is simple to implement, but it is possible to perform a cryo-analysis
In ECB and OFB modes, when transmitting a single 64-bit block of ciphertext Ci, a distortion occurs after decryption of only the corresponding open block Mi, therefore such modes are used for transmission over communication channels with a large number of distortions.
In CBC and CFB modes, when transmitting one block of Ciphertext text, distortion of no more than two plaintext blocks Mi, Mi + 1 on the receiver. Changing Mi leads to changing all other Mi + 1, Mi + 2 blocks ... This property is used to generate message authentication code.