Cryptography Reference
In-Depth Information
Input: Any permutation Π = (π
0
,π
1
,...,π
n−1
).
Output: Random permutation Π = (π
0
,π
1
,...,π
n−1
).
for i = n−1 down to 1 do
π
i
↔ π
rand(0,i)
;
end
Algorithm 3.2.1: RandPerm
Theorem 3.2.1. Algorithm 3.2.1 produces a random permutation.
Proof: Use induction on n. For n = 1, the result is obvious. Suppose that
the result holds for n = k−1, i.e., each of the (k−1)! factorial permutations
are equally likely. Let
Σ = (σ
0
,σ
1
,...,σ
k−1
)
be any permutation of {0,1,...,k−1}. We have
P(Π = Σ)
= P(π
k−1
= σ
k−1
)
P
(π
0
,...,π
k−2
) = (σ
0
,...,σ
k−2
)
| (π
k−1
= σ
k−1
)
.
1
k
By construction, the first probability is
and by inductive hypothesis, the
1
(k−1)!
, giving
second probability is
1
k!
.
P(Π = Σ) =
The RC4 KSA and the RandPerm algorithm are not similar, on account
of the following issues [110, Chapter 6].
1. The index i increases from 0 to N−1 in the RC4 KSA (number of trans-
positions is N), but the index i decreases from N −1 to 1 in RandPerm
(number of transpositions is N −1).
2. The index j can take any value between 0 to N −1 at any step and the
pseudo-random value of j is based on the secret key bytes in the KSA.
On the other hand, in RandPerm, j = rand(0,i), that implies that it
can take values only in the range 0 to i at the i-th step.
In [110, Chapter 6], it has also been pointed out that the RC4 KSA does not
produce permutations uniformly at random. On the other hand, the Rand-
Perm algorithm cannot be used for key scheduling using the secret key bytes
instead of rand(0,i). In that case, the permutation after the key scheduling
algorithm would have revealed the secret key completely (e.g., π
N−1
will con-
tain the first accessed secret key byte, π
N−2
will contain the second accessed
secret key byte, and so on). Thus, it is necessary to design a key schedul-
ing algorithm that will produce a random looking permutation with certain
cryptographic properties.
