# How is Diffie-Hellman secure when the exchanged number is a power of the generator less than the modulo

I'm trying to understand how Diffie-Hellman is still secure when $$A$$ ends up being a power of $$g$$ less than $$p$$.

I chose $$p$$, where p is prime, and $$g$$ is a primitive root modulo $$p$$.

$$g=2$$ and $$p=29$$

Now considering Alice creating her $$A$$ where $$A=2^a\mod{29}$$. If she chooses $$a=30$$ this results in $$2^{30}=4\mod{29}$$, which means I can trivially recover an $$a$$ with the same result $$a=log_2{4}=2$$ and use that to recover the shared secret.

In general any returned $$A$$ that is a power of $$2$$ less than $$29$$ (ie. $$2,4, 8,16$$) can be trivially recovered by taking $$log_2{A}$$ and getting a valid $$a$$.

How does Diffie-Hellman resist against this? Am I missing something else? I know I chose a small $$a$$ and $$p$$ but it seems this problem would exist with large $$a$$ and $$p$$ too.

If $$g^a, then the discrete logarithm mod $$p$$ becomes plain logarithm, even for a 2048-bit $$p$$. So, you are right that in this case $$a$$ can be easily computed from $$g^a$$. However, this is not bad because there are only at most $$\log_2 p$$ such $$a$$s (that satisfy $$g^a). Compared to $$p$$, $$\log_2 p$$ is a negligible number. In other words, since $$a$$ is chosen uniformly at random from $$p-1$$ values, the probability that it falls into the first $$\log_2 p$$ values is negligible (in $$\log_2 p$$, the bit length of $$p$$).
• Addition: It's been experimentally and publicly demonstrated that we can solve the DLP modulo $p$ for $\log_2 p\approx795$. In the question, $\log_2 p\approx5$. @ᴘᴀɴᴀʏɪᴏᴛɪs
First of all, the choice of $$a$$ must satisfy $$1 \leq a < p$$, The exponent $$a = 30$$, for this prime, is equivalent to the exponent $$2$$ because $$30 \equiv 2 \mod{\phi(29)}$$.
Secondly, as you stated the $$p$$ is very small. Thus, with a paper and pencil one can calculate the discrete log problem. When you consider, the recommended size of $$p$$ as 2048-bit (see at update of RFC4419) you will face the real problem.
When $$a$$ is chosen randomly, it will have 2047-bits with 1/2 probability-think of the MSB has 1/2 probability to equal 1. Now consider calculating discrete logarithm problem. The complexity is $$\mathcal{O}(\sqrt{p})$$ with Baby-step giant-step. With Pollard's kangaroo algorithm it is $$\mathcal{O}(\sqrt{b-a})$$ where the algorithm selects a set $$\{a,\ldots, b\}$$, the original paper.