Cryptography Reference
In-Depth Information
The proof of
j
G
= z | z =
i
G
+ 1 + N
2
2
N
−
1
N(N −1)
P
=
is similar.
Given
2z = i
G
+ 1 mod N,
the events
z =
i
G
+ 1
2
z =
i
G
+ 1 + N
2
and
are equally likely. Thus we get the result.
The above results imply that z is either positively or negatively biased
to j
G
at any stage of PRGA. The bias is approximately
1
N
2
away from the
1
random association
N
as given in items 1, 2 in Corollary 5.4.2. The bias
is quite high when 2z = i
G
+ 1 and this bias is of the order of
1
N
over the
1
random association
N
. Experimental results also support the claim, which
identify that the assumption of “any permutation can arrive uniformly at
random at any step of RC4 PRGA” works with a very good approximation
and the absence of the Finney states does not change the order of the results.
The theoretical probabilities appearing on the right-hand side of items
1, 2, and 3 of Corollary 5.4.2 are 0.00392151, 0.00389099 and 0.00779718
respectively. The experimental values are very close to the theoretical ones,
but not exact. The reason is as follows. We arrive at the theoretical values
from combinatorial results based on 256! different permutations, which is a
huge number and cannot be generated in practice in a feasible time. Each
run of the experiment is based on samples of one million different keys, i.e.,
1 million permutations are considered, which is much less than the number
256!. Also there are some approximations involved in the theoretical results
as given in Corollary 5.4.2.
The next result presents an idea on how the cases for the Finney cycle can
be tackled. These cases may be subtracted from the cases in Theorem 5.4.1
for exact calculations.
Theorem 5.4.3. Suppose j
G
= i
G
+ 1 and S
G
[j
G
] = 1 (Finney cycle). Then
we have the following.
(1) If i
G
= 0, then
8
<
:
2(N − 2)!
if z = 0;
ψ(i
G
,j
G
,z) =
0
if z = 1;
(N −2)!−(N −3)!
otherwise.
(2) If i
G
= 1, then
(N −2)!
if z = 1,2;
ψ(i
G
,j
G
,z) =
(N −2)!−(N −3)!
otherwise.
