#!/usr/bin/python
import random
 
# Implements the Shamir key exchange protocol
 
__author__ = "doug@neverfear.org"
 
# Public information
p = 1171 # Prime. In the real world this should be generated to be a very big prime.
 
def inverse(a, b):
    dividend = a
    divisor = b
    lines = []
    lasta = 1
    lastb = 0
    remainder = 1
    while remainder > 0:
        quotient = dividend / divisor
        remainder = dividend - (quotient * divisor)
        b = lasta - (lastb * quotient)
        dividend = divisor
        divisor = remainder
        lasta = lastb
        lastb = b
    return int(b)
 
class Agent():
    def __init__(self, name, private):
        self.name = name
        self.priv = private
        self.inverse = inverse(p - 1, private)
 
    def PadlockOn(self, Kn):
        next = (Kn ** self.priv) % p
        print self.name, "placed lock on", Kn, "resulting in", next
        return next
 
    def PadlockOff(self, Kn):
        next = (Kn ** self.inverse) % p
        print self.name, "took lock off", Kn, "resulting in", next
        return next
 
Alice = Agent("Alice", 97)
Bob   = Agent("Bob", 107)
 
K = 103 # At the end of this, Kn should be 103
Kn = Alice.PadlockOn(K)
Kn = Bob.PadlockOn(Kn)
Kn = Alice.PadlockOff(Kn)
Kn = Bob.PadlockOff(Kn)
print "Key was", Kn