EE 312 Project 4 - Parameters, Strings, and Ciphers

Programming Assignment 4: You must complete this assignment by yourself. You cannot work with anyone else in the class or with someone outside of the class. You are encouraged to get help from the instructional staff.

Due:

Description: The purposes of this assignment are:

1. Work with strings and arrays
2. Work with user input

In this assignment you will write a program that performs encryption on a message from a user using a columnar transposition cipher. It then will decrypt a message from the user using a columnar transposition cipher. The new features you will use in this program are parameters, strings, and user input. You will continue to use functions to provide structure and remove redundancy. On this assignment you may only use the features of C that we've covered in class. In particular, you may not use any arrays other than one-dimensional arrays.

Background: A cipher is a series of steps (algorithm) for either encrypting or decrypting a message. Encrypting a message is the process of taking the original message and applying the cipher. The result of the encryption process is a message that is (hopefully) difficult to understand if it is intercepted by someone other than the intended receiver. Decrypting a message is the process of taking the encrypted message, applying the correct cipher in order to retrieve the original, unencrypted message.

A transposition cipher is one in which the characters in the original message are retained, but scrambled in some way. The encrypted message contains all the same characters as the original message, but the characters positions are changed (transposed) in some way.

Note that the depiction below is only used to explain the algorithm. You may not use a two dimensional array in your solution.

A simple columnar transposition cipher consists of taking the original message and writing the characters one at a time, down in columns. Each column has a specified number of rows. When the last row is reached for a particular column the process continues at the first row of the next column.

For example assume the original message is "Hook_'em_Horns!!!". In this example I am using underscore characters instead of spaces. To encrypt the message we must choose the number of rows per columns. Assume we choose 5 rows per column. The encryption takes place by writing the characters in columns.

In order to make the decryption algorithm easier, empty rows in the last column are filled with padding characters. In this example and in your program we will use a capital X as the padding character. After adding the padding characters the table looks like this:

To finish the encryption the characters are added row by row. So, in this case the encrypted message becomes:

H'o!oer!omnXk_sX_H!X

Notice how the first four characters of the encrypted message are the characters in the first row (H'o!), the next four characters are the characters in the second row (oer!) and so forth. In your program the encryption algorithm will be implemented somewhat differently, but will result in the exact same encrypted text.

Your program must also encrypt the clear text without padding. The algorithm in each case is the same and can be accomplished with the same method given the right parameters and the correct limits on the for loop.

To decrypt a message we must know the number of rows. The number of columns will be the length of the message divided by the number of rows. To see the decryption process consider the message with indices such as the characters in a string (i.e., a char array).

To decrypt the message we start at position 0, the character H, and concatenate that character to the end of the decrypted message which is initially the empty string.

decrypted message: H

Then we skip over 4 characters, the number of columns in the table. This is the character at index 4, an o. We concatenate this to the decrypted message:

decrypted message: Ho

This continues a number of times equal to the number of columns in the cipher. (The length of the message divided by the number of rows used.)

 decrypted message: Hook_

Next, move back to position 1, the character ', and repeat the process. The number of times to repeat this process is equal to the number of rows in the cipher.

This results in the decrypted message with the padding characters at the end:

Hook_'em_Horns!!!XXX

Note, it is possible to not use the padding characters, but the decryption algorithm becomes more complicated. (With the padding characters it is relatively straight forward.)

The program: Look at sample output from the program below. The user input is indicated with the bold font. Your program must reproduce this output exactly given the same input.

The program performs the following steps:

1. Prints an introduction.
2. Asks the user for a clear text message.
3. Shows the encrypted text based on the clear text message. The program performs the encryption with various numbers of rows starting at 2 and going up to some maximum. The maximum should be a program constant. The program shows the encrypted message both with and without padding.
4. Next the program asks the user for an encrypted message. The message is then decoded with various numbers of rows. The decryption is done assuming the message was encrypted with padding characters if necessary. If the length of the message is not a multiple of the number of rows padding characters (X's) are added to the end. Note, adding padding characters will throw off the decryption in some cases, but you do not have to account for that.

By way of comparison, my solution consists of approximately 100 lines of code not counting comments and 9 functions. Note some functions are used to provide structure to the program even though they do not remove any redundancy. For this program, a good rule of thumb is that no function exceeds 15 lines of code. If a function has more than 15 lines of code it is a good idea to break it up into smaller functions to provide structure to the program.

One Sample Run:

MAX_ROWS set to 6: the underscore character represents a blank space that would appear in your output.  (This is not part of the program output.)

This program demonstrates a transposition cipher.
A cipher is an algorithm to encrypt or decrypt a message.

This program will demonstrate encrypting a message with
a columnar transposition cipher both with and without
padding characters. The program will then decrypt a message
assuming it was encrypted with a columnar transposition cipher
with padding.


A demonstration of encrypting with a columnar transposition cipher:

Enter the message to encrypt: Hook_'em_Horns!!!

Message encrypted with columnar transposition cipher and no padding.
Encrypted with 2 rows: Ho_e_on!!ok'mHrs!
Encrypted with 3 rows: HkeHn!o_mos!o'_r!
Encrypted with 4 rows: H__n!o'Hsoeo!kmr!
Encrypted with 5 rows: H'o!oer!omnk_s_H!
Encrypted with 6 rows: Henomso_!kH!_o!'r

Message encrypted with columnar transposition cipher and padding.

Clear text padded for 2 rows: Hook_'em_Horns!!!X
Encrypted with 2 rows: Ho_e_on!!ok'mHrs!X

Clear text padded for 3 rows: Hook_'em_Horns!!!X
Encrypted with 3 rows: HkeHn!o_mos!o'_r!X

Clear text padded for 4 rows: Hook_'em_Horns!!!XXX
Encrypted with 4 rows: H__n!o'HsXoeo!Xkmr!X

Clear text padded for 5 rows: Hook_'em_Horns!!!XXX
Encrypted with 5 rows: H'o!oer!omnXk_sX_H!X

Clear text padded for 6 rows: Hook_'em_Horns!!!X
Encrypted with 6 rows: Henomso_!kH!_o!'rX


A demonstration of decrypting with a columnar transposition cipher.
If the length of the message is not a multiple of the number of rows
it will be padded which may throw off the decryption.

Enter the message to decrypt: H__n!o'HsXoeo!Xkmr!X

Message decrypted with a columnar transposition cipher:

Encrypted text padded for 2 rows: H__n!o'HsXoeo!Xkmr!X
Decrypted with 2 rows: Ho_e_on!!Xok'mHrs!XX

Encrypted text padded for 3 rows: H__n!o'HsXoeo!Xkmr!XX
Decrypted with 3 rows: HHX_sk_Xmnor!e!ooX'!X

Encrypted text padded for 4 rows: H__n!o'HsXoeo!Xkmr!X
Decrypted with 4 rows: Hook_'em_Horns!!!XXX

Encrypted text padded for 5 rows: H__n!o'HsXoeo!Xkmr!X
Decrypted with 5 rows: H!som_oX!r_'oX!nHekX

Encrypted text padded for 6 rows: H__n!o'HsXoeo!Xkmr!XXXXX
Decrypted with 6 rows: H!somX_oX!rX_'oX!XnHekXX


Look at the tips below for help on how to approach the problem.

• review the general project requirements?
  
• work on the assignment individually?
• fill in the header (provided in your previous project descriptions) in your file cipher.c?
  
• only use concepts and features of C that we've covered?
• create a logical, structured solution that is easy to understand and reduces redundancy?
• use parameters as appropriate?
• ensure your program does not suffer a compile error or runtime error?
• ensure your program has a global constant that when changed alters the maximum number of rows used in demonstrating encryption and decryption?
• put a comment at the start of each function describing in broad terms, what it does?
• make sure that your output exactly matches the sample output above?
  
• turn in your C source code in a file named cipher.c on Canvas?
  

Tips:

1. As usual develop the program in steps. Design one function at a time, implement it, and test it before moving on to the next portion of the program.
2. Use parameters to send information from one function to another as necessary. No global variables other than your one global constant MAX_SIZE (described above.)
   
3. In the case when encrypting the message with padding added you should create a new string padded with the appropriate number of X's for the current number of rows. Padding can be done with a loop.
   
4. When encrypting the message you will not actually create the table shown in the example above. Instead you will use nested loops to generate the necessary indices in the string. I think it is easiest to generate the indices of the first row, then the second row, and so forth. Work this out on paper with various messages and various numbers of rows to find the necessary pattern for the for loops.
5. Remember that scanf() stops reading when it encounters whitespace. Remember that fgets() includes an ending newline character in the string it reads.
   
6. You will likely want to use strlen() from string.h.

7. If you program does not work a good debugging technique is to use gdb to look at the current loop control variables and the current version of the encrypted or decrypted string.