From: paul@fatmans.demon.co.uk
Date: Tue, 17 Sep 1996 10:40:03 +0800
To: cypherpunks@toad.com
Subject: Diffie Hellman - logs in Galois fields
Message-ID: <842896368.27767.0@fatmans.demon.co.uk>
MIME-Version: 1.0
Content-Type: text/plain



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)

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.

3. Are the Galois fields used in Diffie Hellman specially constructed 
in any way or are they just normal GF????

Thanks for any help anyone can give me....


  Datacomms Technologies web authoring and data security
     Paul Bradley, Paul@fatmans.demon.co.uk
       Http://www.fatmans.demon.co.uk/crypt/
         "Don`t forget to mount a scratch monkey"

-----BEGIN PGP PUBLIC KEY BLOCK-----
Version: 2.6.3ia

mQCNAjH9j+cAAAEEAMBvREiQR0ot9dFCO0TiSCSunAYLv2g1Bc6I3bz8FzKXNH53
6mieJf/W4rD+CxJpT0q9RQaaoRtkHJLwbjfK2il3D7mEahMAyqvF/xRJNqkXfhM3
sRJM0Jh43l+W0M5vwokbEbk25/bxWWGspTsLD3YHbzKnG6pOcL5OPIRbv66xAAUR
tCdQYXVsIEJyYWRsZXkgPHBhdWxAZmF0bWFucy5kZW1vbi5jby51az6JAJUDBRAy
NwfvNkCBjDT0xHEBATQPA/9TORmN/UjNecj03q4anpvdyCLiez5sKuNbnYK50RiP
Jj4QpWWvST3smyQ0A86DrZY/re056MXwQmARESx0rFZxdnD0oORICl5r8dJLIy3b
j8rbA5olXwZwKz73/X5s13v/pvHYX4cIsbVK8NHXqh5llSKt6TBAuGgkIGF29z5k
C4kAlQMFEDI3B9mdtf/umVkv7QEBcRYD/1FBteLqsUmr81euxqqnnrpLlyHb58B/
9sdATuua4uSjX46hXDZ264YozspNrzSB4NEdrmXOWVX3fiE0ga6XkSSkIeF23V90
En37Z0BdbFzgF00FRYTFyTq8eezQrdg/+rBPUsZUmG5wpq3e12FKHQsX01i+1mB2
YmqqwCV5e95eiQCVAgUQMh8uSb5OPIRbv66xAQEqJwP/fxQyiCasjFcbDpsFfsYp
put5cCC/9pOx6X3DlbKShPMpUOS+A9HsTEmJQN8Iawv1nSwPdtc2cR/GhW6ilVjW
LSloGdMVLabm9pGpZZMkRaZlXFUkOv7VhfgsUiL+vIDryBCAwUZCzQiWycjt/cPi
mUqFH41Z7NkyO8ZFdi5GGX0=
=CMZA
-----END PGP PUBLIC KEY BLOCK-----