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 Problem 3.7. 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 \quad=\) the concatenation of the bit strings \(A\) and \(B\)

\(T_{i}(R \| L)=\) the transformation defined by the \(i\) th iteration of the encryption algorithm for \(1 \leq I \leq 16\)

\(T D_{i}(R \| L)=\) the transformation defined by the \(i\) th iteration of the encryption algorithm for \(1 \leq I \leq 16\)

\(T_{17}(R \| L)=L \| R\), where this transformation occurs after the sixteenth iteration of the encryption algorithm

a. Show that the composition \(T D_{1}\left(\operatorname{IP}\left(I P^{-1}\left(T_{17}\left(T_{16}\left(L_{15} \| R_{15}ight)ight)ight)ight)ight)\) is equivalent to the transformation that interchanges the 32-bit halves, \(L_{15}\) and \(R_{15}\). That is, show that

\[T D_{1}\left(I P\left(I P^{-1}\left(T_{17}\left(T_{16}\left(L_{15} \| R_{15}ight)ight)ight)ight)ight)=R_{15} \| L_{15}\]

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:

\[T D_{1}\left(\operatorname{IP}\left(I P^{-1}\left(T_{16}\left(L_{15} \| R_{15}ight)ight)ight)ight)=L_{15} \| R_{15}\]

Does it?