Eric Marcarelli

Software Developer, Writer, Painter

A Fair Game of Blackjack between Two Players

August 08, 2010 by in Projects, Technology

It is possible for two players to use cryptographic techniques to play a fair game of Blackjack without having to trust the other player or use a trusted intermediary. The cards a player receives are random and at the end of the game both players are able to confirm that the other player’s score accurately reflects the other player’s cards. I will begin with a general discussion of the technique, then move into an examination of the program that implements it. Logs from an example game and the code for the project are included at the end.

Although both players are involved in dealing cards, it was useful to make a distinction between the “dealer” and “player” in the program, so for consistency I will use that terminology in the general description. The dealer and player begin by agreeing on a large prime p. In my implementation the dealer simply generates one and sends it to the player. The dealer then calculates an ά value such that gcd(ά,p-1) is 1 and the player similarly calculates a β value such that gcd(β, p-1) is 1. Each also calculates its ά or β inverse mod p. The player uses its β value to encrypt each card in the deck by raising it to the β power mod p, then shuffles the deck and sends it to the dealer. The dealer has no way of quickly determining which encrypted value corresponds to each card, so it is fair for the dealer to now select any of those cards to send back to the player.

The first set of cards the dealer sends back are encrypted by raising them to the ά power mod p. This ensures that the player is not able to determine which cards the dealer will be getting. The player uses its β inverse to undo its half of the encryption and sends the cards back to the dealer. The dealer then selects two more cards and sends them without additional encryption. Each player can now remove its encryption and see its cards. After each player receives its cards and the round ends the players exchange ά and β values so they can confirm that the other player actually received the cards it claimed to have.

In writing the example program I simplified some of the cryptographically insignificant aspects. Rather than using direct socket connections, I created the following system. Each player generates a random integer that serves as its unique identifier (uid). I set up a table in a mySQL database to store messages, and wrote PHP scripts to get and send messages to this database. To send a message to another client, the sender only needs to construct and load the URL:

http://blackjack.alderforest.org/send_message?uid=&msg=

Similarly, to retrieve a sent message one uses the get_message.php script with the uid parameter. The system is not efficient but it has its advantages. Java makes retrieving data from the web in this way simple and testing the program was also easier than it otherwise would have been.

The rules of blackjack are also simplified in the program. Only one round is played, and each player gets exactly two cards every time. Unlike in a real game, the dealer gets the first set of cards and players get both of their cards at the same time instead of alternating. Also note that the program is non-interactive. It is started from the command line using one of two options: dealer, which will start the game as the dealer and await a connection, or providing a uid, which starts the game as a player and attempts to connect to a dealer with that uid. Once the program is started it is fully automated and will respond to input from the other player by taking the next necessary action.

The program is made up of two classes: BlackJack and Game. There is not a clearest line of distinction between the functions of the two classes, but in general BlackJack takes care of the actions of the game and Game handles the program flow and inputs. BlackJack stores the deck, p, ά, inverse of ά, and other data related to the game, and has a number of methods related to operations on that data. The Game class has main, play (which serves as the game loop), sendMessage, and getMessage. The program makes use of BigInteger throughout, which greatly simplified the code necessary to do the math.

The regular deck is stored as an array of fifty two ints. The starting values of the cards are arbitrary, and both players know them. Trappe and Washington encoded each card based on the letters in its name, but this seemed unnecessary and my system simply uses random eight digit numbers.

private int[] deck = { 
	83457934, 64564563, 23098538, 43985794, 43099738, 39089478, 34587989, 
	49387567, 95073848, 13980397, 34928765, 46732865, 23768564,  // hearts
	58638745, 23576725, 29865747, 43568275, 25687293, 23758979, 25687538, 
	23049792, 23874582, 12984908, 45982639, 10293897, 98763482,  // diamonds
	98563847, 32560234, 98560239, 84796325, 80470326, 98756240, 69573264, 
	56325761, 23059817, 49484031, 98276456, 21305968, 53098127,  // clubs
	10928734, 68592487, 13897865, 42314568, 97087426, 54233746, 39824781, 
	59328741, 24691253, 75218738, 46051982, 73513287, 45682763}; // spades
}

The encrypted card values are stored in the BigInteger array encDeck. There are several methods to determine the value and name of cards, and calculate score based on a user’s two cards. For example, to determine a card’s numeric value:

public int cardValue(int c) {		
	int ret = -1;
	for (int i = 0; i < deck.length; i++) {
		if (c == deck[i]) 
			ret = (i+2)%13;				
	}
		
	if (ret > 10 || ret == 0)
		ret = 10;
	
	return ret;
}

When determining the score, an ace is given a value of eleven unless a player has two aces, which is the only case that would put the score over twenty one.

When a dealer starts a game it will generate a p value along with (p-1) using the following method:

public void generateP() {
	p = BigInteger.probablePrime(128, new Random());
	pMinus1 = p.subtract(BigInteger.ONE);
}

After p is generated it will select a value for ά. To determine an ά it simply tries a random large prime and checks to make sure gcd(ά, p-1) is 1. After ά is selected, the inverse of ά is also calculated.

public void generateAlpha() {	
	do
		alpha = BigInteger.probablePrime(128, new Random());	
	while (alpha.gcd(pMinus1).toString().compareTo("1") != 0);
}

public void computeAlphaInverse() {
	alphaInv = alpha.modInverse(pMinus1);
}

Once these values are set, the dealer waits for a player to connect. A player can establish a connection by sending a message that is just that user’s uid. After a connection is established both players enter a loop that continues to retrieve and parse messages from the other player until the round ends.

The connection message format is unique within the program. Other messages are in the form [:value]*, that is, a command name followed by values separated with colons. After a connection is established, the dealer sends p to the player and the player calculates its own ά and ά inverse.

sendMessage("p:"+blackjack.getP());

The player now prepares the deck by raising each of the card values to ά power mod p, and shuffles the cards by swapping positions in the encDeck array 10,000 times. The player sends the encrypted deck of cards to the dealer.

public void encryptDeck() {
	BigInteger tmp;
	for (int i = 0; i < deck.length; i++) {
		tmp = new BigInteger(String.valueOf(deck[i]));
		encDeck[i] = tmp.modPow(alpha, p); 
	}
}

sendMessage("deck:"+blackjack.getEncDeckStr(":"));

public void setEncryptedDeck(String[] d) {
	deckCounter = 0;
	
	// start at 1 because the first element of d will be "deck"
	for (int i = 1; i < d.length; i++) {
		encDeck[i-1] = new BigInteger(d[i]); 
	}
}									

The dealer receives this data when it parses the deck command. It sets its encDeck, and reshuffles the deck. The players are now set up to play a hand of blackjack.

To deal its hand the dealer selects two cards, uses its ά value to encrypt them, and sends these cards to the player.

sendMessage("dealercards:" + 
	blackjack.encryptCard(blackjack.getCard()) 
	+ ":" + blackjack.encryptCard(blackjack.getCard()));

public BigInteger encryptCard(BigInteger c) {
	return c.modPow(alpha, p); 
}

When the player receives this message it decrypts the cards by raising the values to the ά inverse power mod p, and sends those cards back to the dealer. The dealer will now be able to determine what its cards are, but at this point it would still be computationally difficult for the player to determine the dealer’s cards. The player saves the dealer’s cards so that they can be verified later when the dealer’s ά inverse value is disclosed.

otherCard1 = blackjack.decryptCard(new BigInteger(input[1]));
otherCard2 = blackjack.decryptCard(new BigInteger(input[2]));
sendMessage("yourcards:"+otherCard1+":"+otherCard2);		

When the dealer receives its cards it sends two more cards to the player, unencrypted. This is the player’s hand. It also saves these for confirmation later.

Both players now have their cards. They determine the values of the cards and their score. Each player sends their score to the other along with their ά inverse values. Each player uses the other’s ά inverse to decrypt the opponent’s cards. The score of these cards is calculated and compared to the score that the other user reported to verify that they did not cheat. Because of the simplified rules, it is not possible for either player to have exceeded twenty one. The player with the higher score wins, unless there is a tie, in which case the dealer wins. The players were thus able to play a fair round of blackjack without either having to trust that the other was telling the truth at any point.

Log of the Dealer’s Game

$ java Game dealer
1402256783
Generating P and Alpha, and computing Alpha Inverse.
-----
P: 290485332089682301714110312272926253351
P-1: 290485332089682301714110312272926253350
Alpha: 176571867822716636338490137726779129241
Alpha Inverse: 33620151711669712150920678878391484661
-----
Waiting for player...
Got connection: 2046062213
Sending P to player
Sent: p:290485332089682301714110312272926253351
Got: deck:59093244672239728140469484469130050481:2320232767
3030560710000320389503534563:15311051146064217241412929522
7991192284:76128218097314543181091832994089824313:15078371
6762367498000836904828120820269:28467149879680578580612430
3730164355310:157357057504283169451798080191057097954:1879
02163045452481090378414010811147243:1240104398737619699921
0753283008773270:146973312153212475780531882334295503256:2
18860007019913818884415417030532029845:1438455171938972229
86997677742117824300:1320349693199257332978573973729429055
81:228818953534344157529180669859753110495:665880648447202
6102790613722064762034:21060586000448285953851940245228650
5282:3819202820270131992374987774944204322:643324667762565
8098101525181353854505:26433515153016711017077299221133957
5686:253488762809607855632055189510490399584:2304730043566
51571151196678790331343703:6938248639646706660361919024717
6001017:19809499069415653548531819109162159192:26517205461
2866286381372119736736508079:89159277393657512386480729933
422586523:131191876506237903323816223057719911811:23124946
2760780636418746247497673693384:18718379842059473552937326
201582006998:97621106010121420281308091253729025522:230905
408996826057853249995510244037838:125972447433013963621122
108211987318389:263200498393215695036647654785098286568:69
846090608212505723503290698288613394:286464759820428006553
496133884925215582:37743751254208265560330474862396964403:
99393865183517878278594404203517930415:1193586898455732309
46702688632291531364:1599503787015354984866545983703327863
18:202051535380360940978258924096151333948:605624265500043
69168846430481344564825:1777145335624999251322112706731318
70985:251785163798821909935786197523703279366:59055600202
635163559059826520836411139:43409694362192924259312884154
483115263:178004260446695288189704415714298194008:9384319
9955404181397889838060664800373:2255496870169058608804785
35069176955248:240504257683866949753862043531388262794:10
0979714196289755600021401388674991554:2283750083667689084
14334168427551138520:290020087765985304012577749496890240
281:283482747135095725126984046467774082953 (53)
Received deck.
Reshuffle the deck.
Select top two cards, encrypt them, and send.
Sent: dealercards:80186339648626151745475658741642476166:23872970
2001192223656089792929723584992
Got: yourcards:138815687569834880995285013235085961685:198881448
678562787197364062905930606134 (3)
Your cards are: 
	49484031
	25687293
	Jack of Clubs
	6 of Diamonds
Your score: 16
Send the player's two cards.
Sent: yourcards:119358689845573230946702688632291531364:177714533
562499925132211270673131870985
Got: myscore:12:88463238332629290275682852149939034449 (3)
The other player claims their score is: 12
The other player's score should be: 12
You win.
Sent: myscore:16:33620151711669712150920678878391484661

Log of the Player’s Game

$ java Game 1402256783
2046062213
Sent: 2046062213
Connecting to: 1402256783
Got: p:290485332089682301714110312272926253351 (2)
Received p. Generating alpha and computing alpha inverse.
-----
P: 290485332089682301714110312272926253351
P-1: 290485332089682301714110312272926253350
Alpha: 277143322521614513293683805691059305799
Alpha Inverse: 88463238332629290275682852149939034449
-----
Encrypt and shuffle the deck.
Send the deck to the dealer.
Sent: deck:59093244672239728140469484469130050481:2320232767303
0560710000320389503534563:153110511460642172414129295227991192
284:76128218097314543181091832994089824313:1507837167623674980
00836904828120820269:284671498796805785806124303730164355310:1
57357057504283169451798080191057097954:18790216304545248109037
8414010811147243:12401043987376196999210753283008773270:146973
312153212475780531882334295503256:2188600070199138188844154170
30532029845:143845517193897222986997677742117824300:1320349693
19925733297857397372942905581:22881895353434415752918066985975
3110495:6658806484472026102790613722064762034:2106058600044828
59538519402452286505282:3819202820270131992374987774944204322:
6433246677625658098101525181353854505:264335151530167110170772
992211339575686:253488762809607855632055189510490399584:230473
004356651571151196678790331343703:6938248639646706660361919024
7176001017:19809499069415653548531819109162159192:265172054612
866286381372119736736508079:8915927739365751238648072993342258
6523:131191876506237903323816223057719911811:23124946276078063
6418746247497673693384:18718379842059473552937326201582006998:
97621106010121420281308091253729025522:23090540899682605785324
9995510244037838:125972447433013963621122108211987318389:26320
0498393215695036647654785098286568:698460906082125057235032906
98288613394:286464759820428006553496133884925215582:3774375125
4208265560330474862396964403:993938651835178782785944042035179
30415:119358689845573230946702688632291531364:1599503787015354
98486654598370332786318:20205153538036094097825892409615133394
8:60562426550004369168846430481344564825:177714533562499925132
211270673131870985:251785163798821909935786197523703279366:590
55600202635163559059826520836411139:43409694362192924259312884
154483115263:178004260446695288189704415714298194008:938431999
55404181397889838060664800373:22554968701690586088047853506917
6955248:240504257683866949753862043531388262794:10097971419628
9755600021401388674991554:228375008366768908414334168427551138
520:290020087765985304012577749496890240281:283482747135095725
126984046467774082953
Got: dealercards:80186339648626151745475658741642476166:2387297020011
92223656089792929723584992 (3)
Received dealer's two cards. Decrypt and send back to dealer.
Sent: yourcards:138815687569834880995285013235085961685:198881448678
562787197364062905930606134
Got: yourcards:119358689845573230946702688632291531364:177714533562
499925132211270673131870985 (3)
Your cards are:
        32560234
        56325761
        3 of Clubs
        9 of Clubs
Your score: 12
Sent: myscore:12:88463238332629290275682852149939034449
Got: myscore:16:33620151711669712150920678878391484661 (3)
The other player claims their score is: 16
The other player's score should be: 16
You lose.

View the source for this project.

About the Author:

Leave a Comment!

You must be logged in to post a comment.