The Solitaire cryptographic algorithm was designed by Bruce Schneier at the request of Neal Stephenson for use in his novel Cryptonomicon, in which field agents use it to communicate securely without having to rely on electronics or having to carry incriminating tools.[1] It was designed to be a manual cryptosystem calculated with an ordinary deck of playing cards. In Cryptonomicon, this algorithm was originally called Pontifex to hide the fact that it involved playing cards.
One of the motivations behind Solitaire's creation is that in totalitarian environments, a deck of cards is far more affordable (and less incriminating) than a personal computer with an array of cryptological utilities. However, as Schneier warns in the appendix of Cryptonomicon, just about everyone with an interest in cryptanalysis will now know about this algorithm, so carrying a deck of cards may also be considered incriminating. Furthermore, analysis has revealed flaws in the cipher such that it is now considered insecure.
This algorithm uses a standard deck of cards with 52 suited cards and two jokers which are distinguishable from each other, called the A joker and the B joker. For simplicity's sake, only two suits will be used in this example, clubs and diamonds. Each card is assigned a numerical value: the clubs will be numbered from 1 to 13 (Ace through King) and the diamonds will be numbered 14 through 26 in the same manner. The jokers will be assigned the values of 27 and 28. Thus, the jack of clubs would have the value 11, and the two of diamonds would have the value 15. (In a full deck of cards, the suits are valued in bridge order: clubs, diamonds, hearts, spades, with the suited cards numbered 1 through 52, and the jokers numbered 53 and 54.)
To begin encryption or decryption, arrange the deck of cards face-up in an order previously agreed upon. The person decrypting a message must have a deck arranged in the same order as the deck used by the person who encrypted the message. How the order is initially decided upon is up to the recipients; shuffling the deck perfectly randomly is preferable, although there are many other methods.
The algorithm generates a keystream, a sequence of values which are combined with the message to encrypt and decrypt it. Each value of the keystream is used to encrypt one character of the message, so the keystream must be at least as long as the message. If the keystream is longer than the message, the message may be padded with an additional repeated character, thus denying the attacker knowledge of the exact length of the message.
To encrypt a message:
To decrypt a ciphertext:
This algorithm generates keystream values by moving cards within the deck. The keystream algorithm is deterministic, so the keystream values depend only on the initial order of the deck. The deck is assumed to be a circular array, meaning that should a card ever need to advance below the bottom card in the deck, it will simply rotate back to the top (in other words, the first card follows the last card).For example, take this starting deck:
Perform these steps to generate one character of the keystream.
In 1999 Paul Crowley discovered that there is a bias towards repeating characters in the keystream, which occur about every 1/22.5 characters rather than the expected 1/26. As a result, Solitaire leaks information at a rate of about 0.0005 bits per character.[2] While its security may perhaps be adequate for very short messages, in general Solitaire is considered insecure.
Crowley also noticed that in some cases, there are two different deck configurations which result in the same configuration after executing the keystream algorithm. For instance, when the A joker is either on the bottom of the deck or on the top of the deck it will become the second card after step 1. This means the algorithm is not always reversible as Schneier had originally claimed.[3]
In 2019 Daniel Shiu proposed modifications to the algorithm which would increase its security, at the cost of making it more difficult for the user to implement manually.