Description
1 Introduction
CS 135 (and other first year courses) establish the foundations for your critical and logical thought processes that you will apply to every problem encountered as engineers.
Secondary to that, you also learned some C/C++ syntax to articulate your solutions to the aforementioned problems. The purpose of this assignment is to serve as the refresher and application of all things learned in CS 135.
This assignment should be thought of as a CS 135 capstone project.
2 Background
Encryption is, and always has been, a fundamental aspect of life; without it, everyone could know everything about everyone else. Historically (over 2000 years ago now), the Romans used encryption algorithms in times of their warring and conquering periods across modern day Europe.
Julius Caesar used similar algorithms in his personal correspondents to obfuscate intended messages. What is now almost a century ago, the Germans used more advanced encryption methods via the Enigma machine to transmit sensitive battle plans during World War II.
Needless to say, in the applications of modern day technology, encryption has become evermore present. The only way you could have accessed this pdf file is by logging in to the Canvas system with a user name and password.
The only way you could have accessed the Canvas website is 1 through an encrypted TLS handshake protocol between your computer and the server where the file is hosted. None of that would have been possible if I didn’t deliberately upload the files to the server in the first place (which also includes everything stated earlier).
For those of us living in the information era, it is critical that you know these systems are in place to protect our information, personal assets, and identity. However, for those hoping to earn a degree in or related to computer science, engineering, or mathematics; eventually, you will need to know of more than just their existence.
3 Task
This is a multi-part assignment where you will implement two different encryption algorithms: Stream Ciphers: Modified Caesar Cipher (part 1) Textbook RSA (part 2) Naturally, I cannot assume that you have any knowledge or background in encryption algorithms or higher level mathematics to implement either of the prior 2 algorithms. But, fret not.
This writeup will walk you through everything you need to know about the mathematics, methods, and behaviors needed for the Modified Caesar Cipher and part 2 will have much of the maths already implemented. It will then be up to you to figure out how to take that information and convert it into an equivalent C/C++ style program. It should be noted, the only programming techniques needed for the program’s solution are those taught to you in CS 135 (this is a review assignment after all).
4 Stream Ciphers
Stream Ciphers, like the ones Julius Caesar and the Germans used, augment the original message one character at a time. This augmentation can come in many forms: 1. Offsets 2. Rotations 3. Repositioning (Mixing) In this part of the assignment we are only going to focus on offsets and rotations.
4.1 Offsets Offsetting is the act of changing the ”value” of a letter. In the English language, we have a set of letters {a,b,c, … , x, y, z}. Assume that each one of these letters can be related to a value on a subset of the integer number line. (a, 0) (b, 1) (c, 2) . . . (x, 23) (y, 24) (z, 25) Mathematics tells us that any value with position on the number line can be moved along that line.
If we wished to offset a character then we simply need to add that offset value to that character. 2 E.g., ’a’ + 2 = ’c’ (a, 0) (b, 1) (c, 2) . . . (x, 23) (y, 24) (z, 25) Inversely, we can also move a offset a character in the other direction by performing subtraction (negative addition). E.g., ’c’ – 2 = ’a’ (a, 0) (b, 1) (c, 2) . . . (x, 23) (y, 24) (z, 25) However, let us consider the following application of the offset function. ’y’ + 2 = ? Now, we’ve run into an issue.
The offset has landed us beyond the boundaries of our domain. (a, 0) (b, 1) (c, 2) . . . (x, 23) (y, 24) (z, 25) The solution to this issue is quite simple and elegant.
4.1.1 Modular Arithmetic Modular arithmetic is its own branch of mathematics that you will formally learn (or may already have already learned) about in any number of courses (E.g., Discrete Mathematics, Number Theory, Circuit design, Complex Algebra, etc…).
We won’t go into great detail on this branch of mathematics, but we will cover 2 things in this section: 1. Basic theory of counting systems 2. How to implement modular arithmetic Basic theory of counting systems We have been performing modular arithmetic our whole lives by simply counting on our fingers or reading an analog clock.
Fundamentally, when we count numbers on our fingers, we can only count up to 10 and then start over. Therefore, we refer to our number system as ”base 10”. Each time the value of 10 is reached as we count, we add 1 to the next ”place” in our count and reset the original ”place” to 0. 3 0 + 1 = 1 + 1 = 2 + 1 = 3 + 1 = 4 + 1 = 5 + 1 = 6 + 1 = 7 + 1 = 8 + 1 = 9 + 1 = 10 + 0 These ”places” are referred to as the 1’s place, 10’s place, 100’s place, etc…
This implies that any value in the domain of base 10 integers can be mathematically represented by the following equation. Figure 1: Series Composition X p i=0 v[i] ∗ 10i , (1) p := number of places v := value at place i E.g., Figure 2: v = {9, 6, 7, 1} = 9 ∗ 100 + 6 ∗ 101 + 7 ∗ 102 + 1 ∗ 103 = 9 ∗ 1 + 6 ∗ 10 + 7 ∗ 100 + 1 ∗ 1000 = 9 + 60 + 700 + 1000 = 1769 We can apply this same logic to reading an analog clock. Seconds, base 60
For every 60 seconds to pass, 1 minute has passed Minutes, base 60 For every 60 minutes to pass, 1 hour has passed Hours, base 12 For every 12 hours to pass, 1 clock rotation has passed 4 Now, we can apply this same logic to our alphabetized number line. (a, 0) (b, 1) (c, 2) . . . (x, 23) (y, 24) (z, 25) We can say that our number line is base 26.
Therefore, for every offset to exceed the base, the offset cycles back to the beginning (much like a clock) ’y’ + 2 = ’a’ (a, 0) (b, 1) (c, 2) . . . (x, 23) (y, 24) (z, 25) We can now see that the answer to our original question is ’a’. But, why? Implementation of Modular Arithmetic The reason is because the remainder after division by the base is 0. Recall, that output of every division operation with a numerator(N) and denominator(D) yields a quotient(Q) and a remainder(R).
In C/C++ dividing 2 integers will only give us the quotient N D = Q If division gives us the quotient then modulus will give us the remainder. Mathematically, this is expressed by the following equation. R = N (mod D) or R = N % D D is the base of our number system. N is the value of the character we are evaluating combined with the offset.
R is the output character of the function. Let’s take a look at some of the examples we have done up to now. 1. ’a’ + 2, R = 0 + 2 mod 26 = 2 mod 26 = 2 = ’c’ 2. ’c’ – 2, R = 2 – 2 mod 26 = 0 mod 26 = 0 = ’a’ 3. ’y’ + 2, R = 24 + 2 mod 26 = 26 mod 26 = 0 = ’a’ 5 4. ’a’ – 2, R = 0 – 2 mod 26 = -2 mod 26 = 24 = ’y’ 4.1.2 Offset Encryption Now, that we understand how to apply offset encryption to a single character, let’s consider what it takes to apply that encryption to a word or a sentence.
Consider the phrase: ”The brown cat, sleeping quietly, awoke.” and an offset of 5. What we expect is: ”Ymj%twfslj%hfy1%xqjjunsl%vznjyq 1%f—tpj3”. and if we apply the offset of -5 we get the original phrase back.
While we are going to offset each character individually, we have new constraints to consider. Namely: 1. Capitol letters 2. Special characters 3. Spaces While Caesar had an easier time expanding his base system to accommodate these constraints by adding on the additional 26 uppercase characters and a few special characters for spaces, commas, and other punctuation characters to have a base of 60; we are using computers and to do the same thing as Caesar would be inefficient and complicated.
Thus, we turn to the ASCII table. No doubt, if you go to your favorite search engine and look up ”ascii table” you will find something like this. The ascii table (UTF-8) standard represents a set of the first 128 encoded characters for most computer systems. This domain of character to value encodings contains everything we need to implement the offset encryption.
Thankfully, all we have to do is use it in combination with an offset value and the domain value (number of characters, 128) 6 4.1.3 Code Implementation That’s enough theory. Now, let’s get into writing some code to implement all of the things we’ve learned up to now. Along with this pdf was a tar file that contains all files you will need to complete this part of the assignment.
First, we are going to look at the sequential encryption.cpp file. This file is where you will be writing all of your code. The first thing you may notice is all of functions that have already been declared for you. At this point you should be very well acquainted with functions, function parameters, and functions returning values from CS 135.
These functions are where you will write your code. (see for more guidelines on writing the code). Throughout the remainder of this assignment writeup (in the sections where we talk about code) you will see the names of functions color coded as follows: Functions that you must implement are in red. Functions that have been implemented for you are in blue.
Functions that have been partially implemented are in magenta and are yours to finish implementing. Provided variables will be highlighted in green 1. main: main has already been implemented for you and contains exactly 3 function calls. Each one of these function calls serve to test the efficacy of the functions you will write throughout this part of the assignment.
You will notice that the second and third functions are already commented out. Don’t uncomment them until you have finished this part of the assignment. 2. offset encryption: In this function you will define and offset and a message to encrypt / decrypt. The offset encryption function will then call the offset(string, int) function 2 times.
The first time will encrypt the message and the second will decrypt the message. You must display the message to the terminal before and after each successive call to the offset function. Example output: ☎ 0 [ z x p s ] s t r e am ci p h e r s <=> g++ s t r e am ci p h e r s . cpp [ z x p s ] s t r e am ci p h e r s <=> . / a . out 2 Text : The o r an ge cat , s l e e p i n g q ui e tl y , awoke .
4 Cipher : Ymj%t w f s l j%h fy 1%x q j j u n s l%vzn jyq˜1% f | t p j 3 6 DeCipher : The o r an ge cat , s l e e p i n g q ui e tl y , awoke . 8 [ z x p s ] s t r e am ci p h e r s <=> ✆ 7 3. offset(string, int): This function is where you will perform the actual character offset and return the encrypted message. You must iterate over each character individually and perform the proper maths as seen in section ”Implementation of Modular Arithmetic”.
To obtain the number of characters in your string parameter use the length function from the string library Once a character has been offset it should be added to a the return string. After every character in the string parameter has been offset you must return the offset string back to the offset encryption function for its print out. (note: the numeric value of a character can be printed by adding (int) before the character. (e.g., cout << (int)a; outputs 97))
4.2 Alternative Storage Once you get the provided offset and message from the offset encryption function working, feel free to play around with other offset values and messages. You may find what you have coded to be full of bugs, and that’s okay (it’s actually expected and deliberate).
While convenient the UTF-8 ascii standard in combination with the use of cout to allow escape characters like \n, \t, \b, and ascii value 127 (delete) introduces many bugs. Thus, we must look to alternative methods for storing the data we encrypt and decrypt.
4.2.1 Input and Output Files In CS 135 you were exposed to writing and reading data to and from files. Here you must put what you have learned to the test. There is a collection of 5 functions you will need to write. Each one is relatively small, but the progression of their function calls are linked. When you have so many functions in a single program, it can be easy to get lost and forget which function does what and why.
Therefore, you should get in the habit of making flow charts for small scale and linear programs. The nodes are labeled with the function name, the black edges are labeled in accordance with the entries in the numbered list below, and the red edges are from the handout code. main seq file encrypt open input file open argv file open output file open input file open output file
3. 5. 2. 1. 1. 4. 8 1. open input file(string) This is a helper function to any other function that requests a file to be opened. Given the name of a file this function will attempt to open said file an store it in an ifstream varaible. If the open function failed, then the user must log that and exit the program with a status of -1; otherwise return the ifstream varaible. Assume the following main function: ☎ 0 int main ( int argc , char const ** argv ) { o p e n i n p u t f i l e ( ” i n c o r r e c t f i l e n a m e . t x t ” ) ; 2 return 0 ; } ✆
The behavior of the program is as follows: ☎ 0 [ z x p s ] s t r e am ci p h e r s <=> g++ s t r e am ci p h e r s . cpp [ z x p s ] s t r e am ci p h e r s <=> . / a . out 2 ERROR: Could not open f i l e : i n c o r r e c t f i l e n a m e . t x t 4 [ z x p s ] s t r e am ci p h e r s <=> ✆ 2. open argv file(int argc, const char** argv) This function will attempt to open a file, whose name is provided before the execution of the program, and should behave as follows. Assume the following main function: ☎ 0 int main ( int argc , char const ** argv ) { o p e n i n p u t f i l e ( ” i n c o r r e c t f i l e n a m e . t x t ” ) ; 2 return 0 ; }
✆ The behavior of the program is as follows: ☎ 0 [ z x p s ] s t r e am ci p h e r s <=> g++ s t r e am ci p h e r s . cpp [ z x p s ] s t r e am ci p h e r s <=> . / a . out q u o t e s . t x t q u o t e s . t x t 2 ERROR: I n c o r r e c t u s a ge ! 4 . / a . out [ z x p s ] s t r e am ci p h e r s <=> . / a . out 6 ERROR: I n c o r r e c t u s a ge ! 8 . / a . out [ z x p s ] s t r e am ci p h e r s <=> . / a . out i n c o r r e c t f i l e n a m e . t x t 10 ERROR: Could not open f i l e : i n c o r r e c t f i l e n a m e . t x t 12 [ z x p s ] s t r e am ci p h e r s <=> . / a . out q u o t e s . t x t [ z x p s ] s t r e am ci p h e r s <=> ✆
Note: The error message generated on the second run of the program comes from open input file() and not this one! 9 3. open input file() This function will serve as a user prompting function that requests a file name from the user at runtime.
Once the user has entered a file name you must call the open input file function and provide it with the aforementioned user input and return the open input file return value. Assume the following main function: ☎ 0 int main ( int argc , char const ** argv ) { o p e n i n p u t f i l e ( ) ; 2 return 0 ; } ✆ The behavior of the program is as follows: ☎ 0 [ z x p s ] s t r e am ci p h e r s <=> g++ s t r e am ci p h e r s . cpp [ z x p s ] s t r e am ci p h e r s <=> . / a . out 2 Pl e a s e e n t e r the name o f your i n p u t f i l e : i n c o r r e c t f i l e n a m e . t x t 4 ERROR: Could not open f i l e : i n c o r r e c t f i l e n a m e . t x t [ z x p s ] s t r e am ci p h e r s <=> . / a . out 6 Pl e a s e e n t e r the name o f your i n p u t f i l e : q u o t e s . t x t [ z x p s ] s t r e am ci p h e r s <=> ✆
Note: The error message generated on the first run of the function comes from the open input file function. 4. open output file(string) This is a helper function that behaves identically to the open input file(string) function. Where the only difference is storing the opened file in an ofstream variable. Note: This function call should not generate any error messages.
If it does then something larger than this function is the issue and you should seek guidance from a TA or an instructor on how to address it. 5. open output file() This function will behave identically to the open output file function. Where the only difference is a modification to the prompt the user sees and returning an ofstream variable instead of an ifstream.
☎ 0 int main ( int argc , char const ** argv ) { o p e n o u t p u t f i l e ( ) ; 2 return 0 ; } ✆ 10 The behavior of the program is as follows: ☎ 0 [ z x p s ] s t r e am ci p h e r s <=> g++ s t r e am ci p h e r s . cpp [ z x p s ] s t r e am ci p h e r s <=> . / a . out 2 Pl e a s e e n t e r the name o f your output f i l e : t e s t . t x t [ z x p s ] s t r e am ci p h e r s <=> l s t e s t . t x t 4 t e s t . t x t [ z x p s ] s t r e am ci p h e r s <=> ✆
Note: This function call should not generate any error messages. If it does then something larger than this function is the issue and you should seek guidance from a TA or an instructor on how to address it.
4.2.2 Parsing an Input file and Writing to and Output File Once you get the prior 5 functions working as expected this next part should be easy.
First, edit your main function so the only function call in it is the preprovided function call. sequential_file_encryption(open_output_file(), open_argv_file(argc, argv)); sequential file encryption Some of this function has already been implemented for you.
First, it will prompt the user for an offset value. Then comes your job. This function will parse a given input file one line at a time and encrypt the line using the offset function you implemented earlier. How you obtain the data at each line is up to you.
I would strongly recommend using the getline string library function. The string returned by offset should then be written to the output file provided in the parameter list (output). After each line of the input file is processed close both the input and output files.
If you are having issues with this function here are a few debugging tips 1. Print the data to cout instead of the output (remember you can encrypt data that isn’t there in the first place) 2. Don’t use the quotes.txt file. We will use that file to grade, for sure. But, as you develope your code take it slow. Write your own file one line at a time to make sure everything is working properly.
3. Defunctionalize your code. While your final submission must have all code written in the provided functions, that shouldn’t stop you from writing the code in main. Then testing it and finally transferring it to the function and testing it again.
Assume the following main: ☎ 0 int main ( int argc , char const ** argv ) { s e q u e n t i a l f i l e e n c r y p t i o n ( o p e n o u t p u t f i l e ( ) , o p e n a r g v f i l e ( argc , argv ) ) ; 2 return 0 ; } ✆ 11 The behavior of the program is as follows: ☎ 0 [ z x p s ] s t r e am ci p h e r s <=> g++ s t r e am ci p h e r s . cpp [ z x p s ] s t r e am ci p h e r s <=> . / a . out 2 ERROR: I n c o r r e c t u s a ge ! 4 . / a . out [ z x p s ] s t r e am ci p h e r s <=> . / a . out q u o t e s . t x t 6 Pl e a s e e n t e r the name o f your output f i l e : ci p h e r . t x t What i s your s h i f t key ? 5 8 [ z x p s ] s t r e am ci p h e r s <=> . / a . out ci p h e r . t x t Pl e a s e e n t e r the name o f your output f i l e : message . t x t 10 What i s your s h i f t key ? =5 [ z x p s ] s t r e am ci p h e r s <=> ✆
What’s happening here is two fold: 1. On the first run of the program. I am providing the program with the quotes.txt and then telling the program to create (or open) a file called cipher.txt to write the encrypted data to.
Each line of quotes is then encrypted with a shift key of 5 and then written to cipher. 2. On the second run of the program. I am undoing all of what I just did in the first run by providing the exact same program with the cipher.txt file instead of the quotes file and ”decrypting” it with a shift key of -5.
This restores the original data to what was in quotes and writes that data to the message.txt file. As part of the handout I have included the quotes, cipher, and message text file for you. Use the cipher text file to make sure your offset function is performing as expected.
4.3 Rotation Encryption Analogous to the offset cipher encryption is the rotation based encryption schemes.
Conceptually, rotation is a fairly easy subject to understand. For rotation you are given a string and a number of positions to ”rotate” by. E.g., Assume you are given the following string: ”Hello” and 3 positions to rotate by. The following is the Naiive approach. ☎ 0 int main ( int argc , char const * argv [ ] ) { s t r i n g message = ” H ell o ” ; 2 int r = 3 ; char c ; 4 int l e n = message . l e n g t h ( ) ; 6 for ( int i = 0 ; i < r ; i++) { c = message [ l e n = 1 ] ; 8 for ( int j = l e n = 1 ; j > 0 ; j ==) 10 message [ j ] = message [ j = 1 ] ; message [ 0 ] = c ; 12 } } ✆ 12 This approach is terrible for three big reasons. First, it requires the string (character array) to be parsed more than once.
For small strings this isn’t a major issue; after the first pass your message is ”oHell” then ”loHel” and finally ”lloHe”. However, consider what would happen if your string was a million characters long and the value of r was in the hundred of thousands. That is on the order of 1011 (billions) of array accesses for a single line of encryption.
Such approaches are never acceptable except under very strict circumstances. Second, it cannot rotate to the left. If r is negative (as it will be in left rotation), then the for loop on line 6 of the code above will never terminate. This necessitates more code it accommodate for this fundamental flaw in rotation. ☎ 0 int main ( int argc , char const * argv [ ] ) { s t r i n g message = ” H ell o ” ; 2 int r = =3; char c ; 4 int l e n = message . l e n g t h ( ) ; 6 i f ( r > 0 ) { // Rotate Right for ( int i = 0 ; i < r ; i++) { 8 c = message [ l e n = 1 ] ; for ( int j = l e n = 1 ; j > 0 ; j ==) 10 message [ j ] = message [ j = 1 ] ; message [ 0 ] = c ; 12 } } e l s e i f ( r < 0 ) { // Rotate L e f t 14 for ( int i = r ; i < 0 ; i++) { c = message [ 0 ] ; 16 for ( int j = 0 ; j < l e n ; j++) message [ j ] = message [ j + 1 ] ; 18 message [ l e n = 1 ] = c ; } 20 } } ✆
Notice, that the structure of lines 13 to 18 are identical to the original algorithm to rotate right. Unfortunately, this is something that can’t be overcome without introducing some clever index trickery. The final reason for why this algorithm is terrible is because of its ability to allow rotations that are greater than the length of the message. Question: What is the message ”Hello”, after rotating by 5 or any other multiple of 5?
Answer: The EXACT SAME THING. Meaning, if any application of the rotation function satisfies the following equation: 0 = r % message.length() Then, the output of the rotation function is the same as the input message and no work should be done other than returning the original message. At face value rotation seems rather simple, but as you begin to think about the details the implementation complexity grows.
This WILL be a common theme as you manoeuver through your engineering career. The ability to think of the details and create your own solutions is something every great engineer and scientist must master before you graduate university. Therefore, I want to you to develope your own rotation algorithm. 13 rotate(string, int) The expected behavior of this function is rather simple.
Given an input string and number of integer places to rotate, return the rotated string. However, we now know that the details of this will be complicated and I have some further restrictions for your implementations.
1. The use of modulus and division operations are strictly forbidden WITHIN looping constructs. 2. The rotator value must be adjusted to not allow excess rotations (as described in the final reason above) 3. You may only evaluate each character of the input string ONCE (in contrast to reason 1) 4. NO built in library functions other than length may be used.
A good place to start this function by making a copy of the original message in another string and go from there. I also highly recommend busting out the pen and paper or dry erase board and markers to sketch out and verify your ideas before coding them. Don’t develope code you aren’t 100% sure will work and you will never have bugs 🙂
4.4 Combining Rotation and Offset Once you have finished the rotate function and are sure it is working you can move on to the final function of this file. Now that you have 2 methods of augmenting text data it is time to combine them. The beauty of encryption is that it is based on invertible functions. We saw this with offset where we moved a character left and inversely right on its number line and in rotation where we could rotate characters left and right within a string.
Logically, we can conclude that the combination of these functions is safe to perform (so long as you remember how to undo the original manipulation). First, I would like you to try rotating a string and then offsetting it by using the rotate and offset functions. This should give you some kind of jumbled mixture of letters that we can consider to be an encrypted message.
Then I want you to reverse the offset and then reverse the rotation and you should end up with your original message. E.g., ☎ 0 message = ” . . . . . . . . . . . ” ; message = r o t a t e ( message , R) ; 2 message = o f f s e t ( message , O) ; message = o f f s e t ( message , =O) ; 4 message = r o t a t e ( message , =R) ; ✆ 14 Then I want you to do the same thing again but encrypt the message twice and then decrypt it twice with differing values. E.g., ☎ 0 message = ” . . . . . . . . . . . ” ; message = r o t a t e ( message , R) ; 2 message = o f f s e t ( message , O) ; message = r o t a t e ( message , R2) ; 4 message = o f f s e t ( message , O2) ; message = o f f s e t ( message , =O2) ; 6 message = r o t a t e ( message , =R2) ; message = o f f s e t ( message , =O) ; 8 message = r o t a t e ( message , =R) ;
✆ If the final message is the same as your original than you are ready to implement the last function and get the password to part 2. rotation encryption(string) This function performs the encryption or decryption protocols based on user input and will perform them for as many times as instructed by the scheme parameters struct. You briefly learned about C/C++ structs towards the CS 135 and how they are a means of encapsulating data.
I have already implemented the struct for you and all of the embedded data is there. The only thing you have to do is access it through the es variable. If you aren’t sure how to do this, you will by then end of your lecture on classes. ☎ 0 struct scheme p a r ame te r s { s t a t i c const int s t a g e s = 3 ; 2 int r o t a t e [ s t a g e s ] = {2 2 , 4 , 4 0 }; int o f f s e t [ s t a g e s ] = {2 , 4 , 8 } ; 4 } ; ✆ The function will first prompt the user for a protocol to use; encryption (e or E) or decryption (d or D).
Based on that input the function will then rotate then offset or offset then rotate stages many times (stages is a member of scheme_parameters es) where the rotate and offset parameters (R and O) are the values in the rotate and offset arrays. Once you get the rotation encryption(string) function working, it’s time. Edit main so that the rotation file encryption function is the only one active. Then provide the function with the pt2Key.txt file and tell the function to decrypt (d or D).
This will give you the pass phrase to unlock the second part of this assignment. The pass phrase is something in English so that should help you to verify that it worked or not. Also keep in mind, the only one who knows the pass phrase is me and the only way to obtain it is by implementing all of this code correctly. So please, work hard to decrypt the key for yourself; because the graders will know if you didn’t. I’ll see y’all in part 2. 15
