The Discrete Logarithm Problem

The DLP in Fp\mathbb{F}_{p}^{*}

As discussed in the previous sections, the first published public-key system by Diffie and Hellman is based on the discrete logarithm problem in the multiplicative group Fp\mathbb{F}_{p}^{*} of a finite field, with pp prime. According to the primitive root theorem :Primitive_Root_Theorem , there exists a primitive element aFpa \in \mathrm{F}_{p}^{*} that generates the whole group, i.e.,

Fp=a={1,a,a2,,ap2}.F_{p}^{*}=\langle a\rangle=\left\{1, a, a^{2}, \ldots, a^{p-2}\right\}.

Discrete logarithm problem (DLP) in Fp\mathbb{F}_{p}^{*}


Let aa be a primitive element (i.e., a generator) of the cyclic group Fp\mathbb{F}_{p}^{*} and bFpb \in \mathbb{F}_{p}^{*}. The DLP is the problem of finding an exponent xx such that

axbmod pa^{x} \equiv b \quad mod \space p

xx is said to be the discrete logarithm of bb to the base aa. However, if there exists a solution for xx, then there’s an infinite number of solutions to this problem. Due to Fermat’s little theorem :Fermats_Little_Theorem , it holds that

ap11mod p,a^{p-1} \equiv 1 \quad mod \space p,

and hence

ax+k(p1)=ax(ap1)kb1kbmod p.a^{x+k(p-1)}=a^{x} \cdot\left(a^{p-1}\right)^{k} \equiv b \cdot 1^{k} \equiv b \quad mod \space p.

Thus, we conclude that if xx is a solution to the problem axbmod pa^{x} \equiv b \quad mod \space p, then x+k(p1)x+k(p-1) is also a solution for every kZk \in \mathbb{Z}.

Computing the DLP in Fp\mathbb{F}_{p}^{*} is a very hard computational problem if pp is sufficiently large. Since axbmod pa^{x} \equiv b \quad mod \space p can be computed efficiently if xx is known, this serves as a one-way function. However, there are several well-known attacks against the DLP, which we introduce in this section.

The generalized discrete logarithm problem

So far, we just considered the DLP in the multiplicative group Fp\mathrm{F}_{p}^{*}. However, the DLP isn’t restricted to only this group, but rather can generally be defined over any cyclic group.

Generalized DLP


Let GG be a cyclic group with group operation *, a primitive element aGa \in G and any given bGb \in G. Then, the discrete logarithm problem for GG is to find an integer xx that satisfies

ax={aaa}x times =b.a^{x}=\{a * a * \ldots * a\}_{x \text { times }}=b .

Every group GG has its own discrete logarithm problem, whereas the difficulty of the DLP depends on the structure of GG. We consider the DLP for the following three cyclic groups: the additive group (Zn,+)\left(\mathbb{Z}_{n},+\right), the multiplicative group (Fp,)\left(\mathbb{F}_{p}^{*}, \cdot\right), and the elliptic curve (E(Fp),+)\left(E\left(\mathbb{F}_{p}\right),+\right).

  1. For (Zn,+)\left(\mathbb{Z}_{n},+\right), the DLP is to find an integer xx for two given a,bZna, b \in \mathbb{Z}_{n} such that xa=bmod nx \cdot a=b \quad mod \space n. This problem can be solved very easily since it works by using the Euclidean algorithm that takes O(log(n))\mathcal{O}(\log (n)) steps and hence works in polynomial time.

  2. For (Fp,)\left(\mathbb{F}_{p}^{*}, \cdot\right), the DLP is according to this definition. The solution is hard. For example, there exists the index calculus method that works in sub-exponential time. The best-known algorithm is the generalized number field sieve, which also has a sub-exponential running time.

  3. For (E(FP),+)\left(E\left(F_{P}\right),+\right), the DLP (known as ECDLP) is to find an integer xx for two given points P,Q(E(Fp),+)P, Q \in\left(E\left(F_{p}\right),+\right) such that xP=Q.x P=Q . However, the problem is very hard to solve since the fastest known algorithm takes O(p)\mathcal{O}(\sqrt{p}) steps and hence needs fully exponential time.

In conclusion, the ECDLP is harder than the DLP in (FP,)\left(\mathbb{F}_{P}^{*}, \cdot\right), provided that the orders of the groups are about the same.

Get hands-on with 1200+ tech skills courses.