Coin Flipping at a Distance\302\251 2007 by Mike May, S.J., Saint Louis University - maymk@slu.eduThis worksheet demonstrates a method where cryptographic techniques can be used to flip a coin at a distance. In particular it allows the person who calls to coin toss to have confidence in the honesty of the other person\342\200\231s reporting whether or not the call was correct. restart;More precisely, we want to have a method where Alice and Bob communicate, Alice asks Bob a question, Bob has a 50% chance of getting the question correct, and Bob leaves the discussion without a concern that Alice cheated.The method used in the book uses modular square roots. This method uses the fact that finding a square root mod p is very easy if p is congruent to 3 mod 4. With the Chinese remainder theorem it is easy to find a square root mod n when n is a product of primes congruent to 3 mod 4 if we know how to factor n.On the other hand if n is a product of two primes, finding a square root mod n is equivalent to factoring n.Bob starts with a prime size and then finds two primes of the correct size with each prime congruent to 3 mod 4.Bob compute n=p*q. Bob sends this number to Alice.PrimeSize := 25:
test1 := 1:
while (test1=1) do
p := nextprime(rand(10^PrimeSize)()):
test1 := p mod 4:
end do:
test1 := 1:
while (test1=1) do
q := nextprime(rand(10^PrimeSize)()):
test1 := q mod 4:
end do:
"p" = p;
"q" = q;
n := p*q;
p := 3775405218338988823656467;
q := 3548156839678504695583939;
n := p*q;Alice then picks a random number x and computes y=x^2. She sends Bob the value of y and asks for the value of of x. (The value of -x is also considered correct.)x := rand(n)();
y := Power(x,2) mod n;x := 2880024573171479426972681966277037706864972895256;
y := Power(x,2) mod n;For each of the two primes, Bob computes the value of y, and finds a square root. He then uses the Chinese Remainder theorem to compute the four square roots of y mod n.Note that n=r1+r4=r2+r3.a := numtheory[msqrt](y,p);
b := numtheory[msqrt](y,q);
r1 := chrem([a,b], [p,q]);
r2 := chrem([a,-b], [p,q]);
r3 := chrem([-a,b], [p,q]);
r4 := chrem([-a,-b], [p,q]);
"r1+r4" = r1+r4;
"r2+r3" = r2+r3;Bob now chooses a square root. If he chooses r1 or r4 he has chose correctly and wins.If on the other hand Bob chooses incorrectly, say he chooses r2, then Alice uses the fact that x-r2 will have a nontrivial common factor with n to find a factorization of n.test2 := x-r2;
fact1 := igcd(n,test2);
fact2 := n/fact1;For the flip to be fair, Bob must use primes large enough that he is convinced Alice cannot factor n.Exercise:
1) Using 40 digit primes, use the bulletin board to flip a coin with someone in the class.Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic=