Mental Poker (with code in Rust)

Dealing Cards With Nobody You Trust

Two people want to play poker over the phone. There is no table, no deck, and crucially no dealer either of them is willing to trust with the shuffle. Whoever controls the cards controls the game, so handing that power to one side is a non-starter. Handing it to a third party just moves the problem. The question that Shamir, Rivest, and Adleman asked in 1979 was deceptively simple: can two mutually suspicious players shuffle and deal a deck so that the game is provably fair, with no referee anywhere in the loop?

The answer is yes, and the trick is a particular kind of encryption that does not care about the order in which you apply it. Once you have that, the whole protocol falls out of it. You can shuffle a deck that neither player can read, deal cards that only the recipient can see, and prove afterward that nobody cheated. All of it runs on arithmetic small enough to fit in this post.

Why a normal lock will not work

Think about what a dealer actually does. They take a known, ordered deck, scramble it into an order nobody can predict, and then hand out cards face down so each player sees only their own. To remove the dealer, both players have to perform the shuffle together in a way that neither can bias and neither can peek at.

The instinct is to reach for encryption. Alice locks the deck in a box, Bob cannot see inside, problem solved. But ordinary encryption fails here in a subtle way. If Alice encrypts the deck and Bob encrypts it again on top, you now have a box inside a box. To open it you must remove Bob’s lock first, then Alice’s, in strict reverse order. That ordering is exactly what we cannot afford, because dealing a card to Alice means stripping away only Bob’s lock while leaving hers intact. With nested locks, Bob’s removal would expose Alice’s lock to Bob in the wrong sequence, and the whole scheme tangles.

What we need is encryption where the locks behave like a pile of keys on a ring rather than a stack of boxes. Any lock can come off in any order, and the result is the same. That property has a name: commutativity.

Commutative encryption from a single exponent

Here is the entire cryptographic engine. Pick a large prime p that both players agree on in public. A player’s secret key is a number e chosen so that it has no common factor with p - 1. To encrypt a message m, you raise it to that power modulo the prime:

// encryption: c = m^e mod p
// decryption: m = c^d mod p, where e * d ≡ 1 (mod p-1)

Encryption is exponentiation. And exponentiation commutes, because raising to a power and then another power just multiplies the exponents:

(m^a)^b = m^(a*b) = m^(b*a) = (m^b)^a   (mod p)

That single line is the whole reason mental poker works. If Alice encrypts with her exponent a and Bob encrypts the result with his exponent b, the doubly-locked card is m^(a*b). Bob can remove his lock by applying his decryption exponent, and what remains is m^a, a card still sealed under Alice’s key, regardless of the fact that Bob locked it second. The locks are keys on a ring.

The decryption exponent d is the modular inverse of e with respect to p - 1. By Fermat’s little theorem, exponents on the multiplicative group modulo p wrap around every p - 1 steps, so choosing d such that e * d ≡ 1 (mod p-1) guarantees that encrypting and then decrypting returns you to the original m. Finding that inverse is a job for the extended Euclidean algorithm, which we will need in code anyway.

const P: u128 = (1 << 61) - 1; // a Mersenne prime, 2^61 - 1

fn powmod(mut base: u128, mut exp: u128) -> u128 {
    base %= P;
    let mut result = 1u128;
    while exp > 0 {
        if exp & 1 == 1 {
            result = (result * base) % P;
        }
        base = (base * base) % P;
        exp >>= 1;
    }
    result
}

The prime 2^61 - 1 is a deliberate choice for a teaching example. Both factors in any multiplication stay below 2^61, so their product stays below 2^122 and never overflows a u128. A production system would use a prime hundreds of digits long, but the arithmetic would be identical, just wrapped in a bignum library. The logic does not change when the numbers grow.

A key pair per player

A player is nothing more than a name and a pair of exponents. Generating the pair means picking a random e coprime to p - 1 and computing its inverse:

struct Player {
    name: &'static str,
    e: u128, // encryption exponent
    d: u128, // decryption exponent, the inverse of e mod (p-1)
}

impl Player {
    fn new(name: &'static str, rng: &mut impl Rng) -> Self {
        let phi = P - 1; // the order of the multiplicative group mod P
        loop {
            let e = rng.random_range(3..phi) | 1; // odd candidate
            let (g, _, _) = egcd(e as i128, phi as i128);
            if g == 1 {
                let d = inverse(e, phi);
                return Player { name, e, d };
            }
        }
    }

    fn encrypt(&self, card: u128) -> u128 { powmod(card, self.e) }
    fn decrypt(&self, card: u128) -> u128 { powmod(card, self.d) }
}

The loop keeps drawing candidates until it finds one coprime to p - 1. Most odd numbers qualify, so it rarely runs more than once or twice. The egcd helper is the extended Euclidean algorithm, and inverse uses it to solve e * d ≡ 1:

fn egcd(a: i128, b: i128) -> (i128, i128, i128) {
    if b == 0 {
        (a, 1, 0)
    } else {
        let (g, x, y) = egcd(b, a % b);
        (g, y, x - (a / b) * y)
    }
}

fn inverse(e: u128, m: u128) -> u128 {
    let (_, x, _) = egcd(e as i128, m as i128);
    (((x % m as i128) + m as i128) % m as i128) as u128
}

Notice that the two players never share these keys. Alice’s a stays with Alice, Bob’s b stays with Bob, for the entire game. That secrecy is what keeps each side honest, and it is also why a card sealed under the other player’s key is genuinely unreadable to you: you would need their secret exponent to peel that layer, and you never get it.

Encoding the cards safely

Before anything can be encrypted, the 52 cards have to become numbers. The naive choice is to call the cards 0 through 51, but exponentiation has an embarrassing property: it preserves whether a number is a perfect square modulo p. Roughly half the numbers below p are squares, called quadratic residues, and half are not. Since (m^e) is a square exactly when m is, a player can test any ciphertext for square-ness and learn one full bit about the hidden card without ever decrypting it. Over a deck, that leakage is enough to break the secrecy we are trying to build.

The fix is clean. Encode every card as a number that is already a perfect square, so the residue test tells an attacker nothing because the answer is always yes:

fn encode(card: usize) -> u128 {
    let r = (card as u128) + 2; // avoid 0 and 1, which are fixed points
    (r * r) % P                 // every encoding is a quadratic residue
}

Squaring the card index guarantees a quadratic residue, and the values stay distinct, so a public lookup table can map any recovered plaintext back to a card. Players agree on this encoding in the open before the shuffle, the same way they agree on the prime. The honesty of the game does not depend on hiding it.

The shuffle, layer by layer

With the engine in place, the protocol is short. The two phases are shuffling, where the deck becomes unreadable and unordered, and dealing, where individual cards are surfaced to exactly one player.

In code the shuffle phase is two maps and two shuffles:

let plain: Vec<u128> = (0..52).map(encode).collect();

// Alice encrypts everything, then hides the order.
let mut deck: Vec<u128> = plain.iter().map(|&c| alice.encrypt(c)).collect();
shuffle(&mut deck, &mut rng);

// Bob encrypts the already-encrypted cards, then hides the order again.
let mut deck: Vec<u128> = deck.iter().map(|&c| bob.encrypt(c)).collect();
shuffle(&mut deck, &mut rng);

After this runs, the deck is a vector of 52 numbers of the form m^(a*b). Alice cannot read any card, because each is still wrapped in Bob’s key. Bob cannot read any card either, because each is still wrapped in Alice’s. And neither knows the final order, because each applied a shuffle the other never saw. The deck is genuinely scrambled, and it took two suspicious parties working in sequence to scramble it, with no trusted dealer anywhere.

Dealing a card to exactly one player

This is where commutativity earns its keep. To give the top card to Alice, Bob applies his decryption exponent and hands the result over. That single operation peels off Bob’s layer and nothing else. What remains is m^a, a card sealed under Alice’s key alone. Bob never sees the face value, because to read it he would need Alice’s secret a. Alice then peels her own layer and reads the card.

Dealing a card to Bob is the mirror image: Alice strips her layer first, leaving m^b that only Bob can open. The protocol is symmetric, and the same commutative identity makes both directions work without either player ever exposing a key.

for _ in 0..5 {
    // One card to Alice: Bob strips his layer, Alice strips hers.
    let for_alice = bob.decrypt(deck[top]);
    let card = decode[&alice.decrypt(for_alice)];
    hands.entry("Alice").or_default().push(card);
    top += 1;

    // One card to Bob: Alice strips her layer, Bob strips his.
    let for_bob = alice.decrypt(deck[top]);
    let card = decode[&bob.decrypt(for_bob)];
    hands.entry("Bob").or_default().push(card);
    top += 1;
}

Run the program and it deals two five-card hands:

Alice: 7♦ 5♦ A♠ K♦ 8♣
Bob: 3♣ A♣ 6♦ 6♠ 5♥
All 10 dealt cards are distinct: the shuffle was a clean permutation.

The final assertion matters more than it looks. Because both players encrypted with invertible keys and both shuffles were genuine permutations, the dealt cards must all be distinct. If either side had tried to inject a duplicate or corrupt the deck, the recovered plaintexts would collide or fail to decode, and the check would fire. The deck’s integrity is self-verifying.

What the keys-on-a-ring picture really buys you

Strip away the modular arithmetic and the lesson is about structure. Ordinary encryption nests like boxes, and nesting forces an order of operations that a multi-party protocol cannot tolerate. Commutative encryption flattens that nesting into a set of independent locks, and independence is what lets two parties each contribute a layer that the other can later remove on demand, in whatever order the game requires.

That same shape shows up well beyond card games. Secure multi-party computation, threshold cryptography, and anonymous credential systems all lean on operations that compose without caring about order. Mental poker is the friendliest place to meet the idea, because the stakes are concrete and the whole protocol fits on a screen. Once the keys-on-a-ring picture clicks, the rest of the field reads as variations on it.

The honest caveat is that this is the 1979 protocol in its teaching form. It assumes both players follow the steps and only tries to keep them from seeing each other’s cards. A real implementation hardens it with zero-knowledge proofs that each shuffle was a true permutation, so a player cannot quietly swap an ace into their own hand and prove nothing went wrong. The cryptographic core, though, the commutative exponent that lets locks come off in any order, is exactly what you just ran.

Take the code and break it. Try dealing the whole deck and confirming all 52 cards appear exactly once. Swap the safe encoding for the naive 0..51 version and watch the quadratic-residue leak reappear if you test for it. Add a third player and see how the encrypt-shuffle-encrypt chain extends to three keys instead of two. The protocol scales the way the multiplication of exponents does, which is to say it just keeps working.

The full, compilable implementation lives in this gist.

Want more like this?

I write regularly about Rust, design patterns, and performance tips. Follow me here on Medium to stay updated.