Preliminary Material
Project 2 is worth 9% of your grade.
This project deals with a circular doubly linked list containing a single alphabet that holds both plaintext and cipher character. It implements an Enigma machine.
Enigma Machine a German cipher machine consisting of 2 cipher
wheels that rotate each time a character is enciphered or deciphered. It
was used during WWII by the Germans for military and naval
communications.
Enigma
Machine
See the Enigma
Machine Work
Download an Enigma
Simulator
- only works for DOS or Windows 95 and earlier
Purpose
- To use the basic features of a circular doubly linked list such as insert, erase, copy, etc.
- To understand and implement a thread in a circular doubly linked list.
- To explore another alternative to creating a cipher wheel.
- To understand wheel movement of a hardcoded wheel.
- To create an Enigma machine that can encipher and decipher messages.
- To have some fun.
Academic Integrity Statement
Please note that *all* programming projects in this course (including this one) are to be done independently or with the assistance of the instructional staff of this course only.
Please review the policies outlined on the class syllabus concerning the use of class computer accounts and concerning the University's Code of Academic Integrity. The instructors of this course will review the programs submitted by students for potential violations of the Code of Academic Integrity and if it is believed that a violation has occurred it will be referred to the Office of Judicial Programs and the Student Honor Council.
Hardcoding is considered a violation of academic integrity
Background
You have implemented a Coder class that represents a wheel of letters for enciphering and deciphering in project 1. (If you haven't gotten this working yet, go back NOW and fix it!) Now you are ready to build a class called Enigma. When the Germans made their version of the Enigma, they had to keep a few things in mind; the machine had to be versatile and uncrackable.
VERSATILITY: Enigma machines were issued in mass to thousands of German vessels. Since the Germans could not allow the Allies (British and American forces) to read the encoded messages, it was necessary to make the Enigma machine versatile enough so that even if the Allies captured a vessel and acquired an Enigma machine, they still could not use it to decipher "coded" (enciphered) messages. To aid in versatility, we will implement the following characteristics in our Enigma class -- similar to what the Germans did:
- The user defines five wheels by giving five keywords and five positions. Each
wheel will be defined the same way as in Project #1 with the following
changes:
- Each wheel consists of only one alphabet, a circular doubly linked list.
- Each plaintext letter is connected to its corresponding cipher letter with a link.
- The cipher letters are linked into a circular singly linked list.
- The input file designates which three of the five wheels are to be used for a particular message.
With these allowances, it would be near impossible for an Ally to decipher a code even if she had an Enigma machine because she would not know if she had the right wheels, or which wheels to use.
I used the word "she" in the above paragraph because during World War II, women were heavily recruited into the Army (WAAC) and Navy (WAVES) to relieve men working in noncombat positions - many of which were in cryptography.
UNCRACKABILITY: Enciphered messages were sent using radio waves in Morse code, and unfortunately, anyone with a radio could intercept these messages. With the Allies on the alert, coded messages needed to be uncrackable. If you have ever worked on a cryptogram, you would know that there are two dead-giveaways in a code where each letter transcribes to one other letter.
- First, ideosyncrasies in the language can provide clues for cryptographers.
For example, 'Q' is always followed by a 'U', and it would be very easy to figure
out which letters represented 'Q' and 'U' in the code. To avoid
this, we would like the ability to erase letters such as 'Q' from the wheel, so
that any 'Q's in the code will be transcribed as blanks (more on this later).
- Our Enigma machine, unlike the German's, will allow the deletion of 0 or 1 letter from each wheel
- Each removed letter will be replaced with a single blank
- To illustrate the second problem, let's pretend the Germans wanted to send the message "ATTACK
MISSISSIPPI". If the enciphered message looked something like: "BYYBFG
PLKKLKKLSSL"
it wouldn't take much to crack this cipher because of the repeated letters.
To
avoid this problem, the Germans made the wheels rotate once with each letter
typed, so
that each letter would transcribe to a different letter every time; thus
doubles were no longer a problem.
- Our machine's wheels will have the ability to all rotate with each letter typed.
- A wheel will be able to rotate clockwise as well as counterclockwise.
Now that you understand what makes a good Enigma machine, you are ready to start the tasks. Read the entire section before starting because you might save yourself a lot of work and frustration if you understand the whole assignment first.
Files Provided
- Node.h Stores a plaintext character and pointers.
- Coder.h The header file for Coder.cpp.
- Enigma.h The header file for Enigma.cpp.
Files Submitted
- Node.h and Node.cpp
- Coder.h and Coder.cpp
- Enigma.h and Enigma.cpp
- main.cpp
- should produce our primary.output when tested with our primary.input
- myExcept.cpp
- You will add at least 2 more exceptions to this class. They will be thrown from methods in Enigma.cpp
- testCoder.cpp
- testNode.cpp
- testEnigma.cpp
- Makefile Your makefile, spelled exactly this way (not "makefile" or anything else).
Tasks
Task 1: Update Coder.cpp given the new Coder.h
-
int cog;
Since we are adding the functionality of spinning wheels, each wheel will be given a number that represents how many letters the wheel rotates for every enciphered character. This number will be called a cog.
- int offset;
When the wheel spins, the plaintext letters will be "off" from their original cipher letters by a certain amount. Rather than redirecting every pointer in the wheel, we can just keep track of how far "off" the letters are, and traverse down that extra amount. This number will be called offset. For example:
An example wheel (with offset = 3) before any rotations
plaintext: 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
cipher: c o w a b u n g d e f h i j k l m p q r s t v x y z
The same wheel after enciphering one letter with a step of positive 1 (cog = 1)
plaintext: 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
cipher: c o w a b u n g d e f h i j k l m p q r s t v x y z
Notice that the second wheel can be accomplished simply by using the first wheel, except once you find the plaintext letter, traverse one more letter in the DLL before grabbing the cipher letter. The case can be generalized for multiple turns of the wheel if 'offset' is augmented each time the wheel turns, and you traverse down your DLL 'offset' times. At this point, it should be evident why we needed to implement this as a doubly linked list -- since the wheels can turn in either direction, we may need to move left (counterclockwise) or right (clockwise) to grab the cipher letter. There is a complete example below.
- void reader();
Since we will be creating five wheels in our Enigma class, we can't have each wheel reading to the EOF, so this function will have to change. The reader method should read only the keyword and the position. Remember that the keyword can be any sequence of spaces and uppercase/lowercase alphabet characters. It is also possible that the keyword is the empty string. Each keyword is guaranteed to be followed by an integer between 0 and 25 inclusive, which is its offset. Refer to the BNF below.
- void erase(char x);
Because of the way we have implemented our doubly linked list, we only have one copy of the alphabet. This makes deleting a letter such as 'Q' from a wheel rather complicated. Take a look at this example:
plaintext: 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
cipher: c o w a b u n g d e f h i j k l m p q r s t v x y zNow if we delete the letter 'q' from our doubly linked list, 'v' will not have a cipher letter because we only have ONE copy of the alphabet, and 'q' is gone! To solve this problem, we will have the cipher letter of 'v' be 'j' -- that is, we will change the cipher-letter of the plaintext-letter that lost its cipher-letter to the cipher-letter that was pointed to by the deleted-letter.
plaintext: d e f g h i j k l m n o p r s t u v w x y z a b c
cipher: c o w a b u n g d e f h i k l m p j r s t v x y zNotice that now there are no 'q's in either line, and thus it is safe to have deleted 'q' completely.
HINTS:
- You will have to change the doubly linked list pointers to skip over the letter 'q'.
- You will have to change 'v's cipher pointer.
- You will also have to manipulate the pointers in the CipherThread so that 'j's original position is skipped and that the 'q' is replaced with 'j'.
Depending on how you write your code, the following situations may or may not need to be handled separately:
- The plaintext front letter is deleted.
- The cipherFront letter is deleted.
- The deleted-letter's cipher-letter is itself.
- void encipher();
Just make small changes to this method so that the new pointers are hooked up. This is good for testing your wheel prior to adding spin and deleting letters from the wheel.
- void encipherSpin();
Just make the same changes to this method as encipher(). Here is where you will use the variable cog. Also, if the plaintext letter is not found on the wheel (it has been erased), this method should change it into a blankspace character: ' '. Note that a blank transcribes to a blank.
- void decipherSpin();
The same kind of changes are made as in encipher(). Notice that, because the wheels are turning, it is possible that blanks can show up anywhere when deciphering. This is a desired side-effect.
EXPLANATION: Let's say our first wheel has all its letters, but our second wheel is missing the 'x' letter. Every time the first wheel enciphers a letter into an 'x', the second wheel will encipher it into a blank. Since the first wheel is turning, ANY letter could be enciphered into an 'x', and thus we will have what seems to be random blanks. Of course, this problem could be avoided if we deleted 'x' from all the wheels, but that would be too logical.
- void augmentOffset();
The wheel turns cog amount every time a letter is transcribed. This function changes the offset variable by cog amount.
- void traverseOffset( Node*& curr );
Called by encipher, this method aids in transcribing the plaintext letters back into the cipher letters by moving curr left by offset amount of letters -- or right if offset is negative. (See example below.)
- void traverseOffsetBackwards( Node*& curr );
Called by decipher, this method aids in transcribing the cipher letters back into the plaintext letters, which requires traversing 'backwards'. (See example below.)
- int offset;
plaintext: 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
cipher: c o w a b u n g d e f h i j k l m p q r s t v x y z
The same wheel after rotating once with a step of positive 1 (cog == 1)
plaintext: 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
cipher: c o w a b u n g d e f h i j k l m p q r s t v x y z
The same wheel after rotating a second time with a step of positive 1 (cog == 1)
plaintext: 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
cipher: c o w a b u n g d e f h i j k l m p q r s t v x y z
Let's say we wanted to encipher the message "go". First, encipher() would call augmentOffset() so that offset would increase by cog, so offset is now equal to 1. Then, encipher() would find plaintext 'g' on the original wheel and then call traverseOffset(), which would move curr left by offset (offset == 1) and then grab that cipher letter which is 'w'. For the second letter, encipher() would call augmentOffset() again so that offset would increase by cog, so offset is now equal to 2. Then, encipher() would find plaintext 'o' on the original wheel and then call traverseOffset(), which would move curr left by offset (offset == 2) and then grab that cipher letter which is 'e'.
As you can see from the wheel after one rotation, 'g' truly does transcribe to 'w', and looking at the wheel after two rotations, 'o' transcribes to 'e'.
To decipher the message "we", offset gets set to zero. When deciphering 'w', decipher() first calls augmentOffset() so that offset would increase by cog, so offset is now equal to 1. Then, decipher() would find cipherletter 'w' on the original wheel and then call traverseOffsetBackwards(), which would move curr right by offset (offset == 1) and then grab that plaintext letter which is 'g'. When deciphering 'e', decipher() would first call augmentOffset() so that offset would increase by cog, so offset is now equal to 2. Then, decipher() would find cipherletter 'e' on the original wheel and then call traverseOffsetBackwards(), which would move curr right by offset (offset == 2) and then grab that plaintext letter which is 'o'.
Task 2: Write Enigma.cpp given Enigma.h
The explanations in the header file should be enough for you to accomplish this.
BNF
The input file will follow this format:[keyword][number][newline]
[keyword][number][newline]
[keyword][number][newline]
[keyword][number][newline]
[keyword][number][newline]
[newline]
[digit-one-to-five][spaces][digit-one-to-five][spaces][digit-one-to-five][newline]
[newline]
[digit-minus-to-plus][spaces][digit-minus-to-plus][spaces][digit-minus-to-plus][newline]
[alpha-or-space][alpha-or-space][alpha-or-space][newline]
[message]
With the following definitions:
[keyword] := [alpha-or-space][keyword] | ""
[number] := [digit][digit] | [digit]
[newline] := "\n"
[digit-one-to-five] := "1" | "2" | "3" | "4" | "5"
[digit-minus-to-plus] := [number] | -[number]
[spaces] := [space][spaces] | [space]
[alpha-or-space] := "a" through "z" | "A" through "Z" | [space]
[message] := [message-character][message] | ""
[digit] := "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" | "0"
[space] := " "
[message-character] := (any ascii character)
Notes:
[number] will be an integer between 0 and 25 inclusive.
You will strip [message] of anything that is not an alpha-character.
Since integers (like 13) cannot appear in a message, they will be spelled out instead (like thirteen).
| See the class syllabus for policies concerning email
Last Modified: Saturday, February 20, 2003 |
|
|
|
|
|