Introduction to Key Schedule by Prof. Paar.

Link to video on youtube

Accompanying Lecture Notes

DES Key Schedule - Theory

The DES key schedule genrates 16 round keys (or sub-keys) for the 16 encryption rounds. The sub-keys are derived out of the original 64-bit key given as an input.

Step 1: The original 64-bit key is reduced to 56-bit key using the PC-1 permutation table (Fig 1a). Note: Every 8th bit is ignored in the table(i.e. bits numbered 8, 16, 24, 32, 40, 48, 56, and 64). Nevertheless number the bits from 1 to 64, going left to right(Fig 1b).

Fig 1a: PC-1 Permutation table

Fig 1b: 64-bit key input bit description

Link to video on youtube

Step 2: Split the 56-bit Key in two 28-bit halves: Left - $ C_0 $ and Right - $ D_0 $(Refer Fig 2).

Fig 2: Key Schedule for DES encryption

Link to video on youtube

Step 3: With $ C_0 $ and $ D_0 $ defined, we now create sixteen blocks $ C_n $ and $ D_n $, $ 1≤n≤16 $ using following rules.

• In rounds i = 1,2,9,16 , the two halves are each rotated left by one bit.
• In all other rounds, where i ≠ 1,2,9,16 , the two halves are each rotated left by two bits.
• Total number of rotations 4*1 + 12* 2 = 28 which leads to an interesting property : $ C_0 $=$ C_{16} $ and $ D_0 $=$ D_{16} $.

Step 4: We now form the keys $ K_n $, for $ 1≤n≤16 $, by applying the PC-2 permutation table (Fig 3) to each of the concatenated pairs $ C_nD_n $ to generate 48-bit keys out of 56-bit bit $ C_nD_n $.

Fig 3: PC-2 Permutation table

The complete lecture video can be found here.

DES Key Schedule - Example

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.
• J. Orlin Grabbe, The DES Algorithm Illustrated.

Questions and comments

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

Back to 2015 Summer Cryptography Prof. Paar