YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer Security Handout #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

Therefore, given MmMm+1, we compute

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

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).

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.

• Base: the case when i = 1.

For instance DES(L0R0,K),

For instance DES(L0R0,K),
Since f(Ri,Ki) uses the bitwise operation to combine input bits of Ri (after expansion) and Ki 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(L0R0,K),

For instance DES(L0R0,K),

Therefore, after 16 stages of Feistel network, we can get L16 = L16 and R16 = R16. Concatenating L16 and R16, 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 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.

• For the base case i = n, the claim is true since An = Ln, Bn = Mn, and Cn = Rn.
• By the induction hypothesis, assume the claim is true for some i, i.e., Ai = Li, Bi = Mi, and Ci = Ri.
• In the induction step, we check the case for i - 1:

Therefore, the claim is true for all i. As a result, A0B0C0 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 L32(EK(Xj)) on both sides of the encryption function, it is straightforward that

We also update Xj in the same way as

2. We show that the corrupted C1 will not affect the decryption of blocks Pi for all i 4. The reasoning is as follows.
• P1 cannot be calculated since C1 is wrong.
• The second half of X2 = R32(X1)||C1 is wrong because C1 is wrong.
• P2 is wrong since X2 is wrong.
• The first half of X3 = R32(X2)||C2 is wrong because R32(X2) = C1.
• P3 is wrong since X3 is wrong.
• X4 = R32(X3)||C3 = C2||C3 is correct, because both C2 and C3 are correct.
• Thus, P4 is correct. As all other ciphertexts Cjj 4 are correct, all Xjj 4 will be correct, and all Pjj 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).

/⋆ 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.
• 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) = me 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.

• 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).
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;
}