# DES Key Schedule Algorithm

Reading through the DES Specification it says that the keys are permuted with PC-1 initially and then shifted left both $C$ and $D$. However, before it gets permuted again through PC-2 it does not mention how $C$ and $D$ are put together before going through PC-2.

Is it assumed that $C$ is the lower half of the input to PC-2 with the higher half being $D$ (this comes from it saying that they are $CD$), or are they multiplied together/some other operation is used?

## CD

CD is collectively referring to the C and D Registers. Their use and operation while simultaneous is independent. C and D are concatenated together to specify PC2.

## Permuted Choice 2

PC2 is a selection permutation. You might notice that the first 24 bits of the selected Key are from the C Register (CD(1 to 28)) and the second 24 bits are from the D register (CD(29 to 56)). The order of the selected Key bits in each have is non-linear.

The left portion of the table is recognizable as PC2 from the Digital Encryption Standard.

## Permuted Choice 1

To demonstrate the how C and D Registers are concatenated we look to PC1.

The above table shows how PC1 maps a 64 bit input to the two 28 bit C and D registers from an 8 bit interface where the LSB of each input byte is a parity bit and the upper 7 bits are used as key bits loaded into the C and D Registers. Once the C and D Registers are loaded they are independently shifted (recirculated) by either 1 position or 2 positions to distinguish each round key from it's neighbors. Shift direction is in the opposite direction for encryption and decryption, reversing the key schedule order.

## C and D operated simultaneously

The following table plotting selected Key bits versus round keys for encryption is taken from the Carl Meyers and Stephen Metyas book Cryptography, A New Dimension in Computer Security, subtitled 'A Guide for the Design and Implementation of Secure Systems', Wiley Interscience, 1982, ISBN-0-471- 04892-5.

It's generated by this answer's author from a program keytab (keytab.c, executed as keytab -s). It demonstrates that the C and D blocks are independent that the first 24 bits of selected key are from the C Register and the last 24 bits of selected key are from the D Register.

The KS column and Bit rows demonstrate the round index and selected key bits of CD respectively. The table is formatted to a) show that C and D recirculate independently and b) to fit in an 80 column display.

  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


You might note that KS16 shows the values for Permuted Choice 2 from the Digital Encryption Standard. It says that decryption can occur without being preceded by a shift operation should you actually use recirculating shift registers to hold C and D registers. The above table demonstrates simultaneous operation.

## C and D used independently

The following is a description of the inputs to each S Box in the round function f(R,K), expressed in E(R) and Ks bits.

Each six bits of KS are applied to each of eight S Boxes after XOR with the matching E(R) permutation bits. The header row shows the Column Address bits (CA) and Row Address bits (RA) applied to each S Box.

f(R,K) can actually be devolved into operations associated with a nybble register of R, borrowing Row Address R bits from adjacent nybbles via the E permutation. C Register selected key outputs are applied to S Boxes 1 - 4, while D Register selected key outputs are applied to S Boxes 5 - 8.

## DES is hardware

You shouldn't be surprised we can't describe DES without resorting to hardware terms. There's a paper by Miles E. Smid and Dennis K. Branstad of the National Institute of Standards and Technology (NIST) entitled The Data Encryption Standard Past and Future, first appearing in Proceedings of the IEEE, vol. 76, no. 5, pp. 550-559, May 1988 (and not copyright eligible as a a U.S. government work), which makes the distinction between Basic standards, Interoperability standards, Interface standards and Implementation standards and points out that the DES is an interoperability standard. It describes how to interconnect an 8 bit interface to the Initial Permutation, Inverse Initial Permutation and Permuted Choice 1 as well describing which bits are association in time ordered hardware operations.

The Digital Encryption Algorithm described in FIPS Pub 46 (-1, -2 and -3) describes the hardware implementing IBM's block cipher commonly known as DES and found in U.S. patents 3,958,081 and 3,962,539. The original implementations where bounded by chip count using MSI (Medium Scale Integeration) devices. It's easily possible today to implement shift registers with a shift of distance of one or two, or use a schedule key register file as a look up, or some other 'faster' scheme.