Bruce Schneier designed what he calls the “Solitaire” system that field agents could use to encrypt their messages securely. All they needed was a full deck of 52 cards plus two jokers, and a whole lot of time. This system is used in Neal Stephenson’s novel Cryptonomicon
In this assignment, you will implement a simplified version of the Solitaire encryption algorithm. Simplified because you will use a half deck of 26 cards, plus two jokers. You will store the deck in a CIRCULAR linked list. What follows is a description of the encryption/decryption algorithm.
The algorithm starts with a deck in some random order. It uses this deck to generate what is called a keystream, which is a sequence of numbers called keys. Each key will be a number between 1 and 26. Imagine that you want to encrypt the following message to send to your friend:
DUDE, WHERE'S MY CAR?
Imagine also that you start with the following half deck of cards, with the two jokers given values of 27 (Joker “A”) and 28 (Joker “B”):
INITIAL DECK: 13 10 19 25 8 12 20 18 26 1 9 22 15 3 17 24 2 21 23 27 7 14 5 4 28 11 16 6
Starting with this deck, you will get the following keystream (you will see how), one key for every alphabetic character in the message to be encrypted. Here’s the message again, with everything but the letters taken out of consideration, followed by a parallel list of integers which correspond to the positions of the message letters in the alphabet, and finally, the keystream, one key per character:
Message: D U D E W H E R E S M Y C A R Alphabet: 4 21 4 5 23 8 5 18 5 19 13 25 3 1 18 Position Keystream: 7 16 5 8 8 15 26 9 14 23 12 15 25 3 1
Encryption is then done by simply adding each key of the keystream to the corresponding alphabetic position, and if this sum is greater than 26, subtracting 26 from the sum. Here’s the resulting sequence of numbers:
11 11 9 13 5 23 5 1 19 16 25 14 2 4 19
The numbers are converted back to letters, to get the following encrypted message.
Decryption follows a similar process.
When the decrypter gets the coded message, she generates the keystream in exactly the same way, using the same original deck as the encryption. Then, the keystream is subtracted from the alphabetic position values of the letters in the coded message. If a code value is equal or smaller than the corresponding decryption key, 26 is first added to it and then the key is subtracted:
Code: 11 11 9 13 5 23 5 1 19 16 25 14 2 4 19 Keystream: 7 16 5 8 8 15 26 9 14 23 12 15 25 3 1 -------------------------------------------------------------------- Message: 4 21 4 5 23 8 5 18 5 19 13 25 3 1 18 D U D E W H E R E S M Y C A R
Download the solitaire_project.zip file attached in the Sakai assignment. DO NOT unzip it. Instead, follow the instructions on the Eclipse page under the section “Importing a Zipped Project into Eclipse” to get the entire project into your Eclipse workspace.
You will see a project called Solitaire with the classes CardNode (which implements a node of the linked list deck), Solitaire (which implements the encryption and decryption algorithms), and Messenger (the application driver), all in the package solitaire.
You will also see a sample input file, deck.txt, DIRECTLY UNDER THE PROJECT FOLDER (NOT under solitaire or src). This is where other input files must go when you test your program.
You need to fill in the implementation of the Solitaire class where indicated in the Solitaire.java source file.
The printList method has been implemented for your convenience - you may use it to print the deck for verification/debugging. (But it is NOT used by us when testing your program - see the Grading section at the end for details.)
Do NOT change CardNode.java in any way.
While working on Solitaire.java:
- You may NOT add any import statements to the file.
Note: Sometimes Eclipse will automatically add import statements to the file, if you are using an unknown class other than the ones you are given. It is your responsibility to delete such automatically added import statements. At the time of grading, we will delete all such additional import statements we find, before compiling your code. If your code does not compile, we will not be able to test it, and you will get a zero.
- You MUST work with CIRCULAR LINKED LISTS only. You may NOT transfer the contents of the linked lists to arrays or other data structures for processing.
- You may NOT add any new classes (you will only be submitting Solitaire.java).
- You may NOT add any fields to the Solitaire class.
- You may NOT modify the headers of any of the given methods.
- You may NOT delete any methods.
- You MAY add helper methods if needed, as long as you make them private.
The java.lang.Character class has several useful methods for manipulating characters. Here are a few you may find useful.
You can switch between character and integer values using casts. Here’s an example that starts with the character ‘D’, gets its position in the alphabet (4), adds 1 to it, and gets the next character (‘E’):
char ch = 'D';
System.out.println(ch); // D
int c = ch-'A'+1
System.out.println(c); // 4
ch = (char)(c-1+'A');
System.out.println(ch); // E
Make sure you read the comments above each method in the code for additional details on what the method does. This information, in addition to the specification in this document, is essential to correctly implement the method.
The class Messenger has a main method, so it can be run as a Java application.
Here’s a sample run to encrypt a message, with the deck supplied in the file deck.txt (which came with the project):
Enter deck file name => deck.txt Encrypt or decrypt? (e/d), press return to quit => e Enter message => DUDE, WHERE'S MY CAR? Encrypted message: ODALGGPCLAVJNAP
And here’s a sample to decrypt a message that was encrypted using deck.txt:
Enter deck file name => deck.txt Encrypt or decrypt? (e/d), press return to quit => d Enter message => ODALGGPCLAVJNAP Decrypted message: DUDEWHERESMYCAR
You should look at the code in Messenger and understand that it reads the deck from whatever input file you specify, and sets up the Solitaire object’s linked list for this deck, by calling the makeDeck method. It then calls the encrypt or decrypt methods.
Make sure you test your code comprehensively with other test cases of your own. Pay particular attention to the extreme or special cases in each of the steps of the algorithm. Remember, when you create other test input files, you should put them alongside deck.txt, DIRECTLY UNDER THE PROJECT FOLDER.
You may assume that all input decks will be legitimate: a deck will consist of (only) values from 1 through 28 in some order. So you don’t need to do any check on input format.
You may also assume that all the letters in the string to be encrypted or decrypted will be uppercase, so you don’t need to do any checking. But the string to be encrypted may have spaces, punctuation characters, etc. which should be ignored while encrypting. So the decrypted string will only have uppercase letters, even if the input string that was encrypted had characters other than letters.
Since there will no be no errors in input, you will not need to throw any exceptions.
Submit your Solitaire.java source file (NOT Solitaire.class) in Sakai.
You will ONLY submit this file, which means you should not make any changes to CardNode.java because we will be using the original CardNode.java to test your implementation.