Cryptography Reference
In-Depth Information
group elements is the basis for cryptosystems such as the Diffie-Hellman key ex-
change.
Z
11
has the element 2 as a generator. It
is important to stress that the number 2 is not necessarily a generator in other cyclic
groups
From this example we see that the group
Z
n
. For instance, in
Z
7
,ord(2)=3, and the element 2 is thus not a generator
in that group.
Cyclic groups have interesting properties. The most important ones for crypto-
graphic applications are given in the following theorems.
Z
p
,
Theorem 8.2.2
For every prime p,
(
·
)
is an abelian finite cyclic
group.
This theorem states that the multiplicative group of every prime field is cyclic.
This has far reaching consequences in cryptography, where these groups are the
most popular ones for building discrete logarithm cryptosystems. In order to under-
line the practical relevance of these somewhat esoteric looking theorem, consider
that almost every Web browser has a cryptosystem over
Z
p
built in.
Theorem 8.2.3
Let G be a finite group. Then for every a
∈
G it holds that:
1. a
|
G
|
= 1
2. ord
(
a
)
divides
|
G
|
The first property is a generalization of Fermat's Little Theorem for all cyclic
groups. The second property is very useful in practice. It says that in a cyclic group
only element orders which divide the group cardinality exist.
Z
11
which has a cardinality of
|
Z
11
|
Example 8.7.
We consider again the group
= 10.
The only element orders in this group are 1, 2, 5, and 10, since these are the only
integers that divide 10. We verify this property by looking at the order of all elements
in the group:
ord(1)=1
ord(6)=10
ord(2)=10
ord(7)=10
ord(3)=5
ord(8)=10
ord(4)=5
ord(9)=5
ord(5)=5
ord(10)=2
Indeed, only orders that divide 10 occur.
