Problem 2
Note the change in (a) : find the
rho
length. Exact calculation
is not required, give an
estimate.
On Hellman's tradeoff:
"A single matrix cannot efficiently cover
all the $N$ points,
(in particular, the only way we can cover
the approximately $N/e$ leaves
of a random directed graph is to choose them
as starting points). As we
add more rows to the matrix, we reach a situation
in which we start to
re-cover points which are already covered,
which makes the coverage
increasingly wasteful. To find this critical
value of $m$, assume
that the first $m$ paths are all disjoint,
but the next path
has a common point with one of the previous
paths. The first $m$ paths
contain exactly $mt$ distinct points (since
they are assumed to have
no repetitions), and the additional path
is likely to contain exactly
$t$ distinct points (assuming that $t$ is
less than $\sqrt N$).
By the birthday paradox, the two sets are
likely to be disjoint
as long as $t \cdot mt \leq N$, and thus
we choose $m$ and $t$
which satisfy the relation $mt^2=N$, which
we call
{\bf the matrix stopping rule}."
Problem 3
Please ignore the initial permutation
(IP) of DES. In question (b)
assume that bits are numbered 1..64
from left to right, so that
the zero bit (bit 64) is entering
the F-function of the first round.
Problem 5
I have added Part II to this exercise
for additional points.
Both Part I and II can be solved
with about 2^{16} queries and steps.