Cryptography Reference
In-Depth Information
Suppose the indices r−1, τ and r are not touched by the pseudo-random
index j
G
in the first r−2 rounds of the PRGA. This happens with probability
(
N−
N
)
r−2
. In round r−1 of the PRGA, due to the swap, the value τ at index
r − 1 moves to the index j
r−1
with probability 1, and j
r−1
∈ {τ,r} with
probability (
N−2
N
). Further, if S
r−1
[r] remains 0, then in round r of the
PRGA, j
r
= j
r−1
and
= S
r
S
r
[r] + S
r
[j
r
]
z
r
= S
r
S
r−1
[r] + S
r−1
[j
r−1
]
= S
r
[0 + τ]
= S
r
[τ]
= f
r−1
with probability
r−2
N −3
N
N − 2
N
β
r
γ
r
= δ
r
(say).
Since, τ can values r,r+1,r+2,...,N−1, the total probability is δ
r
(N−r).
Substituting the values of α
r
,β
r
,γ
r
,δ
r
, we get the probability that the event
(z
r
= f
r−1
) occurs in the above path is
0
1
[
r(r−1)
2
+r]
N −r
N
N −r + 1
N
N −1
N
1
N
@
A
p ≈
+
N−r
r−2
γ
r
.
N −2
N
N −3
N
If the above path is not followed, still there is (1 − p)
N
probability
of occurrence of the event due to random association. Adding these two
probabilities, we get the result.
The theoretically computed values of the probabilities according to the
expressions derived in the above two theorems match with the experimental
values provided in Table 5.6. Theorem 5.6.6 does not cover the cases r = 1 and
r = 2. Case r = 1 has already separately been presented in Theorem 5.6.5. It
is interesting to justify the absence of bias in case r = 2 as observed experi-
mentally in Table 5.6.
5.6.3 Cryptanalytic Applications
Consider the first keystream output byte z
1
of the PRGA. We find the
results that P(z
1
= 1 − f
1
) = 0.0053 (from Theorem 5.6.3) and that
P(z
1
= f
0
) = 0.0043 (from Theorem 5.6.5 and Table 5.6). Further, from
Theorem 5.5.2, we have the result that P(z
1
= f
2
) = 0.0053. Taking them
