[Next] [Up] [Previous] [Index]
Main : Index : Pencil and Paper Systems : Fun With Playing Cards

# Fun With Playing Cards

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.

### My Playing Card Cipher

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
```

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. One way to eliminate this would be to count only red cards from the front of the deck, and only black cards from the back. Another would be to take any card from the front, and then take a card in any of the other three suits to that of that card from the back. A third way would simply be to subtract the keystream digit from 9, thus changing even digits to odd, whenever the first card in the deck is red. 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: From the beginning of the deck, take the first face card, treating J as 1, Q as 2, and K as 3, and then count face cards to find a face card. If that face card is red, add 1 to the keystream digit, otherwise, do not change it. Take one card from the end of the deck as previously described, but from the beginning of the deck, use the first red card from A to 10 to find a red card from A to 10, and the first black card from A to 10 to find a black card from A to 10. Add the three cards thus found to form the keystream digit.

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.

### The Keying Procedure

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
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] [Up] [Previous] [Index]