Mastering Algorithms With C - Kyle Loudon [181]
Computing Subkeys
The first step in DES is to compute the 16 subkeys from the initial key. Figure 15.1 illustrates this process. DES uses a key that is 56 bits; however, the key we provide is a 64-bit value. This is so that in hardware implementations every eighth bit can be used for parity checking. In software, the extra bits are simply ignored. To obtain the 56-bit key, we perform a key transformation as shown in Table 15.1. To interpret this table, read from left to right, top to bottom. Each position p in the table contains the position of the bit from the initial key that occupies position p in the transformed key. For example, using Table 15.1, bit 57 of the initial key becomes bit 1 of the transformed key, bit 49 becomes bit 2, and so forth. The convention is to number bits from left to right starting at 1.
Figure 15.1. Computing subkeys in DES
Table 15.1. The Key Transformation in DES
57,
49,
41,
33,
25,
17,
9,
1,
58,
50,
42,
34,
26,
18,
10,
2,
59,
51,
43,
35,
27,
19,
11,
3,
60,
52,
44,
36,
63,
55,
47,
39,
31,
23,
15,
7,
62,
54,
46,
38,
30,
22,
14,
6,
61,
53,
45,
37,
29,
21,
13,
5,
28,
20,
12,
4
After transforming the key to 56 bits, we compute the subkeys. To do this, we first divide the 56-bit key into two 28-bit blocks. Next, for each subkey, we rotate both blocks an amount that depends on the round in which the subkey will be used (see Table 15.2), then rejoin the blocks. After this, we reduce the 56-bit subkey formed from the rejoined blocks to 48 bits by permuting it as shown in Table 15.3. (This table is read like Table 15.1.) Note that Table 15.3 contains two fewer columns because 8 bits are discarded. This permutation is called the permuted choice. This process is repeated once for each of the 16 subkeys. All together, the goal here is to ensure that we apply different bits from the initial key to the data in each round.
Table 15.2. The Number of Rotations per Round for DES Subkeys
Round
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Rotations
1
1
2
2
2
2
2
2
1
2
2
2
2
2
2
1
Table 15.3. The Permuted Choice for DES Subkeys
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
Enciphering and Deciphering Data Blocks
Once we have prepared the subkeys, we are ready to encipher or decipher data blocks. Figure 15.2 illustrates this process. We begin by permuting the 64-bit data block as shown in Table 15.4. (This table is read like Table 15.1.) This permutation is aptly named the initial permutation . It does not enhance the security of DES, but is believed to have been added to make data easier to load into DES chips before the advent of 16-bit and 32-bit buses. Although anachronistic, the permutation should still be performed in order to comply with the DES standard. After the initial permutation, the 64-bit data block is divided into two 32-bit blocks, L 0 and R 0.
Figure 15.2. Enciphering and deciphering data blocks in DES
Table 15.4. The Initial Permutation for Data Blocks in DES
58,
50,
42,
34,
26,
18,
10,
2,
60,
52,
44,
36,
28,
20,
12,
4,
62,
54,
46,
38,
30,
22,
14,
6,
64,
56,
48,
40,
32,
24,
16,
8,
57,
49,
41,
33,
25,
17,
9,
1,
59,
51,
43,
35,