How was PC2 designed?

Question

I am trying to understand DES. Can anyone explain the table given in one of the answer DES Key Schedule Algorithm. My question is from where the first entry of Ks comes from. i.e 15 18 12 25 2 etc

  Bit  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
KS
   1  15 18 12 25  2  6  4  1 16  7 22 11 24 20 13  5 27  9 17  8 28 21 14  3
   2  16 19 13 26  3  7  5  2 17  8 23 12 25 21 14  6 28 10 18  9  1 22 15  4
   3  18 21 15 28  5  9  7  4 19 10 25 14 27 23 16  8  2 12 20 11  3 24 17  6
   4  20 23 17  2  7 11  9  6 21 12 27 16  1 25 18 10  4 14 22 13  5 26 19  8
   5  22 25 19  4  9 13 11  8 23 14  1 18  3 27 20 12  6 16 24 15  7 28 21 10
   6  24 27 21  6 11 15 13 10 25 16  3 20  5  1 22 14  8 18 26 17  9  2 23 12
   7  26  1 23  8 13 17 15 12 27 18  5 22  7  3 24 16 10 20 28 19 11  4 25 14
   8  28  3 25 10 15 19 17 14  1 20  7 24  9  5 26 18 12 22  2 21 13  6 27 16
   9   1  4 26 11 16 20 18 15  2 21  8 25 10  6 27 19 13 23  3 22 14  7 28 17
  10   3  6 28 13 18 22 20 17  4 23 10 27 12  8  1 21 15 25  5 24 16  9  2 19
  11   5  8  2 15 20 24 22 19  6 25 12  1 14 10  3 23 17 27  7 26 18 11  4 21
  12   7 10  4 17 22 26 24 21  8 27 14  3 16 12  5 25 19  1  9 28 20 13  6 23
  13   9 12  6 19 24 28 26 23 10  1 16  5 18 14  7 27 21  3 11  2 22 15  8 25
  14  11 14  8 21 26  2 28 25 12  3 18  7 20 16  9  1 23  5 13  4 24 17 10 27
  15  13 16 10 23 28  4  2 27 14  5 20  9 22 18 11  3 25  7 15  6 26 19 12  1
  16  14 17 11 24  1  5  3 28 15  6 21 10 23 19 12  4 26  8 16  7 27 20 13  2

  Bit 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
KS
   1  42 53 32 38 48 56 31 41 52 46 34 49 45 50 40 29 35 54 47 43 51 37 30 33
   2  43 54 33 39 49 29 32 42 53 47 35 50 46 51 41 30 36 55 48 44 52 38 31 34
   3  45 56 35 41 51 31 34 44 55 49 37 52 48 53 43 32 38 29 50 46 54 40 33 36
   4  47 30 37 43 53 33 36 46 29 51 39 54 50 55 45 34 40 31 52 48 56 42 35 38
   5  49 32 39 45 55 35 38 48 31 53 41 56 52 29 47 36 42 33 54 50 30 44 37 40
   6  51 34 41 47 29 37 40 50 33 55 43 30 54 31 49 38 44 35 56 52 32 46 39 42
   7  53 36 43 49 31 39 42 52 35 29 45 32 56 33 51 40 46 37 30 54 34 48 41 44
   8  55 38 45 51 33 41 44 54 37 31 47 34 30 35 53 42 48 39 32 56 36 50 43 46
   9  56 39 46 52 34 42 45 55 38 32 48 35 31 36 54 43 49 40 33 29 37 51 44 47
  10  30 41 48 54 36 44 47 29 40 34 50 37 33 38 56 45 51 42 35 31 39 53 46 49
  11  32 43 50 56 38 46 49 31 42 36 52 39 35 40 30 47 53 44 37 33 41 55 48 51
  12  34 45 52 30 40 48 51 33 44 38 54 41 37 42 32 49 55 46 39 35 43 29 50 53
  13  36 47 54 32 42 50 53 35 46 40 56 43 39 44 34 51 29 48 41 37 45 31 52 55
  14  38 49 56 34 44 52 55 37 48 42 30 45 41 46 36 53 31 50 43 39 47 33 54 29
  15  40 51 30 36 46 54 29 39 50 44 32 47 43 48 38 55 33 52 45 41 49 35 56 31
  16  41 52 31 37 47 55 30 40 51 45 33 48 44 49 39 56 34 53 46 42 50 36 29 32

Answer 1

They are the output of PC2s during the key schedule. PC2 table;

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

Let's look at only the $C$ register map. The $D$ register map will be similar.

Let number the output of PC1's first half as;

   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Now the outputs can be calculated as;

   1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 - index

   2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  1 - rotate 1 PC1's first half to left
  14 17 11 24  1  5  3 28 15  6 21 10 23 19 12  4 26  8 16  7 27 20 13  2 - apply PC2 left half 
  15 18 12 25  2  6  4  1 16  7 22 11 24 20 13  5 27  9 17  8 28 21 14  3 - get this

   3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  1  3 - rotate 1 to PC1's first half left
  14 17 11 24  1  5  3 28 15  6 21 10 23 19 12  4 26  8 16  7 27 20 13  2 - apply PC2 left half
  16 19 13 26  3  7  5  2 17  8 23 12 25 21 14  6 28 10 18  9  1 22 15  4 - get this

Note that sometimes you will see rotate left 2 since the rotate amount is defined in the key schedule according to round number as;

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline \text{Number of Round } & 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16\\ \hline \text{Number of Left rotations} & 1&1&2&2&2&2&2&2&1&2&2&2&2&2&2&1\\ \hline \end{array}

Answer 2

Per this comment, it is asked how PC2 was designed.

PC2 is the last component of the transformation from the 64-bit DES key to the 48-bit subkeys of each of the 16 rounds. We examine the components of that transformation.

The 64-bit DES key is first reduced by PC1 to a 56-bit CD value. This is a compromise between the IBM designers (wanting a large key for security, initially 128-bit, then 64-bit) and the NSA (wanting to be able to crack DES by brute force at reasonable cost if necessary and thus pushing for 48-bit key); see this for an historical account.

CD is split into C and D each 28-bit, and each is rotated per the key rotation schedule, rotating each of C and D by 1 or 2 bits depending on round number. PC2 then selects 48 bits from the rotated CD.

Accordingly, when we mentally put the two tables in the question side by side (removing the Bit columns), then in the resulting Key Selection Table (hereafter KST) each of the 16 lines contains 48 integers, which are the numbers in CD of the bits that form the subkey for the round corresponding to that line of the KST. The first line is one more than PC2 (with 19 replaced by 1, and 57 replaced by 19, to account for rotation in C and D). Next lines are obtained by repeating that addition process one or twice, depending on the key rotation schedule. That process ends with the last line equal to PC2 (which simplifies using the same circuitry for decryption and encryption).

Within the limited effective key size of 56 bits, the design of PC2 tries to make DES as secure as possible. Towards that goal, the combination of the key rotation schedule and PC2 is such that:

• Bits of C are segregated to S-boxes 1..4 and bits of D to S-boxes 5..8 (the first half of PC2 contains integer in 1..28, while the second contains integers in 29..56).
  _{I can only speculate that's in order to simplify the design of something: PC2, E, P, and/or S-boxes per some criteria, a simulation, chip layout?}
• A key bit is never used twice in a round (there is no duplicate in PC2, equivalently in any line of the KSC).
• A key bit that was not used in a round is always used in the next and previous round (if an integer in [1,56] is not in a line of the KST, then it is in the next and previous lines).
• If two bits enter the same S-table in a round, then they do not in the next and previous few rounds (if we divide the 48 numbers in each line of the KST in 8 blocks of 6, then any pair of numbers in a block do not appear in the same block in the next and previous few lines).

_{I looked at Don Coppersmith's The Data Encryption Standard (DES) and its strength against attacks (IBM journal, 1994). It states rationale for the S-boxes and expansion E, but not PC2. So far I failed to find a reference that does. It is conceivable that PC2 and E are co-optimized for fast diffusion.}

Answer 3

See The Block Cipher Companion, Knudsen & Robshaw, © Springer-Verlag 2011, Chap 2 DES, 2.2 Design Features, P. 26:

Turning to the key schedule, the design principles are not public and it is probably fair to say that it is still not fully understood (at least publicly). However, a few properties are recognised.

For instance, the sum of the rotation amounts r1, ..., r16 for the C and D registers is equal to 28. This is no coincidence and at the end of an encryption the registers C and D are back at their initial state. The registers are ready for the next encryption. It is also interesting to note that the key schedule can be reversed for decryption, with the register rotations being applied in the opposite directions (to the right).

There is a somewhat irregular appearance to the rotations by one or two bit positions. In particular it may seem odd that the rotation amount in the ninth round is 1. The plausible explanation is that this irregularity avoids the existence of so-called related keys; see Sect. 8.5. If, for example, all rotations in the key schedule of DES were set to 2, then the pair of keys k and k∗, where k∗ is equal to k rotated by two positions, would have many round keys in common [46, 45]. If, for example, the rotation amounts for r9 and r15 were swapped then there would also be many pairs of keys having many round keys in common [385].

Clearly, each bit in a round key corresponds to a bit from the user-supplied key. Table 2.3 listed the 16 round keys in terms of the bits in the user-supplied key. Note, however, that the key bits of the user-supplied key do not appear equally often in the set of round keys. The frequencies of bits is given in Table 2.6 and we see that some bits occur in only 12 round keys, whereas others are used in 13, 14, and even 15 round keys. Since there are 48 bits in a DES round key, a round key cannot depend on all of the user-supplied key. It is interesting to observe that, for any pair of round keys, at least 54 bits of the (effective) key bits appear in one or both round keys. However, inspection of Table 2.3 reveals that all 56 (effective) key bits appear in either the first, or the last round key, or in both. This can have some consequence for a more advanced form of cryptanalysis, see Chap. 8, and it is a property that does not hold for any other pair of round keys.

The mentioned Table 2.3 is that produced by keytab -s in the OP's referenced question.

Two characteristics of PC2 not mentioned therein are the C and D influence separation for S Boxes 1-4 and 5-6 respectively and that the tap-offs in each of PC2_C and PC2_D are not in linear order. You might suspect these relate to security against an as yet publicly unrecognized cryptanalysis technique.

Earlier in 2.2 Design Features it's reported that the non-linear S Boxes and P Permutation add strength against differential cryptanalysis:

After the publication of differential cryptanalysis [81] it became clear that both the S-boxes as well as the expansion E and the permutation P were designed to increase the resistance of DES to this attack. This was confirmed in [167]. However, it is not clear whether the DES designers were aware of linear cryptanalysis [476, 475], see Chap. 7, which gives the fastest analytical attacks on DES.

There were other design criteria than those given above for the S-boxes, the P permutation, and the E expansion. It is worth observing that if we were to pick the contents of the DES S-boxes at random, we would almost certainly have a weaker cipher. In fact, even if we were to consider the 8! = 40, 320 possible orderings of the S-boxes (with the contents of the S-boxes being unchanged) for the vast majority of orderings the resultant cipher would be weaker than DES. Thus it is not only the contents of the S-boxes that matter, but also their position within the algorithm. Other criteria considered the avalanche of change and the ciphertext bits depend on all plaintext bits and on all key bits after five rounds of encryption [498]. A range of statistical tests was also conducted [414].

81.    E. Biham and A. Shamir. Differential Cryptanalysis of the Data Encryption Standard. Springer, 1993. 

167.    D. Coppersmith. The Data Encryption Standard and its strength against attacks. IBM Technical Report, RC18613 (81421), December 1992.  

414.    A. G. Konheim. Cryptography: A Primer. John Wiley & Sons, 1981.  

475.    M. Matsui. The first experimental cryptanalysis of the Data Encryption Standard. In Y.G. Desmedt, editor, Advances in Cryptology - CRYPTO ’94, volume 839 of Lecture Notes in Computer Science, Springer, pages 1–11, 1994. 

476.    M.Matsui. Linear cryptanalysis method for DES cipher. In T. Helleseth, editor, Advances in Cryptology - EUROCRYPT ’93, volume 765 of Lecture Notes in Computer Science, Springer, pages 386–397, 1994.  

498.    C. H. Meyer and S. M. Matyas. A New Direction in Computer Data Security. John Wiley & Sons, 1982.

(The program keytab.c was written to reproduce some of the tables from the Meyer/Matyas book.)