CMSC 201 Programming Project Four Data Security Out: Monday 11/10/08 Due Date: Sunday 11/23/08, before midnight The design document for this project, design4.txt, is due: Before Midnight, Sunday 11/16/08

The Objective

What is a Hailstone Sequence?

IN FACT...

• Does this procedure eventually reach 1 and stop for every choice of starting number? So far, this is an unsolved problem -- no one has yet proved that the process always results in 1, and no one has yet found a counterexample. This problem was first posed by L. Collatz in 1937 and goes under several names: the Collatz conjecture, the '3n+1 conjecture', the Ulam conjecture, and the Syracuse problem. The sequence is also commonly called the hailstone sequence.

• John Conway proved that the original Collatz problem has no nontrivial cycles of length less than 400. Lagarias (1985) showed that there are no nontrivial cycles with length less than 275,000. Conway (1972) also proved that Collatz-type problems can be formally undecidable. The conjecture has been check by computer for all start values up to 1.2 × 10^**12, but a proof of the conjecture has not been found. Paul Erdös said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 for its solution. There are some heuristic, statistical arguments supporting the conjecture: if one considers only the odd numbers in the sequence generated by the Collatz process, then one can argue that on average the next odd number should be about 3/4 of the previous one, which suggests that they eventually hit the bottom.

Background

We at CMSC 201 Inc. are worried about the integrity of the files stored on our servers. This concern is a result from watching a number of students attempting to copy files from non-public directories. We look to you as programmers to solve this issue making it impossible for someone to understand our files without our decryption method.

Data security is the protection of data against the deliberate or accidental access of unauthorized persons, also known as file security. The methods most commonly used are encryption and decryption. This is a very old concept and has been done to secure more than just files. In World War II, native americans used their native language to hide the meaning of battle orders from the Japanese.

The computer science department at UMBC has a few professors and classes that look into advanced methods to provide this kind of security. And, we have a number of research opportunities if you are interested.

The Task

• You are to write a program that will allow the user to encrypt or decrypt messages from a file or those entered by the user. S/he may enter any sequence of characters which can include whitespaces, newlines, punctuation and will not exceed a line length of 80 characters. This 80 character length guarantee is also valid for files.

• You will be using a menu system in your program to allow the user to choose whether to:
  • P - allow the user to print the encryption key table
  • F - prompt the user to enter the input and output files to be encrypted or decrypted
  • S - will allow the user to enter a message as a string to encrypt or decrypt
  • Q - Quit the program.
  • Further Menu Specifications:
    • The menu must use the letters P, F, S, and Q for its choices. The user should be allowed to enter either the upper-case or lower-case versions of these letters. Other letters should be rejected and the user prompted for a new choice.
    • Menu Choices F and S should then prompt the user to choose to either encrypt (E) or decrypt (D) the message that is about to be entered or read in from a file. The user must enter an E or a D at this point, which can be either upper or lower case.
    • HINT:Since you are using a menu that must accept character input, you must make sure that you have read all of the characters from stdin before trying to read the character the user has just entered. (this means the newline character entered after each character choice)

  ASCII Codes

  • ASCII stands for "American Standard Code for Information Interchange". The ASCII character set was designed for English and other languages which use a Roman alphabet.
  • ASCII characters have a decimal value which associates every character to a unique decimal number.
  • The characters with decimal numbers 0 through 31 represent control characters (e.g., line feed, back space), 32-126 are printable characters, and 127 is delete.
  • This means you can assign a character to an integer variable and pass a character to a function as an integer. You can also think of an integer as a character. You will need to fully grasp these ideas about characters for the encryption/decryption method.

  Creating the Encryption Table

  You will populate a table which will map each upper case character to a unique lower case character using the third term of its Hailstone sequence.
  • To generate the Hailstone sequence:
    
    Given an integer X:
    • If X is equal to 1 stop
    • If X is even divide it by two, start again with this new value of X
    • If X is odd multiply X by three and add one, start again with this new value of X
    HINT: This method stops when X has a value of 1. We want the third term in the sequence, so you will need to edit the stop condition.

  • Populating the table will require you to do the following:
    1. Start with capitol A
    2. Convert to an integer X, its ASCII value
    3. Find the third term of the Hailstone sequence of X.
       However, the following exceptions need to be made:
       • INPUT -> OUTPUT
       • D -> 111
       • H -> 114
       • L -> 115
       • P -> 117
       • R -> 120
       • T -> 121
       • V -> 97
       • X -> 103
       • Z -> 109
       any other character which produces a term greater than 122, neeeds to be modified by subtracting 26 from that term, (i.e. 123 must be modified to 97). The first key in the array of KEYS (index 0) is A, then B, and so on. This table is going to be a means for you to encrypt and decrypt.

  Encrypting and Decrypting Messages

  • Encrypting or decrypting a message will take the following steps:
    1. Start with the first character C.
    2. If C is an alphabetic character, change it to upper case C and go to step 3. If not write it to the output location.
    3. Check the key table for the encrypted or decrypted value. Print the converted character to the output location.
    4. Move to the next character in the message.

Specifications

• You must use the following structure definition and typedef:
  typedef struct key { char input; char output; }KEYS; where input is a character before encryption and output is the character's encrypted value.
• You must dynamically allocate every array and/or string in this program. This entails using malloc() or calloc() any time an array or string is created. And you need to prevent memory leaks by using free() any time an array is not needed.
• You may not use printf() or scanf() for this project. You may however use any method such as fscanf(), fprintf(), fgets(), which takes a FILE * as its write or read location. You will need to use stdin, stdout, or a FILE* whenever you need to scan of print.
• YOU MUST have a function to solve the Hailstone problem with the following prototype: int Hailstones(int num, int times); this function takes in the start number num, and times is the number of stone values to be calculated. The value returned from this function is the encrypted value of the character that started the hailstone sequence. This function must be a RECURSIVE function.

• The message itself can be as long as 80 characters. A file may be composed of multiple lines (messages), each of which will not exceed 80 characters. Don't forget you'll also need space for the null terminator.

• Any non-alphabetic characters in the input message are to be placed unchanged into the output message at that position, whether encryption or decryption is taking place.

Guarantees

• The users will only enter characters when interacting with the menu system.

Sample Output

Submitting the Program

To submit your program, type the following command at the Unix prompt

submit cs201 Proj4 followed by the .c and .h files necessary for compilation

To verify that your project was submitted, you can execute the following command at the Unix prompt. It will show all files that you submitted in a format similar to the Unix 'ls' command.

submitls cs201 Proj4