Public-Key Cryptosystems Based on the Discrete Logarithm Problem - Understanding Cryptography - page 215

8.3.2 The Generalized Discrete Logarithm Problem

The feature that makes the DLP particularly useful in cryptography is that it is not
restricted to the multiplicative group Z p , p prime, but can be defined over any cyclic

groups. This is called the generalized discrete logarithm problem (GDLP) and can
be stated as follows.

Definition 8.3.2 Generalized Discrete Logarithm Problem
Given is a finite cyclic group G with the group operation ◦ and

cardinality n. We consider a primitive element α ∈ G and another

element G. The discrete logarithm problem is finding the inte-

ger x, where 1

β ∈

≤ x ≤ n, such that:

x

β = α ◦ α ◦ ... ◦ α = α

xtimes

Z p , such an integer x must exist since

As in the case of the DLP in is a primi-

tive element, and thus each element of the group G can be generated by repeated
application of the group operation on

α

.
It is important to realize that there are cyclic groups in which the DLP is not
difficult. Such groups cannot be used for a public-key cryptosystem since the DLP
is not a one-way function. Consider the following example.

α

Example 8.13. This time we consider the additive group of integers modulo a prime.
For instance, if we choose the prime p = 11, G =( Z 11 , +) is a finite cyclic group

with the primitive element α = 2. Here is how α generates the group:

i 123456789 0 1

i α 2468 013579 0

We try now to solve the DLP for the element β = 3, i.e., we have to compute the

integer 1 ≤ x ≤ 11 such that

x · 2 = 2 + 2 + . .. + 2 ≡ 3 mod 11

x times

Here is how an “attack” against this DLP works. Even though the group operation
is addition, we can express the relationship between α , β and the discrete logarithm

x in terms of multiplication :

x · 2 ≡ 3 mod 11 .

In order to solve for x , we simply have to invert the primitive element α :

2 − 1 3 mod 11 x ≡