Cryptography Reference
In-Depth Information
12
21
As can be shown,
|
P
n
|
=
n
!=1
·
2
·
...
·
n
. For the first position, we have
n
possibilities. For the second position, we have
n
1 possibilities. This continues until
the last position, where we have only one possibility left. Consequently, there are
n
−
=
n
!. More specifically,
the formula is proven by induction over
n
. Because
P
1
has 1! = 1 element, the
formula is correct for
n
=1. We assume that the formula is correct for
n
·
n
−
1
·
...
·
1 possibilities, and this value is equal to
|
P
n
|
−
1 (i.e.,
|
1)!) and show that the formula is then also correct for
n
. Therefore,
we look at the permutations of
P
n
thatmap1toanarbitrary
x
P
n−
1
|
=(
n
−
∈
S
n
. By using such
a permutation, the numbers 2
,
3
,...,n
are mapped to 1
,
2
,...,x
−
1
,x
+1
,...,n
,
and this function is bijective. There are (
n
1)! such functions. Furthermore, there
are
n
possibilities to map 1 to an
x
(i.e.,
x
=1
,...,n
). Consequently, there is a total
of
−
|
P
n
|
=
n
(
n
−
1)! =
n
! permutations of
S
n
.
n
be the set of all binary strings of length
n
. A permutation of
S
in which the bit positions are permuted is said to be a
bit permutation
. To specify
a bit permutation
f
, we must select a
π
Let
S
=
{
0
,
1
}
∈
P
n
and set
n
n
f
:
{
0
,
1
}
−→ {
0
,
1
}
b
0
...b
n−
1
−→
b
π
(0)
...b
π
(
n−
1)
.
Every bit permutation can be described in this way, and hence there are
n
!
possible bit permutations for binary strings of length
n
.
There are bit permutations that are frequently used in cryptography, such as
cyclic shift left
and
cyclic shift right
. A cyclic shift left for
i
positions maps the bit
string (
b
0
,b
1
,...,b
n−
1
) into
(
b
i
mod
n
,b
(
i
+1) mod
n
,...,b
(
i
+
n−
1) mod
n
)
.
A cyclic shift right is defined similarly.
Last but not least, we sometimes use the notion of a family of permutations.
Roughly speaking,
F
is a
family of permutations
if the domain and range are the
same and each
f
k
is a permutation (according to Definition 3.23).
