# Let's call our parties Alice and Bob and we are going to assume throughout that neither party trusts the other one. (If they did trust each other, one # of them would simply flip a coin and tell the other one the result!) In our scheme, Bob's job will be to factor a number Alice provides him. If he # succeeds in factoring the number, he wins the flip, and if not, Alice wins. The math, number theory in this case, involves the Chinese Remainder Theorem # and a criterion developed by Euler. Neither of these proofs are recent, so presumably this coin-flipping algorithm could have been applied 150 years ago. # This method, like RSA encryption, relies on the difficulty of factoring large numbers. Non-intuitive as it seems, it is substantially easier to test a # number to see if it is prime, than it is to find the factors of a composite (non-prime) number. Alice starts the process by generating two odd primes, # p and q, and sending Bob their product n. Since Bob will win the flip if he can factor n, Alice generates a number that # she is confident cannot be factored in a reasonable amount of time by computer. Remember, this whole "flipping" process should only take a few minutes at # most, and almost all of that time is spent exchanging numbers electronically. # Bob generates a random number less than n, squares that number, takes its n modulus, call it a, and returns a to Alice. # The random number that Bob used to generate a is its square root, but it is one of 4 square roots of a. Using the Chinese Remainder # Theorem and Euler's Criterion, Alice can compute the other 3 square roots of a, but, and this is crucial to the operation of the algorithm, she has # no idea which of the 4 square roots Bob used to generate a. # Alice randomly selects one of the roots and sends it to Bob. First Bob checks that the number Alice sent is a square root of n and is not bogus. # Two of those roots, and, of course, not the one Bob started with (which Alice doesn't know), can be used with Euclid's greatest common divisor algorithm to # factor n. So 50% of the time Bob will be able to factor Alice's original number. If Bob can do the factorization, he sends Alice p and q, # he wins, and Alice knows it. # In the event that Bob cannot factor Alice's number, he asks her to forward her choices for p and q to confirm that their product is the # number she sent him initially and that each is congruent to 3 mod 4 (another requirement on Alice's choice of primes). When everything checks out, Bob # is convinced that Alice played fair and that she won the "toss". # The following Python program is an implementation of this coin-flipping algorithm: #!/usr/local/bin/python3 from random import random, randrange from fractions import gcd from number_theory import rabin_miller_certain, pow_mod, crt_1_variable # Single application of electronic coin-flipping algorithm, pg. 340-1 Rosen, 3rd Edition P_AND_Q_MIN, P_AND_Q_RANGE = 10000000000, 1000000000 while True: p = randrange(P_AND_Q_RANGE) + P_AND_Q_MIN if p % 4 != 3: continue if rabin_miller_certain(p): break while True: q = randrange(P_AND_Q_RANGE) + P_AND_Q_MIN if q % 4 != 3: continue if rabin_miller_certain(q) and q != p: break n = p * q print('Alice chooses p = {0:d} and q = {1:d} and sends Bob pq = {2:d}.'.format(p, q, n)) x0 = randrange(n - 1) + 1 print('\nBob picks a random number < {0:d}, say {1:d}.'.format(n, x0)) a = pow_mod(x0, 2, n) print('\nBob calculates {0:d}^2 (mod {1:d}) = {2:d} and sends that number to Alice.\n'.format(x0, n, a)) a_p = a % p print('a_p = a (mod p) = {0:d} (mod {1:d}) = {2:d}'.format(a, p, a_p)) a_q = a % q print('a_q = a (mod q) = {0:d} (mod {1:d}) = {2:d}'.format(a, q, a_q)) x_1 = pow_mod(a_p, (p + 1) // 4, p) print('\nx_1 = a_p^(p + 1) / 4) = {0:d} mod({1:d})'.format(x_1, p)) x_2 = pow_mod(a_q, (q + 1) // 4, q) print('x_2 = a_q^(q + 1) / 4) = {0:d} mod({1:d})'.format(x_2, q)) def apply_crt(t_of_t): print('\nUsing Chinese Remainder Theorem to solve:') for a_t in t_of_t: print('x = {0:d} (mod {1:d})'.format(a_t[0], a_t[1])) try: result = crt_1_variable(t_of_t) print('\nx =', result) except DataError as e: print('\nDataError exception occurred:', e.value) return result solutions = [] t_of_t = ((x_1, p), (x_2, q)) solutions.append(apply_crt(t_of_t)) t_of_t = ((x_1, p), (-x_2, q)) solutions.append(apply_crt(t_of_t)) t_of_t = ((-x_1, p), (x_2, q)) solutions.append(apply_crt(t_of_t)) t_of_t = ((-x_1, p), (-x_2, q)) solutions.append(apply_crt(t_of_t)) print('\nFour incongruent solutions are:', solutions, '.') x_choice = solutions[randrange(len(solutions))] print('\nAlice randomly chooses x =', x_choice, 'and sends that number to Bob.') a_alice = pow_mod(x_choice, 2, n) print('Bob first confirms that Alice\'s solution satisfies {0:d}^2 (mod {1:d}) = {2:d} = {3:d}.'.format(x_choice, n, a_alice, a)) fac_1 = gcd(n, x0 + x_choice) print('Then Bob calculates gcd = gcd({0:d}, {1:d} + {2:d}) = {3:d}.\n\n'.format(n, x0, x_choice, fac_1)) if fac_1 == 1 or fac_1 == n: print('Alice wins because Bob cannot (easily) factor', n, '.') else: fac_2 = n // fac_1 print('Bob wins by returning the factors of', n, '=', fac_1, '*', fac_2, '.') # End of Code # Test Ouput 1 (Alice wins): # Alice chooses p = 10625745343 and q = 10414902359 and sends Bob pq = 110666100238943964137. # Bob picks a random number < 110666100238943964137, say 2930932775883526600. # Bob calculates 2930932775883526600^2 (mod 110666100238943964137) = 90834303625468593944 and sends that number to Alice. # a_p = a (mod p) = 90834303625468593944 (mod 10625745343) = 10572239851 # a_q = a (mod q) = 90834303625468593944 (mod 10414902359) = 2654235935 # x_1 = a_p^(p + 1) / 4) = 9328987522 mod(10625745343) # x_2 = a_q^(q + 1) / 4) = 9238476508 mod(10414902359) # Using Chinese Remainder Theorem to solve: # x = 9328987522 (mod 10625745343) # x = 9238476508 (mod 10414902359) # x = 101112873596480924924 # Using Chinese Remainder Theorem to solve: # x = 9328987522 (mod 10625745343) # x = -9238476508 (mod 10414902359) # x = 2930932775883526600 # Using Chinese Remainder Theorem to solve: # x = -9328987522 (mod 10625745343) # x = 9238476508 (mod 10414902359) # x = 107735167463060437537 # Using Chinese Remainder Theorem to solve: # x = -9328987522 (mod 10625745343) # x = -9238476508 (mod 10414902359) # x = 9553226642463039213 # Four incongruent solutions are: [101112873596480924924, 2930932775883526600, 107735167463060437537, 9553226642463039213] . # Alice randomly chooses x = 2930932775883526600 and sends that number to Bob. # Bob first confirms that Alice's solution satisfies 2930932775883526600^2 (mod 110666100238943964137) = 90834303625468593944 = 90834303625468593944. # Then Bob calculates gcd = gcd(110666100238943964137, 2930932775883526600 + 2930932775883526600) = 1. # Alice wins because Bob cannot (easily) factor 110666100238943964137 . # Test Output 2 (Bob wins): # Alice chooses p = 10307037959 and q = 10677961963 and sends Bob pq = 110058159277399153517. # Bob picks a random number < 110058159277399153517, say 67651847318516044956. # Bob calculates 67651847318516044956^2 (mod 110058159277399153517) = 3566685500757706995 and sends that number to Alice. # a_p = a (mod p) = 3566685500757706995 (mod 10307037959) = 920088490 # a_q = a (mod q) = 3566685500757706995 (mod 10677961963) = 3346726104 # x_1 = a_p^(p + 1) / 4) = 2583504146 mod(10307037959) # x_2 = a_q^(q + 1) / 4) = 324182031 mod(10677961963) # Using Chinese Remainder Theorem to solve: # x = 2583504146 (mod 10307037959) # x = 324182031 (mod 10677961963) # x = 48693017205594935493 # Using Chinese Remainder Theorem to solve: # x = 2583504146 (mod 10307037959) # x = -324182031 (mod 10677961963) # x = 67651847318516044956 # Using Chinese Remainder Theorem to solve: # x = -2583504146 (mod 10307037959) # x = 324182031 (mod 10677961963) # x = 42406311958883108561 # Using Chinese Remainder Theorem to solve: # x = -2583504146 (mod 10307037959) # x = -324182031 (mod 10677961963) # x = 61365142071804218024 # Four incongruent solutions are: [48693017205594935493, 67651847318516044956, 42406311958883108561, 61365142071804218024] . # Alice randomly chooses x = 48693017205594935493 and sends that number to Bob. # Bob first confirms that Alice's solution satisfies 48693017205594935493^2 (mod 110058159277399153517) = 3566685500757706995 = 3566685500757706995. # Then Bob calculates gcd = gcd(110058159277399153517, 67651847318516044956 + 48693017205594935493) = 10677961963. # Bob wins by returning the factors of 110058159277399153517 = 10677961963 * 10307037959 .