Symmetric Cryptography: Data Encrypton Standard（DES)

Symmetric Cryptography: Data Encrypton Standard（DES）

Overview

Here is a black box of DES:

des_black_box

Now we want to open the box to see what happened inside. The box consisits of three sub-modules:

fist_layer_of_des

When the plain text goes into the black box, it should first be permutated, i.e., shift the order of the bits. The word “permutaion” means bit re-arrangement, for example, the permutation [4 1 2 3] means that:

  • The fourth input bit becomes the first output bit.
  • The first input bit becomes the second output bit.
  • The second input bit becomes the third output bit.
  • The second input bit becomes the third output bit.

After the initial permutation, the plaintext goes into the Feistel cipher module. Feistel cipher is a way of doing block ciphers, which I will talk in detail later.

The last module is final permutation. Similar to initial permutation, there is also some bit re-arrangements. Following the encryption process, we can get the ciphertext.

DES Feistel cipher

Now we focus on Feistel cipher:

feistel_cipher_1

Feistel cipher consists of 16 round, each round uses a subkey computed by so-called key schedule. The key schedule process is shown as follows:

des_key_schedule

Each round works as follows:

  • Split input in half
  • Apply Feistel function to the right half
  • Compute XOR of result with old left half to be new left half
  • Swap old right and new left half, unless we are in the last round

feistel_cipher_2

DES Feistel function

des_feistel_function

Now we focus on a deeper layer of DES, i.e., Feistel function. Feistel function consists of four procedures:

  1. Expansion permutation: Expand 32-bit message half block to 48 bit block by doubling 16 bits and permuting them.

  2. Round key addition: Compute XOR of this 48 bit block with round key Ki.

  3. S-Box: Split 48 bit into eight 6-bit blocks. Each of them is given as input to eight substitution boxes, which substitute 6-bit block by 4-bit block. An S-box substitution is a table lookup. Input is 6 bit, output is 4 bit. S-Box works as follows:

    • Strip out outer bits of input and join them. This two-bit number is the row index.
    • Four inner bits indicate column number.
    • Output is corresponding entry in table.

For example, if we have a 6-bit block 0 1 1 0 1 1, of which the outer bits is 0 1, and the inner bits is 1 1 0 1. By looking up the table, we can output a 4-bit block 1 0 0 1.

s_box

  1. P-Box: Combine these eight 4-bit blocks to 32-bit block and apply another permutation.

Confusion and Diffusion

The design of DES aims to provide confusion and diffusion.

Confusion means that each bit of the ciphertext should depend on several parts of the key, obscuring the connections between the two. In another word, the process of producing the ciphertext by using the key is so complex that the ciphertext gives no clue about the plaintext. A substitution can provide confusion.

A secure cipher should also provide something else, which we called diffusion. Diffusion means that if we change a single bit of the plaintext, then (statistically) half of the bits in the ciphertext should change. A permutaton can provide diffusion.

DES_supplementary_material