Cryptography Reference
In-Depth Information
l ǫ (in %) ǫ
max
(in %) u
max
v
max
n
5
n
10
n
5
(in %) n
10
(in %)
5
0.75
73.67
9
254
1160
763
1.770
1.164
8
0.48
42.48
15
255
548
388
0.836
0.592
12
0.30
21.09
23
183
293
198
0.447
0.302
15
0.25
11.34
44
237
241
2
0.368
0.003
16
0.24
35.15
128
127
161
7
0.246
0.011
20
0.20
5.99
30
249
3
0
0.005
0.000
24
0.19
4.91
32
247
0
0
0.000
0.000
30
0.19
6.54
45
29
1
0
0.002
0.000
32
0.22
35.37
128
127
11
6
0.017
0.009
48
0.18
4.24
194
191
0
0
0.000
0.000
64
0.26
35.26
128
127
6
4
0.009
0.006
96
0.21
4.52
194
191
0
0
0.000
0.000
128
0.34
37.00
128
127
3
2
0.005
0.003
256
0.46
2.58
15
104
0
0
0.000
0.000
TABLE 3.4: The number and percentage of anomaly pairs along with the
average and maximum error for different key lengths.
3.3 Movement Frequency of Permutation Values
During the KSA, each index of the permutation is touched exactly once by
i and some indices are touched by j additionally. Let us turn the view around.
Instead of the permutation indices, let us investigate the actual entries in the
permutation in terms of being touched by i and j. We are going to show that
many values in the permutation are touched at least once with a very high
probability by the indices i,j during the KSA.
Theorem 3.3.1. The probability that a value v in the permutation is touched
exactly once during the KSA by the indices i,j, is given by
2v
N
(
N−1
N
)
N−1
,
0 ≤v ≤ N −1.
Proof: Initially, v is located at index v in the permutation. It is touched
exactly once in one of the following two ways.
Case I: The location v is not touched by any of {j
1
,j
2
,...,j
v
} in the first v
rounds. This happens with probability (
N−
N
)
v
. In round v + 1, when
i becomes v, the value v at index v is moved to the left by j
v+1
due to
the swap and remains there until the end of KSA. This happens with
probability
P(j
v+1
∈{0,...,v−1})P(j
τ
= j
v+1
,v + 1 ≤ τ ≤N)
N−v−1
v
N
N −1
N
=
.
