Cryptography Reference
In-Depth Information
The structure of the
f
-function is shown in Fig. 3.10. First, the 32-bit input is ex-
panded to 48 bits by partitioning the input into eight 4-bit blocks and by expanding
each block to 6 bits. This happens in the E-box, which is a special type of permuta-
tion. The first block consists of the bits (1
,
2
,
3
,
4), the second one of (5
,
6
,
7
,
8),etc.
The expansion to six bits can be seen in Fig. 3.11.
1
2
3
4
5
6
7
8
9
. . .
32
1
2
3
4
5
6
7
8
9
10
11
12
13
14
. . .
47
48
Fig. 3.11
Examples for the bit swaps of the expansion function
E
As can be seen from the Table 3.1, exactly 16 of the 32 input bits appear twice in
the output. However, an input bit never appears twice in the same 6-bit output block.
The expansion box increases the diffusion behavior of DES since certain input bits
influence two different output locations.
Table 3.1
Expansion permutation
E
E
3212345
456789
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, the 48-bit result of the expansion is XORed with the round key
k
i
, and
the eight 6-bit blocks are fed into eight different
substition boxes
, which are often
referred to as
S-boxes
. Each S-box is a lookup table that maps a 6-bit input to a
4-bit output. Larger tables would have been cryptographically better, but they also
become much larger; eight 4-by-6 tables were probably close the maximum size
which could be fit on a single integrated circuit in 1974. Each S-box contains 2
6
= 64
entries, which are typically represented by a table with 16 columns and 4 rows. Each
entry is a 4-bit value. All S-boxes are listed in Tables 3.2 to 3.9. Note that all S-boxes
are different. The tables are to be read as indicated in Fig. 3.12: the most significant
bit (MSB) and the least significant bit (LSB) of each 6-bit input select the row of
the table, while the four inner bits select the column. The integers 0,1,...,15ofeach
entry in the table represent the decimal notation of a 4-bit value.