Mastering Algorithms With C - Kyle Loudon [184]
Complexity
O (1)
Implementation and Analysis of DES
Considering the amount of bit twiddling in DES, it probably comes as no surprise that it is frequently implemented in hardware. Even the figures and terminology associated with DES (diagrams drawn with boxes and lines, and terms such as S-boxes and P-boxes) tend to suggest a certain affinity toward hardware implementations. Nevertheless, software implementations have their place as well. In software, it is helpful to have several basic operations to assist in carrying out the numerous permutations, transformations, and substitutions that DES requires. For this purpose, the implementation presented here makes use of the bit operations presented in Chapter 14. The details of each permutation, transformation, and substitution are defined by the tables at the beginning of Example 15.2. These match the tables presented earlier in the text.
des_encipher
The des_encipher operation (see Example 15.2) enciphers a 64-bit block of plaintext using DES. Since one of the nice properties of DES is that the same process can be used both to encipher and decipher data, des_encipher simply calls des_main, which des_decipher calls as well. The des_main function uses its direction argument to determine whether to encipher or decipher the data provided in source. The direction argument simply alters the order in which subkeys are applied. In the case of des_encipher, we set direction to encipher.
The des_main function begins by testing whether key is NULL. This allows a caller of des_encipher to reuse subkeys computed during a previous call. To accommodate this, we declare the subkeys array as static. If key is not NULL, we compute the subkeys. To do this, we perform the steps presented earlier. The key transformation is performed using the function permute , which permutes bits in a buffer according to a specified table. Assuming that in each position i of a table there is some value p, permute permutes the buffer passed to it by moving the bit at position p to position i.
To transform the key, we pass permute the table Des_Transform (the same table as in Table 15.1). The necessary rotations are performed by calling the bit operation bit_rot_left. This operation rotates a buffer to the left by a specified number of bits. To rotate the 28-bit subkey blocks the correct amount for each round, we pass bit_rot_left the appropriate element from the table Des_Rotations (the same table as in Table 15.2). We apply the permuted choice to each subkey by calling permute and passing it the table Des_Permuted (the same table as in Table 15.3).
To encipher a data block, we begin by performing the initial permutation. To do this, we call permute and pass it the table Des_Initial (the same table as in Table 15.4). Next, we divide the data into two 32-bit blocks, lblk and rblk. Recall that most of the work in enciphering data takes place in a series of operations repeated over 16 rounds. The majority of each round is spent computing the value of the function f, which is stored in fblk as we go.
We begin each round by performing an expansion permutation on rblk. To do this, we call permute and pass it the table Des_Expansion (the same table as in Table 15.5). Next, we call the bit operation bit_xor to compute the XOR of the expanded right block and the appropriate subkey. The subkey depends on the round we are executing and whether we are enciphering or deciphering data. Once the XOR has been computed, we perform a series of S-box substitutions on the result. Des_Sbox defines the eight S-boxes used by DES (the same S-boxes as in Table 15.6). We look up each substitution exactly as