YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer SecurityHandout #11
Xueyuan Su   March 3, 2010



 

Solutions to Problem Set 3

Due on Tuesday, February 23, 2010.

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 Mj+2 = Mj f(K,Mj+1), we know that
    Mj = Mj  ⊕ f(K, Mj+1 )⊕ f(K, Mj+1 ) = Mj+2 ⊕ f(K, Mj+1)

    Therefore, given MmMm+1, we compute

    M     = M     ⊕ f (K, M   )
  m-1     m+1          m

    Repeating the same process until M0 is computed. Then M0M1 is the corresponding plaintext.

  2. If the encryption runs for 2 rounds, then the resulting ciphertext is M2M3, where M2 = M0 f(K,M1) = M0 M1 K, and M3 = M1 f(K,M2) = M1  M0 M1 K K = M0. Therefore, the first part of the plaintext is known as M0 = M3, but neither the second part of the plaintext M1 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
    M  ⊕ M   ⊕ M  =  M  ⊕ M   ⊕ K ⊕ M  ⊕  M  = K
  2    0     1     0    1         0     1

  3. If the encryption runs for 3 rounds, then the resulting ciphertext is M3M4, where M3 = M0, and M4 = M2 f(K,M3) = M0 M1 K M0 K = M1. 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).

Li+1  =  Ri                                       (1)
Ri+1  =  Li ⊕ f(Ri,Ki )                           (2)

For DES(L0R0,K), define L0 = L0, R0 = R0 and Ki = Ki, which leads to another instance DES(L0R0,K). We will show that for any stage of the Feistel network, Li = Li and Ri = Ri.

Therefore, after 16 stages of Feistel network, we can get L16 = L16 and R16 = R16. Concatenating L16 and R16, we conclude

              -------  --
y′ = L′16R′16 = L16R16 = y
(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 EK(EK(m)) and DK(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 (K1,K2) 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 EK() = EK(EK()), 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.

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 L32(EK(Xj)) on both sides of the encryption function, it is straightforward that
    Pj = Cj ⊕ L32 (EK (Xj ))

    We also update Xj in the same way as

    Xj+1  = R32(Xj)||Cj

  2. We show that the corrupted C1 will not affect the decryption of blocks Pi for all i 4. The reasoning is as follows.

Problem 6: Fast exponentiation algorithm

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

/⋆ computes m^e mod n recursively ⋆/  
int modexp( int m, int e, int n) {  
  int r;  
  if ( e == 0 ) return 1;         /⋆ m^0 = 1 ⋆/  
  r = modexp(m⋆m % n, e/2, n);    /⋆ r = (m^2)^(e/2) mod n ⋆/  
  if ( (e&1) == 1 ) r = r⋆m % n;  /⋆ handle case of odd e ⋆/  
  return r;  
}

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

/⋆ alternate method to compute m^e mod n recursively ⋆/  
int modexp2( int m, int e, int n) {  
  int r;  
  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;  
}

Both algorithms operate by computing mk (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 m23 (mod n). For example, if an algorithm computes m5 by computing m2 = m * m, m3 = m2 * m, m5 = m3 * m2, 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.
  2. The redundant multiplications are marked by underlines in the previous part.
  3. 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;  
    }