Cryptography Reference
In-Depth Information
Problems
8.1.
Understanding the functionality of groups, cyclic groups and subgroups is im-
portant for the use of public-key cryptosystems based on the discrete logarithm
problem. That's why we are going to practice some arithmetic in such structures
in this set of problems.
Let's start with an easy one. Determine the order of all elements of the multi-
plicative groups of:
Z
5
1.
Z
7
2.
Z
13
Create a list with two columns for every group, where each row contains an element
a
and the order ord(
a
).
(Hint: In order to get familiar with cyclic groups and their properties, it is a good
idea to compute all orders “by hand”, i.e., use only a pocket calculator. If you want to
refresh your mental arithmetic skills, try not to use a calculator whenever possible,
in particular for the first two groups.)
3.
Z
53
. What are the possible element orders? How many
elements exist for each order?
8.2.
We consider the group
8.3.
We now study the groups from Problem 8.2.
1. How many elements does each of the multiplicative groups have?
2. Do all orders from above divide the number of elements in the corresponding
multiplicative group?
3. Which of the elements from Problem 8.1 are primitive elements?
4. Verify for the groups that the number of primitive elements is given by
|
Z
p
|
φ
(
).
8.4.
In this exercise we want to identify primitive elements (generators) of a multi-
plicative group since they play a big role in the DHKE and and many other public-
key schemes based on the DL problem. You are given a prime
p
= 4969 and the
corresponding multiplicative group
Z
4969
.
1. Determine how many generators exist in
Z
4969
.
2. What is the probability of a randomly chosen element
a
∈
Z
4969
being a genera-
tor?
3. Determine the smallest generator
a
∈
Z
4969
with
a
>
1000.
Hint: The identification can be done naıvely through testing
all
possible factors
of the group cardinality
p
−
1, or more efficiently by checking the premise that
q
e
i
. You can simply
start with
a
= 1001 and repeat these steps until you find a respective generator of
Z
4969
.
4. What measures can be taken in order to simplify the search for generators for
arbitrary groups
a
(
p
−
1)
/
q
i
−
= 1mod
p
for all prime factors
q
i
with
p
1 =
∏
Z
p
?
