Cryptography Reference
In-Depth Information
Inductive Case: Suppose for some y, 1 ≤y ≤ N −2, the result holds, i.e.,
S
ρN+y
= < b
y
,b
0
,...,b
y−1
,b
y+1
,...,b
N−1
>
(inductive hypothesis).
Now, in round ρN +y+ 1, the index i
G
becomes y + 1 and the other index
j
G
remains fixed at 0. Thus, the values b
y
and b
y+1
are swapped. Hence,
S
ρN+y+1
= < b
y+1
,b
0
,...,b
y
,b
y+2
,...,b
N−1
>,
i.e., the result also holds for y + 1.
Lemma 8.4.11.
(1) After round ρN + y of the PRGA, ρ ≥ 0, 1 ≤y ≤ N −1, the permutation
S
ρN+y
is given by
< a
N−ρ+y
,a
N−ρ
,a
N−ρ+1
,...,a
N−ρ+y−1
,a
N−ρ+y+1
,...,a
N−ρ−2
,a
N−ρ−1
>
and the permutation S
(ρ+1)N
after round ρN + N is the same as the permu-
tation S
ρN+N−1
after round ρN + N −1.
(2) The index where the keystream output byte is chosen from is given by
a
N−ρ+y−1
+ a
N−ρ+y
if ρ ≥ 0, 1 ≤y ≤ N −1;
t
ρN+y
=
2a
N−ρ
if ρ ≥ 1, y = 0.
Proof: The proof of item (1) will be based on induction on ρ.
Base Case: Take ρ = 0. We need to prove that
S
y
= < a
y
,a
0
,a
1
,...,a
y−1
,a
y+1
,...,a
N−2
,a
N−1
>,
1 ≤ y ≤N −1.
This immediately follows from Proposition 8.4.10 above, taking ρ = 0.
Inductive Case: Suppose the result holds for some ρ ≥ 0, i.e., for 1 ≤ y ≤
N −1, the permutation S
ρN+y
is given by
< a
N−ρ+y
,a
N−ρ
,a
N−ρ+1
,...,a
N−ρ+y−1
,a
N−ρ+y+1
,...,a
N−ρ−2
,a
N−ρ−1
>
(inductive hypothesis).
Thus, in round ρN + N −1, we have
S
ρN+N−1
= < a
N−ρ−1
,a
N−ρ
,a
N−ρ+1
,...,a
N−ρ−2
> .
In the next round, i.e. in round ρN + N, the deterministic index i
G
becomes
0 which is equal to the value of j
G
and hence no swap is involved. Thus,
S
(ρ+1)N
= S
ρN+N−1
= < a
N−ρ−1
,a
N−ρ
,a
N−ρ+1
,...,a
N−ρ−2
>,
which can be rewritten as
< b
0
,b
1
,...,b
N−1
>, where b
y
= a
N−ρ−1+y
,0 ≤y ≤ N −1.
