Cryptography Reference
In-Depth Information
Proof: Let A
y
denote the event as defined in the proof of Lemma 3.1.3.
Now, S
r
[y] can be equal to f
y
in two ways. One way is that the event A
y
and
the event S
r
[y] = S
0
[j
y+1
] occur together (recall that P(E
y
|A
y
) = 1)). Com-
bining the results of Lemma 3.1.3 and Lemma 3.1.4, we get the contribution
of this part to be approximately
y(y+1)
2
r−1
N −1
N
N −y
N
N −1
N
P(A
y
)P(S
r
[y] = S
0
[j
y+1
])
=
[
y(y+1)
2
+(r−1)]
N −y
N
N −1
N
=
.
Another way is that neither of the above events happen and still S
r
[y] equals
y
y
S
0
S
0
[x] +
K[x]
due to random association. The contribution of this
x=0
x=0
1 − (
N−y
N
)
[
y(y+1)
N
. Adding
these two contributions, we get the total probability to be approximately
) (
N−1
N
+(r−1)]
second part is approximately
2
[
y(y+1)
2
+(r−1)]
N −y
N
N −1
N
0
1
[
y(y+1)
2
+(r−1)]
N −y
N
N −1
N
1
N
@
A
+
1−
[
y(y+1)
2
+(r−1)]
1−
1
N
N −y
N
N − 1
N
1
N
=
+
[
y(y+1)
2
+r]
N −y
N
N −1
N
1
N
.
=
+
Corollary 3.1.6. The bias of the final permutation after the KSA toward the
secret key is given by
[
y(y+1)
2
+N]
N −y
N
N −1
N
+
1
P(S
N
[y] = f
y
) ≈
N
, for 0 ≤ y ≤N −1.
Proof: Substitute r = N in the statement of Theorem 3.1.5.
Note that if the initial permutation S
0
is identity, then we have f
y
=
y
y(y+1)
2
+
K[x]. Table 3.2 shows the theoretical values of the probability
x=0
P(S
N
[y] = f
y
) in this case which is consistent with the experimental values
provided in Table 3.1.
Index 48 onwards, both the theoretical as well as the experimental values
tend to
1
N
= 0.00390625 ≈ 0.0039, for N = 256. This is the probability of the
equality between two randomly chosen values from a set of N elements.
