Cryptography Reference
In-Depth Information
In consistence with the notations in [187, Section 4], one may write the
keystream generation step as follows. For 0 ≤ i mod 1024 < 512,
h
1
(P[i ⊟ 12])⊕P
up
[i mod 512], for 0 ≤i mod 512 ≤ 11;
h
1
(P
up
[i ⊟ 12])⊕P
up
[i mod 512], for 12 ≤ i mod 512 ≤ 511.
(10.2)
Let P
up
denote the updated array P, when the two “+” operators are replaced
by “⊕” in the right-hand side of Equation (10.1). Then for 0 ≤ b≤ n−1, the
b-th bit of the updated words of the array P is given by
s
i
=
b
b
⊕
10+b
P
up
[i mod 512]
=
P[i mod 512]
P[i ⊟ 3]
23+b
⊕
8+b
.
⊕
P[i ⊟ 511]
P[i ⊟ 10]
Define
h
1
(P[i ⊟ 12])⊕P
up
[i mod 512], for 0 ≤i mod 512 ≤ 11;
h
1
(P
up
[i ⊟ 12])⊕P
up
[i mod 512], for 12 ≤ i mod 512 ≤ 511.
Each s
i
can be treated as the “distorted” value of s
i
due the XOR-
approximation of the sum of three integers in Equation (10.1). From Corol-
lary 10.2.2 of Proposition 10.2.1 and the definition of s
i
's, one can immediately
note the following result.
Lemma 10.2.3. For 0 ≤ i mod 1024 < 512 and 0 ≤ b ≤n−1,
Prob
s
i
=
b
=
b
b
=
b
s
i
P
up
[i mod 512]
s
i
= Prob
P
up
[i mod 512]
= p
b
.
Now, 32-bit integers ζ
i
's can be constructed as estimates of the keystream
words s
i
's as follows.
b
s
i
if b = 0,1;
[ζ
i
]
b
=
b
s
i
1⊕
if 2 ≤ b < 32.
Thus, one has the following result.
Theorem 10.2.4. The expected number of bits where the two 32-bit integers
s
i
and ζ
i
match is approximately 21.5.
Proof: Let m
b
= 1, if [s
i
]
b
= [ζ
i
]
b
; otherwise, let m
b
= 0, 0 ≤ b ≤ 31.
Hence, the total number of matches is given by
31
M =
m
b
.
b=0
By linearity of expectation,
31
E(M)
=
E(m
b
)
b=0
31
=
Prob(m
b
= 1).
b=0
