The Somewhat Simplified Solitaire Encryption Algorithm

Lester I. McCann
Department of Computer Science
The University of Arizona
mccann@cs.arizona.edu


Overview

Summary 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.
Topics
 Linear data structures; encryption.
Audience
 Accessible by students from late CS1; more appropriate for CS2.
Difficulty
 Moderate
Strengths
 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 the novel!
Weaknesses
 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.
Dependencies
 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.
Variants
 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:
  1. 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).
  2. 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.
  3. 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)).
  1. 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.)
  2. Find the B joker (28). Move it two cards down by performing two exchanges.
  3. 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.
  4. 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.
  5. 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.

An Example:

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.

Materials


References