# Exponential modular arithmetic for Diffie-Hellman

I've been playing around with some finite fields to test how rapid brute-force is when solving discrete logarithm problems occurring in DH methods.

Working in $\mathbb{F}_{101}$, pick a private key $\alpha=88$, $\beta$ arbitrary and let $g=41$ such that $A=g^{\alpha}\equiv 87 \pmod{101}$. I believe $g$ is not a primitive root modulo 101, and it is confirmed by the fact that $g^{8}\equiv g^{88} \equiv 87 \pmod{101}$.

Say if you were to use the naive algorithm to attack this DLP and find this value $\tilde{\alpha}=8$, can we then simply say that we found the common key $K=g^{\alpha\beta}$? So is it always true that in this case $g^{\alpha\beta}\equiv g^{\tilde{\alpha}\beta} \pmod{101}$?

I feel like this should not necessarily hold, but I'm not sure if we can simply say this. Does it maybe have to do with $g$ not being a primitive root?

In DHKE, it is required that an attacker find a solution $$\alpha$$ to $$A=g^\alpha$$ (with $$g$$ and $$A$$ known), not the solution that Alice chose at the outset. This is actually why we demand that $$g$$ be primitive: there will be no repetitions in the output beyond the typical mod $$p-1$$ repeats you would see from Euler's Theorem anyway. So, by choosing a primitive, you maximize the difficulty of a brute force attack. This is an important idea. The algebra of DHKE works even without using a primitive, but that doesn't mean it's cryptologically sound.
And the reason that that attack works is clear: if Eve can find $$x$$ with $$g^x=A$$ then--whether or not $$x$$ is actually $$\alpha$$--Eve can still reconstruct the common key $$K =g^{\alpha\beta}$$ since she knows Bob's value of $$B=g^\beta$$: $$K = g^{\alpha \beta}=(g^\alpha)^\beta=(g^x)^\beta = (g^\beta)^x = B^x.$$ In short, Eve just computes $$B^x$$, where $$B$$ is known and $$x$$ is her solution, and this ends up being $$K$$. That's all she needs.