Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003- Introduction to Procedural Programming ENGG1003 - Programming Assignment 1 English Text Ciphers Brenton...

1 answer below »
Have to program everything using C. All lines, need commenting to help understand the code.


Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003- Introduction to Procedural Programming ENGG1003 - Programming Assignment 1 English Text Ciphers Brenton Schulz Due date: 6pm Monday of Week 8 Submission: Upload your final .c file to Blackboard as an assignment submission Marking: During your Week 8 lab Weighting: 20% of your final grade 1 Introduction A cipher is an algorithm which encrypts a message into cipher text so that it can be safely transmitted without an eavesdropper being able to (easily) read it. For the purposes of this assignment the message and ciphertext will be stored as strings of ASCII characters. Cipher algorithms always perform two tasks: encryption and decryption. The encryption process takes a “message” and “key” as inputs and produces cipher text. The decryption process performs the reverse: it turns cipher text and the key back into the original message. The exact details of how the key and message are processed to produce the cipher text vary between algorithms. However, the general principle is that algorithms employ a mathematical function which is “easy” to calculate with the key but “difficult” to invert without it. A rigorous discussion of modern cryptographic techniques can be found in the excellent (but highly mathematical) text, An Introduction to Mathematical Cryptography (available in the Auchmuty library). This assignment will cover three cipher algorithms: 1. The classical “rail-fence” cipher 2. A modified “2-level” rail-fence cipher 3. The substitution cipher Your task is to write a C program which performs the following broad tasks: • Encryption of a message using the classical rail-fence cipher algorithm • Encryption of a message using the 2-level rail-fence cipher • Decryption of a message using the 2-level rail-fence cipher • (HD level) Partial decryption of a block of cipher text encrypted with a substitution cipher without the key Page 1 of 11 Brenton Schulz http://library.newcastle.edu.au/record=b3576154~S16 Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003- Introduction to Procedural Programming 2 Cipher Algorithms 2.1 2-Level Rail-fence Cipher This section describes a transposition cipher algorithm which has been created for this project. To my knowledge code for this cipher does not commonly exist on the Internet. A transposition cipher is one which creates ciphertext by re-ordering the characters in the message. This is similar to an anagram except the output cipher text looks like random characters, not a new word. The algorithm documented here is an extension of the classical rail-fence cipher. You should read about it here and here before continuing. You can view C code for this cipher here. Your implementation should be done from scratch and not simply re-use existing code. The encryption algorithm involves two broad steps: 1. Writing the message on a 2D grid where each row is called a “rail”. The message “zig-zag“s between the top and bottom rails, one message character per column. The height (number of rows) is the “key”. 2. The cipher text is created by reading the characters off the grid in a top-to-bottom-left-to-right sequence. Where the classical rail fence cipher has a “key” which is a single integer, A, your algorithm will use two integers A, and B with A > B and B > 1; alternating between them when writing out the message on the fence rails. This algorithm reduces down to the classical rail fence cipher if A = B. 2.1.1 General Example If the message characters are denoted A, B, C, D, ... , etc and the cipher key is chosen as A = 4 and B = 2 then the message characters would be written on the rails as: A-------I-------Q -B-----H-J-----P- --C-E-G---K-M-O-- ---D-F-----L-N--- Observe the general pattern in the algorithm: 1. Down A rails (to D) 2. Up to a peak of B rails (up 1 to E) 3. Down B − 1 rails back to the bottom (down 1 to F) 4. Up to a peak of A rails (up 3 to I) 5. Repeat until whole message has been written to the grid The ciphertext can then be read off left-to-right-top-to-bottom: A, I, Q, B, H, J, P, C, E, G, K, M, O, D, F, L, N Optional For the purposes of this assignment your message may be “padded” with random characters so that it completes a full cycle on the rails. ie: It always finishes on the top rail. Note that ASCII lower case letters take the values 97 to 122 so a random lower case letter can be generated with rand()%26+97. Similarly, a random upper case letter is generated with rand()%26+65. Note that a N cycles require N × (2A + 2B − 4) + 1 letters. 2.1.2 Worked Example Encrypting the message “Move B company 1km West.” with A = 5 and B = 3: NB: “-” indicates an unused spot on the rails; “ ” indicates a space in the message. NB 2: The final “q” is a random character padding so that the algorithm finishes on the top rail. Page 2 of 11 Brenton Schulz https://en.wikipedia.org/wiki/Rail_fence_cipher http://practicalcryptography.com/ciphers/classical-era/rail-fence/ http://www.cprograms4future.com/p/encryption-rail-fence-cipher.html Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003- Introduction to Procedural Programming M-----------n-----------q -o---------a-y---------.- --v--- ---p--- --- ---t-- ---e-b-c-m-----1-m-W-s--- ---- ---o-------k---e---- Listing 1: The filled in rails. The cipher text is then: Mnqoay.v p tebcm1mWs oke 2.1.3 Decryption Designing and implementing the decyption algorithm will be mostly up to you to work out. However, to get you started, one decryption method could perform the following general steps: 1. Re-create the 2D grid from the cipher text and key (eg: Listing 1) 2. Read off the original message by performing the encryption algorithm again, except reading from the rails instead of writing Given the key numbers A and B and the encrypted cipher text the first decryption step requires you to rebuild the grid show in Listing 1. There are many methods to do this. One option is to observe that you need to know which grid location each letter goes in and realising that you have the means to work this out - the encryption algorithm does it! The encryption algorithm writes message letters to this grid so you can repeat that algorithm and, say, write a ”1” in all locations which have a letter written to them and ”-” (or, in C, a zero) otherwise. Given A = 5 and B = 3 from the previous example the grid will then look something like this: 1-----------1-----------1 -1---------1-1---------1- --1---1---1---1---1---1-- ---1-1-1-1-----1-1-1-1--- ----1---1-------1---1---- Then you can loop over the grid left-to-right-top-to-bottom and write cipher text characters to all grids with a ”1” to get back to what is seen in Listing 1. Once that is done the original “zig-zag” algorithm can again be applied to read off the message in the correct order or you can observe that there is only one letter per column so you can read all non-zero values left to right. 2.1.4 C Implementation Hints In no particular order: • The whole message can be stored in an array • The grid (ie: rail fences) can be a 2D array • When encrypting you can remove the need for a 2D array if you calculate 1D array indices in the message instead of doing it “graphically” with a 2D array Page 3 of 11 Brenton Schulz Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003- Introduction to Procedural Programming 2.2 Substitution Cipher A substitution cipher encrypts a text message by replacing each of the 26 message letters to an encrypted letter. Each letter is only chosen once. The “key” is therefore knowledge of all 26 different substitutions. The number of possible key combinations is: 26! ≈ 4× 1026. Example with a substitution chosen from the qwerty keyboard layout: Message letter: ABCDEFGHIJKLMNOPQRSTUVWXYZ Cipher text letter: QWERTYUIOPASDFGHJKLZXCVBNM As before, a message is encrypted by substituting each letter in the top row with the one below it: Message: PLEASE GET MILK AT THE SHOPS Cipher text : HSTQLT UTZ DOSA QZ ZIT LIGHL There is no neat algebraic method to write the encryption function. It is effectively a “look-up-table” where each letter, xn, becomes a different letter, yn based on a fixed substitution rule. 2.3 Substitution Cipher Attacks With 26! different encryption keys a brute force attack is not possible. Even when testing a million com- binations per second it would take almost 1000 times longer than the age of the universe to test every encryption key. Aside: the German Enigma machine (used in WWII) used a algorithm closely related to the substitution cipher and used a new encryption key every day. Even with modern computers a naive brute force attack would not have been possible. You can read about the Enigma decryption efforts on Wikipedia. Decryption must therefore rely on extra information which reduces the key search space. It is possible, for example, to perform a statistical analysis of the cipher text to estimate which letters were used for ’e’, ’t’, ’a’, ’z’, etc. If the message is assumed to be normal English text then other assumptions can be made. Any single letter word is likely to be ’a’ or ’i’, the latter being easier to spot if the message is case sensitive. Likewise, the most common three letter word is likely to be ’the’. By making educated guesses about the most common short words and letters a subset of the encryption key can be deduced. This knowledge, coupled with a dictionary, and some kind of “spell checker” algorithm such as Levenshtein distance, can then be used in an attempt to work out further letter substitutions. The WWII efforts to decrypt Enigma relied heavily on cribs. These were known, or assumed, sections of plain text for a given encrypted message. For example, many German messages would include regular weather reports in the same format and would reveal several of the day’s letter substitutions. Page 4 of 11 Brenton Schulz https://en.wikipedia.org/wiki/Cryptanalysis_of_the_Enigma Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003- Introduction to Procedural Programming 3 Programming Task Write a C program which performs the following tasks, selectable by the user: 1. Encryption of a message using the classical rail-fence cipher algorithm 2. Encryption of a message using the 2-level rail-fence cipher 3. Decryption of a message using the 2-level rail-fence cipher 4. (D/HD level) Decryption of a block of text encrypted with a substitution cipher but without being provided the key. This cipher text will be released at the same time as the project; you have about a month to analyse it. Your program must perform all analysis calculations (eg: letter or word statistics and dictionary comparisons) from scratch. 5. (HD level) Decryption of a previously unseen block of cipher text encrypted with a substitution cipher without the key. This block of text will be provided at marking time. All tasks you attempt needed to be coded in a single .c file and some kind of user interface designed which can select between them. Your
Answered Same DayMay 16, 2021

Answer To: Project: ENGG1003 - Programming Assignment 1 English Text Ciphers, April 6, 2020 ENGG1003-...

Arun Shankar answered on May 18 2021
133 Votes
#include
#include
#include // for atoi() function
void railFence(
char *message, char *cipherText, int length, int A);
void railFence2(char *message, char *cipherText, int length, int A, int B,
int dir);
int main()
{
    char output[1024];
char message[1024];
char temp[100]; // A char array to store user input.
int key; // Key of the railFence cipher.
printf("\nEnter key for railFence: ");
fgets(temp,100,stdin);
key = atoi(temp);
printf("\nEnter your message (delimiter: ~, ENTER key to stop): ");
...
SOLUTION.PDF

Answer To This Question Is Available To Download

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here