Cryptography Reference
In-Depth Information
the initial permutation S
0
from the first few runs of keystream output bytes
generation.
Input: The RN many keystream output bytes from the first
R(≥ 2) runs of the PRGA.
Output: The original permutation S
0
before the PRGA begins.
Run PartResolvePerm with the given keystream bytes and generate
1
the arrays Next and Conflict;
Run ResolveConflicts on Next;
2
Run ConstructPerm on updated Next;
3
Algorithm 8.4.5: InvertStuckPRGA
Theorem 8.4.18. The average case time complexity of the InvertStuckPRGA
algorithm is O
R
2
+⌈A⌉!
, where A = N (
N−1
N
)
(R−1)(N−2)
.
N
Proof: The time complexity of Step 1 in InvertStuckPRGA is O(RN),
since there are two nested “for” loops in PartResolvePerm of R−1 and N−2
many iterations respectively and one execution of the steps inside the “for”
loops takes O(1) time.
The time complexity of Step 2 in InvertStuckPRGA is O(R
2
N), since from
Theorem 8.4.16, the average value of NumConflicts is O(R) and resolving
each of them in the two nested “for” loops in ResolveConflicts takes O(RN)
time.
According to Theorem 8.4.14, just before the execution of ConstructPerm
in Step 3 of InvertStuckPRGA, the average value of the number m of unas-
signed entries in the array Next is given by
(R−1)(N−2)
N −1
N
A = N
.
Hence the “for” loop in Step 2 of ConstructPerm is iterated ⌈A⌉! times on
the average. Again, from Lemma 8.4.17, the time complexity of each iteration
of the “for” loop in Step 2 of ConstructPerm is O(N). Hence the overall
complexity of Step 3 in InvertStuckPRGA is O(⌈A⌉!N).
Thus, the time complexity of InvertStuckPRGA is O
R
2
+⌈A⌉!
N
.
Remark 8.4.19. If z
ρN+y
= z
(ρ+1)N+(y+1)
for some ρ ≥ 0 and some
y ∈ {1,...,N − 2}, i.e., if the two values in a candidate pair turn out to
be equal, then we would have S
0
[N −ρ + y] = z
ρN+y
, according to item 1 of
Theorem 8.4.12. Once the position of any one entry of a resolved permutation
is known, the positions of all other entries are immediately known. If one
makes use of this fact in the PartResolvePerm algorithm, then rotating T in
the ConstructPerm algorithm is not required at all. One can run StuckPRGA
for 8 rounds on T itself to check whether T = S
0
or not. In that case, the
