Analysis of Key Scheduling - RC4: Stream Cipher and Its Variants - page 46

Adding the two contributions, we get the total probability as 2(N−1)

N 2 .
Here P(S v+1 [u] = v) is calculated for the special case u = 0, v = 1. Note
that the form of P(S v+1 [u] = v) for v ≥ u + 1 in general (see Lemma 3.2.7
later) does not work for the case u = 0,v = 1 only. This will be explained
more clearly in Remark 3.2.8.

v .

N−1
N

Proposition 3.2.5. For v ≥ 0, P(S v [v] = v) =

Proof: In the rounds 1 through v, the deterministic index i touches the
permutation indices 0,1,...,v−1. Thus, after round v, S v [v] will remain the
same as S 0 [v] = v, if v has not been equal to any of the v many pseudo-random
indices j 1 ,j 2 ,...,j v . The probability of this event is ( N−1
N

) v . So the result

holds for v ≥ 1. Furthermore,

0

N −1
N

P(S 0 [0] = 0) = 1 = .

Hence, for any v ≥ 0, we have

v

N −1
N

P(S v [v] = v) = .

Proposition 3.2.6. For v ≥u + 1,

v−u−1

1
N

N −1
N

P(S v [u] = v) = .

Proof: In round u + 1, the permutation index u is touched by the deter-
ministic index i for the first time and the value at index u is swapped with
the value at a random location based on j u+1 . Hence, P(S u+1 [u] = v) =

1

N .
The probability that the index u is not touched by any of the subsequent
v −u− 1 many j values, namely, j u+2 ,...,j v , is given by ( N−1
N

) v−u−1 . So,

after the end of round v,

v−u−1

1
N

N −1
N

P(S v [u] = v) = .

In Proposition 3.2.6, we have considered that the value v occupies the
location u of the permutation just before the deterministic index i becomes v.
In the following lemma, we analyze the same event (i.e., v occupying location
u) after the swap in the next round when i has already touched the location
v.

Lemma 3.2.7. For v ≥ u + 1, except for the case “u = 0 and v = 1,”

v−u v − 1

N 2

2v−u−1

1
N

N −1
N

+ 1
N

N −1
N

N − 1
N

P(S v+1 [u] = v) = .