Cryptography Reference
In-Depth Information
A
1
(y). Thus, the components α
yx
's for the probabilities p
y1
, p
y2
, p
y3
and p
y4
are respectively given by
α
y1
= P (A
1
(y))P (A
1
(y−1)),
y
N −1
N
α
y2
= P (A
2
(y))P (A
2
(y−1))
,
α
y3
= P (A
1
(y))P (A
2
(y−1)),
y
N −1
N
α
y4
= P (A
2
(y))P (A
1
(y−1))
.
Substituting the probability expressions for A
1
(y),A
1
(y−1),A
2
(y) and A
2
(y−
1), we get the results.
Corollary 4.5.3.
(1) P(K[0] ∈G
0
) = 1−(1−p
01
)(1−p
02
).
(2) For 1 ≤y ≤ N −1,
P(K[y] ∈G
y
) = 1−(1−p
y1
)(1−p
y2
)(1 −p
y3
)(1 −p
y4
).
Substituting the values for y yields
P(K[0] ∈G
0
) ≈ 0.37
and for 1 ≤ y ≤ N − 1, P(K[y] ∈G
y
) varies between 0.12 and 0.15. Experi-
mental results also confirm these theoretical estimates.
Based on Theorems 4.5.1 and 4.5.2, we build the framework of retrieving
individual key bytes.
The RC4 key κ of l bytes is repeated in key length boundaries to fill the
N bytes of the key array K. The number of places in K where the same key
byte κ[w] is repeated is given by
⌊
N
l
⌋+ 1
for 0 ≤ w < N mod l;
n
w
=
⌊
N
l
⌋
for N mod l ≤w < l.
Thus, when considering a key byte κ[w], we are interested in the set
T
w
=
G
y
,
y∈Z
N
,y mod l=w
which is a union of n
w
many G
w
n
w
. Denote the corre-
sponding p
yx
's by p
w
1
x
,p
w
2
x
,...,p
w
n
w
x
. Also, for notational convenience in
representing the formula, we denote the size of G
y
's, say, G
w
1
,G
w
2
,...,G
y
by M
y
. We have already
argued that M
0
can be taken to be 2 and for 1 ≤ y ≤ N − 1, M
y
can be
considered to be 4.
Theorem 4.5.4. For 0 ≤ w ≤l−1, let freq
w
be the frequency (i.e., number
of occurrences) of κ[w] in the set T
w
. Then for 0 ≤ w ≤ l− 1, we have the
