YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

	CPSC 467a: Cryptography and Computer Security	Handout #4
Professor M. J. Fischer		September 25, 2008

Problem Set 2

Due on Friday, October 3, 2008.

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 ∈ X1 ∧ m ∈ X1 E (m ) = m if k ∈ X1 ∧ m ∈ X2 k ||| 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.)

Problem 2: Happy Decryption (5 points)

Describe the Happy decryption function D_k(c).

Problem 3: Security (10 points)

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

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?

Problem 5: Group Property (10 points)

Is Happy a group? Why or why not?

___________________________________________________________________________________

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

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.