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.
So really, it has everything to do with the commutativity up in the exponent.