The Solitaire Cipher

  • By Brad Conte, July 3, 2005
  • Post Categories: Security

About The Solitaire Cipher

The Solitaire Cipher was designed by Bruce Schneier specifically for Neal Stephenson's book, Cryptonomicon. The algorithm was developed so that people would have a way of encrypting messages without the aid of computers. All that is necessary is a full deck of standard playing cards (or something equivalent).

How it's used

The Solitaire algorithm itself does not encrypt anything, rather, it generates a string of pseudo-random values that can be used to do the actual encrypting. This string of values is generated by a key that the user provides. The "random" output will always be the same for every key, and since this output is used to encrypt the message, it is easy to see how the key for the random generator is, essentially, the password for the encryption/decryption process, as without it, you have no hope of generating the same values again to use to decrypt the message.

When the key is provided to the algorithm, it is used to initialize the data pool. Once that is done, any number of random characters can be generated.

The values the algorithm spits out range from 1 to 26, corresponding to A-Z (it can also be implemented to spit out values from 1-52, corresponding to A-Z and a-z). To encrypt/decrypt a message (using 26 values), translate all the characters in the message to the same case and then generate enough random characters for them all. If you are encrypting the message, add all the random values to the values in the message (rolling back to 1 should any value exceed 26). To decrypt, subtract the random values from the values in the message (rolling back up to 26 should any value go below 1).

Algorithm

This algorithm assumes that the user has two or four decks of cards and two jokers. For simplicity's sake, only two decks will be used in this example. The two decks of cards will be combined and each card will be assigned a numerical value. The first deck of cards will be numbered from 1 to 13 (Ace through King) and the second deck will be numbered 14 through 26 in the same manner. The jokers will be assigned the values of 27 and 28. Thus, a 5 from the first deck would have the value 5 in our combined deck, the value 1 in the second deck would have the value 14 in the combined deck.

The deck will be 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).

  1. Arrange the deck of cards according to a specific key. This is the most important part of the algorithm as anyone who knows the deck's starting value can easily generate the same values from it. How the deck is initialized is equivalent to the encryption security key and is left up to the recipients. Shuffling the deck perfectly randomly is preferable, although there are many other methods. For this example, the deck will simply start at 1 and count up by 3's, modulo 28. Thus the starting deck will look like this:

    1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26
    
  2. Locate the first joker (value 27) and move it down the deck by one place, basically just exchanging with the card below it. The deck now looks like this:

    1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
    
  3. Locate the second joker (value 28) and move it down the deck by two places.

    1 4 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
    
  4. Perform a triple-cut on the deck. Everything above the top joker (which, after several repetitions, may not necessarily be the first joker) and everything below the bottom joker will be exchanged. The joker's themselves, and the cards between them, are left untouched.
    5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 6
    
  5. Observe the value of the card at the bottom of the deck, if the card is either joker let the value just be 27. Take that number of cards from the top of the deck and insert them back to the bottom of the deck just above the last card.

    23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
    
  6. Note the value of the top card. Count this many places below that card and take the value of the card there. This value is the next value in the keystream, in this example it would be 11. (Note that no cards are changing places in this step, this step simply determines the value).
  7. Repeat steps 2 through 6 for as many keystream values as required.

My implementation of the Solitaire Cipher in the C language can be found on in my code project.

Security

This algorithm has been proven to have bias toward certain values in its output and is not as random as today's modern cryptographic standards would demand. The weaknesses of the algorithm are outlined here. This is not to say, however, that Solitaire is worthless, it is still an easily remembered hand-executable algorithm that does generate "random enough" values.


Note: I used this article to create the first draft of the Wikipedia article on the Solitaire Cipher. Because of this, the text in this article is under Wikipedia's License.