#!/usr/bin/python
"""
  Example code for demonstrating millionaires problem.
  Written for article:
   http://bryanmills.net/archives/2007/10/millionaires-problem/

  Written by Bryan Mills
  
  Released in Public Domain (do what you like - I don't care)
"""
import random
import sys

def isPrime(number):
    """ returns true if the number is prime """
    # convert number to absolute value and int
    number = abs(int(number))
    # the number 1 is not prime
    if number < 2:
        return False
    # yep, 2 is prime
    if number == 2:
        return True
    # all other even numbers are not prime
    if not number & 1:
        return False

    # need to check all numbers between 3 (already dealt with 0,1,2)
    # so between 3 and the square root of the number given
    # the plus one is because we really only want to check odd numbers
    # then we step over by 2 since because if were even we would
    # have already returned false
    for x in range(3, int(number**0.5)+1,2):
        # if the number mod x is 0 then we found a divisor
        if number % x == 0:
            return False
    return True

def chooseRandomPrime(min_num,max_num):
    """ Return a random prime number p such that
        p >= min_num and p < max_num
        If no prime number in range then return None
    """
    firstPrime = min_num
    # search for the first prime number in range
    while not isPrime(firstPrime) and firstPrime < max_num:
        firstPrime += 1
    # if we incremented to the end no prime exists in range
    if firstPrime == max_num:
        return None
    
    # pick some random stop point in the range
    stopPoint = random.randint(firstPrime,max_num)
    # search backwards from stop point until we hit a prime
    # this is gaurenteed to hit at lease firstPrim
    for num in range(stopPoint,firstPrime-1,-1):
        if isPrime(num):
            return long(num)

def extended_euclid_gcd(a,b):
    """ Returns a tuple (d,i,j) such that d = gcd(a,b) = i*a + j*b """

    x = 0
    lastx = 1
    y = 1
    lasty = 0

    while not b == 0:
        temp = b
        quotient = long(a/b)
        b = a % b
        a = temp

        temp = x
        x = lastx - quotient*x
        lastx = temp

        temp = y
        y = lasty-quotient*y
        lasty = temp
        
    return (a, lastx, lasty)

def gcd(p,q):
    """ simple function to return the
        greatest common demoinator between p and q """
    if p < q:
        return gcd(q,p)
    if q == 0:
        return p
    return gcd(q,abs(p%q))

def relativePrime(a,b):
    """ returns true if a and b are relativly prime (ie gcd(a,b) == 1) """
    d = gcd(a,b)
    return (d == 1)

def getRSAKeys():
    """ Generate public and private keys using the RSA algorithm.
        returns the tuple - (prime_1,prime_2,n,public_key,private_key)
         * prime_1 - the first prime choosen  (not used after generation)
         * prime_2 - the second prime choosen (not used after generation)
         * n       - this is the value all caculations are done modual
                     defines the finite field space ( ?? mod n )
         * public_key - this is the public key value
                        by pairing this value and n you have a public key
         * private_key - this is the private key part
    """
    MIN_PRIME = 100L
    MAX_PRIME = 1000L
    
    p = chooseRandomPrime(MIN_PRIME,MAX_PRIME)
    q = chooseRandomPrime(MIN_PRIME,MAX_PRIME)
    n = p * q
    totient_n = (p-1)*(q-1)
    decipher_key = -1
    while decipher_key < 0:
        while True:
            e = chooseRandomPrime(1,MAX_PRIME/2)
            if relativePrime(e,n) and relativePrime(e, totient_n):
                break
        (gcd, decipher_key, j) = extended_euclid_gcd(e,totient_n)
        
    return (p,q,n,e,decipher_key)


if __name__ == "__main__":
    # these variables define the wealth of BOB and ALICE
    BOB_VALUE = 6
    ALICE_VALUE = 8
    # this is known MAX wealth value (recall that they need a range)
    # this simple implementation assumes the range is 1 to MAX_VALUE
    MAX_VALUE = 10

    # this call gets Alices RSA key pair
    # there are two parts to each key
    #  (1)  n (this is the value everything is mod'd by)
    #  (2)  public or private key (depending on which key)
    # example: private key is both (n, private_key)
    #          public key is both (n, public_key)
    (prime_1,prime_2,n,public_key,private_key) = getRSAKeys()

    print "*"*30
    print "Alice's public key %s" % str([n,public_key])
    print "Alice's private key %s" % str([n,private_key])
    print "*"*30
    
    # STEP 1: generate bob's random number
    bob_random = random.randint(1500,4000)
    print "\nSTEP 1:"
    print "BOB's random value %d" % bob_random

    # BOB encrypts his random number using Alice's public key
    c = bob_random**public_key % n
    print "BOB's C value %d" % c
    print "bob creates cypher %s" % c

    # STEP 2: bob encodes his wealth using this random number
    #         this is bobs C - J + 1 value
    send_to_alice = c - BOB_VALUE + 1
    print "\nSTEP 2:"
    print "BOB sends this value to ALICE: %d" % send_to_alice

    # STEP 3: ALICE computes the Yi values
    print "\nSTEP 3:"
    y = []
    for i in range(0,MAX_VALUE):
        y.append((send_to_alice+i)**private_key % n)

    alice_random_prime = chooseRandomPrime(500,1500)
    
    print "ALICE's random prime %d" % alice_random_prime
    print "ALICE's Y values = %s" % str(y)

    # STEP 4: ALICE computes the Zi values
    print "\nSTEP 4:"
    z = []
    for i in range(0,MAX_VALUE):
        z.append(y[i] % alice_random_prime)
        
    print "ALICE's Z values = %s" % str(z)

    ## technically you should check that all z values are seperated
    ##  by at least 2, I ignore that :)

    # STEP 5: ALICE computes the values to send to BOB
    print "\nSTEP 5:"
    send_to_bob = []
    for i in range(0,MAX_VALUE):
        v = 0
        if (i+1) > ALICE_VALUE:
            v = 1
        send_to_bob.append((z[i] + v))

    print "ALICE sends BOB p=%d and %s" % (alice_random_prime,str(send_to_bob))
    
    # STEP 6: BOB computes G = bob_random mod alice_random_prime
    print "\nSTEP 6:"

    bob_x_value = bob_random % alice_random_prime
    print "G = bob_random mod alice_random_prime = %d " % bob_x_value

    # STEP 7: BOB determines who is richer and tells ALICE
    print "\nSTEP 7:"
    print "BOB first decides who is richer:"
    # if bob_x_value is equal to the jth value then bob is richer
    if not bob_x_value == send_to_bob[(BOB_VALUE-1)]:
        print " *** BOB IS RICHER"
    else:
        print " *** ALICE IS RICHER"
    print "\nBOB now tells ALICE who is richer"