Cryptography Reference
In-Depth Information
Case II: Consider y = v. We would have S
v
[v] = v, if v is not touched by
any of {j
1
,j
2
,...,j
v
} in the first v rounds, the probability of which is
(
N−1
N
)
v
.
Case III: Consider y > v. Once S
v
[v] = v, the swap in the next round moves
the value v to a random location j
v+1
. Thus,
P(S
v+1
[y] = v)
= P(S
v
[v] = v)P(j
v+1
= y)
v
1
N −1
N
=
N
.
For all y > v, until y is touched by the deterministic index i, i.e., until
round y + 1, v will remain randomly distributed. Hence, for all y > v,
v
1
N
N −1
N
P(S
y
[y] = v) = P(S
v+1
[y] = v) =
.
Noting that
1
N
+ P(S
y
[y] = v),
E(x
v,y
) = P(x
v,y
= 1) =
we have
E
v
= E(X
v
)
N−1
=
E(x
v,y
)
y=0
N−1
=
1 +
P(S
y
[y] = v)
y=0
v−1
N−1
=
1 +
P(S
y
[y] = v) + P(S
v
[v] = v) +
P(S
y
[y] = v)
y=0
y=v+1
v
v
N −1
N
+ (N −v)
1
N
N −1
N
=
1 + 0 +
v
2N −v
N
N −1
N
=
1 +
.
One can observe that E
v
decreases from 3.0 to 1.37, as v increases from 0
to 255. To demonstrate how close the experimental values of the expectations
match with the theoretical values, we have performed 100 million runs of the
KSA, with random key of 16 bytes in each run. As depicted in Figure 3.6,
The experimental data (left) correspond to the theoretical values (right). One
may also refer to the first two rows of Table 9.1 in Chapter 9 for more details.
