CSE 221 Lab 5

Table of Contents

Objectives

The Problem

From antiquity, people have worried about how to communicate private information to others without revealing, to adversaries, the content of their communications. The Allied forces in World War II, for example, used Navajo Indians for field communications because the enemy did not speak or understand the language of the Navajo. Also, when the Allied forces were able to steal Germany's Enigma machine, used for encrypting messages, the secret was so valued that English citizens were not notified of imminent bombing raids, lest Germany infer that its code had been broken. And today, internet commerce has brought the issue of secure transmission of private data to all our lives.

For this assignment, you will write a program that encrypts and decrypts text files by simulating a two-rotor Enigma machine, as used by German forces in WWII.

How Enigma Machines Work

The figure to the right shows a two-rotor Enigma machine with a reduced alphabet. Rotors 1 (the inner wheel) and 2 (the middle wheel) can rotate clockwise, while the backplate (the outer wheel) is stationary. The numbers around the backplate indicate positions.

To encrypt a character, call it the input character, using this machine, locate the input character on rotor 1. Next, identify the character on the backplate at the same position. Let's call this the backplate character. Now locate the backplate character on rotor 2. The encryption of the input character is the character on the backplate at the same position as the backplate character's position on rotor 2. For example, if the input character is 'A' and since the position of 'A' on rotor 1 is 10, the backplate character will be 'C'. Since 'C' is located at position 12 on rotor 2, 'A' is encrypted by character 'B', the character on the backplate at position 12. After the encryption character has been determined, rotor 1 is advanced one position in the clockwise direction. When rotor 1 completes a full revolution by returning to its original positioning, rotor 2 advances one position in the clockwise direction. This is similar to how the minutes and hours advance on a clock.

The decryption process starts with an encrypted character and determines the corresponding input character. This is done by simply reversing the steps followed to determine the encryption character during the encryption process. As long as the decryption process starts out with the two rotors and the backplate positioned exactly as they were when the encryption process started out, decrypting an encrypted version of a file should result in exactly the original file.

Simulating an Enigma Machine

To simulate an Enigma machine, you will use three id-name tables, one table for each of the two rotors and one for the backplate. The alphabet used will be the entire ASCII character set, including non-printing control characters. As there are 128 different ASCII characters, rotors and backplates will have 128 positions each, and the id's in the corresponding id-name tables will be 0 through 127, inclusive. Each name in the tables will be a Text string of length 1, containg exactly one ASCII character. Since all names in an id-name table must be unique, it follows that names in each table contain exactly the ASCII character set.

The process for encrypting a file will be given an input stream open to a text file. As each character is read from the input stream, an encryption character is determined, as described above, and output to an output stream. The process for decrypting a file will be given an input stream open to an encrypted text file. As each character is read from the input stream, a decryption character is determined, as described above, and output to an output stream.

Set Up

  1. In a terminal window, create a new directory (folder) for this lab by typing the "make directory" command: 
         mkdir lab05
  2. Change or move to the new directory (folder) for this lab by typing the "change directory" command: 
         cd lab05
  3. Copy the catalog for this lab by typing the "copy" command: 
        cp -R /class/sce/now/221/labs/catalogs/lab05/* .
    NOTE: The period . is part of the command. It denotes the current directory (folder).

    This "copy command" will copy recursively (because of the "-R") all the files and directories from the shared class directory into your directory, effectively duplicating the entire substructure from the class directory into your directory.



  4. To see what was copied, type the "list" command: 
         ls
    You should see the following files:

    Enigma_Demo is an executable version of the solution for this assignment. Users of Enigma_Demo have the option of encrytping a file, decrypting a file, or quitting. You can run Enigma_Demo by typing the command Enigma_Demo in an xterm window. The section below, titled Using Enigma_Demo, shows an example of how to use Enigma_Demo.

    sandburg.txt, shakespeare.txt, homer.txt, and homer_bk_1.txt are text files that you can use for test cases. (WARNING: homer_bk_1.txt takes a long time to encrypt/decrypt. You might not want to use it for testing until the last step of this assignment where you will improve the efficiency of the encryption/decryption processes.) sandburg.enc, shakespeare.enc, homer.enc, and homer_bk_1.enc are encrypted versions of sandburg.txt, shakespeare.txt, homer.txt, and homer_bk_1.txt, respectively. These encrypted files are provided to help you with testing, as described below.

    Enigma.cpp is a skeleton for the solution to this assignment. You need to provide operation bodies for the following operations:

    1. Advance_Rotor
    2. Display_Rotor
    3. Encrypt_File
    4. Decrypt_File

    How to Proceed

    1. Begin by implementing and testing the two operations Advance_Rotor and Display_Rotor. Make sure they are working okay before moving to the next step.
    2. Implement and test the Encrypt_File operation. Once you begin testing your program, use SMALL test files. For example, you might proceed as follows:

      1. Use emacs to create a file called small.txt, where the content of small.txt is the text string "this is a small file".
      2. Use Enigma_Demo to get a correct encryption of small.txt. Suppose the encrypted file is called correct_small.enc.
      3. Use your implementation of Enigma.cpp to get another encryption of small.txt. Suppose this encrypted file is called my_small.enc. (Enigma_Demo is likely to run quite a bit faster than your implementation of Enigma.cpp. That's okay. Later in this assignment you'll do some things to improve efficiency.)
      4. At this point, the two files correct_small.enc and my_small.enc can be compared, character-for-character, to see if they are identical. If they are not identical, there is a bug in your implementation of Enigma.cpp. Linux provides a convenient command to test whether two files are identical, character-for-character. In an xterm window, use the "difference" command: 
        diff correct_small.enc my_small.enc
        IF the the two files are identical, character-for-character, the "difference" command will produce NO output. IF the the two files are not identical, character-for-character, the "difference" command will produce output that, for now, is unintelligable. This unintelligable output indicates that there is a bug in your implementation of Enigma.cpp.

        Also, do not forget that it is easy to look at the contents of a file using the Linux less command: 

        less my_small.enc
    3. In procedure_body Get_Command, add an option for decrypting a file. Use Enigma_Demo as a model for how the option should prompt a user. Then, modify program_body main so that it processes a decrypt request just as does Enigma_Demo. Use the response of program_body main to an encrypt request as a guide. Do another Build Project to make sure Enigma.cpp still compiles okay and run it on a test case asking the program to decrypt a file. Because the body of Decrypt_File is still empty, the encryption will not do anything, but at least you can verify that program_body main communicates properly with Decrypt_File.

    4. Fill in the body of Decrypt_File, test, and debug.


    5. The slow running time of Enigma.cpp is due primarily to the Advance_Rotor operation. First we will eliminate all calls to Advance_Rotor in Encrypt_File. Once this is accomplished, then we will remove all calls to Advance_Rotor in Decrypt_File.

      To remove calls to Advance_Rotor in Encrypt_File, use two local Integer objects in the body of Encrypt_File, let's call them adv_cnt_1 and adv_cnt_2, that keep track of the number of times that Advance_Rotor would have been called for rotors 1 and 2, respectively. Further, suppose that the value of adv_cnt_1 is 3, for example, and suppose that a "look-up" operation for rotor 1 locates "A" at position 21 on rotor 1. Then, we should think of "A" as being located at position 24 on rotor 1, instead of at position 21, since rotor 1 should have been advanced 3 times by calls to Advance_Rotor. Compile and test your new implementation of Encrypt_File.

    6. After you have established through testing that the new implementation of Encrypt_File is working correctly, then provide a new implementation for Decrypt_File that also avoids calls to Advance_Rotor.




    Important Suggestions

    1. program_body main of Enigma.cpp uses a case_select statement. It is an easy statement to understand and use. Even so, please be sure to ask about it in class if you have any questions. Also see pages Syntax - 5 and Syntax - 6 in the Foundation types and syntax section of the CSE 221 Handouts.


    2. Some parts of the requires and ensures clauses of the global operations are expressed in terms of the mathematical model of Character_IStream and Character_OStream objects. There is a short explanation of this model in the handout Character Streams - A Brief Summary. This is part of the Foundation types and syntax section of the CSE 221 Handouts.


    3. In the global operations Encrypt_File and Decrypt_File, characters must be read from the input stream one character at a time. Suppose that we have 
      object Character_IStream input_file;
object Character ch
      To read a single character from input_file, use the operation 
      input_file.Read (ch);
      To test whether there are any more characters in input_file, use the Boolean-valued expression input_file.At_EOS () in a statement like 
      while (not input_file.At_EOS ())

    4. After reading an input character from the input stream, Encrypt_File and Decrypt_File will need to "put" the character into a Text object before using it in a "Look_Up" operation. This is because names in an id-name table must be of type Text. Suppose that input_ch is a Character object and that input_ch_as_text is a Text object WHOSE VALUE IS THE EMPTY STRING. For this lab, the safest way to "put" input_ch into input_ch_as_text is: 
          input_ch_as_text.Add (0, input_ch).

    5. The global operation Display_Rotor is included in Enigma.cpp strictly for testing/debugging purposes. For example, you might use Display_Rotor to take a look at the value of a rotor after the rotor has been "advanced" by calling Advance_Rotor. Also, you might want to use Display_Rotor to take a look at the values of rotor1, rotor2, and backplate just after they are initialized in Encrypt_File or in Decrypt_File. (Display_Rotor is identical to the operation Display_Id_Name_Table from Closed Lab 4. You can "copy and paste" an implementation of Display_Rotor from your solution to Closed Lab 4.)


    Using Enigma_Demo

    Here is an example of how to use Enigma_Demo, and of how your solution for this assignment should function. User responses appear in bold face. The "progress" messages, such as 

    Enigma.cpp (190): Encrypt_File
    100 characters have been encrypted
    that you see below were generated by using a debug statement in the body of the global operation Encrypt_File. You may want to do something similar during testing/debugging to see if Encrypt_File is making progress. 
    -------------------------------------------------
Command: e [Encrypt a file]
         d [Decrypt a file]
         q [Quit]: e

Enter the name of a file to be encrypted:   homer.txt
Enter a name for the encrypted file:  homer.enc

Encrypting file ... 


Enigma.cpp (190): Encrypt_File
    50 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    100 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    150 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    200 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    250 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    300 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    350 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    400 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    450 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    500 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    550 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    600 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    650 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    700 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    750 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    800 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    850 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    900 characters have been encrypted


Enigma.cpp (190): Encrypt_File
    950 characters have been encrypted


... encryption completed.



-------------------------------------------------
Command: e [Encrypt a file]
         d [Decrypt a file]
         q [Quit]: d

Enter the name of a file to be decrypted:  homer.enc
Enter a name for the decrypted file: homer.dec

Decrypting file ... 


Enigma.cpp (257): Decrypt_File
    50 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    100 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    150 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    200 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    250 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    300 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    350 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    400 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    450 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    500 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    550 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    600 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    650 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    700 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    750 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    800 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    850 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    900 characters have been decrypted


Enigma.cpp (257): Decrypt_File
    950 characters have been decrypted


... decryption completed.



-------------------------------------------------
Command: e [Encrypt a file]
         d [Decrypt a file]
         q [Quit]: q

*** Quitting the Enigma program

    What To Turn In

    The rcpp-submit command for this lab assignment is:

    where "xx" is to be replaced by lower case letters designating your section (see the course home page for a list).