Cryptography Reference
In-Depth Information
Z
11
,
Z
12
,
3.26 for the notion of a prime). For example,
·
is a cyclic group, but
·
Z
12
generates the entire group and
hence that the group has no generator). In either case,
is not (i.e., it can be shown that no element of
Z
p
,
·
is a cyclic group for
every prime number
p
, and this group is isomorphic to
Z
p−
1
,
+
. For example,
the function
f
(
x
)=
g
x
(mod
p
) defines an isomorphism between
Z
p−
1
,
+
and
Z
p
,
. This isomorphism is reflected by the equation
g
x
+
y
=
g
x
g
y
.
·
·
3.1.4
Permutations
Permutations are important mathematical building blocks for symmetric encryption
systems in general, and block ciphers in particular (in Section 10.2 we argue that
a block cipher represents a family of permutations). In short, a permutation is a
bijective map whose domain and range are the same. This is formally expressed in
Definition 3.23.
Definition 3.23 (Permutation)
Let
S
be a set. A map
f
:
S
S
is a
permutation
if
f
is bijective (i.e., injective and surjective). The
set of all permutations
of
S
is
denoted by
Perm
S→S
,or
P
(
S
)
in short.
→
If, for example,
S
=
{
1
,
2
,
3
,
4
,
5
}
, then an exemplary permutation of
S
can
be expressed as follows:
12345
53421
This permutation maps every element in the first row of the matrice to the
corresponding element in the second row (i.e., 1 is mapped to 5, 2 is mapped to 3,
and so on). Using this notation, it is possible to specify any permutation of a finite
set
S
.
In what follows, we use
S
n
to refer to
{
1
,
2
,...,n
}
for any integer
n
,and
we use
P
n
to refer to
Perm
S
n
→S
n
or
P
(
S
n
).If
◦
represents the concatenation
operator,
11
then
P
n
,
◦
is a noncommutative group for
n
≥
3. For example,
P
2
has
the two elements
12
12
and
11
The permutation
A ◦ B
is the permutation that results by applying
B
and
A
(in this order).
