Skip to main content

Section 6 General attacks on the discrete logarithm problem

We study algorithms to determine solutions of discrete logarithm problems in multiplicative and additive groups.

Subsection 6.1 Baby-Step Giant-Step algorithm

Let \(G\) be a multiplicative group of order \(p\text{,}\) we try to find \(x\) for which
\begin{equation*} g^x=h,\quad g,h\in G. \end{equation*}
In order to find a solution \(x\) we fix an integer \(N\) for which \(N^2>p.\) We determine the elements of two lists. The list corresponding to the baby-steps contains elements of the form
\begin{equation*} g^i\quad \mbox{ for }i=0,1,\ldots,N-1. \end{equation*}
The second list contains the elements related to the giant-steps
\begin{equation*} hg^{-jN}\quad \mbox{ for }j=0,1,\ldots,N-1. \end{equation*}
We compare the two lists to find an element that is on both lists: \(g^i\equiv hg^{-jN}\pmod{p}.\) We obtain a solution \(x=i+jN.\) The two lists have an element in common since if we write \(x\) in base \(N,\) then \(x\) has at most two digits (we note that \(N^2>p>x\)). Therefore \(x=x_0+x_1N\) for some \(0\leq x_0,x_1\leq N-1.\) Now we provide an example in SageMath.
In a similar way we can apply the method in additive groups. In case of elliptic curves we use the SageMath code below to provide an example.

Subsection 6.2 The Pollard's \(\rho\) algorithm

Pollard’s \(\rho\) algorithm is a Monte Carlo type probabilistic method to solve a discrete logarithm problem \(g^x\equiv h\pmod{p}.\) The basic idea is to determine numbers \(u\) and \(v\) for which

\begin{equation*} g^u\equiv h^v\pmod{p}. \end{equation*}

Let us define a sequence \(x_n\) in the following way, \(x_0=1\) and

\begin{equation*} x_{n+1}= \begin{cases} gx_n & \text{ if }0<x_n\leq p/3,\\ x_n^2 &\text{ if }p/3<x_n\leq 2p/3,\\ hx_n & \text{ if }2p/3<x_n<p. \end{cases} \end{equation*}

It is clear that

\begin{equation*} x_n\equiv g^{u_n}h^{v_n}\pmod{p}. \end{equation*}

We can also provide formulas for the sequences appearing in the exponents, we have \(u_0=v_0=0\) and

\begin{equation*} u_{n+1}= \begin{cases} u_n+1 & \text{ if }0<x_n\leq p/3,\\ 2u_n &\text{ if }p/3<x_n\leq 2p/3,\\ u_n & \text{ if }2p/3<x_n<p, \end{cases} \end{equation*}

while in case of \(v_n\) we obtain

\begin{equation*} v_{n+1}= \begin{cases} v_n & \text{ if }0<x_n\leq p/3,\\ 2v_n &\text{ if }p/3<x_n\leq 2p/3,\\ v_n+1 & \text{ if }2p/3<x_n<p. \end{cases} \end{equation*}

In the algorithm we store elements of vectors of the form

\begin{equation*} (x_i,u_i,v_i,x_{2i},u_{2i},v_{2i}). \end{equation*}

We compute such vectors until we get one with \(x_i=x_{2i}\) for so me \(i.\) In this case we have

\begin{equation*} g^{u_i}h^{v_i}\equiv g^{u_{2i}}h^{v_{2i}}\pmod{p}, \end{equation*}

therefore it follows that

\begin{equation*} g^{u_i-u_{2i}}\equiv h^{v_{2i}-v_i}\pmod{p}. \end{equation*}

So we may take \(u\equiv u_i-u_{2i}\pmod{p-1}\) and \(v\equiv v_{2i}-v_{i}\pmod{p-1}.\) If \(v\equiv 0\pmod{p-1},\) then the algorithm fails. Assume that it is not the case. Compute \(d=\gcd(v,p-1)\) and also \(s\) and \(t\) for which

\begin{equation*} d=sv+t(p-1). \end{equation*}

We get that

\begin{equation*} g^{su}\equiv h^{sv}\equiv h^{d-t(p-1)}\equiv h^d\equiv (g^x)^d\pmod{p}. \end{equation*}

It implies that \(su\equiv dx\pmod{p-1},\) hence

\begin{equation*} dx=su+w(p-1). \end{equation*}

Since \(d\) is a divisor of \(p-1,\) we have that \(d\) also divides \(su.\) Thus

\begin{equation*} x=\frac{su+w(p-1)}{d}\mbox{ for some }w\in\{0,1,\ldots,d\}. \end{equation*}

Consider the elliptic curve discrete logarithm problem, that is we have \(Q\in\langle P \rangle\) for some \(P\in E(\mathbb{F}_q).\) Our goal is to determine \(n\) such that \(nP=Q.\) Denote by \(N\) the order of the subgroup generated by the point \(P.\) We define a sequence of points of the form \(R_n=a_nP+b_nQ.\) Let \(R_0=P\) (we may also use some random integers \(a_0,b_0\in\{0,\ldots,N-1\}\)). We need to partition the subgroup generated by \(P\) into three parts, here we apply the rule

\begin{equation*} \begin{aligned} S_1&=&\{R : R\in E(\mathbb{F}_q), y(R)\pmod{3}=0\},\\ S_2&=&\{R : R\in E(\mathbb{F}_q), y(R)\pmod{3}=1\},\\ S_3&=&\{R : R\in E(\mathbb{F}_q), y(R)\pmod{3}=2\},\end{aligned} \end{equation*}

where \(R=(x(R),y(R)),\) that is \(y(R)\) is the \(y\)-coordinate of the point \(R.\) The sequence \(R_n\) is defined as

\begin{equation*} R_{n+1}= \begin{cases} P+R_n & \mbox{ if } R_n\in S_1,\\ 2R_n &\mbox{ if }R_n\in S_2,\\ Q+R_n & \mbox{ if }R_n\in S_3. \end{cases} \end{equation*}

The two sequences \(a_n\) and \(b_n\) can be describes as follows. We have that \(a_0=1\) (since \(R_0=P\)) and \(b_0=0.\) The recurrence definitions are given by

\begin{equation*} a_{n+1}= \begin{cases} a_n+1 & \mbox{ if }R_n\in S_1,\\ 2a_n &\mbox{ if }R_n\in S_2,\\ a_n & \mbox{ if }R_n\in S_3, \end{cases} \end{equation*}

while in case of \(b_n\) we have

\begin{equation*} b_{n+1}= \begin{cases} b_n & \mbox{ if }R_n\in S_1,\\ 2b_n &\mbox{ if }R_n\in S_2,\\ b_n+1 & \mbox{ if }R_n\in S_3. \end{cases} \end{equation*}

We keep computing the vectors

\begin{equation*} (R_n,a_n,b_n,R_{2n},a_{2n},b_{2n}) \end{equation*}

until \(R_n=R_{2n}.\) In that case the definition of the sequence \(R_n\) yields that

\begin{equation*} a_nP+b_nQ=a_{2n}P+b_{2n}Q, \end{equation*}

that is

\begin{equation*} (a_n-a_{2n})P=(b_{2n}-b_n)Q. \end{equation*}

Therefore we obtain that

\begin{equation*} n=\log_P(Q)\equiv \frac{a_n-a_{2n}}{b_{2n}-b_n}\pmod{N}. \end{equation*}

If \(\gcd(N,b_{2n}-b_n)\neq 1,\) then we follow the steps provided in case of the Pollard’s \(\rho\) method in \(\mathbb{F}_p\) to obtain a short list of possible solutions.

Subsection 6.3 Index calculus

We introduce the index calculus algorithm to solve the discrete logarithm problem \(a^x\equiv b\pmod{p}.\) We consider a sequence \(x_1,x_2,\ldots\) of distinct random integers from the set \(\{0,1,\ldots,p-2\}\) and we fix a factor base containing small primes \(B=\{p_1,p_2,\ldots,p_k\}.\) We compute \(a^{x_i}\pmod{p}\) and check if the resulting value is only divisible by primes from the set \(B.\) That is we try to find \(x_i\) such that

\begin{equation*} a^{x_i}\equiv p_1^{u_{i1}}p_2^{u_{i2}}\cdots p_k^{u_{ik}}\pmod{p}. \end{equation*}

If we find such a congruence, then we have

\begin{equation*} x_i\equiv u_{i1}\log_a(p_1)+u_{i2}\log_a(p_2)+\ldots+u_{ik}\log_a(p_k)\pmod{p-1}. \end{equation*}

That is we obtain a linear equation in the unknowns \(\log_a(p_1),\ldots,\log_a(p_k).\) We have \(k\) unknowns so we only need to determine appropriately many linear relations to be able to compute the discrete logarithms of the primes contained in \(B.\) Let us suppose that we solved this linear algebra exercise. Now we take random integers \(m\) from the set \(\{0,1,\ldots,p-2\}\) and we compute \(a^mb\pmod{p}.\) If this latter number is only divisible by primes from \(B,\) then we get

\begin{equation*} \log_a(b)+m\equiv m_{i1}\log_a(p_1)+m_{i2}\log_a(p_2)+\ldots+m_{ik}\log_a(p_k)\pmod{p-1}. \end{equation*}

Thus

\begin{equation*} \log_a(b)\equiv m_{i1}\log_a(p_1)+m_{i2}\log_a(p_2)+\ldots+m_{ik}\log_a(p_k) - m\pmod{p-1}. \end{equation*}

Let us provide an implementation in SageMath.

Subsection 6.4 Pohlig-Hellman algorithm

The Pohlig-Hellman algorithm is very useful in practice if the order of the group in which we would like to solve a given discrete logarithm problem is smooth, that is it has only "small" prime divisors. Hence the discrete logarithm problem in a group \(G\) is as hard as the discrete logarithm problem in the largest subgroup of prime order in \(G.\) Suppose we have a group \(G=\langle g \rangle\) such that

\begin{equation*} \mbox{ord}(g)=\prod_{k=1}^n p_k^{e_k} \end{equation*}

for some primes \(p_1,p_2,\ldots,p_n\) and positive integers \(e_1,e_2,\ldots,e_n.\) Our goal is to determine an \(x\) for which \(g^x=h.\) Instead of solving the general discrete logarithm problem we try to compute \(x\pmod{p_i^{e_i}}\) and than we apply the Chinese Reminder Theorem to obtain \(x\pmod{N}.\) The group \(G\) is a cyclic group so we know from group theory that there is a group isomorphism given by

\begin{equation*} \Phi: G\rightarrow C_{p_1^{e_1}}\times C_{p_2^{e_2}}\times\cdots\times C_{p_n^{e_n}}, \end{equation*}

where the groups \(C_{p_i^{e_i}}\) are cyclic of order \(p_i^{e_i}.\) Let us also consider the projection of \(\Phi\) to the component \(C_{p_i^{e_i}}\) denoted by \(\Phi_i: G\rightarrow C_{p_i^{e_i}}\) and defined by

\begin{equation*} a\longmapsto a^{N/p_i^{e_i}}. \end{equation*}

This is a group homomorphism so from the equality \(h=g^x\) it follows that \(\Phi_i(h)=\Phi_i(g)^x,\) this latter relation provides a discrete logarithm problem but not in \(G,\) but \(C_{p_i^{e_i}}.\) Thus we get \(x\pmod{p_i^{e_i}}.\) We do it for all the prime divisors of \(N\) to get a system of congruences

\begin{equation*} \begin{aligned} x &\equiv & x_1 \pmod{p_1^{e_1}}\\ x &\equiv & x_2 \pmod{p_2^{e_2}}\\ &\vdots &\\ x &\equiv & x_n \pmod{p_n^{e_n}}.\end{aligned} \end{equation*}

A standard application of the Chinese Reminder Theorem yields

\begin{equation*} x\pmod{p_1^{e_1}p_2^{e_2}\cdots p_n^{e_n}} \rightarrow x\pmod{N}. \end{equation*}

It remains to describe how to solve the discrete logarithm problem in \(C_{p^{e}}.\) Let say we would like to determine \(x\) for which \(g^x=h\) in \(C_{p^{e}}.\) The unknown exponent has a base \(p\) representation as follows

\begin{equation*} x=b_0+b_1p+b_2p^2+\ldots+b_{e-1}p^{e-1}. \end{equation*}

We proceed in a recurrent way, suppose we know \(x\) modulo \(p^k\) for some \(0\leq k\leq e-1,\) say

\begin{equation*} x_k\equiv b_0+b_1p+b_2p^2+\ldots+b_{k-1}p^{k-1}\pmod{p^k}. \end{equation*}

We have that \(x\equiv x_k+b_kp^k\pmod{p^{k+1}},\) that is

\begin{equation*} h=g^{x_k}(g^{p^k})^{b_k}. \end{equation*}

Let \(h_{k}=hg^{-x_k}\) and \(g_k=g^{p^k}.\) The reduced discrete logarithm problem is \(h_k=g_k^{b_k}.\)

Basicly the same idea can be used in case of additive groups. For example if we have an elliptic curve \(E\) over a finite field, then the discrete logarithm problem is given by \(nP=Q,\) where \(P\) and \(Q\) are points on the curve. We compute

\begin{equation*} \begin{aligned} n &\equiv & n_1 \pmod{p_1^{e_1}}\\ n &\equiv & n_2 \pmod{p_2^{e_2}}\\ &\vdots &\\ n &\equiv & n_m \pmod{p_m^{e_m}},\end{aligned} \end{equation*}

where the primes \(p_1,\ldots,p_m\) are the divisors of the order of the group generated by \(P.\) For a given prime \(p\) we write

\begin{equation*} n=b_0+b_1p+b_2p^2+\ldots+b_{e-1}p^{e-1}. \end{equation*}

First we set \(P_0=(N/p)P\) and \(Q_0=(N/p)Q.\) The order of \(P_0\) is \(p.\) Here we have

\begin{equation*} Q_0=\frac{N}{p}Q=\frac{N}{p}nP=n(\frac{N}{p}P)=nP_0. \end{equation*}

Since the order of \(P_0\) is \(p\) it follows that \(n\equiv b_0\pmod{p}\) for some \(b_0\in\{0,1,\ldots,p-1\}.\) The next step is to determine \(Q_1=(N/p^2)(Q-b_0P).\) We get that

\begin{equation*} Q_1=\frac{N}{p^2}(Q-b_0P)=\frac{N}{p^2}(n-b_0)P=(b_0+b_1p-b_0)\frac{N}{p^2}P=b_1P_0, \end{equation*}

for some \(b_1\in\{0,1,\ldots,p-1\}.\) In general we determine \(b_i\) from

\begin{equation*} Q_i=\frac{N}{p^{i+1}}(Q-b_0P-b_1pP-\ldots-b_{i-1}p^{i-1}P). \end{equation*}
SageMath summary.
difference()

Returns the difference of two sets.

index()

Returns the position of an element in a list.

intersection()

Returns the intersection of two sets.

rank()

Returns the rank of a matrix.

xgcd()

Applies the extended Euclidean algorithm.

Exercises 6.5 Exercises

1.
Solve the discrete logarithm problem \(3^x\equiv 224\pmod{1013}\) using the Baby-Step Giant-Step algorithm.
2.
Solve the discrete logarithm problem \(n\cdot (51:2)=(62:28)\) in case of the elliptic curve \(E: y^2=x^3+13x+10\) over \(\mathbb{F}_{101}\) using the Baby-Step Giant-Step algorithm.
3.
Use the Pollard’s \(\rho\) method to attack the discrete logarithm problem given by \(g= 3, h= 245\) in \(\mathbb{F}_{1013}^*.\) That is find an integer \(x\) such that \(g^x\equiv h\pmod{1013}.\)
4.
Given the elliptic curve \(E: y^2=x^3+13x+32\) over the finite field \(\mathbb{F}_{2027}\) and two points \(P=(1381 : 839), Q=(6:1229).\) Determine a solution of the elliptic curve discrete logarithm problem \(nP=Q\) by applying the Pollard’s \(\rho\) method.
5.
Apply the index calculus algorithm to solve the discrete logarithm problem \(5^x\equiv 20\pmod{503}.\)
6.
Let
\begin{equation*} p=1747808567274271495694237474897031552001 \end{equation*}
and \((g,h)=(13,2020).\) Apply the Pohlig-Hellman algorithm to compute \(\log_g(h)\pmod{p}.\)