Cryptography Reference
In-Depth Information
Finally, note that the number of hops (n + 1) is bounded from below by 1
and from above by (r−t + 1), depending on the initial gap between t and r
positions. Considering the sum over t and n with this consideration, we get
the desired expression for P(S
r−1
[r] = X).
The following is an immediate implication of Lemma 5.6.1.
Corollary 5.6.2. For 2 ≤r ≤ N −1, we have
r−1
1−
1
N
P(S
r−1
[r] = f
r
) ≈ p
r
+
r−1
r−t
n
r−2−n
1−p
r
N(N −1)
1
n!
r−t−1
N
1−
1
N
,
t=1
n=0
where
[
r(r+1)
2
+N]
N −r
N
N −1
N
1
N
.
p
r
=
+
Proof: Taking X = f
r
and τ = 0 in Lemma 5.6.1, one obtains
P(S
0
[r] = f
r
)
= P(S
N
[r] = f
r
)
[
r(r+1)
2
+N]
N −r
N
N −1
N
1
N
≈
+
(by Corollary 3.1.6)
= p
r
(say).
Assume for all t = r, the events (S
0
[t] = f
r
) are all equally likely and hence
substitute
P(S
0
[t] = f
r
) =
1−p
r
N −1
,
in Lemma 5.6.1. This gives the desired expression.
Now consider the bias of each keystream output byte to a combination of
the secret key bytes. Let ω
r
denote the probabilities P(S
r−1
[r] = f
r
), r ≥ 1.
Theorem 5.6.3. For r ≥ 1, we have
1
N
P(z
r
= r−f
r
) =
(1 + ω
r
).
Proof: Take two separate cases in which the event (z
r
= r−f
r
) can occur.
Case I: S
r−1
[r] = f
r
and z
r
= r−S
r−1
[r]. By Theorem 5.2.1, the contribu-
tion of this case is
2
N
P(S
r−1
[r] = f
r
)P(z
r
= r−S
r−1
[r]) = ω
r
