2/21 Added the following:and you may not use C++vector
2/22 Changed:
You can ignore punctuation characters and consider them a space when it comes to trying to identify what is a word.
to instead be:
You can ignore punctuation characters and consider thema space when it comes to trying to identify what isto be part of a word.
Decrypt the following secret message, following any instructions given after you've done the decoding:
nol ycwh io ffpllhg uenmvi ihv qmdprlieg: zcfnd lfkt pqwayhz ib ofl.db/dgiaoy13
To do this we will use aVigenere cipher.
In addition to knowing how to decipher the text, you also need to know what keyword was used. You don't know what the keyword is, but you know it is one of the 93,297 words found in Joseph Conrad's book
The Secret Agent
. Since this will otherwise take too long, you need to write the program to do this for you, trying every word in that book as a possible decryption key, having your program keep track of which word gives the result with the greatest number of validdictionarywords in it.
The starter code for this is found inZybooks section 7.7.
How Vigenere Works
In order to try and decode the message, it is helpful to fully understand how some original plain text can be encrypted usinga 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 we need to know the keyword. For this example let's 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
HARD WORK
Now use the vertical pairs of letters to encode the plaintext message, which is the text: HARD WORK. For instance the first vertical pair of letters are 'H' on the top row and 'H' on the second row. Use the top 'H' as the row in the Vigenere table, and the 'H' in the second row as the column, giving you the letter 'O', as highlighted inredin the table above. The next (the second) vertical pair of letters are 'I' on the top and 'A' on the second row. 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
HARD WORK
OIUG JVZN
Note that non alphabetic characters (spaces, punctuation) are not looked up in the table, but are simply copied to the ciphertext.
Decoding:
To decipher a message take the top letter (from the keyword row, e.g. 'D' in the third column below)and find the row corresponding to that letter.Follow across that row until you find the correspondingciphertext character (e.g. 'U' in the third column below). At that spot in the table then go straightup to find the letter that is the label at the top of that column. That character (e.g. 'R' in this case)is the original plaintext character. This is highlighted inbluein the table above.
HIDDENHID
???? ????
OIUG JVZN
In one of the options for our program you don't know what the keyword is, but you do know it is one of the words in a file. You will need to try each word in the file 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. Your program should report the successive best results that are found.
You need to know the following:
- Everything from the previous programs
- How to work with C-style strings, which are arrays of char. How to use C-string functions, such as strlen()
- Reading text from a file. Here is some sample code:
// Open a file for reading
ifstream inStream; // declare an input stream
numberOfWords = 0; // Row for the current word
inStream.open( "dictionary.txt");
if( !inStream.is_open()) {
cout
exit( -1);
}
char theWord[ 81]; // declare input space to be clearly larger than largest word
while( inStream >> theWord) {
// Do something with the word that was read, such as store it, print it, etc.
cout
}
// close the file
inStream.close();
- Reading an entire line of input at a time, including spaces, storing this into an array of char that is NULL terminated. Here is some sample code:
charArray[ 81];
fgets( charArray, 81, stdin); // Read from standard input, which by default is the keyboard
// The last character will be '\n'. You need to overwrite this last character with NULL,
//otherwise it will cause problems in your program. Perhaps also then convert to lower case.
After you handle reading in the menu option, you should also read in the carriage-return that you press after you select the menu option. If you don't then your following attempt to read in an entire line will only read this carriage return! To do this you should have something like the following:
char menuOption;
char carriageReturn;
// Display the menu ...
// Read in menu choice
cin >> menuOption;
// Read in and discard the carriage return
carriageReturn = cin.get(); // Read in a single character, whatever is next on the input buffer.
- How to pull out one word at a time from a string of characters, where words are separated by spaces. To do this follow the approach that we cover in class when we discuss string functions.
- Binary search of words in a dictionary. We covered binary search in class, and you can see some sample codehere. Adapt that program to compare the current dictionary word to the keyword being searched for using:searchResult = strcmp( theWord, dictionary[ mid]);
IfsearchResultis 0, thenreturn true. If the result is negative, thenhigh = mid - 1;If the result is positive, thenlow = mid + 1;
Notes:
- You must use C strings and may not use any variables of type C++stringand you may not use C++vector
.Failure to follow this instruction will result in a 10 point deduction.
- You may not use globalvariables, but youmayuse global constants. Using global variables will result in a 10 point deduction.
- You should convert all inputs to lower-case. Do this for dictionary words, words in the Joseph Conrad file, as well as for user input. An easy way to do this is to have a loop go through the C-string and callc = tolower( c);for each character in the string. Remember that to use tolower() you will need#include at the top of your program.
- I suggest you write the program in stages, as indicated below, with the number of points given for each stage.
- (10 points) Read in thedictionary wordsinto an array, and allow looking up a dictionary word. The filename in your program must be called"dictionary.txt"and it contains 21735 words of length >= 3. Running this part of your program should look like what is shown below. The number of words of size >= 3 can be hard-coded into your program. Having this number right will help ensure you've read in the dictionary correctly.
21735 words of size >= 3 were read in from dictionary.
Choose from the following options:
1. Lookup dictionary word
2. Encode some text
3. Decode some text
4. Auto-decode the ciphertext given with the assignment
5. Exit program
Your choice:
1
Enter a word to be looked up in dictionary:
ostentatious
ostentatious IS in the dictionary.
Running it again could look like:
21735 words of size >= 3 were read in from dictionary. Choose from the following options: 1. Lookup dictionary word 2. Encode some text 3. Decode some text 4. Auto-decode the ciphertext given with the assignment 5. Exit program Your choice:
1
Enter a word to be looked up in dictionary:
cats
cats is NOT in the dictionary.
- (15 points) Running the program toencodeplain text into cipher text. This should look like:
21735 words of size >= 3 were read in from dictionary. Choose from the following options: 1. Lookup dictionary word 2. Encode some text 3. Decode some text 4. Auto-decode the ciphertext given with the assignment 5. Exit program Your choice:
2
Enter the text to be encoded:
all generalizations are false
Enter a keyword for Vigenere encryption:
secret
Keyword, plainText and ciphertext are: secretsecretsecretsecretsecre all generalizations are false spn kxfitrpbrevzsgk cii xenji
Doing the Vigenere encoding could be done mathematically, or you could create a 2d array with all the shifted rows in it.
- (10 points) Add the ability todecodeciphertext into plain text. This should look like what is shown below. Note that there are three extra spaces displayed at the beginning of the line of decoded plain text on the bottom line below:
21735 words of size >= 3 were read in from dictionary. Choose from the following options: 1. Lookup dictionary word 2. Encode some text 3. Decode some text 4. Auto-decode the ciphertext given with the assignment 5. Exit program Your choice:
3
Enter the cipherText to be decoded:
spn kxfitrpbrevzsgk cii xenji
Enter a Vigenere keyword to be tried:
secret
3 words found using keyword: secret giving: all generalizations are false
- ( 20 points) Add the option to automatically decode the ciphertext given with the assignment. The encryption keyword is one of the words in Joseph Conrad's book
The Secret Agent
.The name of this file in your program must be"TheSecretAgentByJosephConrad.txt"and should it make a difference, it contains93,297 words.You can ignore punctuation characters and consider thema space when it comes to trying to identify what isto be part of a word.
21735 words of size >= 3 were read in from dictionary. Choose from the following options: 1. Lookup dictionary word 2. Encode some text 3. Decode some text 4. Auto-decode the ciphertext given with the assignment 5. Exit program Your choice:
4
Enter the cipherText to be decoded:
uev os hnocax xia lxn
1 words found using keyword: secret giving: cat kz dlxyhf vrw ttl 2 words found using keyword: distance giving: rwd of dkgkhx vex ten 3 words found using keyword: unresonant giving: are we having fun yet
Once this is working, you should be able to decode the secret message shown at the top of this assignment description page!
Once you are done submit only your main.cpp file into both Zybooks and Gradescope. Do not turn in the filedictionary.txtnor the fileTheSecretAgentByJosephConrad.txt.Only turn in your program which must be calledmain.cpp
|