[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Diffie Hellman - logs in Galois fields
[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