Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
My understanding is that $a=g^x\bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $x=\log_g a\bmod p$ ?
For instance, if we are trying to compute the discrete logarithm of $3$ to base $2$ - given that $p=11$, what would be the output (or the equation)
How would we attempt to solve that problem in Diffie-Hellman ?
moderator note: that apocryphal extension of the original question came by way of merging with another question.
Discrete Log for arbitrary Groups: Discrete Log can be defined in arbitrary groups and some groups can have an easy solution (powers of 10) and some can have a hard solution.
Let $G$ be any group and $\odot$ be the group operation. For any $k \in \mathbb{Z}_{>0}$, let $g \in G$ then we define $[k]g = \overbrace{g\odot\cdots\odot g}^{{k\hbox{ - }times}} $. Then for a given $a \in G$ the $k$ that satisfies $[k]b = a$ is called discrete log of $a$ to base $g$. It can also be written as $k = \log_g a$
Additive DLog : The analogous definition for $(\mathbb{Z}_p,+)$ is well-defined with given $a,g,n$ find $x>0$ such that $x g \equiv a \bmod n$. It can be solved easily if you find the inverse of $a$ by using the Ext-GCD algorithm.
Multiplicative DLog :, the discrete Logarithm Problem (DLP) is given $a,g,n \in \mathbb{Z}^+$ find $x \in \mathbb{Z}_{>1}$ such that $a^x \equiv g \bmod n$, if such $x$ exists.
For the small modulus we can build a table for the DLP problem, or you can stop building the table whenever you find your case.
The below is a DLog (Discrete Log) table for modulus 19 with base 2.
\begin{array}{c|rrrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& \color{red}{13}& 14& 15& 16& 17& 18\\ \hline 2 ^x \bmod 19& 2& 4& 8& 16& 13& 7& 14& 9& 18& 17& 15& 11& \color{red}{3}& 6& 12& 5& 10& 1 \end{array}
For example, given 3 as the DLog base 2 modulo 19, we will look for 3 in the second row and corresponding $x$ in the first row that is 13. I.e. $2^{13} \equiv 3 \bmod 19$
Different bases will produce different tables; for base 5:
\begin{array}{c|rrrrrrrrrrrrrrrrr} x& 1& 2& 3& 4& 5& 6& 7& 8& 9& 10& 11& 12& 13& 14& 15& 16& 17& 18\\ \hline 5 ^x \bmod 19& 5& 6& 11& 17& 9& 7& 16& 4& 1& 5& 6& 11& 17& 9& 7& 16& 4& 1 \end{array} If you know the relation with the two bases then you don't need to calculate another base.
This approach is actually brute-forcing and has $\mathcal{O}(n)$- time complexity.
The brute-forcing approach will fail around when $n \approx 2^{80}$. There are better search algorithms for DLOG, the generic algorithms that work for any group;
and
Dlog is not hard for every EC like curves with $|E(\mathbb{F}_q)|=q$. In Elliptic Curve Cryptography, we use curves where the Dlog is hard.
Some of the above generic algorithms, Pollard's $\rho$, Pollard's $\lambda$ also apply for DLog for Elliptic Curves, except index calculus-based algorithms and NFS. The records on finding DLog on EC mostly based on parallel Pollard's $\rho$.
Yes, finding the discrete logarithm of $a$ to base $g$ modulo $p$ is solving for $x$ the equation $a=g^x\bmod p$ given integers $g$ (the base), $p$ (the modulus), and $a$ (which discrete logarithm $x$ is thought). That's known as the Discrete Logarithm Problem (modulo $p$).
The discrete logarithm of $a=3$ to base $g=2$ modulo $p=11$ is thus $x=8$, because $2^8=256=23\times11+3$ thus $2^8\bmod11=3$ [not because $2^3=8$ thus $2^3\bmod11=8$, which happens to also hold].
The security of the original Diffie-Hellman Key Exchange (using multiplication modulo $p$ as the group operation) requires that it's practically impossible to solve that problem. In practice, parameters $g$ and $p$, and the range in which $x$ is chosen secretly and at random before $a$ is computed as $g^x\bmod p$, are such that the DLP is intractable!
I'll discuss, from the ground up, what that problem is: and some standard methods to attempt to solve it. At first I'll only assume $p\in\mathbb N\setminus\{0,1,2\}$ and $g\in[1,p)$.
For any $x\in\mathbb N$, by definition of $g^x$, that's $\underbrace {g\cdot g\ldots g}_{x\text{ terms }g}$, with $g^x=1$ when $x=0$ (since $g\ne 0$). That value $g^x$ is an integer (since $g$ is an integer).
And, by definition of the operator$\bmod$ (when there's neither an opening parenthesis immediately on it's left, nor a negative power in it's left operand), $g^x\bmod p$ is the uniquely defined $y$ in range $[0,p)$ such that $g^x-y$ is a multiple of $p$. That $y$ is an integer, and we want it to be the given $a$.
It follows that there can be a solution to $a=g^x\bmod p$ only if $a$ is an integer in $[0,p)$. In the following we'll assume this has been checked to hold.
Notice that for all $n\in\mathbb N$, it holds $g^{n+1}\bmod p=((g^n)\cdot g)\bmod p=(g^n\bmod p)\cdot g\bmod p$. This gives an efficient mean to compute $G_n=g^n\bmod p$ for incremental values of $n\in\mathbb N$, using that $G_0=1$ and the recurrence relation $G_{n+1}=G_n\cdot g\bmod p$. E.g.
That sequence $G_n$ consists of integers in $[0,p)$, thus is bound to cycle at one of it's earlier values after at worst $p$ steps. Thus a basic algorithm to solve for $x$ the equation $a=g^x\bmod p$ is:
In the worst case, this algorithm performs $p$ multiplication modulo $p$, thus has worst-case time complexity $\mathcal O(p\cdot\log^2p)$ using standard algorithms.
When $p$ is not a prime, and if we manage to fully factor $p$, we can use the Pohlig-Hellman algorithm. In a nutshell, the algorithm uses that having factored $p$ as $\prod{p_i}^{m_i}$, the Chinese Remainder Theorem allows to break the original equation $g^x\bmod p=a$ into simpler subproblems ${g_i}^x\bmod{p_i}^{m_i}=A_i$ with $g_i=g\bmod{p_i}^{m_i}$ and $A_i=a\bmod {p_i}^{m_i}$.
In the following I'll restrict to $p$ prime.
When $p$ is prime, the values taken by $G_n$ as defined above always cycle back at $1$, and first do so when $n$ is a certain integer defined as the order of $g$ modulo $p$, often noted $|g|$. That $|g|$ is such that $g^{|g|}\bmod p=1$ (and the smallest strictly positive such integer).
By Lagrange's theorem of group theory, $|g|$ is always a divisor of $p-1$. If we can factor $p-1$, we can compute $|g|$ reasonably efficiently. The general idea uses that we can compute $g^n\bmod p$ (modular exponentiation) with only $\mathcal O(\log n)$ modular multiplications. This allows checking $g^{(p-1)/k}\bmod p=1$ for various $k$. We first do so for $k=q_i$ among the primes dividing $p-1$, and if $g^{(p-1)/k}\bmod p\ne1$ for every of these we conclude that $|g|=p-1$; or, if we find a $k$ with $g^{(p-1)/k}\bmod p\ne1$, we can proceed with larger multiples of $k$ until we find $|g|$.
More often than not, $|g|$ is sizably smaller than $p$; sometime, much smaller. For example, when $(p,g)$ are chosen as in Clauss P. Schnorr's Efficient Signature Generation by Smart Cards, $p$ might have 155 decimal digits, but $|g|$ might have "only" 43 decimal digits†.
Knowing $|g|$ lets us perform a quick test to determine if there is a solution: there's one if and only if $a^{(p-1)/|g|}\bmod p=1$. Thus an alternate algorithm is:
Worst case complexity for known factorization of $p$ is $\mathcal O(|g|\cdot\log^2p+\log^4p)$ with $|g|<p$, for standard algorithms.
Assume we know $|g|$. The baby-step/giant-step algorithm works as follows:
The first repeat loop advances by "baby steps" of one additional power of $g$. The second repeat loop advances by "giant steps" of $r$ additional powers of $g$. The algorithm works because when there's a match, $g^{j\cdot r}\bmod p=a\cdot g^i\bmod p$.
Assuming we know that $p$ is prime, and the order $|g|$, this algorithm has time complexity $\mathcal O(\sqrt{|g|}\cdot\log^2p+\log^3p)$ with $|g|<p$, for standard algorithms. That's a great improvement over search by enumeration thanks to replacing $|g|$ by $\sqrt{|g|}$. However the space complexity is $\mathcal O(\sqrt{|g|}\cdot\log p)$, and that makes it impractical for parameters of cryptographic interest.
The space complexity of baby-step/giant-step can be reduced down to the point of becoming a non-issue, by using collision search rather than a table. See wikipedia's Pollard's rho for the discrete logarithm. The time complexity remains similar to that in baby-step/giant-step.
For a more detailed analysis of the technique, and how it can be used to distribute the work over multiple CPUs, see Paul C. van Oorschot & Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in JoC 1999.
That parallel version of Pollard's rho for discrete logarithm is the algorithm of choice in many cases of cryptographic interest, including Diffie-Hellman when the order $|g|$ is moderate (say up to 50 decimal digits) and $p$ is much larger. And also when, instead of multiplication modulo $p$, it's used another group operation, as is the case in Elliptic Curve Cryptography.
In the case of multiplication modulo $p$, and when $|g|$ is not particularly small, there are even better algorithms: Index calculus, and the function field sieve.
Parallel variants of the later have been used for $p$ of up to 240 decimal digits, and $|g|$ not particularly small.
† Such sizes of $p$ and $|g|$ was borderline safe in the 1990s, and no longer is safe. Nowadays (2022), for new applications, 2048-bit or 3072-bit $p$ (617 or 925 decimal digits) and at least 256-bit $|g|$ (≈77 decimal digits) are customary, in order to resist both the function field sieve and parallel Pollard's rho.
