# 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 Ruby program is an implementation of this coin-flipping algorithm: #! /usr/bin/ruby require '~/ruby/math_libraries/number_theory' # Single application of electronic coin-flipping algorithm, pg. 340-1 Rosen, 3rd Edition P_AND_Q_MIN = 10000000000 P_AND_Q_RANGE = 1000000000 p, q = nil, nil loop do p = rand(P_AND_Q_RANGE) + P_AND_Q_MIN next if p % 4 != 3 break if rabin_miller_certain(p) end loop do q = rand(P_AND_Q_RANGE) + P_AND_Q_MIN next if q % 4 != 3 break if rabin_miller_certain(q) and q != p end n = p * q puts "Alice chooses p = #{p} and q = #{q} and sends Bob pq = #{n}." x0 = rand(n - 1) + 1 puts "\nBob picks a random number < #{n}, say #{x0}." a = pow_mod(x0, 2, n) puts "Bob calculates #{x0}^2 (mod #{n}) = #{a} and sends that number to Alice.\n\n" a_p = a % p puts "a_p = a (mod p) = #{a} (mod #{p}) = #{a_p}" a_q = a % q puts "a_q = a (mod q) = #{a} (mod #{q}) = #{a_q}" x_1 = pow_mod(a_p, (p + 1) / 4, p) puts "\nx_1 = a_p^(p + 1) / 4) = #{x_1} mod(#{p})" x_2 = pow_mod(a_q, (q + 1) / 4, q) puts "x_2 = a_q^(q + 1) / 4) = #{x_2} mod(#{q})" solutions = [] def apply_crt(a_of_a) result = nil puts "\nUsing Chinese Remainder Theorem to solve:" a_of_a.each do |a| puts "x = #{a[0]} (mod #{a[1]})" end begin result = crt_1_variable(a_of_a) puts "\nx = #{result}" rescue RuntimeError => message puts message end result end a_of_a = [[x_1, p], [x_2, q]] solutions << apply_crt(a_of_a) a_of_a = [[x_1, p], [-x_2, q]] solutions << apply_crt(a_of_a) a_of_a = [[-x_1, p], [x_2, q]] solutions << apply_crt(a_of_a) a_of_a = [[-x_1, p], [-x_2, q]] solutions << apply_crt(a_of_a) puts "\nFour incongruent solutions are #{solutions}." x_choice = solutions[rand(solutions.length)] puts "\nAlice randomly chooses x = #{x_choice} and sends that number to Bob." a_alice = pow_mod(x_choice, 2, n) puts "\nBob first confirms that Alice's solution satisfies #{x_choice}^2 (mod #{n}) = #{a_alice} = #{a}." fac_1 = gcd(n, x0 + x_choice) # fac_2 = gcd(n, x0 + n - x_choice) puts "Then Bob calculates gcd = gcd(#{n}, #{x0} + #{x_choice}) = #{fac_1}.\n\n" if fac_1 == 1 or fac_1 == n puts "Alice wins because Bob cannot (easily) factor #{n}." else fac_2 = n / fac_1 puts "Bob wins by returning the factors of #{n} = #{fac_1} * #{fac_2}." end # End of Code # Test Ouput 1 (Alice wins): # Alice chooses p = 10525607167 and q = 10969572071 and sends Bob pq = 115461406409440632857. # Bob picks a random number < 115461406409440632857, say 66392732473749671455. # Bob calculates 66392732473749671455^2 (mod 115461406409440632857) = 59728962320512036916 and sends that number to Alice. # a_p = a (mod p) = 59728962320512036916 (mod 10525607167) = 9080636939 # a_q = a (mod q) = 59728962320512036916 (mod 10969572071) = 1966551516 # x_1 = a_p^(p + 1) / 4) = 2288945383 mod(10525607167) # x_2 = a_q^(q + 1) / 4) = 6798599059 mod(10969572071) # Using Chinese Remainder Theorem to solve: # x = 2288945383 (mod 10525607167) # x = 6798599059 (mod 10969572071) # x = 66392732473749671455 # Using Chinese Remainder Theorem to solve: # x = 2288945383 (mod 10525607167) # x = -6798599059 (mod 10969572071) # x = 106671869176661610989 # Using Chinese Remainder Theorem to solve: # x = -2288945383 (mod 10525607167) # x = 6798599059 (mod 10969572071) # x = 8789537232779021868 # Using Chinese Remainder Theorem to solve: # x = -2288945383 (mod 10525607167) # x = -6798599059 (mod 10969572071) # x = 49068673935690961402 # Four incongruent solutions are [66392732473749671455, 106671869176661610989, 8789537232779021868, 49068673935690961402]. # Alice randomly chooses x = 49068673935690961402 and sends that number to Bob. # Bob first confirms that Alice's solution satisfies 49068673935690961402^2 (mod 115461406409440632857) = 59728962320512036916 = 59728962320512036916. # Then Bob calculates gcd = gcd(115461406409440632857, 66392732473749671455 + 49068673935690961402) = 115461406409440632857. # Alice wins because Bob cannot (easily) factor 115461406409440632857. # Test Output 2 (Bob wins): # Alice chooses p = 10992895699 and q = 10939450703 and sends Bob pq = 120256240582431226397. # Bob picks a random number < 120256240582431226397, say 117879081866275307169. # Bob calculates 117879081866275307169^2 (mod 120256240582431226397) = 116469475688532673740 and sends that number to Alice. # a_p = a (mod p) = 116469475688532673740 (mod 10992895699) = 1319400212 # a_q = a (mod q) = 116469475688532673740 (mod 10939450703) = 5147255247 # x_1 = a_p^(p + 1) / 4) = 3281440073 mod(10992895699) # x_2 = a_q^(q + 1) / 4) = 2598514182 mod(10939450703) # Using Chinese Remainder Theorem to solve: # x = 3281440073 (mod 10992895699) # x = 2598514182 (mod 10939450703) # x = 117879081866275307169 # Using Chinese Remainder Theorem to solve: # x = 3281440073 (mod 10992895699) # x = -2598514182 (mod 10939450703) # x = 61028244257246182587 # Using Chinese Remainder Theorem to solve: # x = -3281440073 (mod 10992895699) # x = 2598514182 (mod 10939450703) # x = 59227996325185043810 # Using Chinese Remainder Theorem to solve: # x = -3281440073 (mod 10992895699) # x = -2598514182 (mod 10939450703) # x = 2377158716155919228 # Four incongruent solutions are [117879081866275307169, 61028244257246182587, 59227996325185043810, 2377158716155919228]. # Alice randomly chooses x = 59227996325185043810 and sends that number to Bob. # Bob first confirms that Alice's solution satisfies 59227996325185043810^2 (mod 120256240582431226397) = 116469475688532673740 = 116469475688532673740. # Then Bob calculates gcd = gcd(120256240582431226397, 117879081866275307169 + 59227996325185043810) = 10992895699. # Bob wins by returning the factors of 120256240582431226397 = 10992895699 * 10939450703.