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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.