Re: Diffie-Hellman in GF(2^n)?
In article <Pine.SUN.3.91.951110184600.19312B-100000@eskimo.com> you write:
Most Diffie-Hellman implementations currently use the multiplicative group of prime fields. However, the multiplicative group of finite fields of characteristic 2 (GF(2^n)) can also be used and should be easier to implement. Is there any reason why they should not be used? Does anyone know the asymptotic running time of the best algorithm for calculating discrete logarithms in GF(2^n)?
I remember that the discrete log problem is quite a bit easier in GF(2^n), but I don't remember how much easier. Let me try to look it up... A. Odlyzko has a paper recommending that people should not use GF(2^n) for discrete log applications; in it he states that you will need at the minimum n > 800, and probably n > 1500. (And you also need to choose n carefully.) A quote from the abstract: ``Hence the fields GF(2^n) out to be avoided in all cryptographic applications.'' I don't know enough about number theory to judge for myself; but you can read the (long) paper yourself at ftp://netlib.att.com/netlib/att/math/odlyzko/discrete.logs.ps.Z I hope this helps!
I don't know enough about number theory to judge for myself; but you can read the (long) paper yourself at
ftp://netlib.att.com/netlib/att/math/odlyzko/discrete.logs.ps.Z
Thanks for the reference. The paper gives a running time of exp(c(n log n)^(1/2)) for discrete log in GF(p) and exp(c*n^(1/3)*(log n)^(2/3)) for discrete log in GF(2^n). However, this paper was published in 1985. There is now an algorithm to calculate discrete logs in GF(p) in exp(c*n^(1/3)*(log n)^(2/3)) (see prime.discrete.logs.ps.Z in the same directory), so perhaps GF(2^n) isn't so bad after all. Wei Dai
I wrote earlier:
Thanks for the reference. The paper gives a running time of exp(c(n log n)^(1/2)) for discrete log in GF(p) and exp(c*n^(1/3)*(log n)^(2/3)) for discrete log in GF(2^n). However, this paper was published in 1985. There is now an algorithm to calculate discrete logs in GF(p) in exp(c*n^(1/3)*(log n)^(2/3)) (see prime.discrete.logs.ps.Z in the same directory), so perhaps GF(2^n) isn't so bad after all.
To clarify my earlier post, although both of the latter two algorithms have a runtime of the form exp(c*n^(1/3)*(log n)^(2/3)), for GF(p) c=1.922+o(1), for GF(2^n) c=1.405+o(1). This seems to imply that if GF(2^n) is to be used, n needs to be 2.56*log p to achieve a comparable level of security to using GF(p). (2.56=1.922^3/1.405^3) Wei Dai
participants (2)
-
David A Wagner -
Wei Dai