Cryptography Reference
In-Depth Information
Theorem 8.4.16. The expected number of conflict sets after the execution of
the PartResolvePerm algorithm is bounded by (R−1)(
N−2
N
).
Proof: The candidate pairs are of the form (z
(ρ+1)N+(y+1)
,z
ρN+y
) and
the corresponding output indices are
t
ρ,y
= a
N−ρ+y−1
+ a
N−ρ+y
,
0 ≤ρ ≤ R−2,1 ≤ y ≤ N −2.
According as item 2 of Theorem 8.4.12, if t
ρ,y
= y + 1, then
z
ρN+y
= suc
2
(z
(ρ+1)N+(y+1)
),
but due to Step 10 of the PartResolvePerm algorithm, z
ρN+y
is wrongly
recorded as suc
1
(z
(ρ+1)N+(y+1)
). For 0 ≤ ρ ≤ R − 2, 1 ≤ y ≤ N − 2, let
x
ρ,y
= 1 if t
ρ,y
= y + 1; otherwise, let x
ρ,y
= 0. Hence, the total number of
wrong entries in the array Next after the execution of the PartResolvePerm
algorithm is given by
R−2
N−2
X =
x
ρ,y
.
ρ=0
y=1
Each wrong entry in Next is a potential contributor to one conflict set, i.e.,
NumConflicts≤ X. Assuming that each output index is uniformly randomly
distributed, we have P(x
ρ,y
= 1) =
1
1
N
N
. Thus, E(x
y
) =
and
R−2
N−2
E(X)
=
E(x
ρ,y
)
ρ=0
y=1
N −2
N
=
(R−1)
.
Given a conflict set {(u,v
1
),(u,v
2
)}, if we are able to locate v
1
,v
2
in a
candidate pair, the conflict is resolved and the exact order of u,v
1
,v
2
is known.
Using this observation, we can devise an algorithm ResolveConflicts which
takes as input a partially resolved permutation P
1
over Z
N
and a collection
of conflict sets and produces as output another partially resolved permutation
P
1
.
Even after R many runs of the PRGA, the permutation may still remain
partially resolved. Then we may exhaustively fill in the remaining unassigned
entries in the array Next to form all possible resolved permutations. By run-
ning StuckPRGA on each resolved permutation in turn, we can determine its
first element and thereby recover the entire permutation.
2
such that P
≥P
2
Lemma 8.4.17. If the initial permutation S
0
becomes resolved at any stage
of the RC4 PRGA, then S
0
can be retrieved completely in O(N) average time.
Proof: Suppose one runs PRGA for M rounds starting with an arbi-
trary permutation P over Z
N
. Assuming that the keystream output bytes are
