2
$\begingroup$

Does anyone have a pseudo-code or an algorithm or even a diagram of the compression (pc2) of the DES algorithm?

I can't find a relation between the bits that are dropped, even when I do it manually it does not generate the right result. I mean put as the first bit of the output (subkey $K_i$) the 14th bit of $C$, the 2nd of the output is the 17th of $C$.. the 25th bit of the output is the 41th of $D$.

Is the above correct or did I misunderstand?

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Anything wrong with the explanation and drawing in Wikipedia? Notice that in DES, the convention is that the bits are numbered from 1 onwards, with 1 being the first or left bit, or the most significant bit of in the big-endian translation to integer of a bitstring, or the most significant bit in the first or left octet in an octet string. Also, the output of PC2 is subdivided into 8 bitstrings of 6 bits (hence the presentation of the table as 8 lines of 6 entries), corresponding to S1 thru S8. $\endgroup$
    – fgrieu ♦
    Feb 7 '16 at 13:37
  • 1
    $\begingroup$ Exactly i didn't understand it @fgrieu ,the drawing seems random, and so the bits that are dropped :9,18, 22, 25 ,35 ,38 ,43 and 54. I understand the substitution phase when we should subdivide the 48bit input to 8 blocks of 6 bits in order to have 8 blocks of 4 bits instead, but that comes later. I'm struggling with how to get the 48 bit subkey from the combination of 28 bit C and D. The substitution comes after we do an XOR of Ki with the expanded Ri. $\endgroup$
    – Balkis
    Feb 7 '16 at 14:18
  • 1
    $\begingroup$ Running an open-source implementation under debugger might be a (hard) way to learn it. $\endgroup$
    – Vadym Fedyukovych
    Feb 7 '16 at 15:20
0
$\begingroup$

The PC-2 substitution transforms the 56-bit concatenation of the 28-bit $C$ and $D$ after they have been appropriately rotated, into the 48-bit subkey $K_i$ for round $i$, before that is combined using XOR with the 48-bit output of expansion $E$ and divided into 6-bit entries for each of the 8 S-tables. The table defining PC-2 is correspondingly organized as 8 lines of 6 values in the defining standard.

14  17  11  24   1   5
 3  28  15   6  21  10
23  19  12   4  26   8
16   7  27  20  13   2
41  52  31  37  47  55
30  40  51  45  33  48
44  49  39  56  34  53
46  42  50  36  29  32

The $j^\text{th}$ integer in the table when scanned in reading order is the index of the bit in the input corresponding to the $j^\text{th}$ bit in the output (in DES, the convention is that the bits are numbered from 1 onwards, with 1 being the first or left bit, or the most significant bit in the first or left octet in an octet or quartet string, with octets and quartets expressed in big-endian hexadecimal).

Hence integers 1..28 in the table corresponds to bits from $C$ (and happen to be directed towards the first 4 S-boxes); and the others corresponds to bits from $D$ (going to the other S-boxes).

In other words, we form the first 24 bits of the output by taking the 14th, 17th, 11th .. 13th and 2nd bits of $C$; and the next 24 bits of the output by taking the 13th, 24th, 3rd.. 1st and 4nd bits of $D$ (we subtract 28 from the integers above 28 to get the index in $D$ ).

Integers 9 18 22 25 and 35 38 43 54 are not in the table; they correspond to bits of $C$ and $D$ that are not used in this round (but have or will be in the previous or next round, if any, due to the combination of the shift counts used with PC-2).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Okay i guess i understand that, so as an algorithm i have to do subkey [1]<- C[14], subkey [2]<- C[17].. subkey[25]<-D[13] ? i can't do it otherwise? using the index as a variable, in order to write it in a loop for example? $\endgroup$
    – Balkis
    Feb 8 '16 at 9:54
  • $\begingroup$ @Abir: generic pseudocode: for j from 1 to 48 output[j] := input[pc2[j]]. Actual code will very much depend on language, array base index, representation of variables. $\endgroup$
    – fgrieu ♦
    Feb 8 '16 at 11:59

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.