Cryptography Reference
In-Depth Information
i.e.,
q
r
(y) = aq
r−1
(y) + a
r−1
b,
(3.2)
where
y(y+1)
2
2
−1
N −1
N
1
N
N −y
N
N −1
N
a =
and b =
.
The solution to the recurrence in (3.2) is
q
r
(y) = a
r−y−1
q
y+1
(y) + (r−y−1)a
r−1
b,
r ≥y + 1.
Substituting the values of q
y+1
(y) (from Lemma 3.1.15), a and b, one can
obtain
y(y+1)
2
+2(r−2)
y
N
N −1
N
q
r
(y)
=
y(y+1)
2
−y+2(r−1)
+
1
N
N −1
N
y(y+1)
2
+2r−3
r−y−1
N
N −y
N
N −1
N
+
,
for y + 1 ≤ r ≤ N and for initial values of y (0 ≤y ≤ 31). Substituting r = N
and noting the fact that
P
(S
N
[S
N
[y]] = f
y
)∧(S
N
[y] ≤ N −1)
= P(S
N
[S
N
[y]] = f
y
),
we get the result.
The theoretical formula matches closely with the experimental results for
0 ≤ y ≤ 31. Item 4 in the proof of Lemma 3.1.15 connects the bias of S
r
[y]
toward f
y
(empirically observed by Roos [146] and theoretically analyzed in
Section 3.1.1 of this chapter) with that of S
r
[S
r
[y]] toward f
y
.
3.2 Non-Randomness of Permutation
RC4 KSA attempts to randomize the permutation S which is initialized
to an identity permutation. How to generate a random permutation is a well-
studied problem. Let us present one well known result from [88]. Given a
permutation of n elements
Π = (π
0
,π
1
,...,π
n−1
),
a series of n−1 transpositions can produce a random permutation as follows:
Here, rand(0,i) produces uniformly distributed random integers in the
range 0 through i. We reproduce the following result from [143, Page 171].
