Cryptography Reference
In-Depth Information
Notations Related to RC4 used in this Topic
We denote the permutation, the deterministic index and the pseudo-
random index be denoted by S,i,j for the KSA and by S
G
,i
G
,j
G
for the
PRGA respectively. t is used to denote the index in S
G
from where the
keystream byte z is chosen.
We use subscript r to these variables to denote their updated values in
round r, where 1 ≤ r ≤ N for the KSA and r ≥ 1 for the PRGA. Thus, for
the KSA,
i
r
= r−1.
For the PRGA,
i
r
= r mod N
and
z
r
= S
r
[t
r
].
According to this notation, S
N
is the permutation after the completion of the
KSA.
By S
0
and j
0
, we mean the initial permutation and the initial value of
the index j respectively before the KSA begins and by S
0
and j
0
, we mean
the same before the PRGA begins. Note that S
0
and S
N
represent the same
permutation.
Sometimes, for clarity of exposition, we omit the subscripts and/or the
superscripts in S,i,j,t,z. This will be clear from the context.
We use the notation S
−1
for the inverse of the permutation S, i.e., if
S[y] = v, then S
−1
[v] = y.
The identity
y
f
y
=
y(y + 1)
2
+
K[x]
x=0
will be used frequently in this topic.
Other notations will be introduced as and when necessary.
2.5 On Randomness and Pseudo-Randomness
When should something be called random has been a long-standing philo-
sophical debate. Without going into historical anecdotes, we briefly discuss the
three primary approaches to randomness prevalent in the scientific paradigm.
The first approach is rooted in Shannon's information theory [163], that
equates randomness with lack of information. In this model, perfect random-
ness is associated with uniform distribution, i.e., a quantity is called random
if all of its values are equally likely. The more non-uniform a distribution is,
the more it is deviated from randomness.
