Program #5: Enigma

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

     Encryption and decryption is the basis for secure communication online. Our last program referred to the Caesar cipher, which is vulnerable to character frequency analysis. This weakness can be addressed by advancing the transposition value after each letter. This approach was refined further in the Enigma machine used by the Germans during World War II. According to one report, the Allied breaking of the Enigma machine code shortened World War II by a year and saved hundreds of thousands of lives on both sides. Your assignment is to make a program that reproduces the functionality of a simplified version of the Enigma machine. This assignment (and much of the text below) is taken from the assignment created by Dave Reed (no relation).

Enigma machines used interchangeable rotors that could be placed in different orientations to obtain different substitution patterns. More significantly, the rotors rotated after each character was encoded, changing the substitution pattern and making the code very difficult to break. The behavior of the rotating rotors can be modeled, in a simplified form, by a device consisting of labeled, concentric rings. For example, the model below has three rings labeled with the letters of the alphabet and '#' (representing a space). To make one of your own, see this paper model, which is used in the pictures below.

To encrypt a character using this model, find the character on the inner rotor (i.e., the inside ring) and note the character aligned with it on the outer rotor (i.e., the outside ring), then find that character on the middle rotor (i.e., the middle ring) and output the one aligned with it on the outer rotor. After a character is encrypted, turn the inner rotor clockwise one step. Whenever the inner rotor returns to its original orientation, the middle rotor turns once in lock-step, just like the odometer in a car. For example, in this configuration the character 'A' would be encrypted as 'N', since 'A' on the inner rotor is aligned with 'H' on the outer rotor, and 'H' on the middle rotor is aligned with 'N' on the outer rotor. After performing this encryption, the inner rotor is rotated clockwise, so the letter 'A' would next be encrypted as 'D'.

Consider the steps taken to encrypt the plain text "HELLO" into "DFMCH"    Note that in the pictures of the paper version used below the space character is represented by a small 'b' with a line through it, rather than '#' as in the picture above.

Note that decrypting a message requires following the same steps, only in reverse (i.e., find the character on the outer rotor, note the character aligned with it on the middle rotor, find that character on the outer rotor, then output the character aligned with it on the inner rotor).

For this assignment design a Java class named Enigma (stored in file Enigma.java) that simulates this three-ring model. You may assume that the rotors have the values and positions as shown in the above diagram. The inner rotor consists of the 26 capital letters and the '#' symbol (representing a space) in the following clockwise order #GNUAHOVBIPWCJQXDKRYELSZFMT, and similarly the middle and outer rotors contain #EJOTYCHMRWAFKPUZDINSXBGLQV and #BDFHJLNPRTVXZACEGIKMOQSUWY, respectively.

Using an Enigma object, it should be possible to encode and decode text messages, with the appropriate rotation of the rotors occurring after each character encoding/decoding. For example, running your program should look like what is shown below. :

Author: Dale Reed 
Class: CS 107, Spring 2009 
Program #5: Enigma 
TA: Billie Joe Armstrong, T 6:00 AM 
April 12, 2009

Choose from the following options:
     1. Encode some text 
     2. Decode using user-entered rotor starting values 
     3. Decode by trying all possible rotor combinations 
     4. Exit program 
Your choice: 1
Enter the inner, mid, and outer rotor starting letters (e.g. ABC) or press enter for default: ABC
Enter the text to be encoded: Rats live on no evil star
TOADYUWFABMPZW WBNKP MQKW
Exiting after encoding text...

And running the program again:

Author: Dale Reed 
Class: CS 107, Spring 2009 
Program #5: Enigma 
TA: Billie Joe Armstrong, T 6:00 AM 
April 12, 2009

Choose from the following options:
     1. Encode some text 
     2. Decode using user-entered rotor starting values 
     3. Decode by trying all possible rotor combinations 
     4. Exit program 
Your choice: 2
Enter the inner, mid, and outer rotor starting letters (e.g. ABC) or press enter for default: ABC
Enter the cipherText to be decoded: TOADYUWFABMPZW WBNKP MQKW
Decoded text is: RATS LIVE ON NO EVIL STAR

Exiting program...

And running the program yet again:

Author: Dale Reed 
Class: CS 107, Spring 2009 
Program #5: Enigma 
TA: Billie Joe Armstrong, T 6:00 AM 
April 12, 2009

Choose from the following options:
     1. Encode some text 
     2. Decode using user-entered rotor starting values 
     3. Decode by trying all possible rotor combinations 
     4. Exit program 
Your choice: 3
Enter the cipherText to be decoded: TOADYUWFABMPZW WBNKP MQKW
Trying rotor combinations starting with:   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 
Decoded text is: RATS LIVE ON NO EVIL STAR

Exiting program...

 

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; How the simplified Enigma machine works; dictionary lookup as done in the previous assignment. It is really helpful for this assignment if you understand and can use the modulus operator (%), that gives the remainder after integer division.

Notes:

Note the point values shown below, out of the total possible 55 points for program execution. The first few stages are not worth any points. To get partial credit your program must at least encode user input, appropriately rotating both the inner and middle rotors.

1. Make a paper version of the Enigma machine, following the links above. (This is really helpful...)
2. Modify your solution (or mine) from the previous program to have the menus that prompt for encoding and decoding.
3. Create the arrays representing the 3 rotors. Get your program to work *without* rotating the inner rotor after each letter. Assume there is no initial rotation of rotors, with the blank character on each of the 3 rotors lined up at the top. Giving an input of "hello" followed by 23 blanks and then "hello" again would give:
   

             1         2         3     
   012345678901234567890123456789012    <- input character number
   hello                       hello    <- input
   DPFFU                       DPFFU    <- output with no inner rotor advance

4. Now rotate the inner rotor after each letter is encoded. This will give:
   

             1         2         3     
   012345678901234567890123456789012    <- input character number
   hello                       hello    <- input
   DFMCHDUKARHYOEVLBSIZPFWMCTJ UWCTY    <- output with inner rotor advance only

   Note that the encoding for the second "hello" is different than the first. This is because the very first time we encode 'h' in the first "hello", the rotors have not advanced. The inner rotor does advance once just before encoding the 'h' in the second "hello".
   
   

5. ( 5 points) Now rotate the middle rotor once after the inner rotor makes a complete rotation. This will give:
   

             1         2         3     
   012345678901234567890123456789012    <- input character number
   hello                       hello    <- input
   DFMCHDUKARHYOEVLBSIZPFWMCTJBWYEV     <- output with inner and middle rotor advancing appropriately

6. (10 points) Add the code that allows selecting the rotor starting position, if different than the default of lining up the three spaces.
   
   
7. (10 points) Now follow a similar sequence to the above for the decoding process, taking it one step at a time.
   
   
8. (30 points) Lastly write the code that generates all possible rotor combinations. For each combination decode the string and do a dictionary lookup, keeping track of the number of words found, and storing the best case found so far. Use this to automatically decrypt some text.
   
   
9. Turnin your program electronically using the "turnin" command from your CS account on ernie.cs.uic.edu as follows:

turnin -c cs107 -p program5 Enigma.java

where the single file containing the solution for this project is called Enigma.java. Do not turn in the entire directory, and do not turn in the dictionary file.