The Big Game — but Bob and Alice just don’t trust each other or, in fact, anyone: The Mental Poker…

We have a major competition … it’s Bob playing Alice in the greatest game of poker ever created. But neither Bob nor Alice trust each other…

The Big Game — but Bob and Alice just don’t trust each other or, in fact, anyone: The Mental Poker Problem

We have a major competition … it’s Bob playing Alice in the greatest game of poker ever created. But neither Bob nor Alice trust each other to deal, as they think the other one will cheat, and they don’t trust anyone else, as each of the dealers selected has some bias towards Bob or Alice.

So how do we deal five cards to each of them so that there are no doubles in their hands, and that Bob and Alice cannot determine what is in each other’s hand?

For this we need the SRA (Shamir, Rivest and Aldeman) algorithm for commutative encryption, and where we can encrypt in any order and decrypt in any order:

Enc(K2,Enc(K1,message) = Enc(K1,Enc(K2,message)

So let’s deal

First Alice and Bob share the 52 cards (M1, M2, …, M52) and a modulus value of N=pq, p, and q (where p and q are the two prime numbers selected). Alice uses her key pair of [e1,d1] and Bob has a key of [e2,d2].

Now we perform the following:

  • Alice encrypts all the cards M1, M2, …, M52 with her key, using:

Cj=Mj^{e1} (mod N) for 1≤j ≤52.

Alice then randomly sends the ciphertexts back to Bob.

  • Bob picks five of the ciphertexts and identifies these as Alice’s hand and sends them back to Alice. Alice then decrypts them, and she has her hand.

Now for Bob to get his cards:

  • Bob now picks five cards and encrypts them with:

Cb = Cj^{e2} (mod N)

  • He sends them back to Alice. Alice then decrypts the ciphertexts and sends to Bob, and Bob then decrypts with his decryption key (d2) and he now has his hand.

So let the poker game start!

But how do we get e1, d1 and e2, d2?

With maths, operators such as multiplication are commutative, such as:

3 x 5 x 4 = 4 x 5 x 3

In encryption, most operations are non-commutative, so we need to modify the methods. One way is to use RSA, but generate two keys which have shared p, q and N values. So we generate Bob and Alice’s keys using the same two prime numbers (p and q), so that they share the same N value (modulus).

So let’s start with Bob:

Let’s select: P=7, Q=13

The calculation of n and PHI is:

N = 7 x 13 = 91
PHI = (P-1)(Q-1) = 72

We need to make sure that our encryption key (e) does not share any factors with PHI (gcd(PHI,e)=1). We can select e as:

e = 5

Next we can calculate d from:

(d x 5) mod (72) = 1

One answer is 29 [Solve]

d= 29, e=5, N=91
Encryption key [91,5]
Decryption key [91,29]

Now for Alice. We have

N = 7 x 13 = 91
PHI = (P-1)(Q-1) = 72

We can select e as (and should not share any factors with PHI):

e = 7

Now we must solve:

(7 x d) mod (72) = 1

For this we get 31 [here]

Alice’s keys are then:

d= 31, e=7, N=91
Encryption key [91,7]
Decryption key [91,31]

So prove it?

So let’s prove that we can implement commutative encryption. The code I’ll use is:

When I run this we get:

A -> B -> B -> A: 5
A -> B -> A -> B: 5

and it works!

A calculator to prove this is here.

Here are five examples:

  • e1=”5", d1=”29",e2=”7",d2=”31",N=”91",message=”5" [Ex 7] Try!
  • e1=”5", d1=”29",e2=”7",d2=”31",N=”91",message=”15" Try!
  • e1=”79", d1=”1019",e2=”11",d2=”1171",N=”3337",message=”15" [Ex 4] Try!
  • e1=”3", d1=”7",e2=”11",d2=”11",N=”33",message=”5" [Ex 1] Try!
  • e1=”7", d1=”503",e2=”13",d2=”677",N=”943",message=”20" [Ex 5] Try!

Conclusions

We have created an Internet where trust is required, but it is currently failing as no-one really can be trusted on the Internet. With PKI we have trusted certificate authorities, but can we really trust Verisign to prove ever singly entity that it has signed for? Also, what if Verisign was to have their private key stolen? Whom do we trust then? The method I’ve outlined assumes that you cannot trust anyone.