The Somewhat Simplified Solitaire Encryption Algorithm
Lester I. McCann
Department of Computer Science
The University of Arizona
The Somewhat Simplified Solitaire (SSSolitaire) Encryption Algorithm --
Bruce Schneier created the card-deck-based Solitaire encryption
algorithm for Neal Stephenson's novel "Cryptonomicon." A
slightly reduced version of Solitaire requires little more than basic
list operations and provides an introduction to encryption.
Linear data structures; encryption.
Accessible by students from late CS1; more appropriate for CS2.
What I like about the assignment is
that it is inspired by an algorithm that is a key element in
a work of fiction. Not only does implementing the algorithm
give the students exposure to encryption and practice with
list manipulation, it can also encourage students to pick up
Simplifying Solitaire no doubt creates an algorithm that is
less resistant to cryptographic attack, but for CS1/CS2 students
that isn't much of a problem.
Students need to be able to handle list manipulations, perform
input from a text file (if they will be expected to read card
decks from a file), and accept that large, complex algorithms
are often merely composed of small, simple algorithms.
Here are three ideas: (1) Vary the number of cards in the
deck. I use 28, which works well with the upper-case letters.
but one could use 38 to include decimal digits.
(2) The algorithm steps can be adjusted in any number of ways.
(3) More advanced students could perform basic statistical
analyses of the algorithm or any variation. See the PDF of the
talk for some additional ideas.
A Bit of Background
The following algorithm description makes the following assumptions:
- Schneier's algorithm assumes a full 52-card deck, plus two jokers.
One fine reason to modify the algorithm is to reduce the size of the
deck so that you can include easy-to-follow examples in an assignment
handout. Half of a deck can fit on one line! For that reason,
I'll present the algorithm here using a half-deck (28 cards).
- Sometimes I use two-character representations of cards, and sometimes
(like here) just integers. I generally specify the sequence for the
students: A,K,Q,J,10-2 of Spades are 1-13, and Hearts are 14-26.
- Steps 1 and 2 are slightly different (slightly simplified, you might say)
than Schneier's. I found that students tended to get stuck on the
interpretation of Schneier's first two steps, even though it isn't
difficult to follow. Moving to a circular list approach avoids that point
of confusion and has the added advantage of getting them some practice
with circular lists.
The SSSolitaire Keystream Algorithm
Assume a half-deck of cards (the cards of two suits, numbered 1-26)
plus two jokers ("A" (#27) and "B" (#28)).
- Find the A joker (27).
Exchange it with the card beneath (after) it in the deck, to move
the card down the deck by one position.
(What if the joker is the last card in the deck?
Imagine that the deck of cards is
continuous; the card following the bottom card is the top card of
the deck, and you'd just exchange them.)
- Find the B joker (28). Move it two cards down by performing two
- Swap the cards above the first joker (the one closest to the top of
the deck) with the cards below the second joker. This is called
a triple cut.
- Take the bottom card from the deck. Count down from the top card by
a quantity of cards equal to the value of that bottom card. (If the
bottom card is a joker, let its value be 27, regardless of which
joker it is.) Take that group of cards and move them to the bottom
of the deck. Return the bottom card to the bottom of the deck.
- Look at the top card's value (which is again 1-27, as it
was in the previous step). Put the card back on top of the deck.
Count down the deck by that many cards. Record the value of the
NEXT card in the deck, but don't remove it from the deck. If that
next card happens to be a joker, don't record anything. Leave
the deck the way it is, and start again from the first step,
repeating until that next card is not a joker.
Assume that this is the original ordering of our half--deck of cards:
1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 27 2 5 8 11 14 17 20 23 26
Step 1: Swap 27 with the value following it. So, we swap 27 and 2:
1 4 7 10 13 16 19 22 25 28 3 6 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
Step 2: Move 28 two places down the list. It ends up between 6 and 9:
1 4 7 10 13 16 19 22 25 3 6 28 9 12 15 18 21 24 2 27 5 8 11 14 17 20 23 26
Step 3: Do the triple cut. Everything above the first joker (28 in this
case) goes to the bottom of the deck, and everything below the second (27)
goes to the top:
5 8 11 14 17 20 23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 6
Step 4: The bottom card is 6. The first 6 cards of the deck are 5, 8, 11,
14, 17, and 20. They go just ahead of 6 at the bottom end of the deck:
23 26 28 9 12 15 18 21 24 2 27 1 4 7 10 13 16 19 22 25 3 5 8 11 14 17 20 6
Step 5: The top card is 23. Thus, our generated keystream value is the
24th card, which is 11.
- Talk Slides (PDF): solitairetalk.pdf
- Basic Assignment Handout:
- Crude Implementation (as obfuscated .class files):
- JAR: SSS.jar (Extract with: jar -xf SSS.jar) Contents:
- Encrypt.class: Encrypts text. Usage: java Encrypt [deckfile]
- Note: Use a 28-card (half-deck) deck file for Encrypt
- Decrypt.class: Decrypts text. Usage: java Decrypt [deckfile]
- Note: Use a 28-card (half-deck) deck file for Decrypt
- DeckFile.class: Creates deck files. Usage: java DeckFile