 Cryptography

# Diffie-Hellman over $GF(2^{128})$

Can I use Diffie-Hellman over, say, $$GF(2^{128}) \bmod$$ irreducible poly in $$GF(2^{128})$$ instead of $$GF(p)$$? If not, why?

Or increase it to $$GF(2^{2^{\text{whatever}}})$$. ## Solution

Always use a randomly chosen prime field.

First of all, $$GF(2^{2^{whatever}})$$ is nonsensical. The field is still $$GF(2^k)$$ for some $$k.$$

The security of Diffie Hellman rests on the difficulty of discrete logarithms.

The discrete logarithm problem for fields of the form $$GF(2^k)$$ is much easier, having quasi-polynomial algorithms developed by Joux and others for some values of $$k$$. See also the answer to this question where the complexity for general $$k$$ of the form you are asking is stated as:

As for the case of $$q=2^k$$, the best asymptotic complexity is provided by Barbulescu et al.'s version of the function field sieve (FFS), which in that case runs in heuristic quasipolynomial time $$2^{O((\log k)^2)}$$.

Even for prime fields $$GF(p)$$, if the prime is known ahead of time there are attacks state actors can mount, but $$p$$ is randomly chosen for proper implementation of Diffie Hellman, thwarting those attacks.

• +0 – Given the weakdh.org attacks I would say if you go to something like 3k bits it's probably acceptable to use a fixed prime, right? — Aug 18, 2022 at 10:19
• +0 – @Elias, I believe so, but my expertise in this area is not that deep. You might want to ask a separate question. — Aug 18, 2022 at 20:27