Cryptography Reference
In-Depth Information
0.4
0.35
0.3
0.25
0.2
<−−−−−−−−−−−−−−−−− A
0.15
0.1
<−−−−−−−−−−−−−−−−− B
<−−−−−−−−−−−−−−−−− C
0.05
0
0
50
100
150
200
250
300
y −−−−>
FIGURE 3.2:
A: P(S N [y]
= f y ), B: P(S N [S N [y]]
= f y ), C:
P(S N [S N [S N [y]]] = f y ) versus y (0 ≤ y ≤ 255).
Suppose S y+1 [y] = x, 0 ≤ x ≤ y− 1. Then S y+1 [x] can be equal to f y , if all
of the following four events occur.
Case I.a From round 1 (when i = 0) to x (when i = x−1), j does not touch
the indices x and f y . Thus, after round x, S x [x] = x and S x [f y ] = f y .
This happens with probability ( N−2
N
) x .
Case I.b In round x + 1 (when i = x), j x+1 becomes equal to f y , and after
the swap, S x+1 [x] = f y and S x+1 [f y ] = x. The probability of this event
is P(j x+1 = f y ) =
1
N .
Case I.c From round x + 2 (when i = x + 1) to y (when i = y − 1), again
j does not touch the indices x and f y . Thus, after round y, S y [x] = f y
and S y [f y ] = x. This occurs with probability ( N−2
N
) y−x−1 .
Case I.d In round y + 1 (when i = y), j y+1 becomes equal to f y , and after
the swap,
S y+1 [y]
= S y [f y ]
= x
Search WWH ::




Custom Search