Super basic questions to DLP and DH

Question

This is a super basic cryptography and I don't get it. My professor only explained it to us on a very abstract level, which I just agreed to without questioning it.

The DLP says it is easy to calculate a^x, but it is not easy to find x with a logarithm if you use a cyclic group. The idea behind the cyclic group is to shuffle the numbers. If you don't do it, you can guess your way to the exponent, because the numbers are ordered and you know if you get a two high or two low number, you can guess in the right direciton.

So very abstract, I do get it. But very concrete, I don't.

What I don't get I mean, with the DH Alice send g^x and g, Bob sends g^y. So the evil person gets both g, g^x and g^y. And she wants to find log_g(g^x) which gives her x. What is her problem? She knows g and she knows what what the number (g^x) is.

I mean, I don't know how to type this in on a calculator because we only used log_e (also called ln) and log_10 (which is just log on my calculator). If I take my calculator and I type log(100), which is log_10(100), I get 2. Which is the number I looked for. Why can't Eve do the same?

Sorry, this is a very stupid question, but I am too emeberassed to ask anyone else than you ^^

Answer 1

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.

Answer 2

you are only looking at base 10 and e. There are some other in practice, base 2 for binary. Base 16 for Hex, Base64 etc.

| what is DLP ?

• Fix a prime p , Let ${\beta}$ and ${\alpha}$ be non-zero integers mod p and suppose
• $${\beta \equiv \alpha ^x (mod p)}$$
• The problem of finding x is called Discrete Logarithm Problem. if n is the smallest positive integer such that ${\alpha^n \equiv 1 (modp)}$, we may assume ${0 \le x < n}$, then we denote $${x=L_\alpha(\beta)}$$
• Here you can see the the base is ${\alpha}$. so, from the first equation if you take Log of ${\beta}$ with base ${\alpha}$ then we have ${L_\alpha(\beta) \equiv xL_\alpha \alpha (modp)}$ , then we know that ${L_\alpha \alpha=1}$, then we are left with ${L_\alpha(\beta) \equiv x (modp)}$. This will give us the x reduced to (mod p)
• | on extra note, here ${\alpha}$ is a generator of a cyclic Group i.e, power of ${\alpha}$ generates all the elements of the Group. (Field as we work with prime number here), and x is one of them. Attacker has to try which value of x can give him ${\beta}$.
• For ex. take a prime 7 it has generators {3,5}. we've ${3^1 mod(7)=3, 3^2 mod(7)=2,3^3 mod(7)=6,3^4 mod(7)=4,3^5 mod(7)=5, 3^6 mod(7) =1}$, so, you can see that if value of ${\beta=6}$, then from above we have x=3.