The Solitaire or Pontifex algorithm is a cryptographic algorithm designed by cryptographer Bruce Schneier based on coordinating two decks of cards so that they can be used to communicate between two field agents. Given a standard deck of 52 playing cards and two distinguishable jokers, a message may be encrypted as a keystream, or sequence of values combined with the message to encrypt or decrypt it. The algorithm features prominently in Neal Stephenson's novel Cryptonomicon.
Playing cards are conventionally numbered as clubs (1–13); diamonds (14–26); hearts (27–39); and spades (40–52). The two jokers (53 and 54) are used to track the position of variables in the keystream.
Per Wikipedia:
To encrypt a message:
Remove all punctuation and spaces, leaving only the 26 letters A–Z.
Convert each letter to its natural numerical value, A = 1, B = 2, ..., Z = 26.
Generate one keystream value for each letter in the message using the keystream algorithm below.
Add each keystream value to the corresponding plaintext number, subtracting 26 if the resulting value is greater than 26. (In mathematics this is called modular arithmetic).
Convert the resulting numbers back to letters. This sequence of letters is the ciphertext.
To decrypt a ciphertext:
Convert each letter in the ciphertext to its natural numerical value.
Generate one keystream value for each letter in the ciphertext.
Subtract each keystream value from the corresponding ciphertext value, adding 26 if the resulting value is less than 1.
Convert the resulting numbers back to letters.
The keystream algorithm generates the overall value by moving cards within the deck. The algorithm is deterministic, which means that the values depend on the initial order of the deck (and thus why two decks are necessary). The deck is circular (a card moved past the bottom cycles back in at the top and vice versa).
The mesage is converted to ALLUPPERCASE, conventionally in groups of five: ALLUP PERCA SEXXX.
To generate one character:
Locate the A joker (value 27) and move it down the deck by one place. If it is the last card, it becomes the second card. There is no way for it to become the first card.
Locate the B joker (value 28) and move it down the deck by two places. Notice that if it is the second to last card, it becomes the second card by wrapping around. If it is the last card, it becomes the third card. There is no way for it to become the first card.
Perform a "triple cut": split the deck into three sections. Everything above the top joker (which, after several repetitions, may not necessarily be the A joker) and everything below the bottom joker will be exchanged. The jokers themselves, and the cards between them, are left untouched.
Perform a "count cut": observe the value of the card at the bottom of the deck. If the card is either joker take its value to be 27. Remove that number of cards from the top of the deck and insert them just above the last card in the deck.
Now, look at the value of the top card. Again, either joker counts as 27. Count this many places below that card and take the value of that card as the next value in the keystream. If the card counted to is either joker, ignore it and repeat the keystream algorithm. In this example the top card is 23, so we count to the 24th card, which is 11; thus the keystream value is 11. (Note that no cards change places in this step, this step simply determines the keystream value).
The foregoing hyperlinks showcase worked examples of Solitaire in action.
Solutions
This solution was produced by ~rabsef-bicrym. It is made available under the GNU GPL. (Note that this is different from the other code snippets on this site, which are made available under the MIT license.
The following Hoon generator can be used to encrypt a message with a default or custom deck. With the default deck:
A custom deck would look like ~[5 31 4 51 ...] for all 54 values in a specified or random order. One could compose a shuffle gate to randomize card order within that range:
|= [count=@ud eny=@uvJ]
^- (list @ud)
=/ rng ~(. og eny)
=/ index 1
=/ deck (gulf 1 count)
|- ^- (list @ud)
?: =(index count) deck
=^ other rng (rads:rng count)
=/ value (snag other deck)
%= $
index +(index)
deck (snap (snap deck (dec index) value) other (snag (dec index) deck))
==
