DES - Overview and Encryption

A slecture on Cryptography by student Divya Agarwal and Katie Marsh

Partly based on the Cryptography Summer 2015 lecture material of Prof. Paar.


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


Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett