Fermat’s Little Theorem and Mental Poker

In this post we demonstrate another use of the Fermat’s Little Theorem.

How can two people play poker when they are not sitting face to face from each other? If the game of poker is played over long distance (e.g. via a telephone line or some electronic communication channel), there will be a need to ensure a fair game. For example, the two players must use the same deck of cards (ensuring that there will be no duplicates). The deck of cards will need to be well shuffled. Each player cannot see the cards of the other player. One solution is to use a trusted third party to do the shuffling and selecting of cards. If a third party cannot be found or it is felt that the third party cannot be trusted to be fair, then one should consider the cryptographic solution described in this post. This soultion was proposed by Rivest, Shamir and Adlemen in 1982 (the creators of the RSA algorithm).

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 Up the Deck of Cards

Let’s say that the players are Andy and Becky. Since they are not using a physical deck of cards, they need to represent the cards by numbers. Let’s say that they agree to number the cards as follows:

    \displaystyle \heartsuit 2=1020 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 2=2020  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 2=3020 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 2=4020

    \displaystyle \heartsuit 3=1030 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 3=2030  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 3=3030 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 3=4030

    \displaystyle \heartsuit 4=1040 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit 4=2040  \ \ \ \ \ \ \ \ \ \ \ \spadesuit 4=3040 \ \ \ \ \ \ \ \ \ \ \ \clubsuit 4=4040

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

      \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \cdots

    \displaystyle \heartsuit Q=1120 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit Q=2120  \ \ \ \ \ \ \ \ \ \ \spadesuit Q=3120 \ \ \ \ \ \ \ \ \clubsuit Q=4120

    \displaystyle \heartsuit K=1130 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit K=2130  \ \ \ \ \ \ \ \ \ \spadesuit K=3130 \ \ \ \ \ \ \ \ \clubsuit K=4130

    \displaystyle \heartsuit A=1140 \ \ \ \ \ \ \ \ \ \ \ \diamondsuit A=2140  \ \ \ \ \ \ \ \ \ \ \spadesuit A=3140 \ \ \ \ \ \ \ \ \ \clubsuit A=4140

___________________________________________________________________________________________________________________

Setting Up the Pad Locks

The card numbers need to be encrypted before they can be passed between the two players. Here’s how it works.

Both players agree to choose a large prime number p. This number p needs to be larger than all the card numbers and the encrypted card numbers. The larger p is, the harder it will be for any one of the players to cheat.

Now each of the players needs to choose an encryption-decryption key (a padlock) that the player keeps secret. Let’s start with Andy. He chooses a pair of positive numbers a_0 and a_1 such that the following holds:

    a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1)

Equivalently the pair a_0 and a_1 satisfies the equation a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. The number a_0 will be used for locking (encryption) and the number a_1 will be used for unlocking (decryption). Andy will also keep this pair of numbers away from Becky.

How will Andy use this padlock? Suppose that m is a number to be encrypted. To encrypt the number, Andy raises m to the power of a_0 and then finds the remainder upon division by p. He will call the remainder f_a(m). Using congruence notation, the following is the encryption function:

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

If Andy needs to recover m from the encrypted card number c=f_a(m), all he has to do is to raise c to the power of a_1 and then find the remainder upon division by p. Call the remainder g_a(c), which will be the original card number m. Using congruence notation, the following is the decryption function:

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

The decrypted number is the original number. Thus we have g_a(c)=m. A proof of this relies on the Fermat’s Little Theorem (see proof).

Because the numbers involved are usually large, no one will try to raise m to the power of a_0 and then divides by p to find the remainder. Instead, Andy should use special software. If software is not available, Andy can rely on congruence modulo arithmetic, which should also be done by a computer. See below for a demonstration of the congruence modulo arithmetic.

The other player Becky also needs a padlock. Specifically, she chooses a pair of numbers b_0 and b_1 that satisfy the following:

    b_0 \cdot b_1 \equiv 1 \ (\text{mod} \ p-1)

This pair of number serves the same purpose as the pair that belongs to Andy. Of course, b_0 and b_1 need to be kept secret from Andy. The following shows the encryption and decryption functions for Becky’s padlock.

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

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

___________________________________________________________________________________________________________________

How to Play the Game

Suppose the card numbers are m_1, m_2, m_3, \cdots, m_{52} (the above is one example of card number assigment). Andy then encrypts the card number using his encryption function f_a(m). The following lists the encrypted card numbers.

    \displaystyle f_a(m_1),\ f_a(m_2), \ f_a(m_3),\cdots,f_a(m_{52})

Andy then passes these encrypted card numbers to Becky. She shuffles the encrypted deck thorughly. She then chooses a 5-card hand for Andy. Becky then chooses another 5-card hand for herself. Becky uses her key to encrypt her 5-card hand. Becky passes both 5-card hands to Andy. The following shows what Becky passes to Andy.

    Andy’s 5-card hand: f_a(m_i) \equiv m_i^{a_0} \ (\text{mod} \ p) for 5 distinct values of i.

    Becky’s 5-card hand: f_b(f_a(m_j)) \equiv f_a(m_j)^{b_0} \ (\text{mod} \ p) for 5 distinct values of j.

Once Andy gets the two 5-card hands, he decrypts his own 5-card hand and gets back the original card numbers. He also decrypts Becky’s 5-card hand and passes that back to Becky.

    Andy’s 5-card hand: g_a(f_a(m_i)) \equiv (m_i^{a_0})^{a_1} \equiv m_i \ (\text{mod} \ p)

    Becky’s 5-card hand: g_a(f_b(f_a(m_j))) \equiv (f_a(m_j)^{b_0})^{a_1}=(f_a(m_j)^{a_1})^{b_0} \equiv m_j^{b_0} \ (\text{mod} \ p), which Andy passes back to Becky.

Once Becky’s recieves her 5-card hand back from Andy, she decrypts the cards immediately and gets back the original card numbers.

    Becky’s 5-card hand: g_b(m_j^{b_0}) \equiv (m_j^{b_0})^{b_1} \equiv m_j \ (\text{mod} \ p)

Now each of the players has a 5-card hand that is only known to himself or herself. If they need to select new cards from the deck, they can follow the same back-and-forth procedures of encrypting and decrypting.

How fair is the poker game played in this manner? How secure is the game? It is very fair and secure if the players follow the rules and do not cheat. It is obviously possible to cheat. When Andy passes the 52 encrypted card numbers to Becky, Becky certainly can try to break Andy’s lock by figuring out Andy’s a_0. When Becky passes her encrypted cards to Andy, he can try to figure out Becky’s b_0. For that to happen, the player who wants to cheat will need to have enormous amount of computational resources at the ready. Thus the prime number p should be large enough to make cheating an intractable problem. On the other hand, even when the prime number is of a moderate size, there has to be a fair amount of computational resources in order to play the game efficiently, with all the encrypting and decrypting that have to be done.


___________________________________________________________________________________________________________________

Fermat’s Little Theorem

We now use Fermat’s Little Theorem to show that the encryption-decryption key works correctly and accurately. We show the following:

    (m^{a_0})^{a_1} \equiv m \ (\text{mod} \ p) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)

For the descriptions of the numbers m, p, a_0 and a_1, see the above section Setting Up the Padlocks. First we state the Fermat’s Little Theorem.

Fermat’s Little Theorem
Let q be a prime number. Then for any integer a, a^q-a is an integer multiple of q (or q divides a^q-a). Using congruence notation, the theorem can be expressed as:

    a^q \equiv a \ (\text{mod} \ q)

If the integer a is not divisible by q, then we can divide out a and the theorem can be expressed as:

    a^{q-1} \equiv 1 \ (\text{mod} \ q)

For a proof and a fuller discussion of Fermat’s little theorem, see this post.

We now prove the property (1). Recall that the pair of positive integers a_0 and a_1 are keys to lock and unlock a number m. They are chosen such that a_0 \cdot a_1 \equiv 1 \ (\text{mod} \ p-1), or equivalently a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. This integer k must be positive since a_0 and a_1 are both positive.

In the derivation below, we repeated use the fact that m^p \equiv m \ (\text{mod} \ p) (applying the Fermat’s Little Theorem).

    \displaystyle \begin{aligned} m&\equiv m^p \ (\text{mod} \ p)=m \cdot m^{p-1} \\&\equiv m^p \cdot m^{p-1} \ (\text{mod} \ p)=m \cdot m^{2(p-1)} \\&\equiv m^p \cdot m^{2(p-1)} \ (\text{mod} \ p)=m \cdot m^{3(p-1)} \\&\cdots \\&\cdots \\&\cdots \\&\equiv m^p \cdot m^{(k-1)(p-1)} \ (\text{mod} \ p)=m \cdot m^{k(p-1)} \\&=m \cdot m^{k(p-1)} \equiv m^{a_0 \cdot a_1} \ (\text{mod} \ p) \end{aligned}


___________________________________________________________________________________________________________________

Example of Congruence Calculation

For a numerical example, we use a small prime number p=55,049. Though a small prime number, it is large enough to make the illustration meaningful. Andy chooses a_0 \cdot a_1 such that a_0 \cdot a_1=1+(p-1) \cdot k for some integer k. Andy decides to use k=3817, leading to a_0=2,657 and a_1=79,081.

As illustration of how the calculation is done, let m=1020 (the number for \heartsuit 2 as indicated above).

To decrypt this card, Andy needs to raise 1020 to the 2657th power and then find the remainder upon division by p=50,049. This is the definition for 1010200^{269} modulo p. But the calculation is not easy to do directly without special software. We present here a “divide and conquer” approach that use the division algorithm in each step to reduce the exponent by half.

To start, note that 1020^2 \equiv 49518 \ (\text{mod} \ 55049), meaning that the remainder is 49518 when 1020^2 is divided by 55049. In the following series of steps, a congruence calculation is performed in each step (using the division algorithm) to reduce the exponent by half.

    \displaystyle \begin{aligned} 1020^{2657}&\equiv (1020^2)^{1328} \cdot 1020 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 49518^{1328} \cdot 1020 \equiv (49518^2)^{664} \cdot 1020  \\&\text{ } \\& \equiv 39766^{664} \cdot 1020 \equiv (39766^2)^{332} \cdot 1020 \\&\text{ } \\& \equiv 52231^{332} \cdot 1020 \equiv (52231^2)^{166} \cdot 1020 \\&\text{ } \\&\equiv 14068^{166} \cdot 1020 \equiv (14068^2)^{83} \cdot 1020 \\&\text{ } \\& \equiv 7469^{83} \cdot 1020 \equiv (7469^2)^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\& \equiv 21324^{41} \cdot 7469 \cdot 1020 \\&\text{ } \\&\equiv 21324^{41} \cdot 21618 \equiv (21324^2)^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\&  \equiv 8236^{20} \cdot 21324 \cdot 21618 \\&\text{ } \\& \equiv 8236^{20} \cdot 1906 \equiv (8236^2)^{10} \cdot 1906 \\&\text{ } \\& \equiv 11328^{10} \cdot 1906 \equiv (11328^2)^{5} \cdot 1906 \\&\text{ } \\& \equiv 4365^5 \cdot 1906 \equiv (4365^2)^2 \cdot 4365 \cdot 1906 \\&\text{ } \\& \equiv 6271^2 \cdot 4365 \cdot 1906 \\&\text{ } \\&\equiv 6271^2 \cdot 7291  \\&\text{ } \\&\equiv 20455 \cdot 7291 \\&\text{ } \\&\equiv 9664 \ (\text{mod} \ 55049)  \end{aligned}

Thus the card number 1020 is encrypted as 9664. To recover the original card number from this encrypted number, Andy needs to raise 9664 to the power of a_1=79081. Here, we get an assist from Fermat’s Little Theorem in addition to the ‘divide and conquer” congruence arithmetic that is used above.

According to Fermat’s Little Theorem, 9664^{55048} \equiv 1 \ (\text{mod} \ 55049). Thus we have

    9664^{79081} \equiv 9664^{55048} \cdot 9664^{24033} \equiv 9664^{24033} \ (\text{mod} \ 55049)

With the help of Fermat’s Little Theorem, the exponent 79081 has come down to 24033. In the rest of the way, the “divide and conquer” approach is used.

    \displaystyle \begin{aligned} 9664^{24033}&\equiv (9664^2)^{12016} \cdot 9664 \ (\text{mod} \ 55049) \\&\text{ } \\&\equiv 29782^{12016} \cdot 9664 \equiv (29782^2)^{6008} \cdot 9664 \\&\text{ } \\&\equiv 8237^{6008} \cdot 9664 \equiv (8237^2)^{3004} \cdot 9664 \\&\text{ } \\&\equiv 27801^{3004} \cdot 9664 \equiv (27801^2)^{1502} \cdot 9664 \\&\text{ } \\&\equiv 7641^{1502} \cdot 9664 \equiv (7641^2)^{751} \cdot 9664 \\&\text{ } \\&\equiv  32941^{751} \cdot 9664 \equiv (32941^2)^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 32941 \cdot 9664 \\&\text{ } \\&\equiv 38642^{375} \cdot 48506 \equiv (38642^2)^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 38642 \cdot 48506 \\&\text{ } \\&\equiv 39^{187} \cdot 5451 \equiv (39^2)^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 39 \cdot 5451 \\&\text{ } \\&\equiv 1521^{93} \cdot 47442 \equiv (1521^2)^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv 1383^{46} \cdot 1521 \cdot 47442 \\&\text{ } \\&\equiv  1383^{46} \cdot 45092 \equiv (1383^2)^{23} \cdot 45092 \\&\text{ } \\&\equiv 41023^{23} \cdot 45092 \equiv (41023^2)^{11} \cdot 41023 \cdot 45092 \\&\text{ } \\&\equiv 38599^{11} \cdot 41023 \cdot 45092  \\&\text{ } \\&\equiv 38599^{11} \cdot 52618 \equiv (38599^2)^{5} \cdot 38599 \cdot 52618 \\&\text{ } \\&\equiv 36665^5 \cdot 38599 \cdot 52618  \\&\text{ } \\&\equiv 36665^5 \cdot 24376 \equiv (36665^2)^{2} \cdot 36665 \cdot 24376  \\&\text{ } \\&\equiv 25645^2 \cdot 36665 \cdot 24376  \\&\text{ } \\&\equiv 25645^2 \cdot 25525  \\&\text{ } \\&\equiv 50671 \cdot 25525  \\&\text{ } \\&\equiv 1020 \ (\text{mod} \ 55049)  \end{aligned}

In each step of the above calculation, the division algorithm is applied to reduce the exponent by half. For example, to go from the first line to the second line, 9664^2 is divided by 55049 to obtain the remainder 29782, i.e. 9664^2 \equiv 29782 \ (\text{mod} \ 55049). The number 1020 in the last line is the remainder when 50671 \cdot 25525 is divided by 55049.

___________________________________________________________________________________________________________________

\copyright \ 2013 \text{ by Dan Ma}

Advertisements