YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer Security Handout #10 Xueyuan Su March 1, 2010

Solution to Midterm Examination

Instructions:

This is a closed book examination. Answer any 5 of the following 6 questions. Write the numbers of the five questions that you want graded on the cover of your bluebook. All questions count equally. You have 75 minutes. Remember to write your name on your bluebook and to justify your answers. Good Luck!

___________________________________________________________________________________

Problem 1:

Consider a symmetric cryptosystem with = = {0,1,2,3}, where the joint probability distribution over message-ciphertext pairs is described by the table below.

1. What is the initial distribution on the message space?
2. What is the most likely message m3 given that c = 3, and what is the conditional probability P[m = m3c = 3]?
3. What can you say about the security of this cryptosystem? I.e., what does Eve learn about m when she sees c?
4. Describe a key space and an encryption function c = Ek(m) that gives rise to the given joint probability distribution when keys are chosen uniformly from .

Solution:

1. By total probability theorem, for any 0 i 3, we have

2. Given c = 3, the most likely plaintext is m3 = 0. The conditional probability

3. When Eve sees c, she learns information about the distribution of the plaintext m in the form of an a posteriori distribution over . Namely,

4. There are many possible answers. For example, let = {0,1,2,3,5,6,7,10,11,15} and Ek(m) = (k - m) mod 4.

Problem 2: Security of a Symmetric Cryptosystem

Happy Hacker decides to improve on the Caesar cipher by making the key space larger. He keeps = = {0, …, 25} as before, but he lets = {0,,49} and defines

Compare the security of Hacker’s system with the ordinary Caesar cipher. Justify your answers.

Solution: Hacker’s system is less secure than ordinary Caesar, despite the larger key space. Because Ek(m) = Ek mod 26(m) for any k, the larger key space does not increase the number of possible encryption functions, but it does alter their distribution. Now, E0(),,E23() are twice as likely to be chosen as E24() and E25(), so P[mc] is not uniformly distributed, and Eve gets partial information about m from seeing c.

Problem 3: Group Property

Let = = {0,,25} as in the Caesar cipher. Let the key space be an arbitrary finite set, let f : be an arbitrary function, and let Ek(m) = (f(k) + m) mod 26.

For each of the following questions, answer whether it holds for all and f(), for some and f(), or for no and f().

1. Is there a decryption function Dk(c) such that Dk(Ek(m)) = m for all m ? If so, define it. If not, explain why not.
2. Does the resulting symmetric cryptosystem have the group property? Why or why not?

Solution:

1. It is true for all and f(). The decryption function is

2. It is true for some but not all (,f() pairs.
True for some pairs
If = and f() is the identity function, then the resulting cryptosystem is the ordinary Caeser cipher, which is known to have the group property.
False for some pairs
If f(k) = 1 for all k , then the resulting cryptosystem does not have the group property. Choose k1 = k2 . Then Ek1,k2(m) = Ek2(Ek1(m)) = (m + 2) mod 26. Since Ek3(m) = (m + 1) mod 26 for all k3 , there is no k3 for which Ek3 = Ek1,k2; hence, the group property does not hold.

Problem 4: Feistel Network

DES is built from a Feistel network.

1. Describe how a Feistel network can be used to build a symmetric cryptosystem from an arbitrary “scrambling” function f() of appropriate type.
2. Describe how encryption and decryption works for a cryptosystem built from a Feistel network.

Solution:

1. A Feistel network consists of some number t of stages. Each stage i uses f() and a subkey Ki to map a pair of n-bit words (Li,Ri) to a new pair (Li+1,Ri+1). By applying the stages in sequence, a t-stage network maps (L0,R0) to (Lt,Rt). (L0,R0) is the plaintext, and (Lt,Rt) is the corresponding ciphertext.
2. To encrypt a message (L0,R0), each stage works as follows:

To decrypt a ciphertext (Lt,Rt), each stage works as follows:

Problem 5: Message Authentication Codes (MAC)

1. Define what a Message Authentication Code (MAC) system is and the properties it should have.
2. Describe a practical use for a MAC.
3. Describe how to build a MAC system from a given symmetric cryptosystem.

Solution:

1. A MAC system is a cryptographic system that generates a short piece of information used to authenticate a message. A MAC is generated by a function Ck(m) that can be computed by anyone knowing the secret key k. It should be hard for an attacker, without knowing k to find any pair (m,ξ) such that ξ = Ck(m). A stronger property requires that the above is true even if the attacker knows a set of valid MAC pairs {(m11),,(mtt)} as long as m is not a message in this set.
2. A MAC can be used to authenticate the sender of a message. Given a symmetric cryptosystem, Alice computes the MAC ξ = Ck(m) and sends (m,ξ) to Bob. Upon receipt of the pair, Bob checks whether ξ = Ck(m). If so, the authentication succeeds; otherwise, the authentication fails. By the properties of a MAC, an attacker without knowing k is unlikely to be able to produce a valid pair (m,ξ) that will be accepted by Bob.
3. A MAC system can be built by using a block cipher in CBC or CFB chaining mode. Let Ek be the resulting cryptosystem, defined for sequences of message blocks m1mt, and suppose c = c1ct = Ek(m1mt). We define the MAC Ck(m) = ct. In CBC or CFB mode, each ciphertext block ck depends on both the current message block mk and on the previous ciphertext block ck-1. Hence, the last ciphertext block ct depends on the entire message m1mt, as desired.

Problem 6: Congruence Equations

1. Describe a necessary and sufficient condition for the congruence equation ax b (mod n) to have a solution x Zn.
2. Solve the congruence equation 45x 49 (mod 77).

Solution:

1. The congruence equation ax b (mod n) has a solution x Zn iff n(ax - b) for some x Z iff

for some x,y Z. This is a linear Diophantine equation. It has a solution iff gcd(a,n)b.

2. To solve
 (1)

we solve the corresponding Diophantine equation

 (2)

Since gcd(45,77) = 149, this Diophantine equation has a solution. We use the extended Euclidean algorithm to solve it.

 i ri ui vi qi 1 45 1 0 2 77 0 1 0 3 45 1 0 1 4 32 -1 1 1 5 13 2 -1 2 6 6 -5 3 2 7 1 12 -7

Therefore, x = 12 and y = -7 satisfies

 (3)

The solution to (2) is x = 12 × 49 = 588 and y = -7 × 49 = -343. The solution to (1) is x mod 77 = 588 mod 77 = 49.

(end of exam)