From: Justin Card <Wyntermute@worldnet.att.net>
Date: Tue, 17 Sep 1996 17:37:55 +0800
To: cypherpunks@toad.com
Subject: Re: Diffie Hellman - logs in Galois fields
In-Reply-To: <842896368.27767.0@fatmans.demon.co.uk>
Message-ID: <323CDB46.1632@worldnet.att.net>
MIME-Version: 1.0
Content-Type: text/plain


paul@fatmans.demon.co.uk wrote:
> 
> Hi all,
> 
> A question for the matematicians out there:
> 
> I am looking at the Diffie Hellman public key exchange protocol and
> am trying to find out why it is computationally hard to take logs in
> a finite (Galois) field.
> 
> My maths tutor has told me a bit about the construction of Galois
> fields (If I`m correct the construction is Z mod N, N some integer,
> then a transformation F(x) on the residue classes already in the
> field) I know also the definition is that there are P**k elements, p
> a prime.
> 
> My questions are as follows:
> 
> 1. How can a field be finite, as by definition it has to be closed
> under addition, subtraction, multiplication and division???? (sorry
> if this one is a bit of a no brainer, maybe the definition is
> different but I can`t seem to see how)

I'll have to let somebody else answer this one, since I am really not
sure.
 
> 2. Why is taking logs in a finite field computationally hard? - Me
> and Alec (My maths tutor at college) guessed that it is because
> exponentiation and logs are each others inverse functions, and
> somehow this becomes a one way function in a finite field.

As far as anybody knows, you're right, exponentiation is a one way
function in a prime field.  

However, there are some things to be said. If you're using a fixed g and
N, or repeat both for too many key exchanges, if anybody logged them, it
becomes a more exciting target, since the hard part of the algorithms
need be completed only once.  Then taking separate logs with the same g
and N is easy.
 
> 3. Are the Galois fields used in Diffie Hellman specially constructed
> in any way or are they just normal GF????

The field used in DH is just a standard Galois Field mod some large
prime. 

-- 
  Wyntermute