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

N−1
N 2 .

Case I: Let K[0] = 0,K[1] = N − 1. The probability of this event is

Now

S 2 [1] = S 1 [K[0] + K[1] + 1]

= S 1 [K[0]]
= S 0 [0]
=

0.

So,

S 2 [S 2 [1]] = S 2 [0]

= S 1 [0]
= K[0]
= K[0] + K[1] + 1.

Note that S 2 [0] = S 1 [0], as K[0] + K[1] + 1 = 0.
Moreover, in this case, S 2 [1] ≤ 1.

Case II: Let K[0] + K[1] = 0,K[0] = 1, i.e., K[1] = N − 1. The probability
of this event is N−1

N 2 . Now

S 2 [1] = S 1 [K[0] + K[1] + 1]

= S 1 [1]
= S 0 [1]
= 1.

Note that S 1 [1] = S 0 [1], as K[0] = 1. So,

S 2 [S 2 [1]] = S 2 [1]

= 1
= K[0] + K[1] + 1.

Also, in this case, S 2 [1] ≤ 1 holds.

Case III: S 2 [S 2 [1]] could be K[0] + K[1] + 1 by random association except
for the two previous cases.
Out of that, S 2 [1] ≤ 1 will happen in

2
N

proportion of cases.

Thus

2(N −1)
N 2

1− 2(N −1)
N 2

1
N

P(S 2 [S 2 [1]] = K[0] + K[1] + 1) = +

3
N

− 4

2
N 3 .

=

N 2 +