Cryptography Reference
In-Depth Information
Definition 8.2.1
Group
A
group
is a set of elements G together with an operation
◦
which
combines two elements of G. A group has the following properties.
1. The group operation
◦
is
closed
. That is, for all a
,
b
,
∈
G, it holds
G.
2. The group operation is
associative
. That is, a
that a
◦
b
=
c
∈
◦
(
b
◦
c
)=(
a
◦
b
)
◦
c
G.
3. There is an element
1
for all a
,
b
,
c
∈
∈
G, called the
neutral element
(or
identity
element
), such that a
◦
1 = 1
◦
a
=
a for all a
∈
G.
G there exists an element a
−
1
4. For each a
∈
∈
G, called the
in-
a
−
1
=
a
−
1
a
= 1
.
5. A group G is
abelian (or commutative)
if, furthermore, a
verse
of a, such that a
◦
◦
◦
b
=
b
◦
a for all a
,
b
∈
G.
Note that in cryptography we use both multiplicative groups, i.e., the operation
“
◦
” denotes multiplication, and additive groups where “
◦
” denotes addition. The
latter notation is used for elliptic curves as we'll see later.
Example 8.2.
To illustrate the definition of groups we consider the following exam-
ples.
(
together
with the usual addition forms an abelian group, where
e
= 0 is the identity ele-
ment and
Z
,
+) is a group, i.e., the set of integers
Z
=
{
...,
−
2
,
−
1
,
0
,
1
,
2
,...
}
−
a
is the inverse of an element
a
∈
Z
.
(
(without the element
0) and the usual multiplication does not form a group since there exists no inverse
a
−
1
for an element
a
Z
without
0
,
·
) is
not
a group, i.e., the set of integers
Z
∈
Z
with the exception of the elements
−
1 and 1.
and
i
2
=
(
C
,
·
) is a group, i.e., the set of complex numbers
u
+
iv
with
u
,
v
∈
R
−
1
together with the complex multiplication defined by
·
−
(
u
1
+
iv
1
)
(
u
2
+
iv
2
)=(
u
1
u
2
v
1
v
2
)+
i
(
u
1
v
2
+
v
1
u
2
)
forms an abelian group. The identity element of this group is
e
= 1, and the
inverse
a
−
1
of an element
a
=
u
+
iv
is given by
a
−
1
=(
u
i
)
/
(
u
2
+
v
2
).
∈
C
−
However, all of these groups do not play a significant role in cryptography be-
cause we need groups with a finite number of elements. Let us now consider the
group
Z
n
which is very important for many cryptographic schemes such as DHKE,
Elgamal encryption, digital signature algorithm and many others.
