Cryptography Reference
In-Depth Information
present an evidence that the permutation after the KSA can be distinguished
from random permutation without any assumption on the secret key.
Due to the small keys (say 5 to 32 bytes) generally used in RC4, some of
the assumptions differ from practice and hence the theoretical formulae do
not match with the experimental results for some values of u and v. We also
discuss this issue later.
Lemma 3.2.4. P(S 2 [0] = 1) = 2(N−1)
.
N 2
Proof: In the first round, we have i = 0, and
j 1
= 0 + S[0] + K[0]
= K[0].
In the second round, i = 1 and
j 2 = j 1 + S 1 [1] + K[1].
Consider two mutually exclusive and exhaustive cases, namely, K[0] = 1 and
K[0] = 1.
Case I: Take K[0] = 1. So, after the first swap, S 1 [0] = 1 and S 1 [1] = 0.
Now,
j 2
= K[0] + 0 + K[1]
= K[0] + K[1].
After the second swap, S 2 [0] will remain 1, if K[0] + K[1] = 0. Hence
the contribution of this case to the event (S 2 [0] = 1) is
1
N
N −1
N
P(K[0] = 1)P(K[0] + K[1] = 0)
=
N −1
N 2
=
.
Case II: Now consider K[0] = 1. After the first swap, S 1 [1] remains 1. Now,
j 2
= K[0] + 1 + K[1]
= K[0] + K[1] + 1.
Thus, after the second swap, S 2 [0] will obtain the value 1, if K[0]+K[1]+
1 = 0. Hence the contribution of this case to the event (S 2 [0] = 1) is
N −1
N
1
N
P(K[0] = 1)P(K[0] + K[1] + 1 = 0)
=
N −1
N 2
=
.
Search WWH ::




Custom Search