Cryptography Reference
In-Depth Information
r−1
r−1−x
N −1
N
P(S
τ
[u] = v)
P(S
x
[x] = v)P(j
x+1
= u)
x=τ
r−1
v
1
N
r−1−x
1
N
N −1
N
N −1
N
(1−p
u,v
τ
=
)
x=τ
v
r−1
r−1−x
)
1
N
2
N −1
N
N −1
N
(1−p
u,v
τ
=
x=τ
v
1−a
r−τ
1−a
)
1
N
2
N −1
N
(1−p
u,v
τ
=
,
where a =
N−
N
. Substituting the value of a and simplifying, we get the above
probability as (1 −p
u,v
τ
)
N
(
N−1
)
v
1−(
N−1
N
)
r−τ
.
Combining the contributions of Cases I and II, we get
N
r−τ
v
r−τ
N −1
N
)
1
N
N −1
N
N −1
N
p
u,v
r
= p
u,v
τ
+ (1−p
u,v
τ
1−
.
Corollary 3.2.10. Suppose, p
u,v
τ
is given for any intermediate round τ,
max{u,v} < τ ≤ N. Then, P(S
N
[u] = v), i.e., the probability after the
complete KSA is given by
N−τ
v
N−τ
N −1
N
)
1
N
N −1
N
N −1
N
p
u,v
τ
+ (1−p
u,v
τ
1−
.
Proof: Substitute r = N in Lemma 3.2.9.
Theorem 3.2.11.
(1) For 0 ≤ u ≤N −2, u + 1 ≤v ≤N −1,
N−1−v
N −1
N
= p
u,v
v+1
P(S
N
[u] = v)
v
−
N−1
v+1
)
1
N −1
N
N −1
N
+(1−p
u,v
,
N
where
2(N−1)
N
2
if u = 0 & v = 1;
p
u,v
v+1
=
1
N
(
N−1
N
)
v−u
+
1
N
(
N−1
N
)
v
−
N
2
(
N−1
N
)
2v−u−1
otherwise.
(2) For 0 ≤ v ≤ N −1, v ≤ u≤ N −1,
N−1−u
v+1
1
N
N −1
N
1
N
N −1
N
P(S
N
[u] = v)
=
+
N+v−u
−
1
N
N −1
N
.
