3
$\begingroup$

I am reading over a slide that I found online regarding the DES algorithm for encryption and I am a little confused about the per round key generation. From the slide below, I understand that each per round key is obtained by shifting left either 1 or 2 bits depending on the round. The thing I do not understand is the permutations for Left half C_i and right half D_i

In the slide, it says that the left half C_i is 14 17 11 24 1 5 3 28 15 6 21 19 23 19 12 4 26 8 16 7 27 20 13 2. Are the numbers in this example random? A textbook I am reading also uses the same numbers for round C_i and I cannot see the connection here. C_0 does not contain 14, so I am not really sure how left shifting bits causes the 14 from D to go to C. Am I misunderstanding the problem here?

Slide

$\endgroup$
  • $\begingroup$ keytab.c, keytab -s outputs key tables shown as CD reg bits shows the round keys, which have 24 of 28 bits derived independently from each of C and D via PC2 (Permuted Choice 2). Was written to replicate tables found in Metyas and Meyers Cryptography. See DES Key Schedule Algorithm $\endgroup$ – user1430 Feb 24 '16 at 1:31
  • $\begingroup$ I'm still not really understanding this, DES was a topic that we covered in class recently. I just wanted to know where the 14 in C_i came from. $\endgroup$ – Rowen McDaniel Feb 24 '16 at 6:52
  • $\begingroup$ Related question. $\endgroup$ – fgrieu Feb 24 '16 at 20:13
3
$\begingroup$

Numbers $\{14,17,11,24,1,5,3,\dots\}$ come from permuted choice PC-2. So let me explain 16 round DES key scheduling:

DES input key size is 64 bit which contains 56 bit key and 8 parity bits. Parity bits are 8th bit of every 8 bits (on byte). So they are all multiple of eight: $\{8, 16, 24, 32, 40, 48, 56, 64\}$. Permuted choice PC-1 is used to remove these bits from the 64 bit input key. So PC-1 gives 56 bits as output.

In round $i\ (1 \le i \le 16)$, there is a 56 bit input, $C_{i-1}$ as left half and $D_{i-1}$ as right half (each 28 bits). These two halves are rotated left (for decryption, right rotate is used). For encryption, rotate amount in rounds $\{1, 2, 9, 16\}$ is one and in other rounds it's two. For decryption, one bit right rotation in rounds $\{2,9,16\}$ and two bit right rotation in all other rounds. As inputs of rotation are $C_i$ and $D_i$, outputs of rotation are $C_{i+1}$ and $D_{i+1}$ which are passed to the next round ($i+1$) as input.

After all, in round $i$ there is a 48 bit output, named $K_i$. This sub key is generated from permuted choice PC-2, which takes $C_i$ and $D_i$ as a 56 bit input and outputs the sub key.

Now i think now you understood where those numbers come from. The overall process is illustrated in the picture below (Encryption):

DES encryption

Image Source: Understanding Cryptography by Christof Paar and Jan Pelzl, Chapter 3

$\endgroup$
  • $\begingroup$ From what I understand, in PC-2 the numbers are defined by the DES algorithms? Each of the 16 rounds would permute the 14th bit to the first position, 17th bit to the second position, ... and so on for each round? $\endgroup$ – Rowen McDaniel Feb 24 '16 at 21:54
  • $\begingroup$ yes, they are defined in the algorithm. $\endgroup$ – Mehran Torki Feb 25 '16 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.