5
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks. Yeah it kinda is - after lectures we have questions to try out on our own :) I'm just not sure how to interpret the question. Since the base is 2, we are raising 2 to 3. In other words: $$2^3 \equiv 8 \mod 11 \equiv 8$$ 8 is what we are looking for. For some reason I was thinking about it another way, $\log_2 3 \equiv \alpha \mod 11$ and we are looking for $\alpha$...Though this way doesn't feel right as you already know the value of LHS - nor does it make much sense as the result of the logarithm has a fractional part. $\endgroup$ Dec 6, 2019 at 6:35
  • 3
    $\begingroup$ The fact that this is a hard problem is literally the reason Diffie-Hellman is secure. $\endgroup$
    – Mikero
    Oct 9, 2022 at 1:17
  • $\begingroup$ I understand that practically it is very difficult to obtain a, but I just want to know how to apply modulo inverse on this without using any numbers. $\endgroup$
    – user104263
    Oct 9, 2022 at 1:30
  • 3
    $\begingroup$ en.m.wikipedia.org/wiki/Pollard's_rho_algorithm $\endgroup$ Oct 9, 2022 at 2:03

2 Answers 2

8
$\begingroup$

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

  • Pohlig–Hellman algorithm that is applicable when the order of the group is smooth. It has $\mathcal O\left(\sum_i {e_i(\log n+\sqrt {p_i})}\right)$-time complexity where $\prod_i p_i^{e_i}$ is the prime factorization of group order $n$. To mitigate this attack this attack a prime order must be selected than is has same worst-case complexity as $\mathcal{O}(\sqrt{n}\log n)$-time.

  • DLog for Elliptic Curves (Additive): DLOG is also defined for Elliptic Curves ( form an abelian group via point addition), in which given a base point $G$ and another point $Q$ find $x$ such that $[x]G = Q$ where $$[x]G = \overbrace{G+\cdots+G}^{{x\hbox{ - }times}}$$

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$.

$\endgroup$
0
2
$\begingroup$

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)$.

Definition: what's $g^x\bmod 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$.

Range check of $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.

Search by enumeration

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.

  • For $(g,p)=(2,11)$ the sequence goes 1, 2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, …
  • For $(g,p)=(2,10)$ the sequence goes 1, 2, 4, 8, 6, 2, 4, 8, 6, 2, …
  • For $(g,p)=(3,10)$ the sequence goes 1, 3, 9, 7, 1, 3, 9, …
  • For $(g,p)=(2,8)$ the sequence goes 1, 2, 4, 0, 0, 0, …

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:

  • $x\gets 0$ and $G\gets 1$
  • while $x<p$
    • if $G=a$ then output "the smallest non-negative integer solution is " $x$, and stop.
    • $x\gets x+1$ and $G\gets G\cdot g\bmod p$
  • output "there is no solution", and stop.

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.

Composite $p$: Pohlig-Hellman

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.

Prime $p$: further check of $a$, and a slight simplification

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:

  • if $a^{(p-1)/|g|}\bmod p\ne 1$, then output "there is no solution", and stop.
  • $x\gets 0$ and $G\gets 1$
  • while $G\neq a$
    • $x\gets x+1$ and $G\gets G\cdot g\bmod p$
  • output "the smallest non-negative integer solution is " $x$, and stop.

Worst case complexity for known factorization of $p$ is $\mathcal O(|g|\cdot\log^2p+\log^4p)$ with $|g|<p$, for standard algorithms.

Baby-step/giant-step

Assume we know $|g|$. The baby-step/giant-step algorithm works as follows:

  • if $a^{(p-1)/|g|}\bmod p\ne 1$, then output "there is no solution", and stop.
  • $r\gets\left\lceil{\sqrt{|g|}}\,\right\rceil$
  • $i\gets 0$ and $y\gets a$
  • repeat
    • enter $y$ and $i$ in a table allowing quick search of $y$ and determining the matching $i$
      [notice that here $y=a\cdot g^i\bmod p$ ]
    • if $i=r-1$ then exit the repeat loop
    • $i\gets i+1$ and $X\gets a\cdot g$
  • $z\gets g^r\bmod n$ (by modular exponentiation)
  • $j\gets 0$ and $y\gets 1$
  • repeat until $y$ (and it's matching $i$) is found in the table
    • $j\gets j+1$ and $y\gets y\cdot z\bmod p$
  • $x\gets j\cdot r-i\bmod|g|$
  • output "the smallest non-negative integer solution is " $x$, and stop.

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.

Pollard's rho for discrete logarithm

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.

Even better algorithms

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.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.