Internet.Security

Table 3.5 E bit-selection table

(see Table 3.4) has bit 58 of the input as its first bit, bit 50 as its second bit, and so on down to bit 7 as the last bit. The right half of the data, Ri , is expanded to 48 bits according to Table 3.5 of an expansion permutation.

The expansion symbol E of E(Ri ) denotes a function which takes the 32-bit Ri as input and produces the 48-bit E(Ri ) as output. The purpose of this operation is twofold – to make the output the same size as the key for the XOR operation, and to provide a longer result that is compressed during the S-box substitution operation.

After the compressed key Ki is XORed with the expanded block E(Ri−1) such that ) Ki for 1 ≤ i ≤ 15, this 48-bit i moves to substitution operations that are performed by eight Si -boxes. The 48-bit i is divided into eight 6-bit blocks. Each

6-bit block is operated on by a separate Si -box, as shown in Figure 3.2. Each Si -box is a table of 4 rows and 16 columns as shown in Table 3.6. This 48-bit input i to the S-boxes are passed through a nonlinear S-box transformation to produce the 32bit output.

If each Si denotes a matrix box defined in Table 3.6 and A denotes an input block of 6 bits, then Si (A) is defined as follows: the first and last bits of A represent the row number of the matrix Si , while the middle 4 bits of A represent a column number of Si in the range from 0 to 15.

For example, for the input (101110) to S5-box, denote as S105 (0111), the first and last bits combine to form 10, which corresponds to the row 2 (actually third row) of S5. The

middle 4 bits combine to form 0111, which corresponds to the column 7 (actually the eighth column) of the same S5-box. Thus, the entry under row 2, column 7 of S5-box is computed as:

S105 (0111) = S25(7) = 8 (hexadecimal) = 1000 (binary)

Thus, the value of 1000 is substituted for 101110. That is, the four-bit output 1000 from S5 is substituted for the six-bit input 101110 to S5. Eight four-bit blocks are the S-box output resulting from the substitution phase, which recombine into a single 32-bit block i by concatenation. This 32-bit output i of the S-box substitution are permuted according to Table 3.7. This permutation maps each input bit of i to an output position of P( i ).

Table 3.8 Inverse of initial permutation, IP−1

The output P( i ) are obtained from the input i by taking the 16th bit of i as the first bit of P( i ), the seventh bit as the second bit of P( i ), and so on until the 25th bit of i is taken as the 32nd bit of P( i ). Finally, the permuted result is XORed with the left half Li of the initial permuted 64-bit block. Then the left and right halves are swapped and another round begins. The final permutation is the inverse of the initial permutation, and is described in Table 3.8 IP−1. Note here that the left and right halves are not swapped after the last round of DES. Instead, the concatenated block R16||L16 is used as the input to the final permutation of Table 3.8 (IP−1). Thus, the overall structure for DES algorithm is shown in Figure 3.4.

Example 3.2 Suppose the 64-bit plaintext is X = 3570e2f1ba4682c7, and the same key as used in Example 3.1, K = 581fbc94d3a452ea is assumed again. The first two-round keys are, respectively, K1 = 27a169e58dda and K2 = da91ddd76748.

For the purpose of demonstration, the DES encryption aims to limit the first two rounds only. The plaintext X splits into two blocks (L0, R0) using Table 3.4 IP such that L0 = ae1ba189 and R0 = dc1f10f4.

The 32-bit R0 is expanded to the 48-biy E(R0) such that E(R0) = 6f80fe8a17a9.

The key-dependent function i is computed by XORing E(R0) with the first round key K1, such that

1 = E(R0) K1

= 4821976f9a73

This 48-bit 1 is first divided into eight six-bit blocks, and then fed into eight Si -boxes. The output 1 resulting from the S-box substitution phase is computed as 1 = a1ec961c.

Using Table 3.7, the permuted values of 1 are P( 1) = 2ba1536c. Modulo-2 addition of P( 1) with L0 becomes

R1 = P( 1) L0

= 85baf2e5

Since L1 = R0, this gives L1 = dc1f10f4.

Consider next the second-round encryption. Expanding R1 with the aid of Table 3.5 yields E(R1) = c0bdf57a570b. XORing E(R1) with K2 produces

2 = E(R1) K2

= 1a2c28ade043

The substitution operations with S-boxes yields the 32-bit output 2 such that 2 = 1ebcebdf. Using Table 3.7, the permutation P( 2) becomes P ( 2) = 5f3e39f7. Thus, the right-half output R2 after round two is computed as

R2 = P( 2) L1

= 83212903

The left-half output L2 after round two is immediately obtained as

L2 = R1 = 85baf2e5

Concatenation of R2 with L2 is called the preoutput block in our two-round cipher system. The preoutput is then subjected to the inverse permutation of Table 3.8. Thus, the output of the DES algorithm at the end of the second round becomes the ciphertext Y:

Y= IP−1(R2||L2)

= d7698224283e0aea

3.1.4DES Decryption

The decryption algorithm is exactly identical to the encryption algorithm except that the round keys are used in the reverse order. Since the encryption keys for each round are K1, K2, . . . , K16, the decryption keys for each round are K16, K15, . . . , K1. Therefore, the same algorithm works for both encryption and decryption. The DES decryption process will be explained in the following example.

Example 3.3 Recover the plaintext X from the ciphertext Y = d7698224283e0aea (computed in Example 3.2). Using Table 3.4 in the first place, divide the ciphertext Y into the two blocks:

68 INTERNET SECURITY

R2 = 83212903

L2 = 85baf2e5

Applying Table 3.5 to L2 yields E(L2) = c0bdf57a570b.

E(L2) is XORed with K2 such that

2 = E(L2) K2

= 1a2c28ade043

This is the 48-bit input to the S-boxes.

After the substitution phase of S-boxes, the 32-bit output 2 from the S-boxes is computed as 2 = 1ebcebdf. From Table 3.7, the permuted values of 2 are P( 2) =

5f3e39f7.

Moving up to the first round, we have L1 = P( 2) R2 = dc1f10f4. Applying Table 3.5 for L1 yields E(L1) = 6f80fe8a17a9.

XORing E(L1) with K1, we obtain the 48-bit input to the S-boxes.

1 = E(L1) K1

= 4821976f9a73

The 32-bit output from the S-boxes is computed as:

1 = a1ec961c

Using Table 3.7 for permutation, we have

P( 1) = 2ba1536c

The preoutput block can be computed as follows:

L0 = P( 1) R1 = ae1ba189

R0 = L1 = dc1f10f4

L0||R0 = ae1ba189dc1f10f4 (preoutput block)

Applying Table 3.8 (IP−1) to the preoutput block, the plaintext X is restored as follows:

X= IP−1(L0||R0 )

= 3570e2f1ba4682c7

Example 3.4 Consider the encryption problem of plaintext

X = 785ac3a4bd0fe12d with the original input key

K = 38a84ff898b90b8f.

The 48-bit round keys from K1 through K16 are computed from the 56-bit key blocks through a series of permutations and left shifts, as shown below:

Compressed round keys

The 64-bit plaintext X splits into two blocks (L0, R0), according to Table 3.4 (IP), such that

L0 = 4713b8f4

R0 = 5cd9b326

The 32-bit R0 is spread out and scrambled in 48 bits, using Table 3.5, such that E(R0) =

2f96f3da690c.

The 48-bit input to the S-box, 1, is computed as:

1 = E(R0) K1

= 2cdd7c169422

The 32-bit output from the S-box is 1 = 28e8293b.

Using Table 3.7, P( 1) becomes

P( 1) = 1a0b2fc4

XORing P( 1) with L0 yields

R1 = P( 1) L0

= 5d189730

which is the right-half output after round one.

Since L1 = R0, the left-half output L1 after round one is L1 = 5cd9b326. The first round of encryption has been completed.

In similar fashion, the 16-round output block (Li , Ri ), 2 ≤ i ≤ 16, can be computed as follows: