February 13th, 2012, 04:10 PM  #1 
Senior Member Joined: Sep 2009 Posts: 115 Thanks: 0  DiffieHellman
Suppose Alice and Bob use the DiffieHellman exchange choosing primitive root "g" for a large prime p. Alice sends and Bob sends . Suppose Eve is able to obtain b and from Bob but not the value of g. Furthermore, suppose gcd(b,p1)=1. Show how Eve can determine g from p, b, and . So I am having difficulty with this problem. I was maybe thinking along the lines of: However at this point I am stuck on how to continue in order to figure out g. Any help would be appreciated. 
February 14th, 2012, 04:39 AM  #2 
Senior Member Joined: Sep 2008 Posts: 150 Thanks: 5  Re: DiffieHellman
Well you are going in the right direction: You want to somehow express . So by Fermat's little theorem we are looking for an integer c such that as in this case we have . And the first term can be computed. Can you see why such a number c exists? And given the context of the question is c fast computable? I.e. , is it just theoretically possible to break this code or also in practical terms? I hope this gets you started. 
February 15th, 2012, 09:40 PM  #3 
Senior Member Joined: Sep 2009 Posts: 115 Thanks: 0  Re: DiffieHellman
Oh ok that makes sense. its because gcd(b,p1)=1 so we know that it exists. thank you very much.


Tags 
diffiehellman 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
PohligHellman Cipher + Affine Hill Cipher, relatively simpl  threesixtify  Applied Math  0  January 22nd, 2013 04:53 AM 