- diffie-hellman finite-field
- Updated Sat, 17 Sep 2022 14:05:30 GMT

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}}})$.

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

External links referenced by this document:

Local articles referenced by this article: