YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer SecurityHandout #9
Xueyuan Su   February 16, 2010



 

Solution to Problem Set 2

Due on Monday, February 15, 2010

In this problem set, we consider a variant of the Caesar cipher which we call the “Happy-2010” cipher (named after the venerable “Happy Hacker” of CPSC 223 fame). Happy-2010 (E,D) is defined as follows: Let M = C = K = {0,,25}. Define

         {  (m  + 2k) mod 26  if m + k is even
Ek (m) =
            m                if m + k is odd

We also consider Double Happy (E2,D2). Here, K2 = K×K, and E(k1,k2)2 = Ek1(Ek2(m)).

Feel free to write programs to help you solve these problems. If you do, include the programs and their output along with your solutions, and say how the computer was used.

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: IAMASECXEZMESSAGE.

Problem 2: Happy Decryption (5 points)

Describe the Happy decryption function Dk(c).

Solution:

        {
          (c- 2k ) mod 26  if c + k is even
Dk(c) =   c                if c + k is odd

Problem 3: Security (10 points)

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

Solution:

  1. No. Because the encryption function maps odd numbers to odd numbers, and even numbers to even numbers. Haven seen the ciphertext, you know the parity of the plaintext.
  2. No. The same reason as before.

Problem 4: Equivalent Key Pairs (10 points)

Suppose m0 = c0 = 4.

  1. Find all key pairs (k,k) such that E(k,k)2(m0) = c0.
  2. Do all such key pairs give rise to the same function E(k,k)2? That is, if E(kˆ,ˆk′)2(m0) = E(k,k)2(m0) = c0, does E(ˆ
k, ˆ′
k)2(m) = E(k,k)2(m) for all m ∈M? Why or why not?

Solution:

  1. You need to consider many interesting cases.
  2. No. Here is a simple counter-example. Consider two key pairs (0,0) and (0,1). Then E(0,0)2(1) = 1, but E(0,1)2(1) = 3.

Problem 5: Group Property (10 points)

Is Happy a group? Why or why not?

Solution: No. There are two ways to think about this problem.

Thus, Happy is not a group.