Solitaire Encryption and Generation of the Keystream (Description) (Menu Crypt/Decrypt \ Symmetric (classic))

The description of the according dialog is Dialog Solitair encryption and key generation.

Solitaire is a typical symmetric paper&pencil encryption algorithm. It became known, because Neal Stephenson used it in his novel "Cryptonomicon".
It was developed by Bruce Schneier. The algorithm gets its security from the inherent randomness in a good shuffled deck of cards (key generation) and the aspect, that each key (this shuffled deck) is used only once.

The key for this procedure is the shuffled card deck which the sender as well as the receiver must have in the identical order of cards.
The actual Solitaire algorithm describes the generation of a relative random keystream out of the actual key (initial deck, bridge suite).
Each keystream letter is XOR-added to each plaintext letter or ciphertext letter (so the Solitaire cipher is based on the idea of the one-time pad, although the keystream is not completely random).

The Solitaire cipher uses the ideas of the Vernam cipher (XOR addition of the plaintext with the keystream) and of stream ciphers (generation of a keystream out of an initial value). The randomness is only guaranteed by the initial deck.

The actual Solitaire algorithm to generate a keystream consists - as descripted below - of 5 steps: The first 4 steps permutate the final deck generated latest. Step1 and step 2 modify only the position of the jokers, step 3 and 4 change complete stacks of cards. Step 5 locates the value of the next keystream letter, but does not change the order of the final card deck. Sometimes the order of cards, which appear during the procedure, are called temporary deck and only the last temporary deck is called final deck.
The initial deck and the final deck contain a permutation of the card values 1 to 54. The keystream contains only the values of 1 to 52 and has the same length as the plaintext.

Encryption with Solitaire

The precondition for encryption is the existence of a keystream, which length is the same as the length of the plaintext. It consists of a stream of numbers between 1 and 26.

The plaintext is splitted in groups of five letters (all non-letters are deleted). Then the plaintext letters are translated in values between 1 and 26 (A represents 1, B represents 2, C represents 3 und Z represents 26) and after that added modulo 26 with the keystream [Because of the aspect that the result of the calculation modulo 26 is between 0 and 25 (inclusive), the value 0 is interpreted as 26 and represents the letter Z]. The text, which is created through the re-convertation of the new number stream is the ciphertext.

Decryption with Solitaire

Because Solitaire is a symmetric cipher, for encryption and for decryption the same key (keystream) is used.

For decryption the ciphertext is also splitted in groups of five letters (as at the encryption). After that the letter keystream is converted to a number keystream. Then the keystream numbers are subtracted modulo 26 of the ciphertext numbers. The new number keystream has to be converted into the letter stream to get the plaintext.

Remark:
It is recommended, that the receiver has a substitute initial deck, because the initial deck is modified during the keystream generation. If the receiver makes a mistake, he will not be able to restart the procedure. So the plaintext cannot be decrypted anymore.

Initial generation of keystream

The cards of club get the value 1 for ace, 2 for two, to 13 for the king, the cards of diamond the values 14 to 26, the cards of heart the values 27 to 39 and the cards of spade the values 40 to 52. The generated keystream is a sequence of numbers between 1 and 26, because of the calculation with modulo 26.

To initialize the card deck, Schneier describes three different alternatives:

1. Shuffle cards:
Shuffle an already used deck (new ones are harder to shuffle) and shuffle it long enough. A randomly shuffled card deck is the key. The recipient needs another deck, sorted in the same order.

2. Bridge suite order:
Use a bridge ordering. A description of a set of bridge hands that you might see in a newspaper or a bridge book. Agree on a way to take the bridge-hand diagram and convert it into an ordering of the deck. Then agree on a way to put the two jokers into the deck. (One obvious one is to put the A joker after the first card mentioned in the text, and the B joker after the second card mentioned in the text.)

3. Password:
Sender and receiver use a password to order the deck. The deck has to have an agreed fixed order (e.g. lowest card to highest card, in bridge suits, followed by the A and then the B joker). Then perform the Solitaire operation, but instead of Step 5, do another count cut based on the first character of the password. In other words, do step 4 a second time. Remember to put the top cards just above the bottom card in the deck, as before.

For security reasons Schneier recommends a password of at least 80 letters (high additional time burdon).

The sender and the receiver need a bridge suite, ordered exactly in the same way. Then both sides generate the keystream. There are 54! (which is ca. 2*10^71) different possibilities, how the card deck can be ordered.

Keystream generation

This is the actual algorithm:
Take the initialized card deck faced up. Then the following five steps are repeated as often as the length of the plaintext.

Step 1:

Find the joker A. Move it one card down. That is, swap it with the card beneath it. If the joker is the bottom card of the deck, move it just below the top card.

Step 2:

Find the joker B. Move it two cards down. If the joker is the bottom card of the deck, move it just below the second card. If the joker is one up from the bottom card, move it just below the top card. Basically, assume the deck is a loop.

Step 3:

Perform a triple cut:
That is, swap the cards above the first joker with the cards below the second joker. Here it plays no role, which joker is the first one. The first joker is the one, which is nearest to the top of the cards. The jokers are not swapped. If there are no cards in one of the three sections (either the jokers are adjacent, or one is on top or the bottom), just treat that section as empty and move it anyway.

Step 4:

Perform a count cut:
Look at the bottom card. The value of the bottom card is u (u is a value between 1 and 53), and then count down from the top card u single cards. Cut after the card that you counted down to, leaving the bottom card on the bottom.

Step 5:

Find the output card:
To do this, count down that many cards as the value of the top card. Count the top card as number one. The card after the one you counted to on is the output card. Don't remove it from the deck. If you hit a joker, don't write anything down (following called as zero round) and start over again with step 1. If not enough keystream letters are generated start with step 1.
The value of the output card (between 1 and 52) generates mod 26 one single letter of the keystream.

With CrypTool it is possible,