Solitaire Cipher¶ ↑

This is an implementation of Bruce Schneier’s Solitaire, as designed for the Neal Stephenson book, Cryptonomicon. It’s Ruby Quiz number one, and a chance for me to try out Cucumber (and RSpec) in anger. The rest of the text here is reproduced from the original Ruby Quiz.

Cryptologist Bruce Schneier designed the hand cipher “Solitaire” for Neal Stephenson’s book “Cryptonomicon”. Created to be the first truly secure hand cipher, Solitaire requires only a deck of cards for the encryption and decryption of messages.

While it’s true that Solitaire is easily completed by hand given ample time, using a computer is much quicker and easier. Because of that, Solitaire conversion routines are available in many languages, though I’ve not yet run across one in Ruby.

This week’s quiz is to write a Ruby script that does the encryption and decryption of messages using the Solitaire cipher.

Let’s look at the steps of encrypting a message with Solitaire.

Discard any non A to Z characters, and uppercase all remaining letters. Split the message into five character groups, using Xs to pad the last group, if needed. If we begin with the message “Code in Ruby, live longer!”, for example, we would now have:
```
CODEI NRUBY LIVEL ONGER
```
Use Solitaire to generate a keystream letter for each letter in the message. This step is detailed below, but for the sake of example let’s just say we get:
```
DWJXH YRFDG TMSHP UURXJ
```
Convert the message from step 1 into numbers, A = 1, B = 2, etc:
```
3 15 4 5 9  14 18 21 2 25  12 9 22 5 12  15 14 7 5 18
```
Convert the keystream letters from step 2 using the same method:
```
4 23 10 24 8  25 18 6 4 7  20 13 19 8 16  21 21 18 24 10
```
Add the message numbers from step 3 to the keystream numbers from step 4 and subtract 26 from the result if it is greater than 26. For example, 6 + 10 = 16 as expected, but 26 + 1 = 1 (27 - 26):
```
7 12 14 3 17  13 10 1 6 6  6 22 15 13 2  10 9 25 3 2
```
Convert the numbers from step 5 back to letters:
```
GLNCQ MJAFF FVOMB JIYCB
```

That took a while to break down, but it’s really a very simple process. Decrypting with Solitaire is even easier, so let’s look at those steps now. We’ll work backwards with our example now, decrypting “GLNCQ MJAFF FVOMB JIYCB”.

Use Solitaire to generate a keystream letter for each letter in the message to be decoded. Again, I detail this process below, but sender and receiver use the same key and will get the same letters:
```
DWJXH YRFDG TMSHP UURXJ
```

Convert the message to be decoded to numbers:

7 12 14 3 17  13 10 1 6 6  6 22 15 13 2  10 9 25 3 2

Convert the keystream letters from step 1 to numbers:

4 23 10 24 8  25 18 6 4 7  20 13 19 8 16  21 21 18 24 10

Subtract the keystream numbers from step 3 from the message numbers from step 2. If the message number is less than or equal to the keystream number, add 26 to the message number before subtracting. For example, 22 - 1 = 21 as expected, but 1 - 22 = 5 (27 - 22):
```
3 15 4 5 9  14 18 21 2 25  12 9 22 5 12  15 14 7 5 18
```
Convert the numbers from step 4 back to letters:
```
CODEI NRUBY LIVEL ONGER
```

Transforming messages is that simple. Finally, let’s look at the missing piece of the puzzle, generating the keystream letters.

First, let’s talk a little about the deck of cards. Solitaire needs a full deck of 52 cards and the two jokers. The jokers need to be visually distinct and I’ll refer to them below as A and B. Some steps involve assigning a value to the cards. In those cases, use the cards face value as a base, Ace = 1, 2 = 2… 10 = 10, Jack = 11, Queen = 12, King = 13. Then modify the base by the bridge ordering of suits, Clubs is simply the base value, Diamonds is base value + 13, Hearts is base value + 26, and Spades is base value + 39. Either joker values at 53. When the cards must represent a letter Clubs and Diamonds values are taken to be the number of the letter (1 to 26), as are Hearts and Spades after subtracting 26 from their value (27 to 52 drops to 1 to 26). Now let’s make sense of all that by putting it to use.

Key the deck. This is the critical step in the actual operation of the cipher and the heart of it’s security. There are many methods to go about this, such as shuffling a deck and then arranging the receiving deck in the same order or tracking a bridge column in the paper and using that to order the cards. Because we want to be able to test our answers though, we’ll use an unkeyed deck, cards in order of value. That is, from top to bottom, we’ll always start with the deck:
```
Ace of Clubs
...to...
King of Clubs
Ace of Diamonds
...to...
King of Diamonds
Ace of Hearts
...to...
King of Hearts
Ace of Spades
...to...
King of Spades
"A" Joker
"B" Joker
```
Move the A joker down one card. If the joker is at the bottom of the deck, move it to just below the first card. (Consider the deck to be circular.) The first time we do this, the deck will go from:
```
1 2 3 ... 52 A B
```
To:
```
1 2 3 ... 52 B A
```
Move the B joker down two cards. If the joker is the bottom card, move it just below the second card. If the joker is the just above the bottom card, move it below the top card. (Again, consider the deck to be circular.) This changes our example deck to:
```
1 B 2 3 4 ... 52 A
```
Perform a triple cut around the two jokers. All cards above the top joker move to below the bottom joker and vice versa. The jokers and the cards between them do not move. This gives us:
```
B 2 3 4 ... 52 A 1
```
Perform a count cut using the value of the bottom card. Cut the bottom card’s value in cards off the top of the deck and reinsert them just above the bottom card. This changes our deck to:
```
2 3 4 ... 52 A B 1  (the 1 tells us to move just the B)
```
Find the output letter. Convert the top card to it’s value and count down that many cards from the top of the deck, with the top card itself being card number one. Look at the card immediately after your count and convert it to a letter. This is the next letter in the keystream. If the output card is a joker, no letter is generated this sequence. This step does not alter the deck. For our example, the output letter is:
```
D  (the 2 tells us to count down to the 4, which is a D)
```
Return to step 2, if more letters are needed.

For the sake of testing, the first ten output letters for an unkeyed deck are:

D (4)  W (49)  J (10)  Skip Joker (53)  X (24)  H (8)
Y (51)  R (44)  F (6)  D (4)  G (33)

That’s all there is to Solitaire, finally. It’s really longer to explain than it is to code up.

Solutions to this quiz should accept a message as a command line argument and encrypt or decrypt is as needed. It should be easy to tell which is needed by the pattern of the message, but you can use a switch if you prefer.

All the examples for this quiz assume an unkeyed deck, but your script can provide a way to key the deck, if desired. (A real script would require this, of course.)

Here’s a couple of messages to test your work with. You’ll know when you have them right:

CLEPK HHNIY CFPWH FDFEH

ABVAW LWZSY OORYK DUPVH

mathie-solitaire_cipher

Runtime

Solitaire Cipher¶ ↑