[Crypto] Super basic questions to DLP and DH

Kudos for the question's critical thinking. Keep on with that attitude!

Eve wants to find $\log_g(g^x)$ which gives her $x$. Why is it a problem? She knows $g$ and she knows what the number $g^x$ is.

The problem as stated in this quote and with $g$ in the set $\mathbb Z$ (the integers) is the logarithm problem restricted to integers, and indeed is easy. Just by looking at the size of $g^x$ (the number of digits in decimal), it's easy to get an idea of how large $x$ is. For example if $g$ is $11$, $g^x$ will have a little over $x$ decimal digits. More generaly, $x$ is $\log(g^x)/\log(g)$, computed over the reals with the logarithm in any base.

In the discrete logarithm problem, $g^x$ is not computed by regular integer multiplications. It's computed in a finite set with group structure. $g^x$ is constrained to be in the same finite set as $g$ is, no matter how large $x$. That makes a huge difference, because Eve always gets a small value, thus techniques based on the size of $g^x$ will no longer work.

The simplest group usable is the multiplicative group modulo a safe prime $p$. In this group, $u*v$ is defined as the remainder of the Euclidean division of $u\cdot v$ by $p$, where $u\cdot v$ is the ordinary product. $g^x$ is defined as usual:$$g^x=\underbrace{g*g\ldots g*g}_{x\text{ terms}}$$ where each $*$ is an operation in the finite set. Note that $g^x$ can be computed with $\approx1.5\log_2(x)$ modular multiplications, rather than the obvious $x-1$.

To convince you things are hard, try with $p=31469$ (small enough that $u\cdot v$ fits 9 decimal digits), $g=3$, $g^x=11292$. How do you get $x$?

One simple method is to try all $x$ sequentially, that has cost $\Theta(p)$ (note that we can move to the next power of $g$ with a single modular multiplication). A better method is baby-step/giant-step, that has cost $\Theta(\sqrt p)$ in work and memory. Yet a better (probabilistic) method is Pollard's rho, which also requires $\Theta(\sqrt p)$ work but reduces memory requirements to $\Theta(1)$, and can largely be parallelized.

Because we use a particularly simple group, there are even better methods. However, with e.g. Elliptic Curve groups, we don't know a much better method that works on computers as we know them. Thus if we use a suitable group with enough elements (e.g. in the order of $2^{256}$), the best way we know to get $x$ requires in the order of $2^{128}$ group operations on computers as we know them.