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 m₃ given that c = 3, and what is the conditional probability P[m = m₃∣c = 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 = E_k(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 m₃ = 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 E_k(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 E_k(m) = E_{k 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, E₀(),…,E₂₃() are twice as likely to be chosen as E₂₄() and E₂₅(), so P[m∣c] 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 E_k(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 D_k(c) such that D_k(E_k(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?

Justify your answers.

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 k₁ = k₂ . Then E_k1,k2(m) = E_k2(E_k1(m)) = (m + 2) mod 26. Since E_k3(m) = (m + 1) mod 26 for all k₃ , there is no k₃ for which E_k3 = E_k1,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 K_i to map a pair of n-bit words (L_i,R_i) to a new pair (L_i+1,R_i+1). By applying the stages in sequence, a t-stage network maps (L₀,R₀) to (L_t,R_t). (L₀,R₀) is the plaintext, and (L_t,R_t) is the corresponding ciphertext.
2. To encrypt a message (L₀,R₀), each stage works as follows:
   

   To decrypt a ciphertext (L_t,R_t), 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 C_k(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 ξ = C_k(m). A stronger property requires that the above is true even if the attacker knows a set of valid MAC pairs {(m₁,ξ₁),…,(m_t,ξ_t)} 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 ξ = C_k(m) and sends (m,ξ) to Bob. Upon receipt of the pair, Bob checks whether ξ = C_k(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 E_k be the resulting cryptosystem, defined for sequences of message blocks m₁…m_t, and suppose c = c₁…c_t = E_k(m₁…m_t). We define the MAC C_k(m) = c_t. In CBC or CFB mode, each ciphertext block c_k depends on both the current message block m_k and on the previous ciphertext block c_k-1. Hence, the last ciphertext block c_t depends on the entire message m₁…m_t, 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 Z_n.
2. Solve the congruence equation 45x ≡ 49 (mod 77).

Solution:

1. The congruence equation ax ≡ b (mod n) has a solution x Z_n 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) = 1∣49, 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)