Discrete Logarithm Problem

This lesson contains quite a few definitions written conceptually so as to resonate with the terminology which is applied to ECDSA.

Cyclic groups form the basis of discrete logarithm cryptosystems.

In very non-mathematical terms, a group is considered as a cyclic group when elements start repeating themselves after a certain known number. They have an essential property which is the "Generator" of the group, explained below -

Generator of the group - Consider a group GG. An element gg of the group is called the generator if gg can generate the entire group, i.e., every element aa of GG can be written as gig^i, i.e., gi=ag^i=a

The generator has practical implications and is used extensively for cryptosystems. Let us attempt to understand this using an example.

z11z_{11} is a cyclic group and where gg denotes the generator.

Let ββ be an element of z11z_{11}, then gxβ mod 11g^x ≡ β \ mod \ 11. Finding the xx involves the same process as solving the Discrete Logarithm Problem. Under certain conditions, it is computationally hard to solve the equation for xx and hence this property can be leveraged and considered a security measure.

Discrete Logarithm Problem - Recall from elementary mathematics where in order to compute the exponent, we need to perform the logarithm. Hence, the name of the Discrete Logarithm Problem (DLP).

Let pp and ββ be elements of ZpZ_p*, with generator gg.

We define the DLP in this instance as - find xx such that gxβ mod pg^x ≡ β \ mod \ p

When pp is large enough, finding xx in the above equation is computationally hard to solve.

Generalised Discrete Logarithm Problem - One of the features of the DLP is that it is not restricted to ZpZ_p* but can be defined over any cyclic group. This makes it extremely useful in building crypto systems and why it is therefore used in ECDSA as well.

Last updated

Was this helpful?