Cryptography Reference
In-Depth Information
So
P (z
1
= f(K)) ≈
2
N
S
1
[2] = f(K)
P
N−1
1
N
S
1
[x] = f(K)
1
N(N−1)
≪
N
)
+
P
(as
x=0
even x=2
N−1
1
N
S
1
[x] = f(K)
+
P
x=0
odd x
S
1
[2] = f(K)
1
N
1
N
S
1
[2] = f(K)
=
P
+
P
N−1
S
1
[x] = f(K)
+
1
N
P
x=0
even x=2
N−1
+
1
N
S
1
[x] = f(K)
P
x=0
odd x
N−1
S
1
[2] = f(K)
1
N
1
N
S
1
[x] = f(K)
=
P
+
P
x=0
1
N
1
N
=
φ
N
+
1
(by Proposition 5.5.1)
1
N
(1 + φ
N
).
=
Let us detail the interpretation of the probabilities involved in the results
that are discussed. The event under consideration is the equality of two ran-
dom variables X and Y , where X is some byte of the permutation (e.g. S[y] as
in Corollary 3.1.2 and Proposition 5.5.1) or some byte of the keystream out-
put (e.g. z
1
as in Theorem 5.5.2), and Y is some function f(K) of the secret
key. Each of X and Y takes values from Z
N
. Thus, the joint space of (X,Y )
consists of N
2
different points (x,y), where x ∈
Z
N
. If X and
Y are i.i.d. uniform random variables, then for any (x,y), P(X = x,Y = y)
should be
Z
N
and y ∈
1
N
2
, and
N−1
P(X = Y )
=
P(X = x,Y = x)
x=0
N−1
N
2
= N
1
1
1
N
.
=
N
2
=
x=0
For N = 256, this value is approximately 0.0039, whereas the observed values
