How to Play Mental Poker: A Tutorial by the Author of Cypher-Poker (edited by TWOC J.Smithy)

(This was dialogue between me and the author of CypherPoker, loosely edited out my comments and questions, posted with permission)

Here are two useful links:

Big Integer Calculator – Arbitrary Precision Arithmetic…This online calculator helps you perform arithmetic operations with 100+ digit numbers using BigInt.js: http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm

http://www.cs.princeton.edu/~dsri/modular-inversion.html

The first is a calculator for very large integer values (beyond what Windows calculator can handle), and the second one is used to find the modular multiplicative inverse of a value — more on that in a bit!

The main mathematical function in SRA (and RSA, El gamal, etc.) is:
(x^y) mod z
…or, “x” to the power of/raised to the exponent “y”, modulo “z”

In JavaScript this would be written as:
Math.pow(x,y) % z;

In Windows calculator, you can perform these calculations like this:

1. Enter a value for “x”
2. Click on the x superscript-y button (to the left of the “sin” button); the calculator will show a “^” symbol to denote exponentiation in the display.
3. Enter a value for “y”, the click “=”
4. Apply the modulus by clicking the “Mod” button, entering a value for “z”, then “=”.

In the big integer calculator (the first link above), the exponentiation button appears as “x^y” and there are two entry fields. for the “mod” operation you would put the result from the “x^y” operation into the “x” field, and the modulus value (32 in the example above), into the “y” field.

In SRA the values are written slightly differently:
(m ^ K) mod P

Same equation, still uses numbers, we just use different letters to denote what those numbers represent:

– “m” is the “message” being encrypted or decrypted (the same function is used for both operations)
– “K” is the encryption or decryption “Key”
– “P” is a prime number

These values can only be positive integers – no negative numbers, no decimals: 0,1,2,3,4,5,6…

One thing to note is that we can’t use 0 or 1 for “m” or “K” (for “P” too, really). Using 0 for either value always produces 0, and 1 always produces the same value.

In our case the “m” value represents the card value. Since this can’t be 0 or 1, we start our “deck” at 2.

So 2=Ace of Spades, 3=Two of Spades, 4=Three of Spades, etc.

In SRA we start by picking a value for “P”. That is, pick a positive, whole prime number which is a number that is evenly divisible only by itself and 1 (every other division produces a remainder).
For example:

3 …
3/3 = 1
3/2=1.5 (remainder!)
3/1=3
… or 5 …
5/5 = 1
5/4 = 1.25 (remainder!)
5/3 = 1.66666667 (remainder!)
5/2 = 2.5 (remainder!)
5/1 = 5
The number 6, however, is not prime since:
6/6 = 1
6/5= 1.2 (remainder – could be prime)
6/4=1.5 (remainder)
6/3=2 (no remainder! This is a “composite” number, not a prime.)
6/2=3 (see above)
6/1=6

In the Ethereum integration I used 59 for “P” (this makes sense once you plug in the other numbers).

Prime numbers are very useful and there are entire projects dedicated to searching for new ones (or prime subtypes), for example:

http://www.mersenne.org/

Great Internet Mersenne Prime Search – PrimeNet
Great Internet Mersenne Prime Search – Finding world record primes since 1996. GIMPS is an organized search for Mersenne prime numbers using provided free software.

The “P” value becomes a ​_seed_​, if you will, for everything else. Next we use it to generate the encryption/decryption keys

The keys are simply numbers that are plugged into the equation as the “K” value.

The keys are simply numbers that are plugged into the equation as the “K” value.
To find a suitable number, we find the ​_modular multiplicative_​ inverse of a candidate value.

That’s fancy talk for which two numbers can allow us to: 1. Change or ​*encrypt*​ the “m” (card value) to some seemingly random value and then 2. Change back or ​*decrypt*​ that seemingly random value back to the original “m”

And these two values are dependent on a value for “P”.

(Here’s the online calculator for this mentioned earlier: http://www.cs.princeton.edu/~dsri/modular-inversion.html)

The only thing is that in this calculator we use ​_phi(P)_​ as the “p” value. (math math math), so the ​_phi_​ of any prime is P-1. In our case, we set “p” to 58 (or 59-1 )

If we had a math library that could exceed 256 bits we could use all of these key pairs. However, we need to eliminate some because in Ethereum (and probably our desktop calculator), they’ll cause overflows.

If our “m” (card) value can go up to 54, the largest exponent (“K”) that can be used within a 256-bit limit is 44. So no key half can be above 44.

I’m simply running through the “n” values by hand. 1,2,3,4,5,6,7,8… all the way up to 58.

So enter 1 for “n”, 58 for “p”, and click “Submit”
Then change “n” to 2, click “Submit”. etc.

I believe only ones where half of the pair is prime are valid pairs.

3,39
5,35
7,25
9,13
11,37
15,31
17,41
27,43

We also remove 1,1 and 57,57 since those will produce insecure results.

This is why the current Ethereum integration is completely insecure. There are only 8 possible keys (16 if you reverse them). Other values won’t work commutatively or will produce other unwanted results.

Let’s say our card to be encrypted, “m”, is 8, or the Seven of Spades  (2=Ace of Spades, 3=Two of Spades, 4=Three of Spades, 5=Four, 6=Five, 7=Six, 8=Seven, …)

We know that “P” is 59, meaning we can use any of the keypairs above. I’ll pick 17,41 ; which keypair do you want (it can be the same one). Note: in a real game you wouldn’t know my keypair until the end, of course!

9,13

I mentioned they can be reversed, meaning that if you used 13 for encryption and 9 for decryption, you would arrive at the same result. However, We’ll use them in the order shown to keep things neater.

So I encrypt:
(8^17) mod 59 = (2251799813685248) mod 59 = 6

Unless you know that I used the 17,41 keypair, you’d have to run through all of the possible combinations to find out how I arrived at 6.

You got it:
(6^9) mod 59

24

Since we’re the only ones “playing”, this card is now full encrypted. We’ve both applied our keys, in other words.

I am now also challenged to discover how you arrived at 24 unless I run through all the possible keypairs relative to ​_phi(P)_​.  Unfortunately, at 256-bits that’s not many.

This same math would be applied to all values: 2 through 54 (53?)

Instead of encrypting one card, I would encrypt the entire 52-card deck, and I would randomly mix/shuffle the results (otherwise you would know how the encrypted values relate to the unencrypted ones — very bad!)

Then I would send those values to you and you would similarly encrypt and shuffle all 52 values. If the encryption is strong, you won’t know what the cards are when you receive them, and I won’t know what your results are.

So now it’s safe for either of us to pick any of the possible values. Let’s say I happen to have chosen the encrypted value 24 as one of my cards. I’d want to be the last player to decrypt this card since only I should know what it is (it’s a hole/private card). I’d want to be the last player to decrypt this card since only I should know what it is (it’s a hole/private card).

So you would decrypt first. Same function, just use the other half of the keypair…
(24^13) mod 59
(876488338465357824) mod 59
= 6

I could probably skip the decryption now since I know how I produced 6, but let’s run it anyways:

(6^41) mod 59 = 8 (Seven of Spades — correct)

Okay, let’s try the commutative part because it’s important.I’ll decrypt 24 first and then you’ll decrypt. If it’s really commutative, we should also end up with 8.

(24^41) mod 59(edited)
(3.8784742299757777577469881858162e+56) mod 59 = 44
(44^13) mod 59
(2316779994178213904384) mod 59
= 8 (Seven of Spades – correct)

The commutative property applies regardless of the number of encryption/decryption operations applied (as long as all encryptions are also matched by decryptions).
Exactly, it doesn’t matter in which order the operations are applied, as long as they’re all applied.

It’s because of this that I can do the final decryption on some cards and you can do the final decryption on others, and therefore only we know which cards we’ve selected for our hole/private cards.

However, because we’ve accepted certain cryptographic parameters at the beginning, like which prime we’re using and what our “face-up” card values are, we can then use a third party to verify that all the calculations match.

As part of the game play the game client would store the selected encrypted cards in Ethereum. In the same way as other players wouldn’t know what those cards are, the contract doesn’t, but provides an irreversible ledger so that players can’t subsequently back out and claim that they selected other cards, etc.

At the end of the game we both release our keypair and can independently verify which cards were part of the game, who held them, etc. This would be done by using the math we just ran through.

If we disputed the results, we would put our verification fee into the contract, along with our keypairs, and have it decide who actually won

Ethereum can only do the math discretely in 256 bits.

What this means is that while some math libraries handle the entire ​_(m^K) mod P_​  function as one function call, in Ethereum they’re two: ​_m^K_​ and then ​_mod P_​

And the result of each discrete operation must fit within 256 bits. That means:
2^256 = 115792089237316195423570985008687907853269984665640564039457584007913129639936 (78 digits)

(This is where the other link I mentioned above comes in handy: http://www.javascripter.net/math/calculators/100digitbigintcalculator.htm)

I mentioned this limit when we were short-listing our keypairs. If our  base, “m”, can be up to 54 then the largest exponent we can use is 44:
54^44 =
16800624767756097671510862680933979548714088826208332700596506880520126201856 (77 digits)

Any number above this will be too large:
54^45 =
907233737458829274261586584770434895630560796615249965832211371548086814900224 (78 digits)

In actual usage, we will need so support a base of up to 58 (because of the modulus value), which means the largest exponent that we can use is 43. Our list, however, is still valid

The reason I say “actual usage” is that the result of a single encryption or decryption operation may produce a value in the range 0 to (P-1), or 0 to 58 in this case. The modulo operation “wraps” the input value so the ouput never equals or exceed the modulo value.

With the game client I don’t have to worry about the limits of any discrete operations because it uses an arbitrary-length integer math library (native math is only as “wide” as your device’s processor: 32-bit or 64-bit). Once Ethereum can support these operations with it’s own arbitrary-length integer library we can take the limits of the values being used.

For secure games we wouldn’t want to use values any smaller than 1024 bits.
2^1024 =
179769313486231590772930519078902473361797697894230657273430081157732675805500963132
708477322407536021120113879871393357658789768814416622492847430639474124377767893424
865485276302219601246094119453082952085005768838150682342462881473913110540827237163
350510684586298239947245938479716304835356329624224137216 (309 digits)

That means that the card, or “m”, value can be between 2 and 2^1024, the “K” value can be any number (relative to “P”) between 2 and 2^1024, and the “P” value can be any prime number between 3 and 2^1024.

As you can imagine, the results of these calculations can become astronomically large.

However, many good arbitrary-length integer math libraries can efficiently calculate with such numbers when they don’t have to be done in discrete steps. For example, ​_(m^K) mod P_​ is often implemented as a single function call.

There’s an extra little step that needs to be taken when selecting “face-up” (plaintext) card values. It turns out that if we simply select them naively as we did, (2,3,4,5,6…), they can leak some information called “quadratic residues”. You’ll probably recognize the formula that it uses: https://en.wikipedia.org/wiki/Quadratic_residue

“Plaintext” means unencrypted. The “plaintext” value for the Ace of Spades is 2. The “plaintext” value for the Two of Spades is 3. etc. Once it’s encrypted, it’s usually called ciphertext.

In a nutshell, values that are quadratic residues (mod P) as plaintext will be quadratic residues (mod P) as ciphertext. This wouldn’t tell you exactly what the cards are but depending on how the values are distributed we could learn information we shouldn’t. For example, if we knew that plaintext “m” values for red suits (Hearts and Diamonds) were quadratic residues, we would know which cards were red suits even after they were encrypted. This was first discovered by Don Coppersmith:http://link.springer.com/chapter/10.1007%2F3-540-39799-X_10#page-1

Cheating at Mental Poker

We review the “mental poker” scheme described by Shamir, Rivest and Adleman [SRA].
In the windows calculator you can do: #^#mod# without hitting = in between. Also, the keyboard shortcut for exponentiation (^) is Y

One thing I want to correct:
That means that the card, or “m”, value can be between 2 and 2^1024, the “K” value can be any number (relative to ​_phi(P)_​) between 2 and 2^1024, and the “P” value can be any prime number between 3 and 2^1024

​_should be_​

That means that the card, or “m”, value can be between 2 and 2^1024 ​*but smaller than “P”*​, the “K” value can be any number (relative to ​_phi(P)_​) between 2 and 2^1024, and the “P” value can be any prime number between 3 and 2^1024

The reason that this number has to be smaller is because ​_mod P_​ “wraps” the value so that the result will never be larger than “P”.

Which means you can’t reproduce the original “m” value.

So there were two things that I kind of glossed over last time: how to generate the modular multiplicative inverse (encryption/decryption keys), and how to choose safe values for cards.

I realize I didn’t adopt any standards in my previous explanation so going forward, “P” is the prime number (59 in our case), and “p” is ​_phi(P)_​ (or P-1 which equals 58 in our case).

If the prime number is 7, phi(P) is 6. If the prime number is 3, phi(P)=2.

So to generate our keys we find what are called a “modular multiplicative inverse” of some chosen values. The way to do this is to solve the following:
(a*b) mod p = 1

When the numbers are small we can calculate this by hand. Again, your standard desktop calculator will do.

So if we start with 2 for the value of “a”:
(2*b) mod 58 = 1

…we can start running through all the possible values of “b” up to and including 58 to see if there’s any value that will produce the result 1.

function modInverse(a, m) {
for(var x = 1; x < m; x++) {
if(((a*x) % m) == 1) {
return (x);
}
}
}

You can try it out on jsFiddle here: https://jsfiddle.net/z4f1bLad/

What this function does is set the value for “a”, and “m” should actually be “p”…
Just click run

You should get 39 as the answer.

At the bottom is where you enter the “a” and “p” values: cons.log(modInverse(3 ,58));

The script simply runs through all of the possible values of “b” to see if one produces a 1:  if(((a*x) % m) == 1) {

And here too, “x” should be “b”

Here’s the example again using the notation I started with: https://jsfiddle.net/z4f1bLad/1/

This returns the value for “b” in:
(a*b) mod phi(P)=1

If you set a=2, the result will be undefined since 2 has no modular multiplicative inverse. In the jsFiddle example, a=3 and its inverse is 39.

That means that our encryption key can be 3 and decryption key can be 39. Or we can use 39 to encrypt and 3 to decrypt.

The reason that both work is because they’re used as the exponent in the encryption/decryption function they will return the original plaintext (unencrypted) value of “m” – in the case of CypherPoker the index of the card (2=Ace of Spades, 3=Two of Spades, etc.)

It’s a lot like saying: if it’s 2 o’clock, how many hours do I need to add to get to 12?

You could say that if you’re trying to produce 0 around a clock with 12 divisions, 2 has a modular multiplicative inverse of 10.

Not exactly, but close enough :

The % operator in the JavaScript function performs the same operation, but instead of an analog clock with 12 divisions we have one with phi_p divisions. Anyhow, it’s called modulo/modulus/clock math and there are many more complicated flavours.

You can of course try other values for phi_p in the function too. It must be P-1, or a prime number minus 1.

So now that we can generate an encryption/decryption keypair relative to a chosen ​_phi(P)_​ (which we agree on before the start of the game), we can use them to encrypt data using:
(m^K) mod P

For P=59 (therefore ​_phi(P)_​=58), we can use the keypair 3,39 (the JavaScript function will confirm this :simple_smile: )

So to encrypt our Ace of Spades (2), we would calculate:
(2^3) mod 59
= 8

The next player would use P=59 (​_phi(P)_​=58) to find their own encryption/decryption key pair and would encrypt my result (8)

And the underlying math makes sure that we can return back to our starting value (2 – the Ace of Spades) by decrypting with both players’ keys.

If you follow the steps correctly the math should always work. The only thing we’d want to do in real-world usage is to use those really big numbers I’d mentioned instead of the small ones we’re using in these examples.

This function will always produce either a -1, 0, or a 1.
Because we’re using only positive integers, we will wither get (P-1), 0, or 1
So for example, let’s take out Ace of Spades…

First let’s re-write the thing to make it easier to read.
since P = 59
_phi(P)_/2 = 58/2 = 29
Since m=2:
(2^29) mod 59 = 58(edited)

That produces 58 (P-1). This means that 2 is a “quadratic non-residue mod P”
Recall that I had encrypted the Ace of Spades to produce 8. If we plug it into the calculation we get:
(8^29) mod 59 = 58

Even after the value has been encrypted we can tell that it’s a quadratic non-residue!

What if I encrypt 8 with another keypair relative to ​_phi(P)_​?

Let’s try 25,7 (jsFiddle: cons.log(modInverse(25,58)))

Encrypting:
(8^25) mod 59 = 33
Let’s see if 33 is a quadratic non-residue too…
(33^29) mod 59 = 58
Sure enough, it’s still a quadratic non-residue.

This is very bad. If we know that the Ace of Spades is a quadratic non-residue then we can simply run the above calculations on any encrypted cards that you’ve selected. It doesn’t give us perfect knowledge but it can give us a strong advantage.

Another example with the Two of Spades (index 3)…
(3^29) mod 59 = 1
This result means that 3 is a quadratic residue mod 59.
I’ll encrypt it with my keypair 25,7 – except I’ll use 7 to encrypt this time:
(3^7) mod 59 = 4
Is 4 a quadratic residue mod 59?
(4^29) mod 59 = 1

Yes it is! And this would be true of ​*all*​ cards encrypted.

What makes this problem worse is that quadratic residues/non-residues aren’t evenly spaced like even number/odd number. You can get brief runs of quadratic residues with a single non-residue.

So whole sections of the deck could be “marked”, if you will.

Think about it as being able to tell which cards are red or black ​*after*​ they’ve been encrypted (face-down). The problem isn’t quite this straightforward but it’s a good analogy.

Each player both gets to pick their own face-down cards and sees which face-down cards are chosen by other players. We may not be able to tell exactly what those cards are but we could, in this analogy, be able to “see” which ones are red and which ones are black.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s