Data Encryption Standard

• DES is a symmetric key block cipher published by NIST (National institute of Standards & Technologies)
• DES is an implementation of a Fiestal cipher.
• It has a 64-bit block size, a 64-bit key length & uses 16 rounds.
• DES has an effective key length of 56 bits, since 8 of the 64 bits are not used by the encryption algorithm (they are check bits)

• Since fiestal cipher blueprint is used for DES, all that is required is to fully specify DES is –

  • The round function: which is based on taking groups of input bits & replacing (substituting) them according to some rules based on tables known as S-boxes.
  • The key structure: which identifies which bits of the key are used to form the subkeys for any given round.
  • Any additional processing steps: for eg. DES conducts an initial permutation of all i/p bits before the first encryption round begins & then performs the inverse of this permutation to all the output bits immediately after the last encryption round has been completed.

Thus DES consists of :

1. General Structure of DES
2. Initial and final Permutations
3. Rounds
4. DES Function 5.Key generation

1.General Structure of DES

• The encryption process is made of two permutations (P-boxes), which are called Initial and final permutations and six Fiestal rounds. Each round uses a different 48-bit round key generated from the cipher key according to a predefined algorithm. The figure below the elements of DES cipher at the encryption site.

2. Initial and Final permutation:

• These are straight permutation boxes (p-boxes) that are inverse of each other. They have no cryptography significance in DES. The initial & final permutation is as shown below.

• Each of these permutations takes a 64-bit i/p and permutes them according to a predefined rule.

• for eg. in the initial permutation, the 1st bit in the input becomes the 40th bit in the output. Similarly, in the final permutation, the 40th bit in the input becomes the 1st bit in the output. In other words, if the rounds between these two permutations do not exist, the 1st bit entering the initial permutation is the same as the 40th bit leaving the final permutation.

3. Rounds:

• The DES uses 16 rounds.
• Each round of DES is a Feistal Cipher
• The round takes $L_{I-1}$ and $R_{I-1}$ from the previous round(or the initial permutation box if that is the first round) and creates $L_{I}$ and $R_{I}$,which go to next round(or final permutation box if that is the last round). Each round has two cipher elements(mixer and swapper).Each of these elements is invertible. The swapper swaps the left half of the text with the right half. The mixer is invertible because of the XOR operation.

4.DES function

DES function is the most important part of DES. It applies a 48-bit key to the rightmost 32 bits ($R_{I-1}$) to produce a 32-bit output.

This function is comprised of four parts as shown in the figure below

• An expansion box

• An XOR function

• A group of S-boxes

• A straight D-box

Expansion D-box:

• As i/p $R_{I-1}$ is 32 bit & round key is of 48-bit, we need to expand the right input to 48 bits.

• $R_{I-1}$ is divided into 8 4-bit sections.

• Each 4-bit section is expanded to 6-bit. It follows the predetermined rules. For each section, input bits 1,2,3 and 4 are copied to output bits 2,3,4 and 5. Output bit 1 comes from the 4th bit of the previous section,output bit 6 comes from the 1st bit of the next section. If sections 1 and 8 can be considered adjacent to each other the same rules can be applied to bits 1 and bit 32 as shown in fig below.

XOR Operation:

After expansion permutation, DES does XOR operation on the expanded right section & the round key. The round key is used only in this operation.

Substitution boxes:

• The S-boxes carry out the real mixing
• DES uses S-boxes, each with 6-bit input and a 4-bit output.

There are total 8 S-box tables. The o/p of all eight S-boxes is then combined in to a 32-bit section.

The 48-bit data from the XOR operation is divided into 8 6-bit sections and each section is given to one S-box.

The result of each S-box is 4-bit section when these results are combined final 32-bit text is obtained.

The substitution in each box follows the predetermined rule based on a 4-row and 16-column table.The combination of bits 1 and 6 of the input defines one of the four rows, the combination of bits 2,3,4 and 5 defines one of the 16 columns as shown in the figure below.

Each S-box has its own table, so total of 8 tables for 8 S-boxes. The values in these tables are stored in decimal numbers.

for example:

Input to the S- box1 is 100011

1st and 6th bit are combined together which forms "11" which in 4 bit binary is 3 in decimal, so we look for the value in row 3 of S-Box 1 table

Now take the remaining bits "0001" whose equivalent binary is 1 in decimal,so we look for the value in column 1 of S-Box 1 table.

So, then the result is again a decimal number calculate its binary.suppose the S-box 1 table has entry 12 in decimal in position (3,1) so output will be 4-bit "1100" for 6-bit "100011".

Straight D box: The 32-bit o/p of the S-boxes then subjected to the straight permutation which transposes the bits.

5. Key Generation: The round key generation creates 48-bit keys out of 56-bit cipher Key.

Normally given as a 64-bit key in which 8 extra bits are the parity bits,which are dropped before the actual key-generation process.

Process of key generation is as follows-

Parity Drop: It drops the parity bits (8,16,24,32,40,48,56,64) from the 64-bit key and permutes the rest of the bits according to the predefined table.

Shift Left:

• After the straight permutation, the key is divided into 2 28-bit parts
• each part is shifted left (circular shift)one or two bits.
• In round 1,2,9,16 shifting is one bit and in other rounds, it is 2 bits
• The two parts are then combined to form a 56- bit part.

Compression D Box: This box changes the 56-bits to 48 bits, which are used as a key for a round.