Diffie-Hellman Example

25 days ago by bcr49

Alice wants to initate a Diffie-Hellman key exchange with Bob.

p = next_prime(2^100) F = GF(p) g = F(primitive_root(p)) print "Alice: Hey Bob, let's do DHKE in F_p^* with p =", p, "and g = ", g a = randrange(p) A = g^a print "Alice: Here is my public key A =", A 
       
Alice: Hey Bob, let's do DHKE in F_p^* with p =
1267650600228229401496703205653 and g =  2
Alice: Here is my public key A = 511914698987694613016588170978
Alice: Hey Bob, let's do DHKE in F_p^* with p = 1267650600228229401496703205653 and g =  2
Alice: Here is my public key A = 511914698987694613016588170978

Bob responds by doing the following computations

b = randrange(p) B = g^b K_bob = A^b print "Bob: OK Alice. Here's my B =", B print "Bob: I have computed our shared key K." 
       
Bob: OK Alice. Here's my B = 90060289719309095781948621
Bob: I have computed our shared key K.
Bob: OK Alice. Here's my B = 90060289719309095781948621
Bob: I have computed our shared key K.

Alice now also computes K

print "Alice: Thanks, Bob." K_alice = B^a 
       
Alice: Thanks, Bob.
Alice: Thanks, Bob.
print "Do Alice and Bob have the same K?" K_bob == K_alice 
       
Do Alice and Bob have the same K?
True
Do Alice and Bob have the same K?
True

Eve has been listening and now tries to get her hands on K. If she can get her hands on Alice's secret a she is in business. She tries to compute a = log_g(A)...

time discrete_log(A,g) 
       

... but runs out of memory and gives up.