1. The 32-bit swap after the sixteenth iteration of the DES algorithm is needed to make the encryption process invertible by simply running the cipher text back through the algorithm with the key order reversed. Suppose the DES F function mapped every 32-bit input R, regardless of the value of the input K, to 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

T_i(R?L) = the transformation defined by the ith iteration of the encryption algorithm for 1≤I ≤16

TD_i(R?L) = the transformation defined by the ith iteration of the encryption algorithm for 1 ≤ I≤ 16

T₁₇(R?L) = L?R, where this transformation occurs after the sixteenth iteration of the encryption algorithm

a. Show that the composition TD₁(IP(IP^-1(T₁₇(T₁₆(L₁₅?R₁₅)))))  is equivalent to the transformation that interchanges the 32-bit halves, L_15  and R_15  .That is, show that

TD₁(IP(IP^-1(T₁₇(T₁₆(L₁₅?R₁₅))))) = R₁₅ 7L₁₅

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:

TD₁(IP(IP^-1(T₁₆(L₁₅?R₁₅)))) = L₁₅ 7R₁₅

Does it?

2. Compare the initial permutation table (Table 3.2a) with the permuted choice one table (Table 3.4b). Are the structures similar? If so, describe the similarities. What conclusions can you draw from this analysis?

Table 3.2.

(a) Initial Permutation (IP)
58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

 

(b) Inverse Initial Permutation (IP–1)
40	8	48	16	56	24	64	32
39	7	47	15	55	23	63	31
38	6	46	14	54	22	62	30
37	5	45	13	53	21	61	29
36	4	44	12	52	20	60	28
35	3	43	11	51	19	59	27
34	2	42	10	50	18	58	26
33	1	41	9	49	17	57	25