Mastering Algorithms With C - Kyle Loudon [182]
27,
19,
11,
3,
61,
53,
45,
37,
29,
21,
13,
5,
63,
55,
47,
39,
31,
23,
15,
7
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 Li and Ri , which are used by the next round, until we finally end up with the data block R 16 L 16. We begin each round with Li - 1 and Ri - 1, and expand Ri - 1 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 Ki , 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:
Table 15.5. The Expansion Permutation for Data Blocks in DES
32,
1,
2,
3,
4,
5,
4,
5,
6,
7,
8,
9,
8,
9,
10,
11,
12,
13,
12,
13,
14,
15,
16,
17,
16,
17,
18,
19,
20,
21,
20,
21,
22,
23,
24,
25,
24,
25,
26,
27,
28,
29,
28,
29,
30,
31,
32,
1
Next, Rint 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 Rint 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 Rint is 101011. Therefore, we consult the third S-box in Table 15.6 to find 9, the four-bit value found in row 112 = 3 and column 01012 = 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.
Table 15.6. The S-Box Substitutions for Data Blocks in DES
S-Box 1
14,
4,
13,
1,
2,
15,
11,
8,
3,
10,
6,
12,
5,
9,
0,
7,
0,
15,
7,
4,
14,
2,
13,
1,
10,
6,
12,
11,
9,
5,
3,
8,
4,
1,
14,
8,
13,
6,
2,
11,
15,
12,
9,
7,
3,
10,
5,
0,
15,
12,
8,
2,
4,
9,
1,
7,
5,
11,
3,
14,
10,
0,
6,
13
S-Box 2
15,
1,
8,
14,
6,
11,
3,
4,
9,
7,
2,
13,
12,
0,
5,
10,
3,
13,
4,
7,
15,
2,
8,
14,
12,
0,
1,
10,
6,
9,
11,
5,
0,
14,
7,
11,
10,
4,
13,
1,
5,
8,
12,
6,
9,
3,
2,
15,
13,
8,
10,
1,
3,
15,
4,
2,
11,
6,
7,
12,
0,
5,
14,
9
S-Box 3
10,
0,
9,
14,
6,
3,
15,
5,
1,
13,
12,
7,
11,
4,
2,
8,
13,
7,
0,
9,
3,
4,
6,
10,
2,
8,
5,
14,
12,
11,
15,
1,
13,
6,
4,
9,
8,
15,
3,
0,
11,
1,
2,
12,
5,
10,
14,
7,
1,
10,
13,
0,
6,
9,
8,
7,
4,
15,
14,
3,
11,
5,
2,
12
S-Box 4
7,
13,
14,
3,
0,
6,
9,
10,
1,
2,
8,
5,
11,
12,
4,
15,
13,
8,
11,
5,
6,
15,
0,
3,
4,
7,
2,
12,
1,
10,
14,
9,
10,
6,
9,
0,
12,
11,
7,
13,
15,
1,
3,
14,
5,
2,
8,
4,
3,
15,
0,
6,
10,
1,
13,
8,
9,
4,
5,
11,
12,
7,
2,
14
S-Box 5
2,
12,
4,
1,
7,
10,
11,
6,
8,
5,
3,
15,
13,
0,
14,
9,
14,
11,
2,
12,
4,
7,
13,
1,
5,
0,
15,
10,
3,
9,
8,
6,
4,
2,
1,
11,
10,
13,
7,
8,
15,
9,
12,
5,
6,
3,
0,
14,
11,
8,
12,
7,
1,
14,
2,
13,
6,
15,
0,
9,
10,
4,
5,
3
S-Box 6
12,
1,
10,
15,
9,
2,
6,
8,
0,
13,
3,
4,
14,
7,
5,
11,
10,
15,
4,
2,