Cryptography Reference
In-Depth Information
Substituting the values above in Equation (6.3), we get
z r = 0 & S r−1 [r] = r
P
2
4
x=r−y
3
S r [x + y] = 0 & S r [r] = x
5
S r−1 [r] = y
=
P
P
y=r
2
3
4
5
1
N(N −1)
S r−1 [r] = y
=
P
0 +
y=r
x=r−y
x=0
(N −2) 1
N(N −1)
S r−1 [r] = y
=
P
y=r
N −2
N(N −1)
S r−1 [r] = y
=
P
y=r
S r−1 [r] = r
N −2
N(N −1)
N −2
N(N −1)
=
1−P
=
(1−p r−1,r )
Now, let us state the main theorem on the bias of RC4 initial bytes from
rounds 3 to 255.
Theorem 6.2.9. For 3 ≤ r ≤ 255, the probability that the r-th RC4 keystream
byte is equal to 0 is
N + c r
1
P(z r = 0) =
N 2 ,
.
N 2
N−1
N
where the value of c r is
p r−1,r
Proof: Adding the expressions of Lemma 6.2.7 and 6.2.8, one obtains
2
N −2
N(N −1)
P(z r = 0)
= p r−1,r
N +
(1−p r−1,r )
p r−1,r
N −1 +
N −2
N(N −1)
=
1
N +
1
N −1
1
N
=
p r−1,r
.
(6.5)
p r−1,r
. Note
N 2
N−1
1
c N 2 , with the value of c r as
N
Hence, P(z r = 0) =
N +
that the values p r−1,r can be explicitly calculated using Lemma 6.2.5.
In Theorem 6.2.9, the parameter c r that quantifies the bias is a function of
r. The next result is a corollary of Theorem 6.2.9 that provides exact numeric
bounds on P(z r = 0) within the interval 3 ≤ r ≤ 255, depending on the
corresponding bounds of c r within the same interval.
Search WWH ::




Custom Search