Explain CypherPoker encryption like I’m 5

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.

masterlock

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:

mK(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 “mK” 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:

64 = 6 x 6 x 6 x 6 = 1296
93 = 9 x 9 x 9 = 729
3211 = 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 x 32 = 36028797018963968

You can do this calculation by hand or on a calculator by entering the value for “m”, pressing the “xy” key, entering a value for “K”, then pressing “=”.

calc-1

Once we calculate mK 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 “mK“, pressing the “MOD” key, entering a value for “P”, and pressing “=”.

calc-2

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:

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:

24-hour time

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).

Modulo clock

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:

mK(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:

23 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”:

87 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:

23 mod 11 = 8
89 mod 11 = 7 (the final encrypted or “face-down” card)

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

79 mod 11 = 8
87 mod 11 = 2 (Ace of Spades)

This works even if we decrypt in a different order:

77 mod 11 = 6
69 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 = 210/2 mod 11 = 25 mod 11 = 32 mod 11 = 10
3(11-1)/2 mod 11 = 35 mod 11 = 243 mod 11 = 1
4(11-1)/2 mod 11 = 45 mod 11 = 1024 mod 11 = 1
5(11-1)/2 mod 11 = 55 mod 11 = 3125 mod 11 = 1
6(11-1)/2 mod 11 = 65 mod 11 = 7776 mod 11 = 10
7(11-1)/2 mod 11 = 75 mod 11 = 16807 mod 11 = 10
8(11-1)/2 mod 11 = 85 mod 11 = 32768 mod 11 = 10
9(11-1)/2 mod 11 = 95 mod 11 = 59049 mod 11 = 1
10(11-1)/2 mod 11 = 105 mod 11 = 100000 mod 11 = 10

When 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:

23 mod 11 = 8
89 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:

77 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:

2512 = 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:

21024 = 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! 😀

2 comments

Add Comment

Required fields are marked *. Your email address will not be published.