CS 107 (Spring '09)
[Schedule] [Programs] [Notes & Reference] [Examples][Syllabus] [Lab & TA] [Tests] [Grades]

Program #4: Decrypt

Prof. Reed, CS 107, Spring '09
Due Wednesday 4/8 at 1:00 PM

While a student at UIC during spring break you hear on the news that your computer professor has disappeared. The last action he performed before falling out of sight was to send an encrypted email to his students. That email message contained:

IQHN OH XALM EJG JYOQ NBGNRV KMBQJ ZTNZZV BH QIQWSHY OH GF RTKHM JUUQOW AHUGX TBGJZZ OIQG KZTG MAY JCYR GZI YS MAY KWDDB

Because you had been talking about it in class before break, you know that this message was created by:

  1. Taking the original text and possibly reversing each word.
  2. Transposing each word by some amount. This is called the Caesar cipher. For instance transposing by 1 would convert "abc" to "bcd", and would convert "xyz" to "yza". Transposing letters at the end of the alphabet "wraps around" back to the beginning of the alphabet
  3. Use the Vigenere cipher with some keyword. You are certain the keyword is one of the words in the following paragraph:

Students I hope you are learning how to use a computer They can be tricky but powerful when you figure out how to use them In addition having technical skills can advance your career in ways you would not otherwise In any case this course will be over in about five weeks

Your job is to figure out what the encrypted text says by writing a computer program to try all possible encryption combinations. For each combination you will take the resulting text and look up the words in a dictionary to see if it is likely that particular combination is the original message.

Further Explanation

In order to try and decode the message, it is helpful to fully understand how the original plain text was encrypted in the first place. The first step reverses text. For instance, input of
     hard work
when reversed would look like
     drah krow
Be sure to check both the original order as well as reversed order when decrypting.

Next comes the transposition step, also called a Caesar cipher. The sample input of
     hard work
when transposed by 1 would look like
     ibse xpsl
Note that non-alphabetic characters are not transposed. The reversed text can also be transposed, which would give:
     esbi lspx

Next comes the Vigenere cipher, which uses an Vigenere table which looks like:

   A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
 

A  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
B  B C D E F G H I J K L M N O P Q R S T U V W X Y Z A 
C  C D E F G H I J K L M N O P Q R S T U V W X Y Z A B 
D  D E F G H I J K L M N O P Q R S T U V W X Y Z A B C 
E  E F G H I J K L M N O P Q R S T U V W X Y Z A B C D 
F  F G H I J K L M N O P Q R S T U V W X Y Z A B C D E 
G  G H I J K L M N O P Q R S T U V W X Y Z A B C D E F 
H  H I J K L M N O P Q R S T U V W X Y Z A B C D E F G 
I  I J K L M N O P Q R S T U V W X Y Z A B C D E F G H 
J  J K L M N O P Q R S T U V W X Y Z A B C D E F G H I 
K  K L M N O P Q R S T U V W X Y Z A B C D E F G H I J 
L  L M N O P Q R S T U V W X Y Z A B C D E F G H I J K 
M  M N O P Q R S T U V W X Y Z A B C D E F G H I J K L 
N  N O P Q R S T U V W X Y Z A B C D E F G H I J K L M 
O  O P Q R S T U V W X Y Z A B C D E F G H I J K L M N 
P  P Q R S T U V W X Y Z A B C D E F G H I J K L M N O 
Q  Q R S T U V W X Y Z A B C D E F G H I J K L M N O P 
R  R S T U V W X Y Z A B C D E F G H I J K L M N O P Q 
S  S T U V W X Y Z A B C D E F G H I J K L M N O P Q R 
T  T U V W X Y Z A B C D E F G H I J K L M N O P Q R S 
U  U V W X Y Z A B C D E F G H I J K L M N O P Q R S T 
V  V W X Y Z A B C D E F G H I J K L M N O P Q R S T U 
W  W X Y Z A B C D E F G H I J K L M N O P Q R S T U V 
X  X Y Z A B C D E F G H I J K L M N O P Q R S T U V W 
Y  Y Z A B C D E F G H I J K L M N O P Q R S T U V W X 
Z  Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

To use this a special keyword is used. For this example lets use the keyword: HIDDEN

Encoding:

Take the plaintext message and write the keyword over it, repeating it as many times as you need it until each plaintext message has a letter over it. This would give you:

HIDDENHID  <-repeated keyword
HARD WORK  <-original plaintext message

Now use the vertical pairs of letters to encode the plaintext message (hard work). The first (left-most) vertical pair of letters are 'H' on the top row and 'H' on the bottom row. Use the top 'H' as the row in the above table, and the bottom 'H' as the column, giving you the letter 'O'. The next vertical pair of letters are 'I' on the top and 'A' on the bottom. Use 'I' as the row, and 'A' as the column, giving you the letter 'I'. Next comes 'D' and 'R', which gives the letter 'U' (this is highlighted in bold in the table above). Resolving these pairs in turn gives:

HIDDENHID  <-repeated keyword
HARD WORK  <-original plaintext message
OIUG JVZN  <-ciphertext (the encoded message)

Note that spaces are not looked up in the table, but are simply copied to the ciphertext. Also note that the "plaintext" message in our case may already be reversed and transposed, which for the example we've been developing above would give:

HIDDENHID  <-repeated keyword
ESBI LSPX  <-original message that has been reversed and transposed
LAEL YZXA  <-ciphertext (the encoded message)

So in this case, your program would need to take the String "LAEL YZXA" and try to figure out what the original text was.

Decoding:

To decipher a message simply take the top letter (from the keyword row, e.g. 'H' in the left-most column below) and follow it across until you find the corresponding ciphertext character (e.g. 'O' in the left-most column below). The character that is the label for that colum (e.g. 'H' in this case) is the original plaintext character.

HIDDENHID  <-repeated keyword
???? ????  <-original plaintext message
OIUG JVZN  <-ciphertext (the encoded message)

In our case you don't know what the keyword is, but you do know it is one of the words in the paragraph given near the top of this program description. You will need to try each word in that paragraph as a keyword. As you try each word your program will generate what it thinks are the words in the plaintext message. To avoid having to read all these yourself, your program must look up these possible words in a dictionary and keep track of how many of them are found. The keyword that gives the most correct dictionary words is the one that is likely to be correct. Lucky for you I've given you the dictionary lookup code and the dictionary file already (see link to file below).

Your program has the added complication that you won't be able to tell right away if a keyword is correct, because the original message may have also been transposed and reversed. So you not only need to look up the words generated for each keyword, but for each of those keyword sets you must also try all possible transpositions and direction (forwards and reverse) and then look up the words in the dictionary.

You need to know the following concepts in order to write this program:

Everything from the previous programs; arrays of char; converting back and forth between String and array of char;

Notes:

  1. Use the program Decrypt.java as a starting point. This program includes the code for dictionary lookup. It also illustrates how to take an input String and convert it directly into an array of Strings. You will also need to have this dictionary of words in the same directory where your program is run from so that the dictionary file can be opened and the dictionary lookup can function correctly.
  2. I recommend you first write the code to encrypt a message using the approaches explained above. Then you will be able to test your program because you will know what the original plaintext code is supposed to be. Once this is working it should be fairly easy to switch it around and go the other way to decrypt some cyphertext.
  3. At some point in your program you may want a convenient way to convert back and forth between an array of characters and a String. You can do this as follows: 
    // create a String
String originalString = "crazy";
// make an array of letters with the characters from this String

char[] newLetters = originalString.toCharArray();
// At some point if you have an array of letters and you want to
//    create a String from them, you can use the following:
String result = String.copyValueOf( newLetters);
  4. Similarly you can take an input line of multiple words and split it into an array of Strings as follows:
    5. System.out.print("Enter some words on a line, with a single space between words: ");
    userInput = keyboard.nextLine();
    // convert to all upper case
    userInput = userInput.toUpperCase();
    // make an array of strings by splitting the input line at spaces
    String[] wordsArray = userInput.split(" ");
// Now you can handle the words individually.  For instance to display the first word:
System.out.println("First word is: " + wordsArray[ 0] );
  5. Turnin your program electronically using the "turnin" command from your CS account on ernie.cs.uic.edu as follows:
    6. turnin -c cs107 -p program4 Decrypt.java
    where the single file containing the solution for this project is called Decrypt.java. Do not turn in the entire directory, and do not turn in the dictionary file. Failure to use turnin to submit this program will result in at least a 5 point deduction.


[CS Dept] [UIC] [Prof. Reed]