In this assignment, you will implement a simple form of message encryption that
ID: 3668463 • Letter: I
Question
In this assignment, you will implement a simple form of message encryption that dates back to the times of Julius Caesar. This technique, called the Caesar Cipher, does not offer much security in modern practice (and in fact the second half of the assignment is to crack it). Nonetheless, it is of historical importance and led to the development of ever-gradually more complex techniques like the Vigenère cipher and the Enigma from WWII.
This assignment will exercise your understanding of the following concepts:
functions and libraries
file stream objects
character arrays and ASCII representation
command-line arguments
Background
Julius Caesar (100-44BC) was involved in many complex affairs and would on occasion want to send messages secretly. Paraphrasing the 1st-century historian Suetonius,
If Caesar had anything confidential to say, he wrote it in cipher, that is, by so changing the order of the letters of the alphabet, that not a word could be made out. If anyone wishes to decipher these, and get at their meaning, he must substitute the first letter of the alphabet, namely A, for D, and so with the others.
Part 1: Encryption and Decryption
As illustrated in the video, the way Caesar would obscure/encrypt a message is the following:
write down the "plaintext" message you desire to send secretly.
write down a new "ciphertext" message: for each letter in the plaintext, write down the letter that appears 3 steps later in the alphabet.
send the ciphertext instead of the plaintext.
For example, if the plaintext is
Statue is safe?
the letter S is replaced by V (since the English alphabet goes ...PQRSTUVW... and the letter 3 steps after S is V), the letter T is replaced by W, etc, resulting in the ciphertext
Vwdwxh lv vdih?
This ciphertext message is what we would actually send. If someone were to intercept it, the meaning of the message would not be immediately obvious — they might think it's in a foreign language — so it provides at least a minimal degree of secrecy.
Your first program, shift, will automate this process. It should take two command-line arguments: the name of a text file which will contain the plaintext, and an integer shift indicating how many places the message should be shifted forward. It should print the ciphertext to standard output (cout).
E.g. if you type in the following two commands, you should see this output:
One issue has not been addressed: what do you do if you fall off the end of the alphabet? For example, how do we shift Z forwards by 3 steps? We will think of the alphabet as cyclic:
This means that the letter "after" Z is A. Here is an example illustrating this cyclicity:
In detail, the first letter of the plaintext is S, and the letter 10 steps "after" S is C, so the first letter of the ciphertext is C.
Decryption
This Caesar shift scheme has the nice property that decryption is basically the same as encryption. For instance, to "reverse" the shift of 3 steps forward, we want to basically move 3 steps backwards. But because we've arranged the letters of the alphabet in a circle, moving 3 steps backwards is the same as moving 23 steps forwards. Thus we can decrypt a message like so:
Part 1 Requirements and Structure
There is one requirement implicit in the above examples: you should shift lowercase letters to lowercase letters, uppercase letters to uppercase letters, and anything that is not a letter should be left alone.
Your shift program should work for any number of steps between 0 and 25. (The number of steps is the second command-line argument.) You could make it work for other values (like -3 or 30) if you like, but it is not required.
Because Part 2 will re-use many of the ideas from Part 1, you are required to create a library with three specific functions. We will give you a file caesarlib.h with the following contents:
You should implement these three functions in caesarlib.cpp.
As you develop caesarlib.cpp it is a good idea to test it. To help, we will include a program libtest.cpp that contains some basic tests:
When you compile and run it, you should see the following:
You may add extra functions to caesarlib if you like, but you may not delete or change the prototype of any of the three given functions is_letter, image, orprint_file_image. We will test them independently and expect them to exhibit the functionality described in the comments above their declaration.
There happens to be a built-in function for this (it is part of the C++ library cctype but can also be accessed through other means). You must not use it! Part of the point of this assignment is for you to be able to create a function like this from scratch. All of the necessary header files will be already given to you in the skeleton code.
After creating caesarlib, complete the skeleton of shift.cpp given to you. Make sure you understand the parts of the skeleton we give you pre-written; do not delete them. Compile your code with make shift and then test shift on the examples given above.
You can upload your part 1 files for testing before proceeding to part 2.
For Part 2 of the assignment, you will implement a specific method that cracks the Caesar cipher. It doesn't crack it perfectly (we'll give examples below) but it works on most ciphertexts that are long enough and not too weird. For example:
Frequency Analysis
The approach that you must use for crack.cpp is based on frequency analysis. In particular, we use the fact that in every language, some letters are more common than others. (It is the same reason that Q is worth a lot more than R in Scrabble.)
We will assume that in the English language, letter frequencies "on average" occur with a specific frequency distribution:
What this means is that "on average," we expect 7.93% of letters in English texts are the letter A, 1.91% are the letter B, 3.92% are the letter C, et cetera. We will give you a skeleton for crack.cpp that includes this frequency table (array) enfreq pre-defined for you.
The Khan Academy video suggested just looking at the maximum frequencies, but we will use a slightly more robust method instead. It is based on giving a score to each possible shift.
The score of a single letter is just its value in the frequency table.
Then the score of a decrypted message is the sum of the scores of its individual letters. (Anything that is not an English letter, like a digit or punctuation sign, has a score of 0.)
For example, on the example ./crack secret.txt above, your program should enumerate the possibilities:
Add shift of 0: message is "Vwdwxh lv vdih?" which has score 0.0098 + 0.0093 + 0.0351 + 0.0093 + 0.0026 + 0.0238 + 0.0506 + 0.0098 + 0.0098 + 0.0351 + 0.0824 + 0.0238 = 0.3014
Add shift of 1: message is "Wxexyi mw weji?" which has score 0.4622
...
Add shift of 23: message is "Statue is safe?" which has score 0.9679
...
Add shift of 25: message is "Uvcvwg ku uchg?" which has score 0.2935
Your program should determine the shift with the maximum score (which is the shift of 23 in this case). Then it should print out the image of the message under this shift.
Part 2 Requirements and Structure
Several of the methods in caesarlib will be useful again for this program. You must also implement the following two functions inside of crack.cpp; they will be useful in structuring your approach:
Again, you can define more functions if you like. However, these two must be present and completed in crack.cpp, with these prototypes.
You may test these functions with this test main:
If you compile and run
it should output
Perform any additional tests you like. You will need to delete, comment or rename that test main in order to add the real main function of crack.cpp.
Reiterating the example given earlier, the main function of crack.cpp should take one command-line argument, which is the name of a ciphertext. It should compute the score of the file's contents under all possible shifts from 0 to 25 and determine the shift with the best score. Then, it should print to standard output (cout) the image of the file under that shift. Compile it with make crack.
Examples and Caveat
You can create small sample files and crack them as follows:
No matter what number of steps you pass as a command-line argument to shift, thecrack program should give the right answer on the last line.
This score-based cracking method is not perfect: it will fail sometimes. For instance, let's repeat the above example with a different plaintext, Rhythm & Blues.
That's not exactly English! However, the score of this shift "Xnezns & Hraky" is 0.5669, which is bigger than the score 0.5486 of "Rhythm & Blues". Better methods could avoid this by looking at consecutive pairs of letters. However, don't do this. We want you to implement the exact method described above, so for our purposes, this is the correct output.
Starter Code:
/*
shift.cpp
Author:
Short description of this file:
*/
#include "caesarlib.h"
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
if (argc != 3) {
cout << "Wrong number of arguments." << endl;
cout << "Usage: shift message.txt shift_number" << endl;
return 1;
}
// FILL this in:
// read the arguments and print the shifted output
int result = print_file_image(________, __________); // FILL in
// return sensible error if the filename is wrong
if (result != 0) {
cout << "Couldn't open the input file." << endl;
return 1;
}
return 0;
}
NEXT CODE
/*
shift.cpp
Author:
Short description of this file:
*/
#include "caesarlib.h"
#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char* argv[]) {
if (argc != 3) {
cout << "Wrong number of arguments." << endl;
cout << "Usage: shift message.txt shift_number" << endl;
return 1;
}
// FILL this in:
// read the arguments and print the shifted output
int result = print_file_image(________, __________); // FILL in
// return sensible error if the filename is wrong
if (result != 0) {
cout << "Couldn't open the input file." << endl;
return 1;
}
return 0;
}
NEXT CODE
/*
libtest.cpp
Author: CS 103 Course staff
Description:
Runs a few basic tests of caesarlib.
See assignment page for expected output.
*/
#include "caesarlib.h"
#include <iostream>
#include <iomanip>
using namespace std;
int main() {
cout << boolalpha;
cout << is_letter('g') << " ";
cout << is_letter('G') << " ";
cout << is_letter('?') << endl;
cout << image('S', 3) << " ";
cout << image('w', 23) << " ";
cout << image('?', 10) << endl;
return 0;
}
NEXT CODE
/*
caesarlib.cpp
Author:
Short description of this file:
*/
#include <fstream>
#include <iostream>
#include "caesarlib.h"
using namespace std;
// is this char an English letter?
bool is_letter(char ch) {
return false; // DELETE this stub and fill in the function body
}
// return shifted image of ch (if ch not letter, don't shift)
// assumes 0 <= steps < 26
char image(char ch, int steps) {
return ' '; // DELETE this stub and fill in the function body
}
// shift all characters in this file and print it to cout
// return 1 if error (file couldn't be opened), 0 if no error
int print_file_image(const char filename[], int steps) {
return 1; // DELETE this stub and fill in the function body
}
NEXT CODE
/*
caesarlib.cpp
Author: FILL THIS IN
Description:
Header file for the caesarlib library.
Provide useful functionality for both parts of the assignment.
*/
#ifndef _H_CAESARLIB
#define _H_CAESARLIB
// is this char an English letter?
bool is_letter(char ch);
// return shifted image of ch (if ch not letter, don't shift)
// assumes 0 <= steps < 26
char image(char ch, int steps);
// shift all characters in this file and print it to cout
// return 1 if error (file couldn't be opened), 0 if no error
int print_file_image(const char filename[], int steps);
// ADD more prototypes below if you want
#endif
Explanation / Answer
Try this following set of code for Caesar Cipher in C++
//letter frequency counter
#include <iostream>
#include <fstream>
#include <string>
//assume lowercase
using namespace std;
int main()
{
int freq[26]={0};
char ch='a';
string inny;
ifstream filein;
filein.open("input.txt", ios::in);
filein >> inny;
filein.close();
int length = inny.length();
while (length > 0)
{
freq[((int) inny[length-1])-97]++;
length--;
}
while ((length) < 26)
{
while (freq[length] > 0)
{
cout << "-";
freq[length]--;
}
cout << ch++;
length++;
cout << endl;
}
int diff = 'h'-'e'; //parameters
length = inny.length();
int count = 0;
int charVal;
while (length > count)
{
charVal = (int) inny[count]-diff; //positive or negative depending on offset
if (charVal < 97)
{
charVal=charVal+26;
}
cout << (char)charVal;
count++;
}
cout << endl;
return 0;
}