YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 467b: Cryptography and Computer Security | Handout #10 | |

Xueyuan Su | March 1, 2010 | |

Solution to Midterm Examination

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!

___________________________________________________________________________________

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

- What is the initial distribution on the message space?
- What is the most likely message m
_{3}given that c = 3, and what is the conditional probability P[m = m_{3}∣c = 3]? - What can you say about the security of this cryptosystem? I.e., what does Eve learn about m when she sees c?
- 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 .

- By total probability theorem, for any 0 ≤ i ≤ 3, we have
- Given c = 3, the most likely plaintext is m
_{3}= 0. The conditional probability - When Eve sees c, she learns information about the distribution of the plaintext m in the form
of an a posteriori distribution over . Namely,
- 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_{0}(),…,E_{23}() are twice as likely to be
chosen as E_{24}() and E_{25}(), so P[m∣c] is not uniformly distributed, and Eve gets partial information about
m from seeing c.

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

- 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. - Does the resulting symmetric cryptosystem have the group property? Why or why not?

Justify your answers.

- It is true for all and f(). The decryption function is
- 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
_{1}= k_{2}. 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_{3}, there is no k_{3}for which E_{k3}= E_{k1,k2}; hence, the group property does not hold.

DES is built from a Feistel network.

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

- 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_{0},R_{0}) to (L_{t},R_{t}). (L_{0},R_{0}) is the plaintext, and (L_{t},R_{t}) is the corresponding ciphertext. - To encrypt a message (L
_{0},R_{0}), each stage works as follows:To decrypt a ciphertext (L

_{t},R_{t}), each stage works as follows:

Problem 5: Message Authentication Codes (MAC)

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

- 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_{1},ξ_{1}),…,(m_{t},ξ_{t})} as long as m is not a message in this set. - 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. - 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_{1}…m_{t}, and suppose c = c_{1}…c_{t}= E_{k}(m_{1}…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_{1}…m_{t}, as desired.

Problem 6: Congruence Equations

- Describe a necessary and sufficient condition for the congruence equation ax ≡ b (mod n)
to have a solution x Z
_{n}. - Solve the congruence equation 45x ≡ 49 (mod 77).

- The congruence equation ax ≡ b (mod n) has a solution x Z
_{n}iff n∣(ax - b) for some x Z ifffor some x,y Z. This is a linear Diophantine equation. It has a solution iff gcd(a,n)∣b.

- 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 r _{i}u _{i}v _{i}q _{i}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)