I’ve recently had the opportunity to run over this topic with someone who I’m quite certain isn’t 5, mentally or otherwise, so the title isn’t meant pejoratively but rather as being reassuringly easy to understand. Please don’t be concerned by the length of the post – it’s mostly examples and demonstrations. To see all of this in action or to learn more please visit http://www.cypherpoker.org/ to join the Slack, drop by the GitHub repository, or visit the subreddit .

### tl;dr

CypherPoker uses a short mathematical equation to encrypt (hide) or decrypt (reveal) information such as cards that can be represented by numbers (*1=Ace of Spades, 2=Two of Spades, etc.*) An important property of this mathematical equation is that when information is encrypted by multiple players, it can be decrypted by those players in any order – as long as everyone who encrypts also decrypts – kind of like a multi-lock box.

### No *fancy* numbers

The encryption/decryption system used in CypherPoker uses numbers known as “positive integers“. This means simply that the numbers it uses are whole numbers – no fractions with remainders or decimal point values – and they’re all positive, or equal to or larger than **1**. (We omit **0** since we can’t really use it).

Here are some examples of numbers that are positive integers:

** 1**

** 5**

** 1000**

** 32**

** 999**

** 812798731901**

** 6**

Here are some examples of numbers that are *not* positive integers:

**-1**

** 0.643**

** 98.1**

** -1000**

** 1000.9**

** -198309180981**

** ¼**

** -½**

### The secret sauce

Here’s the mathematical function that’s used to encrypt or decrypt information:

#### m^{K}(mod P)

Sometimes this is written as:

#### (m^K) mod P

In JavaScript it would look like this:

Math.pow(m,K) % P

You’ll probably recognize the “m^{K}” part which means “m” to the power of “K”, or “m” multiplied by itself “K” times. (I’ll explain why we use the letters “m”, “K”, and “P” in a bit)

Here are some examples:

**6 ^{4} = 6 x 6 x 6 x 6 = 1296**

**9**

^{3}= 9 x 9 x 9 = 729**32**

^{11}= 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 = 36028797018963968You can do this calculation by hand or on a calculator by entering the value for “m”, pressing the “x^{y}” key, entering a value for “K”, then pressing “=”.

Once we calculate m^{K} we do a *modulo* operation on the result – the “mod” part. This is also something that you can calculate by hand or on a calculator by entering the result of “m^{K}“, pressing the “MOD” key, entering a value for “P”, and pressing “=”.

Modulo simply “wraps” a number around some maximum value just like an analog clock which is why it’s sometimes called “clock math”.

To understand this, consider the standard 12-hour analog clock:

In our day we have 24 hours but on this kind of clock we can only show **12**. The first **12** hours are fine but at noon, or **12** o’clock, the clock basically resets (to 0), so that the next hour is **1** o’clock.

If we kept counting beyond **12**, **1** p.m. is actually hour **13**, **2** p.m. is hour **14**, **3** p.m. is hour **15**, and so on:

We could keep going around and around on the clock any number of times and land on some number between **0** and **11** (we would never get **12** since the count resets at that point to **0**).

The result of the modulo operation tells us which number we’ll land on if we go “x” number of hours around a clock with “y” divisions, or:

**x mod y**

An analog clock has **12** divisions so the math would look like this:

**x mod 12**

If we want to find out what hour **13** is on our analog clock with **12** divisions we would calculate:

**13 mod 12 = 1**

If **2927** hours passed on the same clock, what number would we land on?

**2927 mod 12 = 11**

The clock we use doesn’t need to have **12** divisions, it can be any positive integer such as **38**:

**x mod 38**

…or 1001:

**x mod 1001**

…or 3:

**x mod 3**

There are ways to do this math with numbers that aren’t positive integers but that doesn’t happen in CypherPoker.

### Putting it together

Back to:

#### m^{K}(mod P)

The “m” stands for the *message* to be encrypted or decrypted. This is actually just a number but it can *represent* quite a few different things; it could be a letter of the alphabet (*2=A, 3=B, 4=C…*), a coordinate on a map, or maybe a playing card (*2=Ace of Spades, 3=Two of Spades, 4=Three of Spades…*) Although we can use any positive integer for “m”, ** 1** to the power of anything will *always* produce the same value as we started out with so we don’t use it (or **0**, for similar reasons).

The “K” value is the encryption or decryption *Key*. This is a number (of a pair), that is calculated using the “P” value (below) and kept secret by the player.

The “P” value is a *Prime* number. A prime number is one that can be evenly divided only by itself and **1**. Another way to put it is that “P” divided by *any* positive integer other than itself and **1** will always produce a result that’s *not* a positive integer. For example, **5** is a prime number because:

**5/5 = 1
**

**5/4 = 1.25**

**5/3 = 1.666666…**

**5/2 = 2.5**

**5/1 = 5**

But **4** is *not* a prime number because it can be evenly divided by **2** (the result is a positive integer):

**4/4 = 1**

**4/3 = 1.333333…**

**4/2 = 2 (not a prime!)**

**4/1 = 4**

If a number isn’t a prime number we call it a “composite” number.

### Finding a keypair

We use one value for “K” to encrypt, scramble, obfuscate, or hide the “m” value, and another value for “K” to decrypt it, or work in the reverse direction. Since these values come in pairs, together they’re called a “keypair”.

To find keypairs for “K” we find something called a “modular multiplicative inverse”. This simply means finding two values, the keypair “a” and “b” which make the following equation work:

**(ab) mod (P-1) = 1**

This is sometimes written as:

**(a*b) mod (P-1) = 1**

In JavaScript it would look like this:

if ((a*b) % (P-1) == 1) { //a and b are a valid keypair } else { //a and b are NOT a valid keypair }

This means that if you multiply “a” times “b” and modulo the result by “(P-1)” it must produce **1**.

In CypherPoker every player knows the value for “P” before the game begins; let’s say it’s the prime number **11**.

To find keypairs we could simply try every combination of numbers between **1** and **10** (or P-1) to see which ones satisfy the equation.

After lots of calculations we would find two pairs of numbers that work:

**a=3**

** b=7**

** ….since (3 * 7) mod 10 = 21 mod 10 = 1**

**a=9**

** b=9**

** …since (9 * 9) mod 10 = 81 mod 10 = 1**

Keypairs are usually written as *(a,b).* For example: **(3,7)** or **(9,9)**

In the above example we have only **2** keypairs available which means that the encryption system isn’t going to be very secure but the math will work regardless.

### Let’s do some crypto…

To encrypt “m” we use one of the keypairs we found above for “K” and the shared “P” value.

For example, let’s say we want to encrypt **2** (which we’ve decided represents the Ace of Spades). We already know that “P” is **11** and we used that to calculate our keypair of **(3,7)**, so the encryption calculation is:

**2 ^{3} mod 11 = 8**

To decrypt we use the same function, this time using **8** for the encrypted “m” value (from above), and the other half of the keypair for “K”:

**8 ^{7} mod 11 = 2 (Ace of Spades)**

Once we’ve encrypted “m”, the result can again be encrypted again. This can be done over and over and as long as every encryption is followed by a matching decryption we will get back the original value for “m”. Most importantly, all of the encryptions and decryptions can be done in any order.

Here’s an example using both keypairs – **(3,7)** and **(9,9)** – to encrypt the Ace of Spades twice:

**2 ^{3} mod 11 = 8
8^{9} mod 11 = 7 (the final encrypted or “face-down” card)**

Using the other half of the keypairs we can now decrypt:

**7 ^{9} mod 11 = 8
8^{7} mod 11 = 2 (Ace of Spades)
**

This works even if we decrypt in a different order:

**7 ^{7} mod 11 = 6
6^{9} mod 11 = 2 (Ace of Spades)**

### Just a moment

Unfortunately there’s a bit of a problem with using just any number for “m”. It turns out that the “quadratic residue modulo P” of the “m” number will be the same no matter how many times you encrypt it.

Although it sounds pretty fancy, the quadratic residue calculation (also known as the Legendre symbol), is no more difficult than everything else we’ve done:

**m ^{(P-1)/2} mod P**

This may also be written as:

**(m^((P-1)/2)) % P**

…or in JavaScript:

Math.pow(m, (P-1)/2) % P

This calculation will *always *produce either **P-1, 0, or 1**. In other words, if P=**11** then the above equation will always produce either a **10**, a **0**, or a **1**.

Check it out:

**2 ^{(11-1)/2} mod 11 = 2^{10/2} mod 11 = 2^{5} mod 11 = 32 mod 11 = 10**

**3**

^{(11-1)/2}mod 11 = 3^{5}mod 11 = 243 mod 11 = 1**4**

^{(11-1)/2}mod 11 = 4^{5}mod 11 = 1024 mod 11 = 1**5**

^{(11-1)/2}mod 11 = 5^{5}mod 11 = 3125 mod 11 = 1**6**

^{(11-1)/2}mod 11 = 6^{5}mod 11 = 7776 mod 11 = 10**7**

^{(11-1)/2}mod 11 = 7^{5}mod 11 = 16807 mod 11 = 10**8**

^{(11-1)/2}mod 11 = 8^{5}mod 11 = 32768 mod 11 = 10**9**

^{(11-1)/2}mod 11 = 9^{5}mod 11 = 59049 mod 11 = 1**10**

^{(11-1)/2}mod 11 = 10^{5}mod 11 = 100000 mod 11 = 10When the result is **1** we say that it’s a “quadratic residue” and when it’s P-1 we call it a “quadratic non-residue”. When the result is **0** it has no special name since only **0** will produce it.

Now remember when we encrypted the number **2** (the Ace of Spades) above with the keypairs **(3,7)** and **(9,9)**? Quick refresher:

**2 ^{3} mod 11 = 8
**

**8**

^{9}mod 11 = 7*(the final encrypted or “face-down” card)*Here we can see that **2** is encrypted to **8** which is then encrypted to **7**. If we look at the quadratic residue calculations we did above we notice that **2**, **8**, and **7** are all quadratic non-residues (**10**).

As part of our decryption we also ended up with **6**:

**7 ^{7} mod 11 = 6**

And wouldn’t you know it, **6** is also a quadratic non-residue!

It doesn’t matter how many times or with which keypair you encrypt the value **2**; when “P” is **11** the encrypted results will *always* be quadratic non-residues. Similarly, if we encrypt the value **9** (“m” is **9**) we would find that all of the results would be quadratic residues just like **9** itself.

If **2** represents the Ace of Spades, **3** is the Two of Spades, **4** is the Three of Spades, and so on, then we know some information about cards that have been encrypted. After all, even if we don’t know exactly which card an encrypted value represents, we know that if it’s a quadratic residue it can’t be the Ace of Spades (since that is a quadratic non-residue).

It sure would be handy to be able know that your poker opponent(s) definitely can’t be holding certain cards, wouldn’t it?

That’s why in CypherPoker the numbers representing cards are only quadratic residues. For example, if “P” is **11** then our cards would be:

**3=Ace of Spades**

** 4=Two of Spades**

** 5=Three of Spades**

** 9=Four of Spades**

To make sure that our cards don’t “leak” information we can’t use any of the other numbers because they’re all quadratic non-residues.

### The nutshell

When “P” is **11** we only have **4** *secure* cards and **2** keypairs which doesn’t make for a good or secure game of poker. In order to support a full 52-card deck (as quadratic residues) and have enough keypairs to make it nearly impossible for someone to find the one that we chose, the “P” value must be much larger.

As a security baseline, CypherPoker uses numbers that are 512 bits. That means that “m”, “K”, and “P” are all between **0** and:

**2 ^{512} = 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084096**

(here’s a large integer calculator you can use to see how I produced these results: http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm)

For truly secure games we would probably want to use a 1024 bit number (or larger). That means that “m”, “K”, and “P” are all between **0** and:

**2 ^{1024} = 179769313486231590772930519078902473361797697894230657273430081157732675805500963132708477322407536021120113879871393357658789768814416622492847430639474124377767893424865485276302219601246094119453082952085005768838150682342462881473913110540827237163350510684586298239947245938479716304835356329624224137216**

Once we start to work with numbers this big it’s hard just to do the basic math let alone find shortcuts to make it faster, and that’s where the security of the encryption lies.

The trick in any good implementation is to be able to perform these large-integer calculations efficiently but this is a problem for which a solution must be found specific to whatever technology is being used. Some programming languages, for example, support large or arbitrary-length integer math *natively* (without any external libraries or additions), but in most cases developers will need to find or write a suitable solution. The arbitrary-length integer math library used in CypherPoker, for example, is the JavaScript-based BigInt.js by Leemon Baird.

Nevertheless, regardless of how the math is handled it must produce the same results as we’ve covered here so it’s safe to say that if you’ve understood everything above you also understand, at a fundamental level, how CypherPoker encryption and decryption work. Congratulations! 😀

Very interesting, but think you lost the five year old half way down

As long as that five year old made it to the tl;dr section then they’re ready for the follow-up 🙂