[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Re: Diffie Hellman - logs in Galois fields*From*: Justin Card <[email protected]>*Date*: Mon, 16 Sep 1996 00:44:54 -0400*References*: <[email protected]>*Sender*: [email protected]

[email protected] 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

**References**:

- Prev by Date:
**Re: 56 kbps modems** - Next by Date:
**Re: Workers Paradise. /Political rant.** - Prev by thread:
**Diffie Hellman - logs in Galois fields** - Next by thread:
**Re: Diffie Hellman - logs in Galois fields** - Index(es):