My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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 and Bob sends . Suppose Eve is able to obtain b and 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 .


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.
wannabe1 is offline  
 
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 . 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.
Peter is offline  
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.
wannabe1 is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
diffiehellman



Thread Tools
Display Modes


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





Copyright © 2019 My Math Forum. All rights reserved.