2015 Summer Cryptography Paar Divya Agarwal - Rhea

Overview of DES Algorithm

Fig 1: Overview of the DES Algorithm

• DES is a Symmetric cipher: uses same key for encryption and decryption
• Uses 16 rounds which all perform the identical operation
• Different subkey(48 bit) in each round derived from main key

Internal structure of DES

1. Initial Permutaion(IP) : This is the first thing that is seen in the expanded view of DES block in Fig 1.

• IP is a bitwise permutation or simple crosswiring in hardware.
• The corsswiring is done according to the table(left) given in Fig 2.
• The IP has no effect on the DES security at all.

Fig 2: Initial Permutation(left) and the Final Permutation(right) tables

2. DES Encryption Round - Feistel Networks

• DES structure is a Feistel network
• Advantage: encryption and decryption differ only in keyschedule( explained later )

Fig 3: Encryption block round 1 - Feistel Networks

• The encryption block for round 1 in Fig 3 takes an input of 64 bit data permuted in the IP
• Plaintext is split into 32-bit halves $ L_i $ and $ R_i $
• $ R_i $ is fed into the function f, the output of which is then XORed with $ L_i $
• Left and right half halves are swapped at the end of one encryption round
• Each encryption round can be expressed as :

$ L_i = R_{i-1} $

$ R_i = L_{i-1} \oplus f(R_{i-1},k_i) $

Fig 4: Encryption block final round - Feistel Networks

• And as seen in Fig 1, we have sixteen such rounds.
• And the Left and Right side bits are swapped again before the Final Permutation(FP) as shown in Fig 4.

3. The f-funtion(inside the feistel network)

Fig 5: The f-function block

• Main operation of DES
• Inputs to f function are $ R_{i-1} $ and round key $ k_i $
• It has 4 main steps in Fig 5 :

 ** Expansion block E
 ** XOR with round key
 ** S-box substitution (eight of them)
 ** Permutation

3.1 The Expansion fucntion E

• The main purpose of the expansion funtion is to increase diffusion in the input $ R_{i-1} $ bits.
• It is done using the table shown in Fig 6.

Fig 6: The expansion block table(top) and bitwise explanation(bottom)

3.2 XOR with round key

• Bitwise XOR of the round key $ k_i $ and the output of the expansion function E
• We take a 48-bit expanded message bit and XOR with 48-bit key input and the output data is also 48-bit (Fig 5)

[Round keys are derived from the main key in the DES keyschedule later in the notes]

3.3 The DES S-Box substitution

• Eight substitution tables which form the core security of DES (Refer book)
• Take 6 bits of input and gives 4-bit output
• Non-linear and resistant to differential cryptanalysis

3.4 The Permutation P

• This is the last step in the f-fucntion in Fig 5.
• It is also bitiwse permutation, which introduces diffusion using the table in Fig 7.
• Output bits of one S-Box effect several S-Boxes in next round.
• Diffusion by E, S-Boxes and P guarantees that after Round 5 every bit is a function of each key bit and each plaintext bit.

Fig 7: The Permutation table P

The complete lecture on DES by Prof. Paar can be found here.

References

• C. Paar. Understanding Cryptography. Lecture Notes. Dept. of Electr. Eng. and In­for­ma­ti­on Sci­en­ces, Ruhr University.
• C. Paar and J. Pelzl. Understanding Cryptography. A textbook for Student and Practitioners. Springer 2010.

Questions and comments

If you have any questions, comments, etc. please post them here.

Back to 2015 Summer Cryptography Paar