Cryptography Reference
In-Depth Information
Now, we can compute the probabilities P(S
1
[t] = r) based on the probabilities
for S
0
, which are in turn derived from Theorem 3.2.3. We have three cases:
Case t = 1: In this case, using the recurrence relation S
1
[1] = S
0
[S
0
[1]], we
can write
N−1
P(S
1
[1] = r) =
P(S
0
[1] = X)P(S
0
[X] = r).
X=0
Case t = r: In this situation, if S
0
[1] = r, we will surely have S
1
[r] = r as
these are the positions swapped in the first round, and if S
0
[1] = r,
the position t = r remains untouched and S
1
[r] = r is only possible if
S
0
[r] = r. Thus, we have
P(S
1
[r] = r) = P(S
0
[1] = r) + (1 −P(S
0
[1] = r))P(S
0
[r] = r).
Case t = 1,r: In all other cases where t = 1,r, it can either take the value
S
0
[1] with probability P(S
0
[1] = t), or not. If t = S
0
[1], the value S
0
[t]
will get swapped with S
0
[1] = t itself, i.e., we will get S
1
[t] = t = r for
sure. Otherwise, the value S
1
[t] remains the same as S
0
[t]. Hence,
P(S
1
[t] = r) = (1−P(S
0
[1] = t))P(S
0
[t] = r).
Combining all the above cases together, we obtain the desired result.
Now, let us analyze the keystream z
r
. RC4 PRGA begins with j
0
= 0. In
the first round, i.e., for r = 1, we have j
1
= j
0
+ S
0
[1] = S
0
[1] which, due
to Theorem 3.2.3, is not uniformly distributed. In the second round, i.e., for
r = 2, we have j
2
= j
1
+S
1
[2] = S
0
[1] +S
1
[2], which is closer to uniformly
random distribution than j
1
. In round 3, another pseudo-random byte S
2
[3]
would be added to form j
3
. From round 3 onwards, j
G
can safely be assumed
to be uniform over Z
N
. Experimental observations also confirm this.
Before we discuss the next two lemma, note that
= S
r
[S
r
[i
r
] + S
r
[j
r
]]
= S
r
[S
r
[r] + S
r−1
[i
r
]]
= S
r
[S
r
[r] + S
r−1
[r]].
z
r
We would make use of the above identity in proving Lemma 6.2.7 and 6.2.8.
z
r
= 0 & S
r−1
[r] = r
N
.
Lemma 6.2.7. For 3 ≤ r ≤ 255, P
= p
r−1,r
