# Congruence Arithmetic and Fast Powering Algorithm

In some cryptography applications such as RSA algorithm, it is necessary to compute $\displaystyle a^w$ modulo $m$ where the power $w$ and the modulus $m$ are very large numbers. We discuss and demonstrate an efficient algorithm that can handle such calculations. This general algorithm has various names such as fast powering algorithm, square-and-multiply algorithm and exponentiation by squaring.

The problem at hand is to compute $a^w \ (\text{mod} \ m)$. The naïve approach is to compute by repeatedly multiplying by $a$ and reducing modulo $m$. When the power $w$ is large (e.g. an integer with hundreds of digits), this approach is difficult or even impossible (given the current technology). In this post we discuss an alternative that is known as the fast powering algorithm.

___________________________________________________________________________________________________________________

An Example

Compute $1286^{1171}$ modulo $1363$.

Using the naïve approach described earlier, we would do something like the following:

\displaystyle \begin{aligned} 1286^{1171} &=(1286 \cdot 1286) \cdot 1286^{1269} \equiv 477 \cdot 1286^{1269} \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(477 \cdot 1286) \cdot 1286^{1268} \equiv 72 \cdot 1286^{1268} \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&=(72 \cdot 1286) \cdot 1286^{1267} \equiv 1271 \cdot 1286^{1267} \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\text{ }\cdots \\&\text{ }\cdots \\&\text{ }\cdots \end{aligned}

In this naïve approach, we would multiply two numbers at a time and then reduce the result modulo $1363$ so that the numbers do not get too large. The above example would involve $1170$ multiplications and then $1170$ divisions for the reduction modulo $1363$. Great difficulty comes when the power is not $1171$ and instead is an integer with hundreds or even thousands of digits.

Note that in the above naïve approach, the power is reduced by one at each step. In the fast power alternative, the power comes down by an exponent of two in each step. The idea is to use the binary expansions of the exponent $1171$ to transform the computation of $1286^{1171}$ into a series of squarings and multiplications. To this end, we write $1171$ as a sum of powers of two as follows:

$(1) \ \ \ \ \ \ \ \ \ 1171=2^0+2^1+2^4+2^7+2^{10}$

Next we compute $1286^{2^0},1286^{2^1},1286^{2^2},1286^{2^3},\cdots,1286^{2^{10}}$ modulo $1363$. Note that each term is the square of the preceding term, hence the word square in the name “square-and-multiply”. To make it easier to see, we put the results in the following table.

$\displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&1286^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 1363&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&1286^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 1286&\text{ }&* \\ 1&\text{ }&1286^{2^1}&\text{ }&\equiv 1286^2&\text{ }&\equiv 477&\text{ }&* \\ 2&\text{ }&1286^{2^2}&\text{ }&\equiv 477^2&\text{ }&\equiv 1271&\text{ }&\text{ } \\ 3&\text{ }&1286^{2^3}&\text{ }&\equiv 1271^2&\text{ }&\equiv 286&\text{ }&\text{ } \\ 4&\text{ }&1286^{2^4}&\text{ }&\equiv 286^2&\text{ }&\equiv 16&\text{ }&* \\ 5&\text{ }&1286^{2^5}&\text{ }&\equiv 16^2&\text{ }&\equiv 256&\text{ }&\text{ } \\ 6&\text{ }&1286^{2^6}&\text{ }&\equiv 256^2&\text{ }&\equiv 112&\text{ }&\text{ } \\ 7&\text{ }&1286^{2^7}&\text{ }&\equiv 112^2&\text{ }&\equiv 277&\text{ }&* \\ 8&\text{ }&1286^{2^8}&\text{ }&\equiv 277^2&\text{ }&\equiv 401&\text{ }&\text{ } \\ 9&\text{ }&1286^{2^9}&\text{ }&\equiv 401^2&\text{ }&\equiv 1330&\text{ }&\text{ } \\ 10&\text{ }&1286^{2^{10}}&\text{ }&\equiv 1330^2&\text{ }&\equiv 1089&\text{ }&* \end{bmatrix}$

Note that the rows marked by * in the above table are the results that we need. In the above table, there are 10 multiplications for the squarings and 10 divisions for the reduction modulo $1363$.

Now $1286^{1171}$ is calculated as follows:

\displaystyle \begin{aligned} (3) \ \ \ \ \ \ \ \ \ 1286^{1171} &=1286^{2^0} \cdot 1286^{2^1} \cdot 1286^{2^4} \cdot1286^{2^7} \cdot 1286^{2^{10}} \\&\equiv 1286 \ \ \cdot 477 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \text{mod} \ 1363 \\&\equiv 72 \ \ \ \ \cdot 16 \ \ \ \ \ \cdot 277 \ \ \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 1152 \ \ \cdot 277 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 162 \ \ \cdot 1089 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \\&\equiv 591 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 1363 \end{aligned}

We have the answer $1286^{1171} \equiv 591 \ (\text{mod} \ 1363)$. The calculation in (3) is the step that gives the word “multiply” in the name “square-and-multiply”. In this step, we multiply the results obtained from the previous step.

We now tally up the amount of work that is done. The calculation in table (2) requires 10 multiplications for the squaring and 10 divisions for the reduction modulo $1363$. The calculation in (3) requires 4 multiplications and 4 divisions for the reduction modulo $1363$. Together, there are 14 multiplications and 14 divisions. In contrast, the naïve approach would require 1170 multiplications and 1170 divisions!

___________________________________________________________________________________________________________________

Description of Fast Powering Algorithm

To compute $a^w \equiv (\text{mod} \ m)$, use the following steps. The following steps correspond with the steps in the above example.

Step (1)

Compute the binary expansions of the power $w$.

$\displaystyle w=C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}$

where each $j$, $C_j=0$ or $C_j=1$. In particular, we assume that $C_k=1$.

Step (2)

For each $j=0,1,2,\cdots,k$, compute $\displaystyle a^{2^j} \equiv A_j$ modulo $m$. Note that each $\displaystyle a^{2^j} \equiv A_j$ is the result of squaring the previous term $\displaystyle a^{2^{j-1}} \equiv A_{j-1}$. We arrange the calculation in the following table.

$\displaystyle (2) \ \ \ \ \ \ \ \ \ \begin{bmatrix} \text{ i }&\text{ }&a^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } m&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&a^{2^0}&\text{ }&\text{ }&\text{ }&A_0\equiv a&\text{ }&\text{ } \\ 1&\text{ }&a^{2^1}&\text{ }&\equiv A_0^2&\text{ }&\equiv A_1&\text{ }&\text{ } \\ 2&\text{ }&a^{2^2}&\text{ }&\equiv A_1^2&\text{ }&\equiv A_2&\text{ }&\text{ } \\ 3&\text{ }&a^{2^3}&\text{ }&\equiv A_2^2&\text{ }&\equiv A_3&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ \text{ }&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\cdots&\text{ }&\text{ } \\ k-1&\text{ }&a^{2^{k-1}}&\text{ }&\equiv A_{k-2}^2&\text{ }&\equiv A_{k-1}&\text{ }&\text{ } \\ k&\text{ }&a^{2^k}&\text{ }&\equiv A_{k-1}^2&\text{ }&\equiv A_k&\text{ }&\text{ } \end{bmatrix}$

Step (3)

Compute $a^w \equiv (\text{mod} \ m)$ using the following derivation.

\displaystyle \begin{aligned}(3) \ \ \ \ \ \ \ \ \ a^{w}&=a^{C_0 +C_1 \cdot 2^{1}+C_2 \cdot 2^{2}+\cdots+C_{k-1} \cdot 2^{k-1}+C_k \cdot 2^{k}} \\&=a^{C_0} \cdot a^{C_1 \cdot 2^{1}} \cdot a^{C_2 \cdot 2^{2}} \cdots a^{C_{k-1} \cdot 2^{k-1}} \cdot a^{C_k \cdot 2^{k}} \\&=a^{C_0} \cdot (a^{2^{1}})^{C_1} \cdot (a^{2^{2}})^{C_2} \cdots (a^{2^{k-1}})^{C_{k-1}} \cdot (a^{2^{k}})^{C_k} \\&\equiv A_0^{C_0} \cdot (A_1)^{C_1} \cdot (A_2)^{C_2} \cdots (A_{k-1})^{C_{k-1}} \cdot (A_k)^{C_k} \ \ \ \ \ (\text{mod} \ m) \end{aligned}

The last line in (3) is to be further reduced modulo $m$. In the actual calculation, only the terms with $C_j=1$ need to be used.

We now establish an upper bound for the number multiplications. Step (2) requires $k$ multiplications and $k$ divisions to reduce modulo $m$. Step (3) requires at most $k$ many multiplications since some of the $C_j$ many be zero. Step (3) also requires at most $k$ many divisions to reduce modulo $m$. So altogether, the algorithm requires at most $2k$ multiplications and $2k$ divisions.

From Step (1), we know that $\displaystyle 2^k \le w$. Take natural log of both sides, we have $\displaystyle k \le \frac{\text{ln}(w)}{\text{ln}(2)}$ and $\displaystyle 2 \cdot k \le \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}$. So the fast powering algorithm requires at most

$\displaystyle \frac{2 \cdot \text{ln}(w)}{\text{ln}(2)}$

many multiplications and at most that many divisions to compute the congruence calculation $a^w \equiv (\text{mod} \ m)$.

For example, when the power $w=2^{127}-1$, which is a Mersenne prime, which has 39 digits. Now $w \approx 2^{127}$. By the above calculation, the fast powering algorithm would take at most 254 multiplications and at most 254 divisions to do the power congruence computation.

The fast powering calculations demonstrated in this post can be done by hand (using a hand-held calculator). In real applications, such calculations should of course be done in a computer.

___________________________________________________________________________________________________________________

Another Example

Use the fast power algorithm to show that

$4030^{2657} \equiv 21144 \ (\text{mod} \ 55049)$

$21144^{79081} \equiv 4030 \ (\text{mod} \ 55049)$

Note that one congruence is encryption and the other one is decryption. We demonstrate the second calculation.

In doing the second calculation, we use a little bit of help from Fermat’s little theorem. The modulus $55049$ is a prime number. So $21144^{55048} \equiv 1 \ (\text{mod} \ 55049)$. Thus we have:

$21144^{79081}=21144^{24033} \cdot 21144^{55048} \equiv 21144^{24033} \ (\text{mod} \ 55049)$

Step (1)

The binary expansions of $24033$ are:

$24033=2^0+2^5+2^6+2^7+2^8+2^{10}+2^{11}+2^{12}+2^{14}$

Step (2)

Compute $21144^{2^j}$ modulo $55049$ for each $j$. The computation is displayed in the following table. The rows with * are the results that we need for Step (3).

$\displaystyle \begin{bmatrix} \text{ i }&\text{ }&21144^{2^i}&\text{ }&\text{squaring}&\text{ }&\text{modulo } 55049&\text{ }&\text{ } \\\text{ }&\text{ }&\text{ } \\ 0&\text{ }&21144^{2^0}&\text{ }&\text{ }&\text{ }&\equiv 21144&\text{ }&* \\ 1&\text{ }&21144^{2^1}&\text{ }&\equiv 21144^2&\text{ }&\equiv 15807&\text{ }&\text{ } \\ 2&\text{ }&21144^{2^2}&\text{ }&\equiv 15807^2&\text{ }&\equiv 48887&\text{ }&\text{ } \\ 3&\text{ }&21144^{2^3}&\text{ }&\equiv 48887^2&\text{ }&\equiv 41483&\text{ }&\text{ } \\ 4&\text{ }&21144^{2^4}&\text{ }&\equiv 41483^2&\text{ }&\equiv 7549&\text{ }&\text{ } \\ 5&\text{ }&21144^{2^5}&\text{ }&\equiv 7549^2&\text{ }&\equiv 11686&\text{ }&* \\ 6&\text{ }&21144^{2^6}&\text{ }&\equiv 11686^2&\text{ }&\equiv 41076&\text{ }&* \\ 7&\text{ }&21144^{2^7}&\text{ }&\equiv 41076^2&\text{ }&\equiv 40975&\text{ }&* \\ 8&\text{ }&21144^{2^8}&\text{ }&\equiv 40975^2&\text{ }&\equiv 11174&\text{ }&* \\ 9&\text{ }&21144^{2^9}&\text{ }&\equiv 11174^2&\text{ }&\equiv 7144&\text{ }&\text{ } \\ 10&\text{ }&21144^{2^{10}}&\text{ }&\equiv 7144^2&\text{ }&\equiv 6313&\text{ }&* \\ 11&\text{ }&21144^{2^{11}}&\text{ }&\equiv 6313^2&\text{ }&\equiv 53542&\text{ }&* \\ 12&\text{ }&21144^{2^{12}}&\text{ }&\equiv 53542^2&\text{ }&\equiv 14040&\text{ }&* \\ 13&\text{ }&21144^{2^{13}}&\text{ }&\equiv 14040^2&\text{ }&\equiv 46180&\text{ }&\text{ } \\ 14&\text{ }&21144^{2^{14}}&\text{ }&\equiv 46180^2&\text{ }&\equiv 49189&\text{ }&* \end{bmatrix}$

Step (3)

Compute $21144^{79081} \ (\text{mod} \ 55049)$.

\displaystyle \begin{aligned} 21144^{24033} &=21144^{2^0} \cdot 21144^{2^5} \cdot 21144^{2^6} \cdot 21144^{2^7} \cdot 21144^{2^{8}} \cdot 21144^{2^{10}} \cdot 21144^{2^{11}} \cdot 21144^{2^{12}} \cdot 21144^{2^{14}} \\&\equiv 21144 \cdot 11686 \cdot 41076 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \text{mod} \ 55049 \\&\equiv 25665 \cdot 40975 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 22328 \cdot 11174 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 11004 \cdot 6313 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 51463 \cdot 53542 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 9300 \cdot 14040 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 50821 \cdot 49189 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \\&\equiv 4030 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \text{mod} \ 55049 \end{aligned}

___________________________________________________________________________________________________________________

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

# 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}$

# 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$

___________________________________________________________________________________________________________________

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}$

# Fermat’s Little Theorem and RSA Algorithm

RSA is a cryptographic algorithm that is used to send and receive messages. We use the Fermat’s Little Theorem to prove that RSA works correctly and accurately. In other words, the decrypted message is indeed the original message from the sender. Mathematically we show that applying the encryption function and the decryption function successively produces the identity function.

To see how RSA works, see the previous post An Illustration of the RSA Algorithm.

___________________________________________________________________________________________________________________

RSA Algorithm

We first briefly describe the algorithm and then present the mathematical statement to validate.

Let $N=p \cdot q$ where $p$ and $q$ are two prime numbers. Let $\phi=(p-1) \cdot (q-1)$. Choose an integer $e$ with $1 such that $e$ and $\phi$ are relatively prime.

The public key consists of $N$ and $e$ where $e$ is the encryption key. Once it is published, anyone can use it to encrypt messages to send to the creator of the public key. The following is the encryption function:

$f(M) \equiv M^e \ (\text{mod} \ N)$

where $M$ is a positive integer and is the original message.

The private key is a positive integer $d$ that satisfies:

$d \cdot e \equiv 1 \ (\text{mod} \ \phi=(p-1) \cdot (q-1))$

In other words, $d$ is the multiplicative inverse of $e$ in the modular arithmetic of modulo $\phi$. The above condition is equivalent to: $de-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$.

The number $d$ is the decryption key that will be used to decode messages. So it should remain private.

Once the creator of the public key receives an encrypted message $C=f(M)$, he or she uses the following decryption function to obtain the original message $M$.

$g(C) \equiv C^d \ (\text{mod} \ N)$

___________________________________________________________________________________________________________________

The Mathematical Statement to Validate

What we prove is that the decryption function is to undo the encryption function. Specifically, we prove the following:

$g(C)=g(f(M))=(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N) \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1)$

In other words, applying the decryption function $g$ to the encryption function $f$ produces the original message.

___________________________________________________________________________________________________________________

Fermat’s Little Theorem

In this section, we list out the tools we need to prove the correctness of RSA.

Theorem 1 (Fermat’s Little Theorem)
If $p$ is a prime number and $a$ is an integer such that $a$ and $p$ are relatively prime, then

$a^{p-1}-1$ is an integer multiple of $p$

or equivalently $a^{p-1} \equiv 1 \ (\text{mod} \ p)$.

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

Lemma 2 (Euclid’s Lemma)
Let $a$, $b$ and $d$ be integers where $d \ne 0$. Then if $d$ divides $a \cdot b$ (symbolically $d \lvert a \cdot b$), then either $d \lvert a$ or $d \lvert b$.

Euclid’s Lemma is needed to prove the following Lemma.

Lemma 3
Let $M$ be an integer. Let $p$ and $q$ be prime numbers with $p \ne q$.

Then if $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$, then $a \equiv M \ (\text{mod} \ p \cdot q)$.

Proof of Lemma 3
Suppose we have $a \equiv M \ (\text{mod} \ p)$ and $a \equiv M \ (\text{mod} \ q)$. Then for some integers $i$ and $j$, we have:

$a=M+p \cdot i$ and $a=M+q \cdot j$.

Then $p \cdot i=q \cdot j$. This implies that $p$ divides $q \cdot j$ ($p \lvert q \cdot j$). By Euclid’s lemma, we have either $p \lvert q$ or $p \lvert j$. Since $p$ and $q$ are distinct prime numbers, we cannot have $p \lvert q$. So we have $p \lvert j$ and that $j=p \cdot w$ for some integer $w$.

Now, $a=M+q \cdot j=M+q \cdot p \cdot w$, implying that $a \equiv M \ (\text{mod} \ p \cdot q)$. $\blacksquare$

___________________________________________________________________________________________________________________

The Proof of (1)

We now prove the property $(1)$ described above. We show that

$(M^e)^d=M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$

We first show that $M^{ed} \equiv M \ (\text{Mod} \ p)$ and $M^{ed} \equiv M \ (\text{Mod} \ q)$. Then the desired result follows from Lemma 3.

To show $M^{ed} \equiv M \ (\text{Mod} \ p)$, we consider two cases: $M \equiv 0 \ (\text{Mod} \ p)$ or $M \not \equiv 0 \ (\text{Mod} \ p)$.

Case 1. $M \equiv 0 \ (\text{Mod} \ p)$. Then $M$ is an integer multiple of $p$, say $M=p \cdot w$ where $w$ is an integer. Then $M^{ed}=(p \cdot w)^{ed}=p \cdot p^{ed-1} \cdot w^{ed}$. So both $M$ and $M^{ed}$ are integer multiples of $p$. Thus $M^{ed} \equiv M \ (\text{Mod} \ p)$.

Case 2. $M \not \equiv 0 \ (\text{Mod} \ p)$. This means that $p$ and $M$ are relatively prime (having no common divisor other than 1). Thus we can use Fermat’s Little Theorem. We have $M^{p-1} \equiv 1 \ (\text{mod} \ p)$.

From the way the decryption key $d$ is defined above, we have $ed-1=(p-1) \cdot (q-1) \cdot k$ for some integer $k$. We then have:

\displaystyle \begin{aligned} M^{ed}&=M^{ed-1} \cdot M \\&=M^{(p-1) \cdot (q-1) \cdot k} \cdot M \\&=(M^{p-1})^{(q-1) \cdot k} \cdot M \\&\equiv (1)^{(q-1) \cdot k} \cdot M \ (\text{Mod} \ p) \ * \\&\equiv M \ (\text{Mod} \ p) \end{aligned}

At the step with *, we apply Fermat’s Little Theorem. So we have $M^{ed} \equiv M \ (\text{Mod} \ p)$.

The same reason reasoning can show that $M^{ed} \equiv M \ (\text{Mod} \ q)$.

By Lemma 3, it follows that $M^{ed} \equiv M \ (\text{Mod} \ N=p \cdot q)$. $\blacksquare$

___________________________________________________________________________________________________________________

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

Revised August 9, 2014.

# An Illustration of the RSA Algorithm

The following 617-digit number (all 617 digits starting with $251$ and ending in $357$) is a product of two prime numbers $p$ and $q$. How long will it take to find these two prime factors?

25195908475657893494027183240048398571429282126204
03202777713783604366202070759555626401852588078440
69182906412495150821892985591491761845028084891200
72844992687392807287776735971418347270261896375014
97182469116507761337985909570009733045974880842840
17974291006424586918171951187461215151726546322822
16869987549182422433637259085141865462043576798423
38718477444792073993423658482382428119816381501067
48104516603773060562016196762561338441436038339044
14952634432190114657544454178424020924616515723350
77870774981712577246796292638635637328991215483143
81678998850404453640235273819513786365643912120103
97122822120720357

The above number is a challenge to the public to come up with the two prime factors (see RSA challenge number and RSA factoring challenge). No one has been able to successfully meet the challenge. In fact, even with the current state of the art in supercomputing technology, it could take millions of years to factor a number as big as the one shown above. According to the organization that posed the challenge (RSA Laboratories), barring fundamental algorithmic or computing advances, the above number or other similarly sized number is expected to stay unfactored in the decades to come.

RSA is a cryptographic algorithm that is used to send and receive sensitive data. The name RSA stands for the last names of the creators of the algorithm – Ron Rivest, Adi Shamir and Leonard Adleman.

The algorithm uses a pair of large prime numbers in setting up a public key to encrypt and a private key to decrypt data. The public key is known to the public and includes a large integer $N$ (such as the one indicated at the beginning of the post) that is a product of two prime numbers $p$ and $q$. The private key is computed using two prime factors $p$ and $q$ and is needed to decrypt the messages encrypted by the public key. The RSA scheme is built on the monumental difficulty in factoring large numbers. Barring some system vulnerability that hackers can exploit, it is all but certain that messages sent via RSA scheme can only be read by the intended party – the legitimate party that possesses the private key.

This post gives an illustration of how the RSA algorithm work using much smaller prime numbers. The RSA algorithm is also an application of the Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

The example given below makes use of congruence arithmetic. If $a$, $b$ and $m$ are integers, the symbol $a \equiv b \ (\text{mod } m)$ means that the difference $a-b$ is divisible by $m$ (we say that $a$ is congruent to $b$ modulo $m$). For example, $15 \equiv 3 \ (\text{mod } 12)$ (in terms of clock arithmetic, 6 hours after 9 o’clock is not 15th o’clock but is 3 o’clock). For more information about congruence relation and congruence arithmetic, see this blog post or this Wikipedia entry.

___________________________________________________________________________________________________________________

Example of RSA

The example uses small prime numbers to make the illustration easy to follow. The example has the following steps:

1. Andy creates a public key and a private key. He gives the public key to Becky and keeps the private key to himself.
2. Becky then uses the public key to encrypt a message and sends it to Andy.
3. Andy then uses the private key to decrypt the message received from Becky.
4. $\text{ }$

______________________________________________________
Step 1 – Generating the Public Key and Private Key

Choose two prime numbers $p$ and $q$. In this example, let $p=29$ and $q=47$. Then calculate the following numbers:

$N=p \times q=1363$

$(p-1) \times (q-1)=1288$

Choose an integer $e$ with $1 such that $e$ and $(p-1) \times (q-1)$ are relatively prime (meaning the only common divisor is 1). For this example, Andy chooses $e=11$.

The public key consists of $N=1363$ and $e=11$, which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy (see Step 2 below). The number $e$ is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number $d$ such that:

$e \cdot d \equiv 1 \ (\text{mod } (p-1) \cdot (q-1))$

In this example, find the number $d$ such that

$11 \cdot d \equiv 1 \ (\text{mod } 1288)$

Specifically, we need to find the number $d$ that satisfies $11d=1+1288 k$ for some integer $k$. When $k=10$, we have a solution $d=1171$.

The number $d=1171$ will be used to decrypt any message that will come from Becky. So Andy needs to keep $d$ private and secure.

______________________________________________________
Step 2 – Encrypting a Message using the Public Key

Becky wishes to send a message $T$ (in text) to Andy. Becky first translates $T$ into an integer $M$ (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message $M$ back to the text message $T$. Note that the mapping for translating letters into numbers and back is not part of the RSA algorithm, which only encrypts and decrypts numeric messages.

Suppose the message is $M=289$. The following is the encryption function – the function that generates the encrypted message $C$

$f(M) \equiv M^e \ (\text{mod } N)$

In this example, the encryption function is:

$f(M) \equiv 289^{11} \ (\text{mod } 1363)$

The encrypted message is the number $C=f(M)$ is the remainder that is obtained when $289^{11}$ is divided by $N=1363$. This can be done in a process using congruence arithemtic that can be described as “divide and conquer”. The process is to reduce the exponent by half in each step of the step by step approach.

First, note that $289^2 \equiv 378 \ (\text{mod} \ 1363)$ since $378$ is the remainder when $289^2$ is divided by $1363$ (i.e. division algorithm). Then use the division algorithm successively as shown in the following:

\displaystyle \begin{aligned} 289^{11}&\equiv (289^2)^5 \cdot 289 \ (\text{mod} \ 1363) \\&\text{ } \\&\equiv 378^5 \cdot 289 \equiv (378^2)^2 \cdot 378 \cdot 289 \\&\text{ } \\& \equiv 1132^2 \cdot 378 \cdot 289 \\&\text{ } \\&\equiv 1132^2 \cdot 202 \\&\text{ } \\&\equiv 204 \cdot 202 \\&\text{ } \\&\equiv 318 \ (\text{mod} \ 1363) \end{aligned}

In the “divide and conquer” approach, a congruence calculation in done in each step to reduce the exponent (applying the division algorithm). For example, to go from the first line to the second line, the remainder $378$ is obtained when $289^2$ is divided by $1363$. The number $318$ is the remainder when $204 \cdot 202$ is divided by $1363$.

______________________________________________________
Step 3 – Decrypting the Message Receiving from Becky

Andy receives the encrypted message $C=318$. To decrypt $C$, the private key $d$ that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message $M$.

$g(C) \equiv C^d \ (\text{mod } N)$

In particular, Any needs to find the number $M=g(C)$ that satisfies the following:

$g(C) \equiv 318^{1171} \ (\text{mod } 1363)$

The decrypted message $M=g(C)$ is the remainder when $318^{1171}$ is divided by $1363$. A “divide and conquer” approach can be used.

\displaystyle \begin{aligned} 318^{1171}&\equiv (318^2)^{585} \cdot 318 \ (\text{mod} \ 1363) \\&\text{ } \\&\equiv 262^{585} \cdot 318 \equiv (262^2)^{292} \cdot 262 \cdot 318 \\&\text{ } \\& \equiv 494^{292} \cdot 262 \cdot 318 \\&\text{ } \\&\equiv 494^{292} \cdot 173 \equiv (494^2)^{146} \cdot 173 \\&\text{ } \\& \equiv 59^{146} \cdot 173 \equiv (59^2)^{73} \cdot 173 \\&\text{ } \\& \equiv 755^{73} \cdot 173 \equiv (755^2)^{36} \cdot 755 \cdot 173 \\&\text{ } \\& \equiv 291^{36} \cdot 755 \cdot 173 \\&\text{ } \\&\equiv 291^{36} \cdot 1130 \equiv (291^2)^{18} \cdot 1130 \\&\text{ } \\& \equiv 175^{18} \cdot 1130 \equiv (175^2)^{9} \cdot 1130 \\&\text{ } \\& \equiv 639^{9} \cdot 1130 \equiv (639^2)^{4} \cdot 639 \cdot 1130 \\&\text{ } \\& \equiv 784^{4} \cdot 639 \cdot 1130 \\&\text{ } \\&\equiv 784^{4} \cdot 1043 \equiv (784^2)^{2} \cdot 1043 \\&\text{ } \\& \equiv 1306^{2} \cdot 1043 \\&\text{ } \\&\equiv 523 \cdot 1043 \\&\text{ } \\&\equiv 289 \ (\text{mod} \ 1363) \end{aligned}

We just illustrates how Andy decrypts Becky’s message of $C=318$ to find the original message of $M=289$. The calculation is tedious if done manually but is simple for a computer.

___________________________________________________________________________________________________________________

Summary

We summarize the main steps in the above example.

______________________________________________________
Step 1 – Generating the Public Key and Private Key

Choose two prime numbers $p$ and $q$. Then calculate the following numbers:

$N=p \times q$

$(p-1) \times (q-1)$

Choose an integer $e$ with $1 such that $e$ and $(p-1) \times (q-1)$ are relatively prime (meaning the only common divisor is 1).

The public key consists of $N$ and $e$, which Andy passes to Becky. Becky will use the public key to encrypt any message that she wishes to send to Andy. The number $e$ is the encryption key.

Andy can also make the public key known to any one from whom Andy wishes to receive message.

The private key is the number $d$ such that:

$e \cdot d \equiv 1 \ (\text{mod } (p-1) \cdot (q-1))$

The number $d$ is the decryption key and will be used to decrypt any message that will come from Becky. So Andy needs to keep $d$ private and secure.

______________________________________________________
Step 2 – Encrypting a Message using the Public Key

Becky wishes to send a message $T$ (in text) to Andy. Becky first translates $T$ into an integer $M$ (e.g. using a mapping to translate strings of letters and other symbols into blocks of numbers). This same mapping will be used by Andy to translate the decrypted message $M$ back to the text message $T$.

The following is the encryption function – the function that generates the encrypted message $C$.

$f(M) \equiv M^e \ (\text{mod } N)$

The encrypted message that Becky will send to Andy is $C=f(M)$.

______________________________________________________
Step 3 – Decrypting the Message Receiving from Becky

Andy receives the encrypted message $C$. To decrypt $C$, the private key $d$ that is calculated in Step 1 above is used. The following is the decryption function – the function that generates the decrypted message $M$.

$g(C) \equiv C^d \ (\text{mod } N)$

The original message sent from Becky is $M=g(C)$.

Note that $M=g(f(M))$. Thus the function $f$ is the inverse function of $g$ (and vice versa). This fact can be established by using Fermat’s Little Theorem (see the post Fermat’s Little Theorem and RSA Algorithm).

___________________________________________________________________________________________________________________

RSA Exercise

Suppose you are Andy. You set $p=53$ and $q=67$. You also choose $e=7$.

You give the public key $N=3551$ and $e=7$.

Becky sends you an encrypted message $C=2691$.

What is the original message?

___________________________________________________________________________________________________________________

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