My Math Forum Diffie-Hellman

 Number Theory Number Theory Math Forum

 February 13th, 2012, 04:10 PM #1 Senior Member   Joined: Sep 2009 Posts: 115 Thanks: 0 Diffie-Hellman Suppose Alice and Bob use the Diffie-Hellman exchange choosing primitive root "g" for a large prime p. Alice sends $x_{1}= g^a \text{ mod } p$ and Bob sends $x_{2}= g^b \text{ mod } p$. Suppose Eve is able to obtain b and $x_{2}$ from Bob but not the value of g. Furthermore, suppose gcd(b,p-1)=1. Show how Eve can determine g from p, b, and $x_{2}$. So I am having difficulty with this problem. I was maybe thinking along the lines of: $x_{2}^{(p-1)/b}= g^{(p-1)b/b} = g^{p-1} = 1 \text{ mod } p$ 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: Diffie-Hellman Well you are going in the right direction: You want to somehow express $g=g^1\text{ mod } p$. So by Fermat's little theorem we are looking for an integer c such that $bc= 1 \text{ mod }(p-1)$ as in this case we have $x_2^c= (g^b)^c=g^{bc}=g^1= g\text{ mod } p$. 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: Diffie-Hellman Oh ok that makes sense. its because gcd(b,p-1)=1 so we know that it exists. thank you very much.

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post threesixtify Applied Math 0 January 22nd, 2013 04:53 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top