For as long as I’ve been playing with computers I’ve had a mild interest in cryptography. Unfortunately that interest was so mild that I never got off my butt to actually learn anything about it. But that changed recently when I was introduced to the Solitaire encryption algorithm by Bruce Schneier. It is an algorithm to generate a key stream using a deck of cards. This key stream is then used to encrypt a message. Only those who know the starting order of the deck (and the algorithm) can decipher the encrypted message.
If you scroll to the bottom of Schneier’s Solitaire page, you’ll see a list of programming languages that have been used to implement Solitaire. When I first visited that page there was not a version in Clojure, so I decided to write one. I had emailed Mr. Schneier about my Clojure version and he was kind enough to include a link to the code on the Solitaire page. This blog entry will describe the most important bits of that code.
The Algorithm
The result of performing an iteration of the Solitaire encryption algorithm is one key of a key stream. In this case that key stream consists of a stream of the integers from 0 to 25, inclusive. This is achieved by starting with a deck (which contains the two jokers) in an order that must be known to both the sender and receiver of the encrypted message and then performing the following operations on it:
- Move Joker A down one spot
- Move Joker B down two spots
- Perform a triple cut
- Perform a count cut
These steps will be described below. The two Jokers in a normal deck of cards are typically distinguishable. For the purposes of this description one of the Jokers will be called “A” and the other “B”; it doesn’t matter which you call “A” and which you call “B” as long as you are consistent.
Representing the Deck
The Solitaire Encryption algorithm uses a normal deck of cards, including the two Joker cards, therefore, a deck is composed of 54 cards. But, what is a card? There are many ways that one could encode a card but I decided to go with the simplest way that I could think of: encode a card as an integer – 1 through 54. The following function ensures that a given card is valid:
1 2 3 4 5 |
(defn- valid-card? "Returns true if the given value represents a valid card." [card] (and (integer? card) (< 0 card 55))) |
Note the use of the “range-checking” feature of the <
function. This is nicer than the alternative:
1 2 |
(and (< 0 card) (< card 55)) |
Now that we’ve defined what a valid card is, a valid deck can be defined like so:
1 2 3 4 5 6 |
(defn- valid-deck? "Returns true if the given value is a collection of 54 valid cards; false otherwise." [deck] (and (= (count deck) 54) (every? valid-card? deck))) |
This function simply checks that the deck contains 54 items and that those items are all valid cards. These functions are used in the precondition check in all the other functions that take a deck and/or a card as parameters.
I also wrote a bit of helper code to give me a shuffled deck:
1 2 3 4 5 6 |
(def ordered-deck (range 1 55)) (defn random-deck "Returns a deck of cards in a random order." [] (shuffle ordered-deck)) |
Moving a Card Down in the Deck
The first part of the Solitaire algorithm involves moving the two Jokers down one or two spaces in the deck, depending on the Joker. That seemed like a good place to start. I wanted to create a general function that took a deck of cards as input and returned a new deck with a given card moved down in the deck a given number of spaces.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
(defn move-card-down "With two arguments, moves the given card one space closer to the bottom of the deck. With three arguments, moves the given card the given number of spaces toward the bottom of the deck. If card moves past bottom of deck, it cycles back to the top of the deck." ([deck card] {:pre [(valid-deck? deck) (valid-card? card)]} (let [[top [_ next-card & bottom]] (split-with #(not= % card) deck)] (if (not next-card) (list* (first top) card (rest top)) (concat top [next-card card] bottom)))) ([deck card spaces] {:pre [(valid-deck? deck) (valid-card? card) (integer? spaces)]} (if (<= spaces 0) deck (recur (move-card-down deck card) card (dec spaces))))) |
The above is a multi-arity function. As the doc string states, if it is called with two arguments, the given card is moved down one space in the deck (it moves to below the top card if it is the bottom card) and if it is called with three arguments, the given card is moved down the given number of spaces. The three-arg version (beginning on line 12) calls the two-arg version to move card
down the deck one space at a time. It does this recursively decrementing spaces each time until spaces reaches zero.
The real work is done by the two-arg version (beginning on line 6). The body of the two-arg version is a let expression with a single binding but this binding uses nested destructuring that does a lot of the hard work for us. The result of the split-with
call is a two-element vector whose first element is destructured and bound to top
. top
will be bound to the portion of the deck that is above card
and therefore does not include card
. The second element of the two-element result will contain the rest of the deck and so card
will be the first element of that sequence. This bottom part of the deck is further destructured into three parts. The first element is discarded by binding it to _
. This is just card
and we already have that so there’s no need to bind another name to it. The second element is bound to next-card
; we’ll need that in a moment. The rest of the deck is bound to bottom
.
The conditional on line 9 checks the value of (not next-card)
. If this evaluates to true, it means that card
was at the bottom of the deck. Moving the bottom card down one spot in the deck is equivalent to placing it after the top card. This is achieved on line 10 by making a list of the top card, followed by card
and then followed by all but the top card.
The alternative part of the conditional (line 11) is the more likely case when card
is not the bottom card. In this case we concatenate the top of the deck with next-card
followed by card
, then the rest of the deck which is bound to bottom
.
Triple Cut
After the Jokers have been moved down in the deck, a triple cut is performed. A triple cut swaps the cards above the first Joker with the cards below the second Joker; the cards in the middle – including the Jokers – don’t move. The following code defines the triple-cut
function:
1 2 3 4 5 6 7 8 9 |
(defn triple-cut "Performs a triple cut around the two Jokers: the chunk of cards above the first Joker swaps places with the chunk of cards below the second Joker." [deck] {:pre [(valid-deck? deck)]} (let [[top middle [second-joker & bottom]] (split-at-jokers deck) middle (concat middle (list second-joker))] (concat bottom middle top))) |
About half of the work needed for a triple cut is performed by the split-at-jokers
function:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
(defn split-at-jokers "Returns a three-element vector whose first element is the chunk of cards before the first joker, whose second element is the chunk of cards starting with the first joker followed by all the cards after the first joker but before the second joker, and finally whose third element is the chunk of cards starting with the second joker followed by the rest of the cards in the deck." [deck] {:pre [(valid-deck? deck)]} (let [[top [first-joker & therest]] (split-with #(not (joker? %)) deck) [middle bottom] (split-with #(not (joker? %)) therest) middle (cons first-joker middle)] [top middle bottom])) |
The result of calling split-at-jokers
is almost, but not quite, what we need for a triple cut. The difference is that, after splitting, the top card of the bottom of the deck is the second Joker rather than that Joker being the last card of the middle section. For example, the result of calling split-at-jokers
on the following (very small) deck:
1 |
[1 2 3 Joker1 4 5 6 Joker2 7 8 9] |
would be:
1 |
[[1 2 3] [Joker1 4 5 6] [Joker2 7 8 9]] |
We need to do a bit of additional manipulation inside of triple-cut
to get to the point where we can simple swap the top and bottom of the deck. I opted for this pattern because I thought it was more general and consistent with they way other split functions work.
Count Cut
The count cut uses the value of the bottom card to determine where in the deck to cut. Schneier’s Solitaire algorithm describes how to assign values to the cards using the Bridge order of suits: clubs, diamonds, hearts, spades. But since this code just uses integers 1 through 52 to encode cards, there is no need for such a ranking. Note that both jokers are given the value 53 for this purpose.
Once the value of the bottom card has been determined, the deck is cut to one card past that card. But instead of a normal cut where the top and bottom are simply swapped, in this case the bottom card is left in place. Suppose we have to following (very small) deck:
1 |
[9 2 4 7 1 3 6 8 5] |
a count cut would result in the following deck:
1 |
[3 6 8 9 2 4 7 1 5] |
The claim is that the last card is left in place to make this step reversible, but to be honest it’s not obvious to me how that makes it reversible and I haven’t given it much thought. This page talks about how the Solitaire algorithm is not actually reversible as is claimed. Interestingly, that page also discusses how the algorithm is also biased. It goes to show that you should not roll your own security; even security professionals get it wrong!
The following is the code for count-cut
:
1 2 3 4 5 6 7 |
(defn count-cut "Returns a new deck which is the result of performing a cut at the value of the last card (a joker is 53) but the last card stays in place." [deck] {:pre [(valid-deck? deck)]} (let [bottomcard (if (joker? (last deck)) 53 (last deck))] (cut-preserve-bottom deck bottomcard))) |
But as before, most of the work is done by another function, cut-preserve-bottom
:
1 2 3 4 5 6 7 8 |
(defn cut-preserve-bottom "Returns a new deck which is the result of performing a cut at position and leaving the bottom card in place." [deck position] {:pre [(valid-deck? deck) (<= 0 position 54)]} (let [[top therest] (split-at position deck) [middle bottom] (split-at (dec (count therest)) therest)] (concat middle top bottom))) |
Putting Them Together
The previous three sections describe the functions that are used to implement one iteration of the Solitaire algorithm which was described near the beginning of this post. I’ll repeat those steps here:
- Move Joker A down one spot
- Move Joker B down two spots
- Perform a triple cut
- Perform a count cut
And the function representing these steps is the following:
1 2 3 4 5 6 7 8 9 10 |
(defn solitaire "Performs one iteration of the solitaire algorithm on deck and returns the modified deck." [deck] {:pre [(valid-deck? deck)]} (-> deck (move-card-down jokerA 1) (move-card-down jokerB 2) triple-cut count-cut)) |
jokerA
and jokerB
were previously defined as:
1 2 |
(def jokerA 53) (def jokerB 54) |
I think you’ll agree that using Clojure’s threading macro allows this function to be a direct translation of the previously outlined algorithm.
Generating the Keystream
It was mentioned earlier that the result of performing an iteration of the Solitaire encryption algorithm is one key of a key stream. So how do we generate the key? Here’s how: after performing the previously described solitaire algorithm, look at the top card. Then, convert that card to a number. Since we’re representing cards as numbers, this step is already done with one exception: if the top card is a joker, it’s given a value of 53. This is despite the fact that this implementation gives values of 53 and 54 to the two jokers. Next, count down that many cards from the top of the deck. The card after this number is the key. The only caveat to this procedure is if the key happens to be one of the jokers. In that case you must start over by performing another iteration of the solitaire algorithm and do this as many times as required so that the next key is not a joker.
The following function is an implementation of this algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
(defn generate-key "Takes a deck and returns a vector containing the next valid key and the deck used to generate it. The deck is returned because the solitaire algorithm is performed on the passed in deck when the generated key is a joker." [deck] {:pre [(valid-deck? deck)]} (let [topcard (first deck) topcard (if (joker? topcard) 53 topcard) [_ bottom] (split-at topcard deck) key (first bottom)] (if (joker? key) (generate-key (solitaire deck)) [key deck]))) |
On line 7 we look at the top card. On line 8 we do the check for a joker and give it the value 53 if it is. On line 9 we split the deck at that point and destructure it only binding to the bottom portion of the deck. Then, key
is given the value of the top card of the bottom portion. Line 11 does the check for the key being a joker. If it is, we recursively call generate-key
passing it a new deck that has had the solitaire algorithm performed on it. Otherwise, we return a two-element vector that contains the key and the deck. Returning the deck is necessary in the case where we must call generate-key
recursively in which case the deck that was used to call generate-key
initially has been changed.
Now we’re ready to generate the key stream by simply wrapping a recursive call to generate-key
with a call to lazy-seq
as follows:
1 2 3 4 5 6 7 8 |
(defn solitaire-keystream "An infinite sequence of keys generated by performing the solitaire algorithm on the given deck repeatedly producing a key each time." [deck] {:pre [(valid-deck? deck)]} (let [[key newdeck] (generate-key (solitaire deck))] (lazy-seq (cons key (solitaire-keystream newdeck))))) |
Note that this actually produces an infinite key stream!
Keying the Deck
At the beginning of this post I had mentioned that you must start with a deck “in an order that must be known to both the sender and receiver of the encrypted message”, but I did not say how that order could be arrived at. The process of putting the deck in some agreed-upon order is called “keying the deck”. In his article Mr. Schneier talks about several ways that a deck can be keyed:
- Use identically shuffled decks.
- Use a bridge ordering. This is a method that uses a bridge hand found in, say, a newspaper and converting that into a deck ordering.
- Use a passphrase.
The first two methods can be done straightforwardly, but using a passphrase will require an algorithm. Mr. Schneier talks about a method that uses the solitaire algorithm itself to do this. First, start with an ordered deck: lowest card to highest card, in bridge suits (clubs, diamonds, hearts, and spades). Then, perform the solitaire algorithm on it but, instead of finding an output card, perform another count cut using the first letter (converted to a number) of the passphrase to determine where to cut. This process is repeated for each character of the passphrase. The following function takes a deck and a passphrase and returns the keyed deck:
1 2 3 4 5 6 7 8 9 10 11 |
(defn key-deck "Uses the given passphrase to key deck using the solitaire algorithm." [deck passphrase] {:pre [(valid-deck? deck) (valid-message? passphrase)]} (let [key-deck-with-char (fn [deck pass-char] (let [pass-char-val (letter-to-number pass-char)] (-> deck solitaire (cut-preserve-bottom pass-char-val))))] (reduce key-deck-with-char deck passphrase))) |
I always love an opportunity to use a fold or reduce and the key-deck
function was one of those opportunities. Of course, the important part is the function you pass to reduce
which I define in the let
block as key-deck-with-char
on line 6. It takes a deck and a single character from the passphrase. It first converts the character to an integer on line 7 and then uses the ->
macro on line 8 to thread the deck first through the solitaire
function and then through cut-preserve-bottom
which uses the previously defined pass-char-val
as the place to cut to in the deck. The value of that operation is the new deck which is also the value returned by the function itself. We call reduce
with the passed-in deck. reduce
calls key-deck-with-char
with the deck and the first character of the passphrase. The resulting deck is then passed to key-deck-with-char
along with the second character of the passphrase. This process continues until all the characters of the passphrase have been used. The deck that results from reduce
is the keyed deck.
Now, the Fun Part: Encrypting and Decrypting!
Encrypting a message with Solitaire works as follows:
- Generate a key stream whose length is equal to the number of letters in the message to be encrypted.
- Convert each card to a number.
- Convert each letter in the message to a number from 1 to 26.
- Pairwise add a number from the key stream to the corresponding number in the message, modulo 26.
- Convert each number back to a letter.
As before we don’t need to do step 2 since we’re already representing the cards as integers. But, we do need to convert letters to numbers (step 3) and numbers back to letters (step 5). The following two functions do this for us:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
(defn letter-to-number "Return the integer that corresponds to the given character where \\A (or \\a) is 1 and \\Z (or \\z) is 26." [chr] {:pre [(valid-char? chr)]} (- (int (Character/toUpperCase chr)) 64)) (defn number-to-letter "Returns the upper-case character that is represented by the given integer where the integers from 1 to 26 map to characters A through Z." [num] {:pre [(< 0 num 27)]} (char (+ (mod (- num 1) 26) 65))) |
I should also mention the function pad-to-mod-5-with-x
. As Bruce mentions in his Solitaire page it’s tradition to break the message to be encrypted into groups of five and to use “X”‘s to pad the end of the message, if necessary. This step isn’t strictly necessary but I’ve implemented it in the code anyway. Here it is:
1 2 3 4 5 6 7 |
(defn- pad-to-mod-5-with-x "Returns a string that is the given string padded with \"X\" so that its length is an integer number of 5 characters." [s] (let [mod5 (mod (count s) 5) num-pads (if (zero? mod5) 0 (- 5 mod5))] (apply str (concat s (repeat num-pads \X))))) |
With those helper functions out of the way I now present the encrypt
function:
1 2 3 4 5 6 7 8 9 10 11 12 |
(defn encrypt "Encrypts the message text using the given deck. Returns the cypher text as string." [message deck] {:pre [(valid-deck? deck) (valid-message? message)]} (let [key-stream (solitaire-keystream deck) msg (pad-to-mod-5-with-x message) message-vals (map letter-to-number msg) encode-key-and-letter (create-combining-fn +) encoded-vals (map encode-key-and-letter key-stream message-vals)] (apply str (map number-to-letter encoded-vals)))) |
This function takes the plain-text message to be encrypted and the deck to be used for the encryption. On line 7 we use the deck to create the key stream. Line 8 does any necessary padding of the message and line 9 converts the message to a sequence of integers. Line 10 creates an encoding function using a helper function which I’ll go over in a moment. The last line of the let
block produces the encoded values: a sequence of integers which represent the cypher text. Finally, the body of the let produces the actual cypher text by mapping the encoded values to letters and creating a string out of them.
Now, what I call the combining function, encode-key-and-letter
, is created using a helper function, create-combining-fn
, which I use to remove some duplication between the encrypt
and decrypt
functions.
Speaking of the decrypt
function:
1 2 3 4 5 6 7 8 9 10 11 |
(defn decrypt "Decrypts the given encoded message using the given keyed deck. Returns the decoded message as a string." [encrypted-message deck] {:pre [(valid-deck? deck) (= 0 (mod (count encrypted-message) 5))]} (let [key-stream (solitaire-keystream deck) message-vals (map letter-to-number encrypted-message) decode-key-and-letter (create-combining-fn -) decoded-vals (map decode-key-and-letter message-vals key-stream)] (apply str (map number-to-letter decoded-vals)))) |
decrypt
is very similar to encrypt
with a few notable differences. First, decrypt
does not modify the input cipher text by calling pad-to-mod-5-with-x
; it is assumed the the cipher has been encrypted using the encrypt
function so the cipher text will already have a mod-5 length. Besides, it would be inappropriate to make such a modification of the cipher text in any case. Also, the creation of the combining function uses -
instead of +
. Finally, the message-vals
and key-stream
arguments to the map
call on line 10 are reversed.
Removing Duplication
I just mentioned that encrypt
was very similar to decrypt
; in fact, it’s embarrassingly similar! If you’ve looked at the code repo, you’ll have seen that these two functions are not actually coded this way because I’ve already removed the duplication. The first thing I did was to remove the padding of the message text in encrypt
. As mentioned previously it’s only for reasons of tradition that this is done and it’s not strictly necessary. After that, the only real difference between the functions is the combining function and the order of message-vals
and key-stream
. This is easily dealt with. I abstracted the duplication of the two functions with the following function:
1 2 3 4 5 6 7 8 9 10 11 12 |
(defn- create-encrypt-decrypt-fn "A higher-order-function used to create either the `encrypt` or `decrypt` function. Factors out the duplication that would exist if these functions were coded without it." [combining-fn] (fn [txt deck] {:pre [(valid-deck? deck) (valid-message? txt)]} (let [key-stream (solitaire-keystream deck) message-vals (map letter-to-number txt) combined-vals (map combining-fn key-stream message-vals)] (apply str (map number-to-letter combined-vals))))) |
This is a higher order function that both takes a function as input (combining-fn
) and returns a function as output. So we’re now passing in the combining function but what about the order of message-vals
and key-stream
? The only reason that decrypt
needed to reverse these two values was the simplicity of the combining function but this is easily remedied. With the above function we can now define encrypt
and decrypt
like so:
1 2 3 |
(def encrypt (create-encrypt-decrypt-fn (create-combining-fn +))) (def decrypt (create-encrypt-decrypt-fn (create-combining-fn #(- %2 %1)))) |
Notice how the function argument to create-combining-fn
in the definition of decrypt
is now #(- %2 %1)
instead of simply -
. This is how we remove the need to swap the values message-vals
and key-stream
. It’s not as elegant as simply using -
but what can you do?
Let’s See It In Action
Let’s start up a repl and walk through encrypting and decrypting a message.
1 2 3 4 5 6 7 8 9 |
~$ cd solitaire ~/solitaire$ lein repl user=> (use 'com.timmciver.crypto.solitaire) user=> (def keyed-deck (key-deck ordered-deck "aVeryLongAndSomewhatSecurePassword")) user=> (def encrypted-message (encrypt "CANTSTOPTHESIGNAL" keyed-deck)) user=> encrypted-message "OVPEXQOECBHORFASK" user=> (decrypt encrypted-message keyed-deck) "CANTSTOPTHESIGNAL" |
After loading up the solitaire code I def a var keyed-deck
using the key-deck
function with a password on line 4. Next, I encrypt a message using that deck on line 5 and on line 6 I display that encrypted message. Finally, I decrypt the message on line 8 and you can see that we get the original message back again. That’s it. Pretty cool, huh?