a) Show that DES decryption is, in fact, the inverse of DES encryption. b) The 3

Question

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

b) 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 II B = the concatenation of the bit strings A and B

Ti(R II L) = the transformation defined by the ith iteration of the encryption algorithm for 1 less then equal to I less then equal to16

TDi(R II L) = the transformation defined by the ith iteration of the encryption algorithm for "1 less then equal to I less then equal to16"

T17(R II L) = L II R, where this transformation occurs after the sixteenth iteration of the encryption algorithm

b1) Show that the composition TD1(IP(IP-1(T17(T16(L15 II 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 II R15))))) = R15 IIL15
b2). 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 II R15)))) = L15 II R15

Does it?

Explanation / Answer

a) The reasoning for the Feistel cipher, as shown in Figure 3.6 applies in the case of
DES. We only have to show the effect of the IP and IP-1 functions. For encryption,
the input to the final IP-1 is RE16|| LE16. The output of that stage is the ciphertext.
On decryption, the first step is to take the ciphertext and pass it through IP. Because
IP is the inverse of IP-1, the result of this operation is just RE16|| LE16, which is
equivalent to LD0 || RD0. Then, we follow the same reasoning as with the Feistel
cipher to reach a point where LE0 = RD16 and RE0 = LD16. Decryption is completed
by passing LD0 || RD0 through IP-1. Again, because IP is the inverse of IP-1, passing
the plaintext through IP as the first step of encryption yields LD0 || RD0, thus
showing that decryption is the inverse of encryption.

b) start from inside out:

Since:

T16(L15||R15)=L16||R16T16(L15||R15)=L16||R16

T17(L16||R16)=R16||L16T17(L16||R16)=R16||L16

IP[IP–1(R16||L16)]=R16||L16IP[IP–1(R16||L16)]=R16||L16

TD1(R16||L16)=R15||L15TD1(R16||L16)=R15||L15

b.

T16(L15||R15)=L16||R16T16(L15||R15)=L16||R16

IP[IP–1(L16||R16)]=L16||R16IP[IP–1(L16||R16)]=L16||R16

TD1(R16||L16)=R16||L16f(R16,k16)L15||R15

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.