Rosio Pavoris

A lot of textbooks make a distinction between classical cryptography and modern cryptography that is, in my mind, completely artificial. To demonstrate, allow me to explain one particular algorithm that many would put in the category of “classical” cryptography (because it doesn’t involve computers), but that’s a stream cipher using a pseudo-random number generator in a way that one would normally consider to be entirely modern.

The Solitaire cipher was developed in early 1999 by Bruce Schneier for Neal Stephenson’s novel Cryptonomicon (which I still haven’t read). It generates a reproducible random number stream and uses them as keys in a regular addition cipher.
And it’s done with playing cards.

The Algorithm

The concept is simple. Start with a deck of cards consisting of the standard 52 cards and two jokers which can be distinguished from one another (named A and B, for ease of reference).
You start by shuffling the deck and noting the position of each card. The starting position is basically the RNG’s seed, and it will enable another person to generate the exact same keystream later on.

Let’s take a simplified deck, and say the starting position is this:

3 A 1 4 2 B 5

Then, you find Joker A and swap it with the card beneath it (if it’s at the bottom, put it just below the top card).

3 1 A 4 2 B 5

Next, find Joker B and move it two cards down (again, putting it below the second card from the top if it’s at the bottom, or the first card if it’s the second from the bottom).

3 B 1 A 4 2 5

Next, you perform a triple cut, swapping the cards above the joker nearest to the top with the cards below the joker nearest to the bottom (regardless which one is A and which is B). If the jokers are at the ends, this operation won’t change the deck at all.

4 2 5 B 1 A 3

Next, look at the bottom card and convert it into a number from 1 to 53, using some reproducible method (the standard way is to use the bridge order of suits (clubs, diamonds, hearts, spades): a 2 of clubs would be 2, and a queen of hearts would be 38; either joker is 53).
Count down that number from the top card, and cut after the card you counted down to, leaving the bottom card on the bottom.
If the bottom card is a joker, this step leaves the deck unchanged.

B 1 A 4 2 5 3

Almost done. Now we’ll find the output card.
Look at the top card, and convert it into a number, as in the last step. Count down that many cards from the top, and note the card after the one you counted down to.
If it’s a joker, don’t write anything down¹ and go back to step 1, with the joker-moving. If it’s not, this is your output card.

With our limited example deck, the value of a joker would be 6, so our output card is 5.

Convert your output card to a number from 1 to 26 (you can use the same method as before, modulo 26; this is obviously where our example deck breaks down).
To use this value, convert the first letter of your plaintext to a number from 1 to 26 (A being 1, Z being 26), add the number you just generated to it, subtract 26 if the result is higher than 26, and convert the number back to a letter. Wee!

When you’re completely done, shuffle your deck, just in case.

To encrypt the rest of your plaintext, just go back to the first step (after the deck was intialised) and repeat.
To decrypt, just put your deck in the starting position again, generate the same numbers, and subtract them from each ciphertext number, adding 26 if the result is less than 1.

Note

This takes some time to do, obviously, and it’s handy to have a few sheets of paper to take notes on, which is always dangerous (Schneier suggests writing on cigarette papers, since they burn quickly, cleanly, and completely), and if you make a mistake in shuffling the rest of your stream will be worthless, but it’s quite secure and easy to do without looking suspicious, should you find yourself in a resistance movement in a totalitarian country (I hear the London Underground is hiring). Walking around with a deck of playing cards in your pocket is a lot less suspicious (and far cheaper) than owning a laptop with OpenSSL installed.

Of course, communicating your seed is a practical concern. You could keep your deck in your pocket in the arrangement of the seed and hand it over along with your encrypted message (if you’re physically handing over a message), but if you’re caught, the enemy will have your seed, which is a problem if you can’t destroy the ciphertext in time (or shuffle the deck, obviously).
The security of Solitaire doesn’t depend on the secrecy of the method, but if the enemy is aware of the method they will look for your deck of cards.

Also, Solitaire isn’t perfect. Paul Crowley discovered a bias in the RNG in 1999. Basically, the probability that two successive ciphertext characters are the same isn’t 1 in 26, as it should ideally be, but closer to 1 in 22.5.²

Anyway, the point of this post isn’t (necessarily) to teach you how to fight the fascist oppressor, but to show that even pretty secure and advanced ciphers don’t need awesome computers to be feasible, and to give you an example of how a pseudo-random number generator can work in practice.
A lot of people are put off of cryptography because it involves a lot of mathematics and low-level programming, but the concepts involved are really not that complex.

¹ http://www.ciphergoth.org/crypto/solitaire/lategan-1.txt

² http://www.ciphergoth.org/crypto/solitaire/