Cryptography Reference
In-Depth Information
We can estimate the number of pairwise different
k
i
,
j
in one table as follows.
m
t
−
1
E
#
}
=
Pr
k
i
,
j
∈{
}
.
k
i
,
j
;
i
<
i
or
j
<
{
k
i
,
j
;1
≤
i
≤
m
,
0
≤
j
<
t
j
i
=
1
j
=
0
(We
do
not
count
the
end
value
of
each
chain.)
Let
Fresh
i
,
j
be
the
event
k
i
,
j
∈{
}
. Since
k
i
,
j
=
k
i
,
j
;
i
<
i
or
j
<
j
f
(
k
i
,
j
−
1
), we have Fresh
i
,
j
⊆
Fresh
i
,
j
−
1
.
Furthermore, we have
Pr
Fresh
i
,
j
|
Fresh
i
,
j
−
1
≥
it
2
n
.
1
−
Hence we have
1
j
+
1
Pr
Fresh
i
,
j
≥
it
2
n
−
.
We deduce that the expected number of keys per table is greater than
1
j
+
1
m
t
−
1
it
2
n
−
.
i
=
1
j
=
0
The probability of success for looking for
K
is the probability that
K
is one of the keys
in the table. Thus we have
1
j
+
1
m
t
−
1
it
2
n
2
−
n
p
≥
−
.
i
=
1
j
=
0
As the table gets larger, some chain will eventually collide and merge, which pre-
vents the number of keys per table from increasing. So it may be preferable to keep
many small tables. Figs. 2.37, and 2.38 illustrate the multitable version. Obviously the
precomputation complexity is
P
=
mt
encryptions and reductions. The time complex-
t
encryptions and reductions in the worst case, and
T
e
=
2
t
in the average case (for success only). The memory size is about
M
ity of the attack is
T
=
=
m
blocks. The
probability
p
of success is such that
1
j
+
1
1
m
t
−
1
it
2
n
2
−
n
p
≥
1
−
−
−
.
i
=
1
j
=
0
2
3
and 1
e
−
L
We let
x
=
−
be the right-hand term of the
p
inequality. For
=
λ
x
,
m
=
µ
x
, and
t
=
τ
x
, when
µτ
x
,wehave
x
log
1
j
+
1
1
x
−
3
µ
x
τ
x
−
1
i
x
2
L
=−
λ
−
−
i
=
1
j
=
0
Search WWH ::
Custom Search