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