Bob and Alice Play Mental Poker In a World Where They Trust No-one

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…

Bob and Alice Play Mental Poker In a World Where They Trust No-one

We have a major competition … it’s Bob playing Alice in the greatest game of poker ever created. But neither Bob nor Alice trusts 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 Adleman) 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.

2. Alice then randomly sends the ciphertexts back to Bob.

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

4. Now for Bob to get his cards. Bob now picks five cards and encrypts them with:

Cb = Cj^{e2} (mod N)

5. He sends them back to Alice. Alice then decrypts the ciphertexts and sends them 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 that 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?

With Commutative encryption, we can decrypt the keys in any order. Normally we would encrypt with Bob’s key and then encrypt with Alice’s key, and then we must decrypt with Alice’s key and then Bob’s. In Commutative encryption, we can decrypt in any order. To make RSA use Commutative encryption, Bob and Alice must share a common value of N and which is p×q, and choose different values for their encryption key (e).

In the following, Alice selects an e value of 65,539 and Bob selects and e of 65,537. They then determine their decryption key as the inverse of e (mod N). In order to stop Bob from decrypting without Alice’s key, the value of e will be kept secret. The Python code is [here]:

from Crypto.Util.number import *
from Crypto import Random
import Crypto
import gmpy2
import sys
bits=128
msg="Hello"
if (len(sys.argv)>1):
        msg=str(sys.argv[1])
if (len(sys.argv)>2):
        bits=int(sys.argv[2])
p = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
q = Crypto.Util.number.getPrime(bits, randfunc=Crypto.Random.get_random_bytes)
n = p*q
PHI=(p-1)*(q-1)
# RSA Encrytion keys
e_bob=65537
d_bob=(gmpy2.invert(e_bob, PHI))
e_alice=65539
d_alice=(gmpy2.invert(e_alice, PHI))
m=  bytes_to_long(msg.encode('utf-8'))
c1=pow(m,e_bob, n)
c2=pow(c1,e_alice, n)
d1=pow(c2,d_alice, n)
d2=pow(d1,d_bob, n)
print "Message=%s\np=%s\nq=%s\nN=%s\n\n\n" % (msg,p,q,n)
print "First Bob encrypt, Alice encrypt, Alice decrypt, Bob decrypt"

print "Bob key: d=%d, e=%d\nAlice key: d=%d, e=%d" % (d_bob,e_bob,d_alice,e_alice)
print "Cipher1=%s\nCipher2=%s\nDecipher1=%s\ndecipher=%s" % (c1,c2,d1,(long_to_bytes(d2)))

print "\nCommutative Encryption: First Bob encrypt, Alice encrypt, Bob decrypt, Alice decrypt"
c1=pow(m,e_bob, n)
c2=pow(c1,e_alice, n)
d1=pow(c2,d_bob, n)
d2=pow(d1,d_alice, n)

print "Bob key: d=%d, e=%d\nAlice key: d=%d, e=%d" % (d_bob,e_bob,d_alice,e_alice)
print "Cipher1=%s\nCipher2=%s\nDecipher1=%s\ndecipher=%s" % (c1,c2,d1,(long_to_bytes(d2)))

A sample run [here]:

Message=hello
p=852651907763499317
q=745812510383943157
N=635918459812753777283846407136323769
First Bob encrypt, Alice encrypt, Alice decrypt, Bob decrypt
Bob key: d=194849910607746899759497012693375121, e=65537
Alice key: d=70996130097345387886448374455387547, e=65539
Cipher1=346276951573470476021462919534734952
Cipher2=418870736775912205351176794223088302
Decipher1=346276951573470476021462919534734952
decipher=hello
Commutative Encryption: First Bob encrypt, Alice encrypt, Bob decrypt, Alice decrypt
Bob key: d=194849910607746899759497012693375121, e=65537
Alice key: d=70996130097345387886448374455387547, e=65539
Cipher1=346276951573470476021462919534734952
Cipher2=418870736775912205351176794223088302
Decipher1=375365820304942084768113672994830918
decipher=hello

Conclusions

Commutative encryption let’s you put the keys on and off in any order. The method I have outlined is weak, though, as e must be kept secret, and we Bob might be able to discover the e value that Alice has used. And what kind of trust to we have on the Internet. Well, it’s normally PKI, and the major flaw is that we must trust a certificate authority.