# How to toss a coin

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 $m_h$ for head and $m_t$ for tail. These two numbers should be less than the prime number $p$ discussed in the next paragraph.

They now need to encrypt the numbers before tossing the coin. Both players agree on a large prime number $p$. 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 $p$ decided, each of the players chooses an encryption-decryption key, which is a pair of positive integers $x_0$ and $x_1$ such that

$x_0 \cdot x_1 \equiv 1 \ (\text{mod} \ p-1)$,

meaning that $x_0 \cdot x_1=1+(p-1) \cdot k$ for some integer $k$.

Each of the players chooses such a pair of numbers. In terms of notation, Andy chooses $a_0$ and $a_1$. Becky chooses $b_0$ and $b_1$. Each player chooses the number pair independently and keeps it secret from the other player.

The number with the $0$-subscript is the encryption key and the number with the $1$-subscript is the decryption key. The following are the encryption functions, expressed in congruence modulo $p$, for Andy and Becky, respectively.

$f_a(m) \equiv m^{a_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}$

$f_b(m) \equiv m^{b_0} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}$

For example, if Andy wants to encrypt the number $m$, he raises $m$ to the power of $a_0$ and looks for the remainder upon division by $p$. The remainder will be denoted by $f_a(m)$. The function $f_b(m)$ works similarly for Becky.

The following are the decryption functions, expressed in congruence modulo $p$, for Andy and Becky, respectively.

$g_a(c) \equiv c^{a_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Andy}$

$g_b(c) \equiv c^{b_1} \ (\text{mod} \ p) \ \ \ \ \ \ \ \text{Becky}$

For example, if Andy wants to decrypt the number $c=f_a(m)$, he raises $c$ to the power of $a_1$ and looks for the remainder upon division by $p$. The remainder will be denoted by $g_a(m)$, which will be the original number $m$. 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 $g_b(m)$ works similarly for Becky.

___________________________________________________________________________________________________________________

A Numerical Example

For illustration, we use a small prime number. We use $p=7919$. 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.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \end{bmatrix}$

For this illustration, Andy chooses $a_0=\text{47}$ and $a_1=\text{52,899}$ by letting $k=\text{314}$ in the equation below. Becky chooses $b_0=\text{71}$ and $b_1=\text{26,319}$ by letting $k=\text{236}$ in the following equation.

$x_0 \cdot x_1=1+7918 \cdot k$

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:

$2500^{47} \equiv 7518=f_a(2500) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

$5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

The encrypted numbers and the original numbers are displayed in the following table.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Head}&\text{ }&\text{Tail} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Original}&\text{ }&\text{2,500}&\text{ }&\text{5,000} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Andy}&\text{ }&\text{7,518}&\text{ }&\text{698} \end{bmatrix}$

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 $7518$. Becky then encrypted the number $7518$ using her key.

$7518^{71} \equiv 1341=f_b(7518) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (3)$

Becky passes the encrypted number $1341$ (her selection) and $698$ (Andy’s selection) back to Andy. The following table lists out the numbers received by Andy.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \end{bmatrix}$

Andy decrypts his number $698$ and gets back $2500$, which is tail. He also decrypts $1341$ and obtains $223$, which he passes back to Becky.

$698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

$1341^{52899} \equiv 223=g_a(1341) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (5)$

The following summarizes the results up to this point.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \end{bmatrix}$

Once Becky gets the decrypted number $223$ from Andy, she decrypts it using her own key to obtain $2500$, which is a head.

$223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)$

The following table summarizes the results of the coin toss.

$\displaystyle \begin{bmatrix} \text{ }&\text{ }&\text{Andy}&\text{ }&\text{Becky} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Becky's selection}&\text{ }&\text{698}&\text{ }&\text{7,518} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Encrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{1,341} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Andy}&\text{ }&\text{5,000}&\text{ }&\text{223} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Decrypted by Becky}&\text{ }&\text{ }&\text{ }&\text{2,500} \\ \text{ }&\text{ }&\text{ }&\text{ }&\text{ } \\ \text{Results of Coin Toss}&\text{ }&\text{5,000}&\text{ }&\text{2,500} \end{bmatrix}$

___________________________________________________________________________________________________________________

Numerical Calculation

We now show some of the calculations involved in the above encryption and decryption. We show three calculations.

$5000^{47} \equiv 698=f_a(5000) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (2)$

$698^{52899} \equiv 5000=g_a(698) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (4)$

$223^{26319} \equiv 2500=g_b(223) \ (\text{mod} \ 7919) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (6)$

Even with the small prime number $p=7919$, the calculation is not done directly. For example, unless special software is used, $f_a(5000)$ is not found by calculating $5000^{47}$ and then finding the remainder upon division by $7919$. The following demonstrates a “divide and conquer” approach for the calculation for $(2)$ where in each step the exponent is reduced by half.

\displaystyle \begin{aligned} 5000^{47}&\equiv (5000^2)^{23} \cdot 5000 \ (\text{mod} \ 7919) \\&\text{ } \\&=7636^{23} \cdot 5000 \equiv (7636^2)^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 7636 \cdot 5000 \\&\text{ } \\&\equiv 899^{11} \cdot 2501 \equiv (899^2)^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 899 \cdot 2501 \\&\text{ } \\&\equiv 463^5 \cdot 7322 \equiv (463^2)^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 463 \cdot 7322 \\&\text{ } \\&\equiv 556^2 \cdot 754 \\&\text{ } \\&\equiv 295 \cdot 754 \\&\text{ } \\&\equiv 698 \ (\text{mod} \ 7919) \end{aligned}

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 $5000^2$ by $7919$ to obtain the remainder of $7636$. The number $698$ in the last step is the remainder when $295 \cdot 754$ is divided by $7919$. These calculations are tedious if done by hand and should be done by computer.

The calculation for $(4)$ is that $698^{52899} \equiv 5000 \ (\text{mod} \ 7919)$. In other word, decrypting the encrypted number of $698$ recovers the original number of $5000$. This calculation can be shortened by using Fermat’s Little Theorem, which implies that $698^{7919-1} \equiv 1 \ (\text{mod} \ 7919)$. Thus we have:

$698^{47508} \equiv 698^{6 \cdot 7918} \equiv 1 \ (\text{mod} \ 7919)$

So we can reduce $47508$ from the exponent $52899$, leaving the exponent $5391$. We have:

$698^{52899} \equiv 698^{47508} \cdot 698^{5391} \equiv 1 \cdot 698^{5391} \ (\text{mod} \ 7919)$

The following uses the “divide and conquer” approach to compute $698^{5391}$ modulo $7919$.

\displaystyle \begin{aligned} 698^{5391}&\equiv (698^2)^{2695} \cdot 698 \ (\text{mod} \ 7919) \\&\text{ } \\&=4145^{2695} \cdot 698 \equiv (4145^2)^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 4145 \cdot 698 \\&\text{ } \\&\equiv 4714^{1347} \cdot 2775 \equiv (4714^2)^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 4714 \cdot 2775 \\&\text{ } \\&\equiv 1082^{673} \cdot 7081 \equiv (1082^2)^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 1082 \cdot 7081 \\&\text{ } \\&\equiv 6631^{336} \cdot 3969 \equiv (6631^2)^{168} \cdot 3969 \\&\text{ } \\&\equiv 3873^{168} \cdot 3969 \equiv (3873^2)^{84} \cdot 3969 \\&\text{ } \\&\equiv 1543^{84} \cdot 3969 \equiv (1543^2)^{42} \cdot 3969 \\&\text{ } \\&\equiv 5149^{42} \cdot 3969 \equiv (5149^2)^{21} \cdot 3969\\&\text{ } \\&\equiv 7308^{21} \cdot 3969 \equiv (7308^2)^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 7308 \cdot 3969 \\&\text{ } \\&\equiv 1128^{10} \cdot 6074 \equiv (1128^2)^{5} \cdot 6074\\&\text{ } \\&\equiv 5344^5 \cdot 6074 \equiv (5344^2)^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv 2422^2 \cdot 5344 \cdot 6074 \\&\text{ } \\&\equiv2422^2 \cdot 7394 \\&\text{ } \\&\equiv 6024 \cdot 7394 \\&\text{ } \\&\equiv 5000 \ (\text{mod} \ 7919) \end{aligned}

The calculation for $(6)$ is $223^{26319} \equiv 2500 \ (\text{mod} \ 7919)$. We can also get an assist from the Fermat’s Little Theorem. In this particular case, $223^{7918} \equiv 1 \ (\text{mod} \ 7919)$. With $26319=3 \cdot 7918+2565$, we only need to calculate $223^{2565} \ (\text{mod} \ 7919)$, which is done below.

\displaystyle \begin{aligned} 223^{2565}&\equiv (223^2)^{1282} \cdot 223 \ (\text{mod} \ 7919) \\&\text{ } \\&=2215^{1282} \cdot 223 \equiv (2215^2)^{641} \cdot 223 \\&\text{ } \\&\equiv 4364^{641} \cdot 223 \equiv (4364^2)^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 4364 \cdot 223 \\&\text{ } \\&\equiv 7220^{320} \cdot 7054 \equiv (7220^2)^{160} \cdot 7054 \\&\text{ } \\&\equiv 5542^{160} \cdot 7054 \equiv (5442^2)^{80} \cdot 7054 \\&\text{ } \\&\equiv 3882^{80} \cdot 7054 \equiv (3882^2)^{40} \cdot 7054 \\&\text{ } \\&\equiv 67^{40} \cdot 7054 \equiv (67^2)^{20} \cdot 7054 \\&\text{ } \\&\equiv 4489^{20} \cdot 7054 \equiv (4489^2)^{10} \cdot 7054\\&\text{ } \\&\equiv 5185^{10} \cdot 7054 \equiv (5185^2)^{5} \cdot 7054 \\&\text{ } \\&\equiv 7139^{5} \cdot 7054 \equiv (7139^2)^{2} \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 7139 \cdot 7054 \\&\text{ } \\&\equiv 6556^2 \cdot 1585 \\&\text{ } \\&\equiv 4723 \cdot 1585 \\&\text{ } \\&\equiv 2500 \ (\text{mod} \ 7919) \end{aligned}

___________________________________________________________________________________________________________________

$\copyright \ 2013 \text{ by Dan Ma}$