Cryptography Reference
In-Depth Information
Z
p
Definition 8.3.1
Discrete Logarithm Problem (DLP) in
Z
p
of order p
Given is the finite cyclic group
−
1
and a primitive el-
α
∈
Z
p
and another element
β
∈
Z
p
. The DLP is the problem
ement
of determining the integer
1
≤
x
≤
p
−
1
such that:
x
≡
β
α
mod
p
Remember from Section 8.2.2 that such an integer
x
must exist since
is a primi-
tive element and each group element can be expressed as a power of any primitive
element. This integer
x
is called the
discrete logarithm of
α
β
to the base
α
, and we
can formally write:
x
= log
α
β
mod
p
.
Computing discrete logarithms modulo a prime is a very hard problem if the param-
eters are sufficiently large. Since exponentiation
x
≡
β
α
mod
p
is computationally
easy, this forms a one-way function.
Z
47
, in which
Example 8.11.
We consider a discrete logarithm in the group
α
= 5is
a primitive element. For
β
= 41 the discrete logarithm problem is: Find the positive
integer
x
such that
5
x
≡
41 mod 47
Even for such small numbers, determining
x
is not entirely straightforward. By using
a brute-force attack, i.e., systematically trying all possible values for
x
, we obtain
the solution
x
= 15.
In practice, it is often desirable to have a DLP in groups with prime cardinality in
order to prevent the Pohlig-Hellman attack (cf. Section 8.3.3). Since groups
Z
p
have
cardinality
p
−
1, which is obviously not prime, one often uses DLPs in subgroups
Z
p
with prime order, rather than using the group
Z
p
itself. We illustrate this with
of
an example.
Z
47
which has order 46. The subgroups in
Z
47
have thus a cardinality of 23, 2 and 1.
Example 8.12.
We consider the group
α
= 2 is an element in the subgroup
with 23 elements, and since 23 is a prime,
is a primitive element in the subgroup.
A possible discrete logarithm problem is given for
α
β
= 36 (which is also in the
subgroup): Find the positive integer
x
,1
≤
x
≤
23, such that
2
x
≡
36 mod 47
By using a brute-force attack, we obtain a solution for
x
= 17.
