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

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.

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 ₀ and R ₀.

Figure 15.2. Enciphering and deciphering data blocks in DES

After completing the initial permutation, the data block moves through a series of operations that are repeated for 16 rounds. The goal of each round i is to compute L_i and R_i , which are used by the next round, until we finally end up with the data block R ₁₆ L ₁₆. We begin each round with L_i - ₁ and R_i - ₁, and expand R_i - ₁ from 32 to 48 bits using the expansion permutation , as shown in Table 15.5. (This table is read like Table 15.1.) The primary purpose of this permutation is to create an avalanche effect when enciphering data. This makes one bit in the data block affect more bits in the step to follow, and thus produces diffusion. Once the expansion permutation is complete, we compute the XOR (denoted ⊕) of the 48-bit result and K_i , the subkey for the round. This produces an intermediate 48-bit result, which is called R int. If we let E be the expansion permutation, the operations thus far in the round can be expressed as:

Next, R_int undergoes eight substitutions performed using eight separate S-boxes. Each S-box j takes a six-bit block from position 6j to 6j + 6 in R_int and looks up a four-bit value for it in a table (see Table 15.6). This value is written to a buffer at position 4j (see Figure 15.3).

Figure 15.3. Eight S-box substitutions for a data block in DES

To read Table 15.6, find S-box j, look up the row number having the two-bit value formed by the first and last bit of the six-bit block, and find the column having the four-bit value formed by the middle bits of the six-bit block (both zero-indexed). For example, in Figure 15.2, the third six-bit block in R_int is 101011. Therefore, we consult the third S-box in Table 15.6 to find 9, the four-bit value found in row 11₂ = 3 and column 0101₂ = 5 (both zero-indexed). S-boxes add confusion to the data, and more than anything else give DES its security. Consequently, they have also long been the source of great scrutiny. Some groups even suspect that they may include a back door by their designers. No one knows, or at least admits to knowing.

Once we have completed the S-box substitutions, the result is a 32-bit value that we permute using a P-box, as shown in Table 15.7. (This table is read like Table 15.1.)

At this point, it is convenient to think of the operations in the round as a function, typically denoted as f. If b_j is the j th six-bit block of R_int , Sj is the j th S-box, and P is the P-box permutation, this function is defined as:

f = P(S₁(b₁), S₂(b₂),. . ., S₈(b₈))

The last operation in each round is to compute the XOR of the 32-bit result of f and the original left block passed into the round, L _{i - 1}. Once this is complete, we swap the left and right blocks and begin the next round. In the last round, however, we do not swap the left and right blocks. All together, the computations for L_i and R_i in each round can be concisely expressed as follows:

When all 16 rounds have been completed, we concatenate the final right block, R ₁₆, with the final left block, L ₁₆, to produce the 64-bit block R ₁₆ L ₁₆. (Recall that the left and right blocks are not swapped in the final round; thus, we have the last right block on the left and the last left block on the right.) The final step is to permute R ₁₆ L ₁₆ as shown in Table 15.8. This permutation is aptly named the final permutation . It simply undoes what the initial permutation did earlier. When enciphering data, the result is a 64-bit block of ciphertext; when deciphering data, it is the original 64-bit block of plaintext.