# Diffie-Hellman key exchange

# cat diffie-hellman.py
import math

# Zp*
# |Z9*| = totien(9) = 9(1 - 1/3) = 6
# a        1  2  4  5  7  8
# ord(a)   1  6  3  6  3  2
# generators: 2 and 5

g = 2 # generator
p = 9 # prime


print '1. [Alice] and [ Bob ] agree to use g = %d and p = %d' % (g, p)
print

a = 15 # alice secret
A = (g**a) % p
print '2. [Alice] Generates a = %d and sends A = %d' % (a, A)
print

b = 7 # bob secret
B = (g**b) % p
print '3. [ Bob ] Generates b = %d and sends B = %d' % (b, B)
print

a_shared_secret = (B**a) % p
print '4. [Alice] Computes the shared_secret = %d' % a_shared_secret
print

b_shared_secret = (A**b) % p
print '5. [ Bob ] Computes the shared_secret = %d' % b_shared_secret
print

print '6. [Alice] and [ Bob ] now share the same secret'
print

print '-' * 50 + '\n'

def brute_force(shared):
        for i in xrange(0, 100):
                if (g**i) % p == shared:
                        print str(i),
        print

ea = (math.log(A, g)) % p
print '7. [ Eve ] Tries to find a, knowing (A, g and p)'
print 'Logarithm >> a = %d' % ea
print 'Brute force >>',
brute_force(A)
print
eb = (math.log(B, g)) % p
print '8. [ Eve ] Tries to find b, knowing (B, g and p)'
print 'Logarithm >> b = %d' % eb
print 'Brute force >>',
brute_force(B)

# python diffie-hellman.py
1. [Alice] and [ Bob ] agree to use g = 2 and p = 9

2. [Alice] Generates a = 15 and sends A = 8

3. [ Bob ] Generates b = 7 and sends B = 2

4. [Alice] Computes the shared_secret = 8

5. [ Bob ] Computes the shared_secret = 8

6. [Alice] and [ Bob ] now share the same secret

--------------------------------------------------

7. [ Eve ] Tries to find a, knowing (A, g and p)
Logarithm >> a = 3
Brute force >> 3 9 15 21 27 33 39 45 51 57 63 69 75 81 87 93 99

8. [ Eve ] Tries to find b, knowing (B, g and p)
Logarithm >> b = 1
Brute force >> 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97

Reference

https://en.wikipedia.org/wiki/Diffie%E2%80%93Hellman_key_exchange