Prog 3: Vigenere

2/21 Added the following: and you may not use C++ vector

2/22 The data file TheSecretAgentByJosephConrad.txt was changed, with the new version having some non-printable characters stripped out. Also we changed the text:

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 them a space when it comes to trying to identify what is to be part of a word.

3/6 Added a corrected dictionary called fixedDictionary.txt where the words containing punctuation are in the correct order, unlike the original dictionary. For instance, in the original dictionary a search on "cob" failed, because along the way of the binary search it landed on c.o.d. which was in the wrong order and sent binary search off in the wrong direction.

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 a Vigenere 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 valid dictionary words in it.

The starter code for this is found in Zybooks 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 using a 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 <-repeated keyword

HARD WORK <-original plaintext message

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 in red in 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 <-repeated keyword

HARD WORK <-original plaintext message

OIUG JVZN <-ciphertext (the encoded message)

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 corresponding ciphertext character (e.g. 'U' in the third column below). At that spot in the table then go straight up 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 in blue in the table above.

HIDDENHID <-repeated keyword

???? ???? <-original plaintext message

OIUG JVZN <-ciphertext (the encoded message)

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:

1. Everything from the previous programs

2. How to work with C-style strings, which are arrays of char. How to use C-string functions, such as strlen()

3. Reading text from a file. Here is some sample code:

   1. 1. // Open a file for reading

      2. ifstream inStream; // declare an input stream

      3. numberOfWords = 0; // Row for the current word

      4. inStream.open( "dictionary.txt");

      5. if( !inStream.is_open()) {

      6. cout << "Could not find dictionary.txt. Exiting..." << endl;

      7. exit( -1);

      8. }

      9. char theWord[ 81]; // declare input space to be clearly larger than largest word

      10. while( inStream >> theWord) {

      11. // Do something with the word that was read, such as store it, print it, etc.

      12. cout << theWord;

      13. }

      14. // close the file

      15. inStream.close();

4. 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:

5. charArray[ 81];

6. fgets( charArray, 81, stdin); // Read from standard input, which by default is the keyboard

7. // The last character will be '\n'. You need to overwrite this last character with NULL,

8. // otherwise it will cause problems in your program. Perhaps also then convert to lower case.

• 1. 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:

  2. char menuOption;

  3. char carriageReturn;

  4. // Display the menu ...

  5. // Read in menu choice

  6. cin >> menuOption;

  7. // Read in and discard the carriage return

  8. carriageReturn = cin.get(); // Read in a single character, whatever is next on the input buffer.

9. 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.

10. Binary search of words in a dictionary. We covered binary search in class, and you can see some sample code here. Adapt that program to compare the current dictionary word to the keyword being searched for using: searchResult = strcmp( theWord, dictionary[ mid]);

11. If searchResult is 0, then return true. If the result is negative, then high = mid - 1; If the result is positive, then low = mid + 1;

Notes:

1. You must use C strings and may not use any variables of type C++ string and you may not use C++ vector. Failure to follow this instruction will result in a 10 point deduction.

2. You may not use global variables, but you may use global constants. Using global variables will result in a 10 point deduction.

3. 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 call c = tolower( c); for each character in the string. Remember that to use tolower() you will need #include <cctype> at the top of your program.

4. I suggest you write the program in stages, as indicated below, with the number of points given for each stage.

   1. (10 points) Read in the dictionary words into 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.

      1. • 1. 21735 words of size >= 3 were read in from dictionary.

           2. Choose from the following options:

           3. 1. Lookup dictionary word

           4. 2. Encode some text

           5. 3. Decode some text

           6. 4. Auto-decode the ciphertext given with the assignment

           7. 5. Exit program

           8. Your choice: 1

           9. Enter a word to be looked up in dictionary: ostentatious

           10. ostentatious IS in the dictionary.

• • 1. Running it again could look like:

       1. 1. 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.

    2. (15 points) Running the program to encode plain text into cipher text. This should look like:

• • • • 1. 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

• • 3. Doing the Vigenere encoding could be done mathematically, or you could create a 2d array with all the shifted rows in it.

    4. (10 points) Add the ability to decode ciphertext 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:

• • • • 1. 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

4. 2. ( 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 contains 93,297 words. You can ignore punctuation characters and consider them a space when it comes to trying to identify what is to be part of a word.

• • • 1. 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

• • 1. 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 file dictionary.txt nor the file TheSecretAgentByJosephConrad.txt. Only turn in your program which must be called main.cpp