Cryptography Reference
In-Depth Information
The probability distribution of t
1
= S
1
[i
1
] + S
1
[j
1
] can be computed as
follows.
• For odd x,
N−1
P(S
1
[j
1
] = v,S
1
[i
1
] = N −v + x)
P(t
1
= x) =
v=0
v=1
= (N −1)
1
1
N
.
N(N −1)
=
• For even x= 2,
N−1
P(S
1
[j
1
] = v,S
1
[i
1
] = N −v + x)
P(t
1
= x) =
v=0
x
2
,
N+x
2
v=1,
= (N −3)
1
1
N
−
2
N(N −1)
=
N(N − 1)
.
• For x = 2,
P(t
1
= 2) = P(S
1
[j
1
] = 1,S
1
[i
1
] = 1) +
N−1
P(S
1
[j
1
] = v,S
1
[i
1
] = N −v + 2)
v=0
v=1,
N+2
2
N
+ (N −2)
1
1
2N −3
N(N − 1)
=
2
N
−
1
=
N(N −1)
=
N(N −1)
.
5.4 Characterization of PRGA Evolution
The work [9], for the first time, performed a complete characterization of
the RC4 PRGA for one step:
i
r
= i
r−1
+ 1;j
r
= j
r−1
+ S
r
[i
r
];
swap S
r−1
[i
r
],S
r−1
[j
r
] to get S
r
;
z
r
= S
r
[S
r
[i
r
] + S
r
[j
r
]].
Considering all the permutations (keeping in mind the Finney states also), the
distribution of z is shown to be non-uniform given i
G
,j
G
. Further, analysis of
two consecutive steps of RC4 PRGA reveals that the index j
G
is not produced
uniformly at random given the value of j
G
two steps ago. The immediate
implication of the above results is that information about j
G
is leaked in the
keystream.
