DES algorithm

Show that DES decryption is, in fact, the inverse of DES encryption.

The 32-bit swap after the sixteenth iteration of the DES algorithm is needed to make

the encryption process invertible by simply running the ciphertext back through the

algorithm with the key order reversed. This was demonstrated in the preceding problem. However, it still may not be entirely clear why the 32-bit swap is needed. To

demonstrate why, solve the following exercises. First, some notation:

A‘B = the concatenation of the bit strings A and B

(R‘L) = the transformation defined by the ith iteration of the encryption

algorithm for 1 … I … 16

TDi

(R‘L) = the transformation defined by the ith iteration of the decryption

algorithm for 1 … I … 16

T17(R‘L) = L‘R, where this transformation occurs after the sixteenth iteration

of the encryption algorithm

a. Show that the composition TD1(IP(IP-1

(T17(T16(L15 ‘R15))))) is equivalent to the

transformation that interchanges the 32-bit halves, L15 and R15. That is, show that

TD1(IP(IP-1

(T17(T16(L15 ‘R15))))) = R15 ‘L15

b. Now suppose that we did away with the final 32-bit swap in the encryption algorithm. Then we would want the following equality to hold:

TD1(IP(IP-1

(T16(L15 ‘R15)))) = L15 ‘R15

Does it?

Note: The following problems refer to details of DES that are described in Appendix S.