Cryptography Reference
In-Depth Information
where t ≥ 0, 0 ≤ r ≤ N − 1. Note that p
0,r
= P(S
0
[r] = r) can be directly
found from Theorem 3.2.3.
A natural method of calculating p
r−1,r
= P(S
r−1
[r] = r) would be to use
Lemma 5.6.1 with X = r. But unlike Corollary 5.6.2, one cannot take the
initial round to be τ = 0 here. The reason is as follows. We know that after
the swap in the first round of the PRGA,
S
1
[S
0
[1]] = S
1
[j
1
]
= S
0
[i
1
]
= S
0
[1]
So, if S
0
[1] = r, then the event (S
1
[r] = r) occurs with probability 1. If
S
0
[1] = r, then S
1
[r] may contain r due to random association. Thus, for
any given r, there is a sharp jump between the probabilities p
0,r
and p
1,r
.
This means, one should consider τ = 1 as the initial round and then apply
Lemma 5.6.1 to calculate p
r−1,r
. This gives the following result.
Lemma 6.2.5. For r ≥ 3, the probability that S
r−1
[r] = r is
r−2
1−
1
N
p
r−1,r
≈ p
1,r
+
r−1
r−t
n
r−3−n
P(S
1
[t] = r)
n!N
r−t−1
N
1−
1
N
.
t=2
n=0
Observe that for t = r, P(S
1
[t] = r) coincides with p
1,r
. In order to have
the explicit values of p
r−1,r
, we need the probability distribution P(S
1
[t] = r),
0 ≤t ≤ N −1. This is given in the following result.
Lemma 6.2.6. After the completion of the first round of RC4 PRGA, the
probability that S
1
[t] = r, 0 ≤ r ≤ N −1, is given by
P(S
1
[t] = r)
8
<
N−1
P(S
0
[1] = X)P(S
0
[X] = r),
t = 1;
X=0
=
:
P(S
0
[1] = r) + (1−P(S
0
[1] = r)) P(S
0
[r] = r),
t = r;
(1−P(S
0
[1] = t))P(S
0
[t] = r),
otherwise.
Proof: After the first round of RC4 PRGA, we obtain the state S
1
from
the initial state S
0
through a single swap operation between the positions
i
1
= 1 and j
1
= S
0
[i
1
] = S
0
[1]. Thus, all other positions of S
0
remain the
same apart from these two. This gives us the value of S
1
[t] as follows.
8
<
:
S
0
[S
0
[1]],
t = 1;
S
1
[t] =
S
0
[1],
t = S
0
[1];
S
0
[t],
otherwise.
