1995-11-15 - Re: Diffie-Hellman in GF(2^n)?

Header Data

From: David A Wagner <daw@CS.Berkeley.EDU>
To: weidai@eskimo.com
Message Hash: e04d2106e6299f35d623227a3fa8636d2d8de18d39f6b66a82f4724208fe8676
Message ID: <199511122243.OAA18565@delhi.CS.Berkeley.EDU>
Reply To: N/A
UTC Datetime: 1995-11-15 05:59:53 UTC
Raw Date: Wed, 15 Nov 1995 13:59:53 +0800

Raw message

From: David A Wagner <daw@CS.Berkeley.EDU>
Date: Wed, 15 Nov 1995 13:59:53 +0800
To: weidai@eskimo.com
Subject: Re: Diffie-Hellman in GF(2^n)?
Message-ID: <199511122243.OAA18565@delhi.CS.Berkeley.EDU>
MIME-Version: 1.0
Content-Type: text/plain


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!





Thread