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}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s