In this post, we demonstrate how to simulate a random coin toss using a cryptographic algorithm that was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm). Tossing a coin using a cryptographic algorithm is an example of a game of mental poker.
The term mental poker refers to the game of poker played over long distance that has a mechanism for ensuring a fair game without the need for a trusted third party. Mental poker can also refer to other cryptographic games played over long distance without the need for a trusted third party (e.g. tossing a coin over long distance).
Setting the Algorithm
A full discussion of the algorithm used here can be found in the previous post Fermat’s Little Theorem and Mental Poker.
Andy and Becky are in different locations and they would like to simulate a random coin toss. First they need to agree on two positive integers that are to represent head and tail, say for head and for tail. These two numbers should be less than the prime number discussed in the next paragraph.
They now need to encrypt the numbers before tossing the coin. Both players agree on a large prime number . If the goal of preventing or minimizing cheating is important, the players should choose a prime number that is as large as feasible computationally speaking.
With the prime number decided, each of the players chooses an encryption-decryption key, which is a pair of positive integers and such that
meaning that for some integer .
Each of the players chooses such a pair of numbers. In terms of notation, Andy chooses and . Becky chooses and . Each player chooses the number pair independently and keeps it secret from the other player.
The number with the -subscript is the encryption key and the number with the -subscript is the decryption key. The following are the encryption functions, expressed in congruence modulo , for Andy and Becky, respectively.
For example, if Andy wants to encrypt the number , he raises to the power of and looks for the remainder upon division by . The remainder will be denoted by . The function works similarly for Becky.
The following are the decryption functions, expressed in congruence modulo , for Andy and Becky, respectively.
For example, if Andy wants to decrypt the number , he raises to the power of and looks for the remainder upon division by . The remainder will be denoted by , which will be the original number . The proof of this fact is based on the Fermat’s Little Theorem (see the previous post Fermat’s Little Theorem and Mental Poker).
The function works similarly for Becky.
A Numerical Example
For illustration, we use a small prime number. We use . We emphasize that this is just for illustration. In an application where the chance for cheating is to be minimized, a large prime number should be used.
Andy and Becky use the following assignment for Head and Tail.
For this illustration, Andy chooses and by letting in the equation below. Becky chooses and by letting in the following equation.
Andy and Becky choose these keys independently and they keep them secret without letting the other person know. Andy encrypts both the head and tail numbers as follows:
The encrypted numbers and the original numbers are displayed in the following table.
Of course, the above table is kept secret from Becky. However, the encrypted numbers (just the encrypted numbers) are sent to Becky for random selection.
Becky selects one of the encrypted numbers for herself (perhaps thru a coin toss). Then the other encrypted number is the choice for Andy. Suppose Becky selects . Becky then encrypted the number using her key.
Becky passes the encrypted number (her selection) and (Andy’s selection) back to Andy. The following table lists out the numbers received by Andy.
Andy decrypts his number and gets back , which is tail. He also decrypts and obtains , which he passes back to Becky.
The following summarizes the results up to this point.
Once Becky gets the decrypted number from Andy, she decrypts it using her own key to obtain , which is a head.
The following table summarizes the results of the coin toss.
We now show some of the calculations involved in the above encryption and decryption. We show three calculations.
Even with the small prime number , the calculation is not done directly. For example, unless special software is used, is not found by calculating and then finding the remainder upon division by . The following demonstrates a “divide and conquer” approach for the calculation for where in each step the exponent is reduced by half.
In each step in the above calculation, we use the division algorithm to obtain the remainder. For example, to go from the first line to the second line, divide by to obtain the remainder of . The number in the last step is the remainder when is divided by . These calculations are tedious if done by hand and should be done by computer.
The calculation for is that . In other word, decrypting the encrypted number of recovers the original number of . This calculation can be shortened by using Fermat’s Little Theorem, which implies that . Thus we have:
So we can reduce from the exponent , leaving the exponent . We have:
The following uses the “divide and conquer” approach to compute modulo .
The calculation for is . We can also get an assist from the Fermat’s Little Theorem. In this particular case, . With , we only need to calculate , which is done below.