YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

	CPSC 467a: Cryptography and Computer Security	Handout #9
Xueyuan Su		October 12, 2008

Solution to Problem Set 2

In this problem set, we consider a variant of the Caesar cipher which we call the “Happy” cipher (named after the venerable “Happy Hacker” of CPSC 223 fame). Happy (E,D) is defined as follows: Let X₁ = {0,…,12} and X₂ = {13,…,25}. Let = = = X = X₁ ∪ X₂, and let n = |X| = 26. Define

(| (m + k) mod 13 if k ∈ X ∧ m ∈ X ||{ 1 1 Ek(m ) = m if k ∈ X1 ∧ m ∈ X2 |||( m if k ∈ X2 ∧ m ∈ X1 ((m + k) mod 13) + 13 if k ∈ X2 ∧ m ∈ X2

We also consider Double Happy (E²,D²). Here, ² = ×, and E_(k₁,k₂)² = E_k₂(E_k₁(m)).

Problem 1: Happy Encryption (5 points)

Encrypt the plaintext “i am a secret message” using Happy with key k = 3. (As usual, we will ignore spaces.)

Solution:

m = “i am a secret message”;

k = 3;

c = “l dc d shfrht chssdjh”.

Problem 2: Happy Decryption (5 points)

Describe the Happy decryption function D_k(c).

Solution:

( |||{ (c- k) mod 13 if k ∈ X1 ∧ c ∈ X1 D (c) = c if k ∈ X1 ∧ c ∈ X2 k ||| c if k ∈ X2 ∧ c ∈ X1 ( ((c - k) mod 13)+ 13 if k ∈ X2 ∧ c ∈ X2

(1)

Problem 3: Security (10 points)

Is Happy information-theoretically secure? Why or why not?
Is Double Happy information-theoretically secure? Why or why not?

Solution:

(a) No. Before observing any cipher text, the probability of the plain text m being a specific letter m₀ is Prob[m = m₀] = 1
26 . After observing the cipher text, say c = m₀, the probability of the plain text m = m₀ becomes Prob[m = m₀∣c = m₀] = 1246 . Assuming m₀ = 23, Figure 1 illustrates the plain text prior probability distribution and posterior probability distribution after we learn the cipher text c = m₀ = 23.

(a) Prior probability

(b) Posterior probability

Figure 1:

Probability distributions.

(b) Similar to (a).

Problem 4: Equivalent Key Pairs (10 points)

Suppose m₀ = c₀ = 4.

Find all key pairs (k,k′) such that E_(k,k′)²(m₀) = c₀.
Do all such key pairs give rise to the same function E_(k,k′)²? That is, if E_(,)²(m₀) = E_(k,k′)²(m₀) = c₀, does E_(,)²(m) = E_(k,k′)²(m) for all m ? Why or why not?

Solution:

(a) Note that m₀,k₀ X₁. There are four different cases:

1) {(k,k^′)∣k,k^′ X₂}
2) {(k,k^′)∣k = 0,k^′ X₂}
3) {(k,k^′)∣k^′ = 0,k X₂}
4) {(k,k^′)∣k,k^′ X₁,(k + k^′) mod13 = 0}

(b) No. For example, if m = 13, then E_13,14²(13) = 14 (case 1), but E_1,12²(13) = 13 (case 4).

Problem 5: Group Property (10 points)

Is Happy a group? Why or why not?

Solution:

No. group property requires that for any key pairs k₁,k₂ X, there is always a single key k X, such that E_k₁,k₂(m) = E_k(m) for any m X. Taking k₁ = 1,k₂ = 14 for example, now we will show that ∀k, there ∃m such that E_k₁,k₂(m)≠E_k(m).

k X₁: E_1,14(13) = 14, but E_k(13) = 13
k X₂: E_1,14(0) = 1, but E_k(0) = 0

___________________________________________________________________________________

The following problems ask you to compute probabilities. You may do so either analytically (if you’re facile with combinatorial counting techniques) or experimentally by writing a program to simulate 1000 random trials and reporting the fraction of times that the desired result is obtained. Either way, you should show your work – analytic derivation, or program and simulation results.

Problem 6: Birthday Problem (20 points)

Suppose u₁,…,u₆ and v₁,…,v₆ are chosen uniformly and independently at random from X (so duplicates are possible. Find the probability that {u₁,…,u₆}∩{v₁,…,v₆}≠∅. (Note that 6 = ⌈ √n-- ⌉.)

Solution:

We first calculate the probability that sets {u_i} and {v_i} do not have intersection and analyze this situation case by case as follows:

1) 6 members of set {u_i} are identical, (i.e., the form 6), {v_i} choose from the remaining 25 letters:

p1 = [1× (-1-)5]× [(25)6] 26 26

(2)

2) 5 members of set {u_i} are identical, (i.e., the form 5:1), {v_i} choose from the remaining 24 letters:

( ) 6 -1-4 25- 24-6 p2 = 5 × [1 × (26) × 26]× [(26) ]

(3)

3) 4 members of set {u_i} are identical, the rest 2 members themselves are identical, (i.e., the form 4:2), {v_i} choose from the remaining 24 letters:

( ) p = 6 × [1× ( 1-)3 × 25-×-1-]× [( 24)6] 3 4 26 26 26 26

(4)

4) 4 members of set {u_i} are identical, the rest 2 members themselves are different, (i.e., the form 4:1:1), {v_i} choose from the remaining 23 letters:

( ) p4 = 6 × [1× ( 1-)3 × 25-× 24-]× [( 23)6] 4 26 26 26 26

(5)

5) 3 members of set {u_i} are identical, the rest 3 members themselves are identical, (i.e., the form 3:3), {v_i} choose from the remaining 24 letters:

( ) 6 1 1 2 25 1 2 24 6 p5 = 3 × 2! × [1× (26) × 26-× (26-)]× [(26) ]

(6)

6) 3 members of set {u_i} are identical, other 2 members themselves are identical, the last one is different (i.e., the form 3:2:1), {v_i} choose from the remaining 23 letters:

( ) ( ) p6 = 6 × 3 × [1× (-1-)2 × 25-× -1-× 24-]× [(23-)6] 3 2 26 26 26 26 26

(7)

7) 3 members of set {u_i} are identical, the rest 3 members themselves are all different, (i.e., the form 3:1:1:1), {v_i} choose from the remaining 22 letters:

( ) 6 1 2 25 24 23 22 6 p7 = 3 × [1 × (26) × 26-× 26-× 26]× [(26) ]

(8)

8) {u_i} are in the form of 2:2:2, {v_i} choose from the remaining 23 letters:

(6 ) (4) 1 1 25 1 24 1 23 p8 = × × --× [1× --× --× ---× ---× --]× [(--)6] 2 2 3! 26 26 26 26 26 26

(9)

9) {u_i} are in the form of 2:2:1:1, {v_i} choose from the remaining 22 letters:

( ) ( ) 6 4 1 1 25 1 24 23 22 6 p9 = 2 × 2 × 2! × [1× 26 × 26 × 26-× 26-× 26]× [(26) ]

(10)

10) {u_i} are in the form of 2:1:1:1:1, {v_i} choose from the remaining 21 letters:

( ) 6 -1- 25- 24- 23- 22- 21-6 p10 = 2 × [1× 26 × 26 × 26 × 26 × 26]× [(26) ]

(11)

11) All members of {u_i} are different, (i.e., the form of 1:1:1:1:1:1), {v_i} choose from the remaining 20 letters:

p11 = [1 × 25-× 24-× 23-× 22-× 21-]× [(20-)6] 26 26 26 26 26 26

(12)

Then the probability of non-empty intersection between u_i and v_i is:

∑11 p = 1 - pj ≈ 0.752486 j=1

(13)

The above calculation is pretty tedious, but it helps to understand the detailed analysis. We can also use Monte Carlo simulation to obtain the success probabilities.

We can make use of the randRange() function we constructed in PS1 to generate a 6 random numbers u_i and another 6 random numbers v_i. Then we check each pair of (u_i,v_i) one by one to see whether there is a match. If there is such match, the counter increases by 1. In each experiment we run 1,000,000 trials and calculates the non-empty intersection probability. Then we run the experiments for 100 times and calculate the probability. The result is shown in Figure 2. The average probability is about 75.25%.

Figure 2:

Probability of non-empty intersection.

Problem 7: Birthday Attack on Double Happy (40 points)

Assume Alice chooses a random key pair (k₀,k′₀) and a random message m and computes c = E_{(k₀,k′₀)}²(m) using Double Happy. Eve learns the plaintext-ciphertext pair (m,c) and then carries out the Birthday Attack for m and c as follows:

She chooses k₁,…,k₆ uniformly at random from and computes u_i = E_{k_i}(m) for i = 1,…,6.
She chooses k′₁,…,k′₆ uniformly at random from and computes v_j = D_{k′_j}(c) for j = 1,…,6.
If {u₁,…,u₆}∩{v₁,…,v₆}≠∅, we say the Birthday Attack succeeds in producing a candidate key pair. In that case, Eve obtains the candidate key pair (k,k′) = (k_i,k′_j), where (i,j) is the lexicographically smallest pair such that u_i = v_j.
If a candidate key pair (k,k′) is produced and (k,k′) can be used to decrypt any message Alice might send using her key, that is, if D_(k,k′)²(E_{(k₀,k′₀)}²(m)) = m for all m , then we say the Birthday Attack succeeds in breaking Double Happy.

Find the probability that the Birthday Attack succeeds in producing a candidate key pair, and compare your result with your answer to problem 6.
Find the probability that the Birthday Attack succeeds in breaking Double Happy.

Solution:

(a) To successfully produce a candidate key pair, it means that the Birthday Attack succeeds in finding a key pair that decrypts a known plaintext-ciphertext pair (m,c).

We still make use of the randRange() function to generate a random plain letter m and a key pair (k₀,k₀^′). We use this key pair to encrypt m and get c. Now we need to generate 6 random keys k_i and another 6 random keys k_i^′. Use k_i to encrypt m we get the set of {u_i} and use k_i^′ to decrypt c we get the set of {v_i}. Then if there is a match between any pair of (u_i,v_i), the counter increases by 1. In each experiment we run 1,000,000 trials and calculates the probability of succeeding in producing a candidate key pair. Then we run the experiments for 100 times and calculate the probability. The result is shown in Figure 3. The average probability is about 75.29%.

(b) To successfully break Double Happy, it means that the candidate key can decrypts all the cipertext produced from any m X with the key pair that Alice owns. Due to the special property of Double Happy, it is suffice to show that if the candidate key pair can decrypts one plaintext-ciphertext pair (m1,c1) X₁ and another plaintext-ciphertext pair (m2,c2) X₂, it can break the entire encryption system.

Therefore, we make use of the randRange() function to generate two random plain letter m₁ X₁ and m₂ X₂, and a key pair (k₀,k₀^′). We use this key pair to encrypt m₁,m₂ and get c₁,c₂. Now we need to generate 6 random keys k_i and another 6 random keys k_i^′. Use k_i to encrypt m we get the set of {u_i} and use k_i^′ to decrypt c we get the set of {v_i}. By finding the match between any pair of (u_i,v_i), we find the candidate key pair that can decrypts (m₁,c₁). If we also succeed in decrypting (m₂,c₂) with the same candidate key pair, we have succeeded in producing a candidate key pair that breaks Double Happy. In each experiment we run 1,000,000 trials and calculates the probability of succeeding in breaking Double Happy. Then we run the experiments for 100 times and calculate the probability. The result is shown in Figure 3. The average probability is about 13.53%.

Figure 3:

Birthday attack on Double Happy.