The Solitaire Cipher - Superstruct Instructables Series

Hello, and welcome to this Instructable. In the following pages, we'll take a look at the basics of the Solitaire cipher, an encryption algorithm created by cryptography specialist Bruce Schneier for Neal Stephenson's novel "Cryptonomicon", a book released in 1999 - 20 years ago already ! It's been designed to use a simple deck of cards to provide high-tech level security.

As some readers among you might be some of my students (I teach in a small suburbian middle-school near Paris) , let me remind you kids that some of the principles behind Solitaire are part of the European Information Literacy and Protection curriculum since 2015, and you will be expected to be familiar with these for your final exams ! Remember that being able to use this cipher could also turn out to be of vital importance for personal information protection.*

*No I didn't go crazy, and I haven't forgotten this is 2008 and not 2019. This Instructable is the first in a series of Instructables related to the Institute for the Future's Alternate Reality Game Superstruct. Set in 2019, this game places players in a world threatened by five major ills - failing and/or hacked communication and computer networks, a severed food chain, devastating climate catastrophes that force populations to migrate, epidemics of Respiratory Distress Syndrom and a world struggling to survive without oil. If you think you're up to the challenge or would like to explore this world more, check the main site and join us !

Step 1: Tools You'll Need

In order to encrypt data using the Solitaire cipher, you will need the following :

Patience : Encrypting data with the Solitaire cipher takes time. To quote Mr. Schneier, "(Solitaire)'s not fast, though. It can take an evening to encrypt or decrypt a reasonably long message."

Two decks of 54 cards : these decks feature the classic four suits of cards - club, diamonds, hearts and spades - plus two jokers. One of the decks will be used to generate keystream values, the other for backup purposes or communicating to your recipient.

Paper and pencil or a computer terminal : For the purpose of this exercise, any relatively trusted terminal will do. Keep in mind, however, that in a real-life situation you might sometimes not be able to rely on "relatively trusted" hardware. In such situations, all operations should be carried using a disposable writing surface of some sort (only 10 years ago, using paper would have been the easiest option but there are parts of the world where this is no longer the case, alas). Even better, don't write down any information anywhere at all (see my Instructable on methods of loci for more help in that field) - if you can do it all in your head, do so.

Step 2: Overview of the Encryption Process

The process of encrypting a message with Solitaire can be divided into a few steps. Let's see what they are :

1) Writing your cleartext (immediately understandable) message and preparing it for encryption ;
2) Preparing the decks to generate keystream values ;
3) Generating keystream letters ;
4) Generating the ciphertext ;
5) You're done !

If these 5 steps are clear enough to you, let's move on with step one - writing your cleartext and preparing it for encryption.

Step 3: Writing and Preparing Your Cleartext Message

First off, in order to encrypt a message, you need to have a message to encrypt. Given the time it takes to encrypt text with Solitaire and the level of security it offers, Bruce Schneier suggests that the longest messages should be 2000 characters long. This can be a little short for what you have to say so don't hesitate to use slang or abbreviations. Make sure that your recipient will understand what you mean, though !

Once this is done, it's time to prepare your message for encryption. Encrypting a message doesn't change either words' length or message punctuation, both of which can be indications as to what words you've used in your messages. In order to prevent such an attack - called the "probable word attack" - we're going to apply a few changes to your message.

First, we're going to remove ALL the punctuation in your message. Full stops, commas, etc...Just remove them all.

Second, we're going to take care of the length of the words used. You're going to divide your message's characters in small groups of 5 letters. If you have extras, use the letter X. For example, a short message saying "Do not go" would turn into "DONOT GOXXX".

There's nothing really special about using groups of 5 letters - it's just a convention. In the same way, you'll notice we turned the letters into caps - this too is a convention to differentiate more conveniently cleartext from ciphertext. It also takes care of removing all indication of where a sentence starts or finishes. Neat, is it not ?

Now that we're done, let's move to the next step : preparing the decks !

Step 4: Preparing Your Decks

Now is the time to get the decks ready to generate the keystream values. To generate these, we first need to shuffle the decks so that the cards are as randomly distributed as possible. To make sure that's the case, we're going to shuffle the first deck 6 times - if you have no idea how to do this, I suggest you take a look at this Instructable by M5R, or just watch the .ogg video included on this page.

Once this is done, turn it face up and arrange the cards in the other deck to match the distribution of the first. Put it back in its package and don't touch it ! That'll be your backup. You can write down the order of the cards in the deck, save it on your terminal or, as said previously, use mnemonics' to memorize the order of the cards in the deck.

Step 5: Generating Keystream Values

Generating keystream values is the heart of Solitaire, which means this is where we're going to have to pay extra attention to every little step. It might take some time for you to understand completely, so in case you're confused at some point just go up one step, or back to the start if you really have to. The reason for that ? If you make a mistake, chances are you'll have to start all over again from the beginning. With that in mind, are you ready ?

Before fiddling with your deck, let's clarify a few points first - namely, let's explain what these keystream numbers are and what they're going to be used for. Simply put, a keystream is a series of randomly-generated values. Each one of these values is added with one value from the cleartext, the sum of which gives you a third value that is used to generate - you guessed it - ciphertext ! Here's how Solitaire generates these keystream values in just a few steps. If you mess up at some point, just use the backup deck to restore your original keystream-generating deck, and start all over again.

Step 1 : Take the keystream-generating deck face up, and find Joker A and B. In a deck of cards, the two Jokers are usually differentiated one way or another : for example, the Jokers in my deck sport either a red or a black star, and I decided that Joker A would be the Joker with the red star and Joker B the Joker with a black star.

Step 2 : Take Joker A and bring it one card down, then take Joker B and take it two cards down.

Step 3 : We're now going to perform a triple cut. Basically we're going to swap the cards above the first Joker from the top of the deck with the cards under the second Joker from the top of the deck.

Notice I *did* say the first and second Joker from the top, NOT Joker A and B ! Only the cards above and below the Jokers move, not the Jokers themselves. Also, if it turned out that there would be no cards in one of the 3 sections, pretend this is an "invisible" set of cards and swap it nonetheless.

Step 4 : Now is time for a count cut. First, let's check the card at the bottom of the deck - here we have a 10 of Diamonds : we're going to convert it into a number between 1 and 53 using the chart below.*

Clubs are the value of the card + 0 ;
Diamonds are the value of the card + 13 ;
Hearts are the value of the card + 26 ;
Spades are the value of the card + 39.

So we're going to count from the top of the deck all the way down to the 23rd card designated by the value we just figured out. Take all these cards and insert them above the last card of the deck. Make sure that last card stays there - there's a reason for that ! We're almost done !

*Since a Joker is worth 53, a deck with a Joker as the bottom card is left unchanged by Step 4.

Step 5 : It's time to find the first card with which we'll generate a keystream value ! Look at the first card on top of the deck, and convert its value much like you did in Step 4. In our case, we're going to count down to the 33rd card designated by the 7 of Hearts on top of the deck, and write down the card right after (I got a 7 of Spades) on paper. Don't remove that card from the deck ! If the card you hit is a Joker, start over again from Step 1.

Step 6 : Finally, we're going to generate that first keystream value by converting the card's suit and value to a number between 1and 26. Remember the value table we used earlier ? We're going to do something similar here. Let's suppose A of Clubs to King of Clubs will be 1 to 13, A of Diamonds to King of Diamonds will be 14 to 26, A of Hearts to King of Hearts will be 1 to 13 again, and A of Spades to King of Spades will be 14 to 26 again - convert the card you got accordingly, and voila - you have your first keystream value ! All you have to do now is generate as many of these values as there are characters in your message. Of course, don't reset your deck until after you're done generating values.

Once you have the amount of keystream values you need, let's move on to the final step that'll turn your cleartext into ciphertext for good !

Step 6: Generating Ciphertext

We're almost there now ! On the one hand we have a series of numbers and on the other we have a slightly tweaked message. Let's get working...And get familiar with the wonderful world of modulo !

This word "modulo" might sound scary and strange, but that is actually something people do all the time when, for example, we figure out what time it is - namely modulo 12. Let's suppose it's 11 in the morning and you have to meet someone 3 hours later - that'll be 2 in the afternoon. Easy, is it not ? These operations are called modular arithmetics. Now let us apply this to our cleartext and keystream values.

Let's go back to the cleartext we prepared earlier so that it'd turn into DONOT GOXXX. We're going to convert every letter to a numeric equivalent :

D O N O T G O X X X transforms into :
4 15 14 15 20 7 15 24 24 24

To which we had the keystream values (these are completely arbitrary, and are only here as an example) :
17 15 8 24 3 10 20 13 1 14

Which gives us :
21 30 22 39 23 1735 37 25 38

Do you remember the modulo I mentioned earlier ? If watches are modulo 12, then the alphabet is modulo 26. Converting these values accordingly, we have now :
21 4 22 13 23 17 9 11 25 12

Which once converted back to letters becomes :
U D V M W Q I K Z M.

Step 7: Deciphering Ciphertext

Now let's suppose someone just got a message encrypted with Solitaire. How does one decrypt it ? As you might have already figured out, Solitaire is a symmetric algorithm : what you did to encrypt your message, is what you're going to do to decrypt it - the other way around.

Step 1 - You're going to need the keystream values the sender used to encrypt the message. This is pretty simple, all things considered : all one needs to do is follow the process described in Step 6 - Generating keystream values using the correct deck, and generate as many keystream values as there are of characters in the message, as seen before.

Step 2 - We're going to use the example from the previous step :
U D V M W Q I K Z M,

and convert it into numbers :
21 4 22 13 23 17 9 11 25 12.

Step 3 - If the recipient of the message followed the keystream values generation process correctly, starting from the deck that was agreed upon with the sender, the values generated are the same as those the sender used :
17 15 8 24 3 10 20 13 1 14 ;

Step 4 - From there, all one needs to do is substract the generated keystream values from the numbers that came up when we converted the message, still using modulo 26. This gives us :
4 15 14 15 20 7 15 24 24 24,

Which we convert into letters, obtaining :
D O N O T G O X X X.

As I told you, nothing too difficult if you've understood how the encryption process works - the decryption process is just the same, only reversed. Don't hesitate to train and work on it until it makes sense ! Better make mistakes now than when time will actually be of the essence !

If you're clear on that part, let's move on to the conclusion.

Step 8: Conclusion (and a Few Words of Advice)

If you've been patient enough to read through this Instructable and go at least through one round of keystream-value generation, you should be much more familiar, if not completely at ease with the concepts of plaintext, ciphertext and modular arithmetics. Let us not leave without a few words of caution though.

Never, never use the same deck arrangement twice for two different messages. I won't delve into mathematical details here (for this, you should once again check Mr Schneier's original Solitaire page) but a professional cryptographer obtaining two or several messages encrypted with the same deck could easily deduce the keystream values, and decrypt your messages from there.

Don't be lazy and skip the 6 shufflings in the beginning of the process. Would you leave your appartment with your door unlocked when you could have actually locked it ? I thought so. Just do the shuffling :)

If possible, train at generating keystreams before actually having to use Solitaire. This will reduce the risk for errors - which are quite irreversible - as well as help you encrypt your messages faster.

Do as many things as possible in your head, not on paper nor on a computer terminal - granted you can do it without mistakes, that is. For that, you'll need to learn or train in mnemonics, but if the situation calls for such drastic measures, it's worth it.

Once you've finished generating keystream values shuffle your deck a number of times to make the initial deck impossible to retrace. Solitaire is reversible if someone puts their hand on the initial deck, and you do not want this to happen, do you ? Besides, as was said before, you must have written down/saved/memorized the initial deck somewhere (or made a backup deck).

Did I mention never using the same deck arrangement twice ? ;) Alright then, class dismissed ! Enjoy your privacy.

If you notice ANY mistake in this Instructable, make sure to send me a message so I can correct it as soon as possible ! For more details on the mathematics of Solitaire and more advice from Mr. Schneier, visit the original Solitaire webpage as well as [http://en.wikipedia.org/wiki/Solitaire_(cipher) the Wikipedia article] dedicated to this cipher.

And finally, thanks to messieurs BlueScreenJunky and Scribe for their help and proofreading !