In the problems below, “textbook” refers to Wade Trapp and Lawrence C. Washington, Introduction to Cryptography with Coding Theory, Second Edition, Prentice-Hall, 2006.

Problem 1: Simplified DES

Textbook, problem 4-1.

Solution:

1. From the encryption function M_j+2 = M_j ⊕ f(K,M_j+1), we know that

   Therefore, given M_mM_m+1, we compute

   

   Repeating the same process until M₀ is computed. Then M₀M₁ is the corresponding plaintext.

2. If the encryption runs for 2 rounds, then the resulting ciphertext is M₂M₃, where M₂ = M₀ ⊕ f(K,M₁) = M₀ ⊕ M₁ ⊕ K, and M₃ = M₁ ⊕ f(K,M₂) = M₁ ⊕  M₀ ⊕ M₁ ⊕ K ⊕ K = M₀. Therefore, the first part of the plaintext is known as M₀ = M₃, but neither the second part of the plaintext M₁ nor the key K is known. However, if you know a plaintext-ciphertext pair, then it is easy to deduce K by the following operation

3. If the encryption runs for 3 rounds, then the resulting ciphertext is M₃M₄, where M₃ = M₀, and M₄ = M₂ ⊕ f(K,M₃) = M₀ ⊕ M₁ ⊕ K ⊕ M₀ ⊕ K = M₁. Therefore, ciphertext is the same as plaintext.

Problem 2: DES Complementation Property

Textbook, problem 4-4.

Solution: Define C = DES(P,K) and C^′ = DES(P,K). The heart of DES is the Feistel network, whose one stage algorithm is described by (1) and (2).

For DES(L₀R₀,K), define L₀^′ = L₀, R₀^′ = R₀ and K_i^′ = K_i, which leads to another instance DES(L₀^′R₀^′,K^′). We will show that for any stage of the Feistel network, L_i^′ = L_i and R_i^′ = R_i.

• Base: the case when i = 1.

  For instance DES(L₀R₀,K),

  
  For instance DES(L₀^′R₀^′,K^′),
  
  Since f(R_i,K_i) uses the bitwise ⊕ operation to combine input bits of R_i (after expansion) and K_i before the permutation in S-boxes, and ⊕ operation is associative and commutative, the following holds for any r and k of the same length,

  (7)

  Combining (6) and (7) gives

  (8)

• Induction: Assume the claim holds for all i < n, consider the case when i = n.

  For instance DES(L₀R₀,K),

  
  For instance DES(L₀^′R₀^′,K^′),
  

Therefore, after 16 stages of Feistel network, we can get L₁₆^′ = L₁₆ and R₁₆^′ = R₁₆. Concatenating L₁₆^′ and R₁₆^′, we conclude

(13)

Problem 3: Triple DES

Textbook, problem 4-6.

Solution: This version of Triple DES is vulnerable to a known plaintext attack, similar to Double DES is. Suppose the attacker Eve knows a plaintext-ciphertext pair (m,c). She first computes E_K(E_K(m)) and D_K(c) for all possible K. Then Eve looks for the intersection of these two sets. We know the intersection is not empty since the actual key pair (K₁,K₂) must work. Then if there is only one matching key pair, Eve immediately knows the correct key pair. If there are more than one matching pairs, Eve can use other known plaintext-ciphertext pairs to further reduce the number of candidate key pairs. Essentially, if we define E_K^′() = E_K(E_K()), then the meet-in-the-middle attack can be carried out in exactly the same way as in Double DES.

Problem 4: Modified Feistel Network

Textbook, problem 4-8.

Solution: We prove the correctness of the decryption function by induction.

• For the base case i = n, the claim is true since A_n = L_n, B_n = M_n, and C_n = R_n.
• By the induction hypothesis, assume the claim is true for some i, i.e., A_i = L_i, B_i = M_i, and C_i = R_i.
• In the induction step, we check the case for i - 1:
  

  Therefore, the claim is true for all i. As a result, A₀B₀C₀ is the correct plaintext.

Problem 5: Extended CFB Mode

Textbook, problem 4-9. (Note: “CFB mode” as used in this problem is what we called “Extended CFB mode” in the lectures.)

Solution:

1. By ⊕L₃₂(E_K(X_j)) on both sides of the encryption function, it is straightforward that

   We also update X_j in the same way as

   

2. We show that the corrupted C₁ will not affect the decryption of blocks P_i for all i ≥ 4. The reasoning is as follows.
   • P₁ cannot be calculated since C₁ is wrong.
   • The second half of X₂ = R₃₂(X₁)||C₁ is wrong because C₁ is wrong.
   • P₂ is wrong since X₂ is wrong.
   • The first half of X₃ = R₃₂(X₂)||C₂ is wrong because R₃₂(X₂) = C₁.
   • P₃ is wrong since X₃ is wrong.
   • X₄ = R₃₂(X₃)||C₃ = C₂||C₃ is correct, because both C₂ and C₃ are correct.
   • Thus, P₄ is correct. As all other ciphertexts C_j∣j ≥ 4 are correct, all X_j∣j ≥ 4 will be correct, and all P_j∣j ≥ 4 could be successfully decrypted as a result.

Problem 6: Fast exponentiation algorithm

A recursive algorithm for modular exponentiation was presented in class (Lecture 8, slide 17).

Here is a different recursive algorithm to do the same thing.

Both algorithms operate by computing m^k (mod n) for various integers k.

1. Explain why modexp2 is correct.
2. For each algorithm, list the powers of m that are multiplied together during the course of the algorithm when computing m²³ (mod n). For example, if an algorithm computes m⁵ by computing m² = m * m, m³ = m² * m, m⁵ = m³ * m², you would list the exponent pairs (1,1), (2,1), and (3,2).
3. Some of the multiplications performed by these algorithms are redundant. Which ones in part b are redundant?
4. Rewrite modexp2 to make exactly the same useful multiplications but avoid making the redundant ones.

Solution:

1. We prove the correctness of modexp2 by induction.
   • For the base case e = 0, the algorithm is correct since modexp2(m,0,n) = 1.
   • By induction hypothesis, assume the algorithm is correct for all e ≤ y - 1, i.e., modexp2(m,e,n) = m^e mod n for all e ≤ y - 1.
   • In the induction step, consider the case e = y. If y is odd,

     If y is even,

     

     In both cases, modexp2 is correct.

2. • For modexp, we have (1,1), (2,2), (4,4), (8,8), (16,16), (0,16), (16,4), (20,2), and (22,1).
   • For modexp2, we have (1,0), (1,1), (2,2), (1,4), (5,5), (1,10), (11,11), and (1,22).
3. The redundant multiplications are marked by underlines in the previous part.
4. int modexp2( int m, int e, int n) {  
     int r;  
     if ( e == 1 ) return m;  
     if ( e == 0 ) return 1;  
     if ( e&1 ) return m⋆modexp2(m, e-1, n) % n;  
     r = modexp2(m, e/2, n);  
     return r⋆r % n;  
   }