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

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.





Comments (2)

  • +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  


Linked Articles

Local articles referenced by this article: