CSL866: Problem Set 1
[75 points] [Deadline: 31st January]
(Try using latex for problems 3,4, and 5 though hand written answers
will be accepted.)
Problem 1: [10
points]
In this problem you have to decipher a substitution
cipher. Different substitution rules are used for encryption for every
student so that you solve the assignment individually. You may download
your ciphertext from this
page.
Problem 2: [10
points]
The instructions for problem 2 are included in the ciphertext of
problem 1. You will have to solve problem 1 to be able to solve problem
2!
Problem 3: [20
points]
Recall that the DES algorithm consists of a loop that has 16 rounds.
Consider the following attack on DES:
By some means, you have obtained a message-ciphertext pair (M, C) and
you have also obtained the corresponding 32 bit strings L2 and R2.
Recall that L2 and R2 are the strings after the second round of the
loop. Give a key-recovery attack that runs in time much better than
2^{56}.
(Hint: You will have
to dig into the mechanism of DES to figure out how may keys can
possibly give L2, R2)
Problem 4: [15 points]
Show the following version of the birthday lemma:
Let N and r be positive integers and let S be a set of size N. Suppose we pick r elements Y1,...,Yr from the set S randomly and then pick another r elements Z1,...,Zr randomly from S. Let D(N, r) denote the probability that
there is a pair (i, j) such
that Yi = Zj. Show that
D(N, r) >= C(n, 2r)/2.
(Remember C(N, 2r) is the probability that 2r randomly chosen elements from S are not all distinct.)
Problem 5: [20 points]
Given a PRF F:
,
construct a PRF G:
which is secure as long as F
is secure. Give a formal proof.