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