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:
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 . This number needs to be larger than all the card numbers and the encrypted card numbers. The larger 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 and such that the following holds:
Equivalently the pair and satisfies the equation for some integer . The number will be used for locking (encryption) and the number 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 is a number to be encrypted. To encrypt the number, Andy raises to the power of and then finds the remainder upon division by . He will call the remainder . Using congruence notation, the following is the encryption function:
If Andy needs to recover from the encrypted card number , all he has to do is to raise to the power of and then find the remainder upon division by . Call the remainder , which will be the original card number . Using congruence notation, the following is the decryption function:
The decrypted number is the original number. Thus we have . 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 to the power of and then divides by 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 and that satisfy the following:
This pair of number serves the same purpose as the pair that belongs to Andy. Of course, and need to be kept secret from Andy. The following shows the encryption and decryption functions for Becky’s padlock.
How to Play the Game
Suppose the card numbers are (the above is one example of card number assigment). Andy then encrypts the card number using his encryption function . The following lists the encrypted card numbers.
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: for 5 distinct values of .
Becky’s 5-card hand: for 5 distinct values of .
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:
Becky’s 5-card hand: , 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:
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 . When Becky passes her encrypted cards to Andy, he can try to figure out Becky’s . 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 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:
For the descriptions of the numbers , , and , see the above section Setting Up the Padlocks. First we state the Fermat’s Little Theorem.
Fermat’s Little Theorem
Let be a prime number. Then for any integer , is an integer multiple of (or divides ). Using congruence notation, the theorem can be expressed as:
If the integer is not divisible by , then we can divide out and the theorem can be expressed as:
For a proof and a fuller discussion of Fermat’s little theorem, see this post.
We now prove the property . Recall that the pair of positive integers and are keys to lock and unlock a number . They are chosen such that , or equivalently for some integer . This integer must be positive since and are both positive.
In the derivation below, we repeated use the fact that (applying the Fermat’s Little Theorem).
Example of Congruence Calculation
For a numerical example, we use a small prime number . Though a small prime number, it is large enough to make the illustration meaningful. Andy chooses such that for some integer . Andy decides to use , leading to and .
As illustration of how the calculation is done, let (the number for as indicated above).
To decrypt this card, Andy needs to raise to the 2657th power and then find the remainder upon division by . This is the definition for modulo . 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 , meaning that the remainder is when is divided by . In the following series of steps, a congruence calculation is performed in each step (using the division algorithm) to reduce the exponent by half.
Thus the card number is encrypted as . To recover the original card number from this encrypted number, Andy needs to raise to the power of . 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, . Thus we have
With the help of Fermat’s Little Theorem, the exponent has come down to . In the rest of the way, the “divide and conquer” approach is used.
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, is divided by to obtain the remainder , i.e. . The number in the last line is the remainder when is divided by .