To accompany the recent novel Cryptonomicon, Bruce Schneier, author of Applied Cryptography, developed a cipher using the 52 playing cards and two jokers called Solitare, which is described on the Counterpane web site.
This has been an inspiration to both myself and others; for example, Paul Crowley has developed another cipher using playing cards called Mirdek.
I, too, have now succumbed to the temptation to construct an alternative to Solitare. The basic cycle that takes a deck that has already been scrambled to produce a keystream operates as follows:
Step 1: From the prepared deck (the order of the cards in it is the key), turn up, and deal out face up in a row, successive cards until the total of the cards (A=1, J=11, Q=12, K=13) is 8 or more.
Step 2: If the last card dealt out in Step 1 is a J, Q, or K, take its value, otherwise take the total of the values of the cards dealt out in Step 1. (This gives a number from 8 to 17.) In the next row, deal out that many cards from the top of the deck.
Step 3: Deal out the rest of the deck under that row, in successive rows that begin on the left, and end under the lowest card in the top row, the next lowest card in the top row, and so on, in rotation. A red card is lower than a black card of the same denomination, and when there are two cards of the same color and denomination, the first one in the row is considered lower.
These first three steps may lead to a layout which looks like this:
7S QH 3D 6S 3C 2D QD 4S 8S JS JD 10H QC 8H 5H AC 6D KS 10C QS 9D 5D 2H 3S KD JH 2S 9C 9H 6H 8C 2C 7H JC 4C 8D 3H KC 7D 6C AH 4H 5C 10D 10S 7C 9S KH 4D AD 5S AS
Step 4: Take the cards dealt out in Step 3, and pick them up by columns, starting with those under the lowest card in the row dealt out in Step 2. The top card in the column is to be on the bottom of a pile of face up cards, and the first column picked up is to be on the bottom of the re-assembled deck.
Step 5: Place the cards dealt out in Step 2 (the last one on the bottom) in face-up form on top of the re-assembled deck, and then the cards dealt out in Step 1, again, the last one on the bottom of a face up pile put on top of the re-assembled deck.
Step 6: Turn the deck of cards over to face-down position to repeat Step 1.
Thus, these steps would cause the following new order of the deck to result from the layout above:
KS JH JC 7C 5H 10C QS 2H 9H 8C 5C AD 6D 5D KD 7H 10S AS 9C 8D KH AC 9D 3S 6H 2C 10D 5S 4H 3H 4D 6C 7D KC 2S 4C 9S AH 8H QC 10H JD JS 8S 4S QD 2D 3C 6S 3D QH 7S
And the cards that were at the beginning of the deck, and thus controlled the transposition, are now at the end of the deck, and will be subject to the next transposition instead of controlling it.
After doing this three times, obtain a keystream digit as follows:
Looking at the cards from the top of the deck, ignore all J, Q, and K cards; take the first other card, from A to 10, and count down that many cards to find a card from A to 10. Do the same from the bottom of the deck. The last digit of the sum of the values of those two cards is the keystream digit.
Applying this to the scrambled deck obtained above (which is cheating a bit, since in practice the transposition has to be done three times), it works this way:
KS JH JC 7C 5H 10C QS 2H 9H 8C 5C AD 6D
(7) 1 2 3 4 5 6 7*
5D KD 7H 10S AS 9C 8D KH AC 9D 3S 6H 2C
10D 5S 4H 3H 4D 6C 7D KC 2S 4C 9S AH 8H
QC 10H JD JS 8S 4S QD 2D 3C 6S 3D QH 7S
7* 6 5 4 3 2 1 (7)
the two selected cards are the ace of diamonds and the ten of hearts, so the keystream digit is a 1.
This way, people don't have to memorize a bridge ordering of the suits, and they use a straddling checkerboard to allow false addition to apply the key, instead of trying to do Vigenere or modulo-26 arithmetic in their heads.
I have received notification, in a recent E-mail, of a serious weakness in this design. Although the two cards selected are selected independently from the two halves of the deck, since they are two different cards, there is a small bias against their having the same value. Since their values are added together, rather than combined by exclusive-OR or subtraction, this bias is spread over all the even numbers.
Since at least the first two possibilities might conceivably weaken the cipher, perhaps what should be done is to find the first face card from the end of the deck, and if it is a J, Q, or K, respecively, then use the first, second, or third method of removing the bias. But this cipher is already too complicated without such an addition. Two other ways to eliminate the bias, which are in some ways even more complicated, but which might also seem simpler from other perspectives, and safer than those so far examined, might also be considered:
|
By limiting the mental arithmetic required, I'm trying to make my method simpler. However, the way in which the cards are rearranged is more complex; the cards are dealt out in a layout, not merely manipulated in a straight line, and thus the result looks somewhat more like a game of solitare. In the novel, the cipher Solitare was based on a computer stream cipher; my method for using playing cards is instead based on an old pencil-and-paper cipher.
The method of transposition used is the one given by General Luigi Sacco, that breaks up a block into uneven units, and which perhaps has some advantages over ordinary columnar transposition.
Of course, some of the rules used mean that there are biases in the transposition; if every card had a distinct value, the order of the columns would be slightly more random, and the rule intended to limit the row size to 17 instead of 21 makes 11, 12, and 13 more likely row lengths. Note that Step 4 is set up to make the scrambling invertible, so I did accept some good advice from Bruce Schneier's Solitare. The well-known reason for this is noted elsewhere on this site: a non-invertible transformation risks shrinking the state space of the thing transformed. That is: the fact that the transformation is invertible is no guarantee of a long or maximal period. But if every possible ordering of the deck is possible at the start, then every possible ordering of the deck remains possible after 20, 30, or 2000 iterations of an invertible transformation. If two orderings of the deck both transformed to the same ordering of the deck, then the transformation would not be invertible. On the other hand, with a non-invertible transformation, the number of possible orderings can continue to shrink as the transformation is repeated.
Starting with a deck in a fixed order, say AS 2S ... KS AH 2H ... KH AD 2D ... KD AC 2C ... KC, the procedure to obtain a scrambled deck order from a keyphrase is as follows:
Divide the keyphrase into parts that are eight or more letters in length as follows: first, use all the words that are eight or more letters long in the phrase, then, go through the phrase, and, using only the shorter words, take as many words as needed at a time to reach eight or more letters. When the last part is formed, and there are less than eight unused letters in the key phrase, include them in the last part.
Then, take these parts of the keyphrase, and use them in pairs.
First, for each part, imagine the word as standing above the columns of cards, and then perform Step 3 and Step 4 of the normal cycle, but on the entire deck.
Example:
Phrase: THE QUICK BROWN FOX JUMPED OVER THE LAZY DOG
This phrase has the parts:
THEQUICK BROWNFOX JUMPEDOVER THELAZYDOG
So, the first two parts lead to the deck being scrambled as follows:
First, the deck is laid out like this:
T H E Q U I C K 7 4 2 6 8 3 1 5 AS 2S 3S 4S 5S 6S 7S 8S 9S 10S JS QS KS AH 2H 3H 4H 5H 6H 7H 8H 9H 10H JH QH KH AD 2D 3D 4D 5D 6D 7D 8D 9D 10D JD QD KD AC 2C 3C 4C 5C 6C 7C 8C 9C 10C JC QC KC
Since the first card of a column is placed on the bottom when the cards are face up, and the first column picked up is at the bottom of the cards when they are face up, they will be on the top when the deck is in normal face-down order, and so this step leads to the cards being in the order:
7S QH 4C 3S 10S KS 8H 3D 8D KD 7C 10C 6S 3H JH 3C KC 2S 9S QS 5H 7H 2D 7D QD 6C 9C KH 4S AH 9H 4D 9D AC JC AS 8S JS 4H 6H AD 5D 6D JD 5C 8C 5S 2H 10H 10D 2C QC
Now, the deck is then laid out like this for the second part:
B R O W N F O X 1 6 4 7 3 2 5 8 7S QH 4C 3S 10S KS 8H 3D 8D KD 7C 10C 6S 3H JH 3C KC 2S 9S QS 5H 7H 2D 7D QD 6C 9C KH 4S AH 9H 4D 9D AC JC AS 8S JS 4H 6H AD 5D 6D JD 5C 8C 5S 2H 10H 10D 2C QC
which, when picked up, places the deck in this order:
7S QH 3D 6S 3C 2D QD 4S 8S JS JD 10H QC 8H 5H AC 6D KS 10C QS 9D 5D 2H 3S KD JH 2S 9C 9H 6H 8C 2C 7H JC 4C 8D 3H KC 7D 6C AH 4H 5C 10D 10S 7C 9S KH 4D AD 5S AS
Then, each of the two parts is used to scramble half of the deck again; the transpositions above depended on the order of letters in each part, but this step will instead depend on which letters are present.
Go through the alphabet, from A through Z, as you take cards from the top of the deck. When you reach a letter that is part of the current part of the keyphrase, that card completes the current pile you are making. The next card starts a new pile. Z always completes the last pile, even if it is not present.
Then put the piles back together, but in the reverse order in which they were obtained.
Thus, the first part, THEQUICK, divides the first half of the deck like this:
A B C 7S QH 3D D E 6S 3C F G H I 2D QD 4S 8S J K JS KD L M N O P Q 10H QC 8H 5H AC 6D R S T KS 10C QS U 9D V W X Y Z 5D 2H 3S KD JH
causing that half of the deck to be placed in the order:
5D 2H 3S KD JH 9D KS 10C QS 10H QC 8H 5H AC 6D JS KD 2D QD 4S 8S 6S 3C 7S QH 3D
Then, the second half, BROWNFOX, is applied to the second half of the deck.
When there is an odd part of the key phrase, then the deck is transposed with that part, and only its first half is mixed again.
Once the entire keyphrase is applied to the deck of cards, the deck is then subjected to a non-invertible triple cut, as follows:
From each end of the deck, a card with a value from A to 10 is located, by the procedure used to find the keystream numbers in normal encipherment. Then, starting from the top of the deck when it is face down, which we will assume is placed on the left, additional cards are counted from that card according to its value: one more card if it is an ace, two more if it is a deuce, and so on, but this time, face cards are not ignored.
This part of the deck is then placed on the right-hand side.
The procedure is repeated from the other keystream card, again counting inwards. If cards are left, these stay in the middle, and those from the bottom of the deck to the end of the count are placed on the left-hand side.
Using the previous example of obtaining a keystream digit to illustrate how this works:
KS JH JC AH 5H 10C QS 2H 9H 8C//KC AD 6D
(1) 1* 1 2 3 4 5
5D KD 7H 6C AS 9C 8D 5C AC 9D 3S 6H 2C
7D 5S 3H 10D 4D 9S 10S//2S 4C 4H KH 7C 8H
7 6 5 4 3 2
QC 10H JD JS 8S 4S QD 2D 3C 6S 3D QH 7S
1 7* 6 5 4 3 2 1 (7)
the pairs of slashes indicate the points at which the deck will be cut, ending up in the order 2S...7S, KC...10S, KS...8C from the order above.
Finally, the cards are laid out according to the word spacing of the keyphrase:
T H E 2S 4C 4H Q U I C K KH 7C 8H QC 10H B R O W N JD JS 8S 4S QD F O X 2D 3C 6S J U M P E D 3D QH 7S KC AD 6D O V E R 5D KD 7H 6C T H E AS 9C 8D L A Z Y 5C AC 9D 3S D O G 6H 2C 7D T H E 5S 3H 10D Q U I C K 4D 9S 10S KS JH B R O W N JC AH 5H 10C QS F O X 2H 9H 8C
repeated until the deck is all laid out, and then they are picked up in face up form with the last column, and its top card, on the bottom.
In the example, that leads to the cards ending up in this order when turned face down:
6D 10H QD AD JH QS QC 4S KC 6C 3S KS 10C 4H 8H 8S 6S 7S 7H 8D 9D 7D 10D 10S 5H 8C 4C 7C JS 3C QH KD 9C AC 2C 3H 9S AH 9H 2S KH JD 2D 3D 5D AS 5C 6H 5S 4D JC 2H
Next
Table of Contents
Main page