Harvard CS50: Week 2 Assignments (Lectures 5 and 6)

The CS50 lectures are here: https://cdn.javarush.com/images/article/155cea79-acfd-4968-9361-ad585e939b82/original.pngcs50.html . This material contains 3 tasks, theoretical information about them and a guide to action.

Goals

• Go deeper into functions and libraries • Get familiar with cryptography, implement a couple of simple ciphers

Additional materials

https://reference.cs50.net/ - explanation of library functions used during training. In English. http://computer.howstuffworks.com/c.htm pages 11 – 14 and 39

Preparation

Log in to cs50.io update50 to make sure your workspace version is up to date. If you accidentally close the terminal window, go to the View menu and make sure that there is a checkmark next to the Console item (check it if it is not). Click on (+), inside the green circle on the frame of the terminal window, select New Terminal . Create a working directory: mkdir ~/workspace/pset2 Note that there is a space between mkdir and ~/workspace/pset2 . To recap, ~ means the root directory, ~/workspace is a folder called workspace inside the root directory, ~/workspace/pset2 is a directory called pset2 inside ~/workspace . Now run: cd ~/workspace/pset2 to change to the new directory. The command line looks something like this: username:~/workspace/pset2 $ If anything is wrong, repeat the steps. You can also call a command history to view the last few commands in chronological order. You can also place your cursor on the command line and press the up arrow on your keyboard to view all commands in order from the last entered to the first. Using the down button you can go back. By the way, instead of typing the same commands every time, you can scroll through the commands you have already typed and execute them again by pressing Enter. You may have noticed that David does exactly this in his lectures. The tasks of the second week should be saved in pset2 .

Task 0. Initialization

Let's take a closer look at the lines. In the initials.c file, write a program that requests the user's name (using the GetString function we get the name as a string) and then displays the first letters of the first name (or names) and last name in uppercase without spaces, periods or other characters, only with a line feed ( \n ). We assume that users enter only letters (lower or upper case, or both) plus one space between words. Consider that guys named Joseph Gordon-Levitt, Conan O'Brien, or David J. Malan won't use the program. To check the correct operation of the program, call check50: Do you want to play with the implementation of the program prepared by the CS50 staff? Type the line: username:~/workspace/pset2 $ ./initials Zamyla Chan ZC username:~/workspace/pset2 $ ./initials robert thomas bowden RTBcheck50 2015.fall.pset2.initials initials.c~cs50/pset2/initials

Cryptography

Cryptography, the science of encrypting and deciphering information... In fact, encrypted messages have existed since ancient times, and were used by armies to transmit secret messages. Well, now your passwords on Facebook and other networks are stored in encrypted form.

Task 1. Hail, Caesar!

Theoretical information

We will study one of the simplest ciphers - the Caesar cipher, named after the Roman emperor. In this cipher, each letter of the text is replaced by another, which is a fixed number of letters lower in the alphabet. This fixed number of letters is called a key . So, key 1 transforms the Latin letter C into the letter D, and Z through the cycle into A. If the key is 3, then the letter C will transform into F, and Z into C. Examples: we use the Caesar cipher with key 5 on the word cat. c -> h a -> f t -> y Caesar (cat, 5) = hfy Key = 7, word = computer c->j o->v m->t p->w u->b t->a e->l r->y Caesar(computer,7) = jvtwbaly The Caesar cipher is simple, but, alas, unreliable (these are interconnected things!): for the English alphabet there are only 25 encryption options, it’s easy to go through all the options even without a computer. However, the Caesar cipher is often used as a step in other ciphers, such as the Vigenère cipher (more on that in the next paragraph). Let's "mathematicize" the Caesar cipher. Let's denote the plaintext by the letter p, pi is the letter in the text p that is at position number i. Let's call the secret key letter k, c the ciphertext, and ci the letter in the ciphertext that is at position i. Then you can calculate each letter of the cipher using the formula: ci = (pi + k) % 26 Get used to this formalization, it allows you to program the algorithm and expresses the meaning of the cipher accurately and concisely. If the key k = 13 and the original text p is "Be sure to drink your Ovaltine!", this is the cipher we get: Or fher gb qevax lbhe Binygvar! Note that O (the first letter in the ciphertext) is shifted 13 positions from the letter B (the first letter in the original text ). The same thing with the letter r (the second letter in the encryption) is shifted 13 letters from e (the second letter in the original). The third letter in the encryption, f, is shifted by 13 letters from s (the third in the original), here we go in a circle from z to a. A Caesar cipher with key 13 has the special name ROT13 . It is symmetrical: applying it twice, we return to the original text. Of course, there is also ROT26, this one is generally super-secure, but only if you do not express your thoughts clearly =).

Condition

Write in the file caesar.c a program that encrypts text using the Caesar cipher. Provide one command line argument as input to the program: a non-negative integer. For simplicity, let's call it k. If the user executes the program with no command line arguments or with more than one argument, the application should complain and return the value 1 (this is how errors are usually denoted): return 1; In all other cases, the program prompts the user for the text to encrypt, then displays the text encrypted with key k (i.e., shifted k positions to the right along the cycle). If the text contains characters that are outside the English alphabet, the program does not change them. After printing the ciphertext, the application exits, main returns 0: return 0; If main does not explicitly return zero, it returns it automatically (int is actually the return type of main, but more on that another time). According to convention (the rules of good form in programming), if you explicitly return 1 to indicate an error, then you should also return 0 as a pointer to the successful completion of the program. Although there are only 26 letters in the English alphabet, k can be larger than 26. Essentially, the key k = 27 will give the same result as k = 1, but you need to allow the user to enter any non-negative number not exceeding 2^31 – 26 ( it must fit into int). The program must also take into account that lowercase letters are encrypted in lowercase, and uppercase letters are encrypted in uppercase. Where do we start? Since the application must accept the value of k directly in the argument string, our main function header looks like this: int main(int argc, string argv[]) From Chapter 6, you know that argv is an array of strings. The array can be thought of as a row of lockers in a gym. Each of them has some meaning hidden. In our case, inside each cell there is an argument like string To open the first locker, we use argv[0], the second - argv[1], and so on. If we have n locks, then we need to stop at argv[n - 1], since argv[n] no longer exists (or exists, but belongs to someone else, we better not touch it). So you can access the argument k like this: string k = argv[1]; We believe there really is something there! Recall that argc is an int variable equal to the number of rows in argv. This means that it is better to check the value of argc before trying to open the cell, because it may turn out that it does not exist. Ideally argc = 2. Why is this so? Inside argv[0] is usually the name of the program. That is, argc is always at least 1. But our program needs the user to provide a command line argument k, therefore, argc = 2. Naturally, if the user enters more than one argument on the command line, argc also grows and can be greater than 2 If the user enters an integer into a string, this does not mean that the entered value will be automatically stored as an int. More precisely, it will NOT. It will be a string, even if it looks exactly like an int! So we need to convert string to int ourselves. Fortunately, there is a function called atoi designed for this purpose. Its syntax is: int k = atoi(argv[1]); Note that k is of type int, so you can do arithmetic with it. With this function, you don't have to worry about whether the user enters an integer or, say, foo: in that case, atoi will return 0. The atoi function is declared in the stdlib.h library , so be sure to #include it at the beginning of the program. The code will compile without this, since we have already included this function in the cs50.h library . However, it is better to trust native libraries. So you got k stored as an int. Now let's ask for text input. If you did the first week's assignments, you are already familiar with the CS50 library function called GetString. She will help us. After you have received k and the initial text, let's start encryption. To recap, you can iterate through all the characters of a string and print them using the following loop: for (int i = 0, n = strlen(p); i < n; i++) { printf("%c", p[i]); } In other words, just like argv is an array of strings, string is an array of characters. Therefore, we can use square brackets to access individual string elements in the same way as getting individual strings in argv. Of course, there is nothing cryptographic about printing each of the characters. Or, technically, when k = 0. But we must help Caesar encrypt his text! Hail, Caesar! To use strlen, you need to include another library . Since we are automating some validation tests, the program should behave exactly like this: username:~/workspace/pset2 $ ./caesar 13 Be sure to drink your Ovaltine! Or fher gb qevax lbhe Binygvar! Besides atoi , you can find other cool functions in the ctype.h and stdlib.h libraries . To do this, follow the link and rummage around there a little. For example, isdigit is clearly something interesting =). When going from Z to A (or from z to a), don't forget about the modulo operator %in C language. Also study the table , it shows ASCII characters not only for letters. To check that the program is working correctly with check50 , do the following: check50 2015.fall.pset2.caesar caesar.c And if you are interested in playing with the code made by the CS50 staff, run the command: ~cs50/pset2/caesar By the way, uggc://jjj.lbhghor.pbz/jngpu?i=bUt5FWLEUN0 .

Analysis of the task

1. Get the key
2. Get text
3. Encrypt
4. Display an encrypted message

1. We form the main function so that the user enters the key on the command line and checks the key for correctness. int main(int argc, string argv[]) argc: • int • number of arguments entered on the command line • if argc = 2 everything is ok. If not, print the instruction and close the program. • If argc = 2 we check if the key is an integer • Argv is an array of strings, a list with arguments entered into it Array is a data structure containing different data of the same type in different cells. For example, the user entered the string blastoff Team Rocket, then: Using the atoi() function, we convert the resulting number into an integer. If this is not possible, the function will return 0. 2. Prompt the user for text. It's simple: everything the user enters is a string. 3. Encryption. The algorithm is simple, but how can you explain to the computer which letters come one after the other? It's time to remember the ASCII table! However, there can be more than just letters in a string... Before moving on to changing strings, imagine that you only need to change one character. We want to change the letters from the initial text, not the signs or numbers. What should we do? First we need to check if this character is in the alphabet. This can be done using the isalpha() function . If the character is in the alphabet, this function returns true and false otherwise. Two more useful functions - isupper() and islower() return true if the letter is uppercase or lowercase, respectively. Thus: Isalpha(‘Z’) -> true Isalpha(‘;’) -> false Isupper(‘Z’) ->true Isupper(‘z’) -> false Islower(‘Z’) -> false Islower(‘z’)->true If isalpha returns true, we need to change this character using the key. Let's consider and analyze as an example the program of Zamili, the CS50 assistant. You might be wondering why 'A' is an integer when it is clearly a letter. It turns out that symbols and integers are interchangeable. By putting the letter A in single quotes you can get its ASCII code in int. Be careful: you need single quotes; without them, the compiler will look for a variable named A, not a symbol. Then in line we add the key value to the ASCII code of the letter and store them in an integer variable. Even if the result is an int, the printf statement uses the %c placeholder for characters. So the program prints the character associated with the integer result. In the second case, we display the number using the %d placeholder. You can enter this code into cs50 IDE and play with it. Let's check how asciimath works for different keys. Let's take the value 25, we will see the following picture: And now let the key be 26: We got [, and not the letter A at all. It is just the next ASCII character after Z. So simply adding the key will not work. We need to use a cipher formula to return to the beginning of the alphabet as soon as we run out of letters. Remember, we already wrote above: /* * asciimath.c * by Zamyla Chan * * Calculates the addition of a char and an integer, * and displays both the resultant character and its * ASCII value. * * Usage: ./asciimath key [char] * */ #include #include #include int main(int argc, string argv[]) { if (argc != 2) { printf("print the key next time \n"); return 1; } // key is the second command line argument int key = atoi(argv[1]); //преобразование строки в int int letter = 'A'; printf("\nCalculating '%c' + %d...\n", letter, key); int result = (letter + key); printf("The ASCII value of %c is %d.\n\n", result, result); return 0; } int result = (letter + key);ci = (pi + k) % 26 Where ci is letter number i in the ciphertext, pi is letter number i in the plaintext, k is the key, and %26 is the remainder of division by 26 (or “modulo 26”). Let's apply this formula to the letter Y. Take k = 2. Calculate ('Y' + 2) %26 ASCII code of the letter 'Y' = 89. Then ('Y' + 2) %26 = (89 + 2)% 26 = 91%26 = 13 But this is not the ASCII value of the letter A we need, which is 65. Now let's give each letter of the alphabet a value from 0 to 25 in order. In this case, Y = 24. (24+2)%26 = 0 The letter A has just such an index. Thus, this formula refers to the alphabetical index of letters, not their ASCII values. To print an encrypted character you will need its ASCII value. And figure out how to switch between an ASCII value and a number in the alphabet. Once we have figured out the formula for one character, we need to apply it to each letter in the string entered from the keyboard. But only if these are letters! And remember, capital letters and small letters require different meanings. This is where the isupper and islower functions come in handy. You may have two formulas, one for capital letters, the other for small letters, functions will help you choose which one to apply. How to apply a formula to every single character in a string? Remember that a string is just an array of characters. The strlen function (string length) will help you determine the number of iterations in a loop .

Task 2. Parlez-vous français?

Theory

The Vigenère cipher is somewhat safer than the Caesar cipher: it uses a word as a key and is difficult to crack manually using frequency analysis or brute force alone. Each letter of the key generates a number, and as a result we get several keys for shifting letters. Example: p = Meet me in the park at eleven am В качестве ключевого слова возьмем k = bacon Длина messages p = 25 В то время How длина k = 5 Поэтому его нужно повторять 5 раз. If the number of letters in the message is not divisible by the key, we use only part of it in the last application of the key: To find the value for the offset, we use the positions of each letter of our bacon key in the alphabet (from a to z). We count from scratch, like true programmers. And each letter in the original text is shifted by a given number, as in the Caesar cipher, returning, if necessary, after Z to the beginning of the alphabet. So M will move by 1, the first e will not move at all, and the second will move by 2 positions. Below you see the original message, the written key and the result of its application. The Vigenère cipher is, of course, stronger, but if you know the length of the key, it is quite easy to break. How to identify it? If the original text is long enough that some words appear several times in it, then you will see some repetitions: You can also use brute force, but there are many options: 26^n – 1 where n is the length of the unknown key. But usually this is a lot. True, this is not a problem for a computer. And now the mathematics of the cipher: Let p be some text, k be the keyword, kj be the j-th letter of the key, pi be the letter number i in the original text, ci be the letter number i in the encryption. Then: ci = (pi + kj) % 26

Exercise

Condition Write a program vigenere.c that encrypts a message using the Vigenere cipher. We supply one command line argument to the program input: the keyword k, consisting of letters of the English alphabet. If the application is launched with more than one argument or with an argument not included in the alphabet, it is necessary to display error information and terminate the program. That is, main will return 1 - in this case, our automatic tests will understand that everything is fine here, and this condition is taken into account. If all is well, the program should proceed to request a text string p, which we encrypt with the key k obtained above, print the result and complete the program, returning the value 0. Clarification It is necessary to make sure that in the key k the characters A and a are designated as 0, B and b as 1, ..., Z and z as 25. The program must apply the Vigenère cipher only to the letters of the text p. The remaining characters (numbers, punctuation marks, spaces) must be output without changes. If the algorithm is going to apply the jth character k to the ith character p that is not in the alphabet, apply that jth key character to the next alphabetic character in the text; you can't just leave it and move on to another character in k. Finally, the program must preserve the case of each letter in p .

Don't know where to start?

Here are some tips from Zamilya, CS50 course assistant

Fortunately, the program is very similar to the Caesar cipher, only the key is a string rather than an integer. If you have successfully implemented the Roman ruler's name cipher, it can be a great start for the second task. You've probably already realized that the Vigenère cipher with one letter as a key is the same as the Caesar cipher. The Vigenère algorithm uses the same steps as Caesar:

1. Get the key
   • codeword is the second command line argument argv[1]
   • must be in the alphabet: isalpha function
2. Get text
3. Encrypt
4. Print cipher text

So, let's check the second command line argument argv[1] to see if it belongs to alphabetic characters. We do this using the already familiar isalpha . If the key is correct, we receive a string from the user and begin encryption. The Vigenère cipher formula is similar to the Caesar cipher formula. How do you convert a letter to the corresponding cipher offset? Try comparing the values ​​using the ASCII table. Most likely, you will be able to find a pattern between the letters and their alphabetical indices using the sequences in the table. Have you figured out how to subtract one letter from another to get the desired result? The offsets for capital and small letters are the same, so you will have to define two similar formulas to determine the offset for lowercase letters and separately for uppercase letters. Also remember that the text loop should ignore non-English characters. And don't forget to preserve letter case. If you look at the cipher formula: ci = (pi + kj) % 26 you will see two index variables, i and j. One saves the position in the source text, the other in the key. If your text is longer than the key, the index on the key goes from the end of the key back to the beginning. How to do it? Using the modulo division operation! The result of the operation is the remainder of the division of two numbers. The practical benefits of this operation in programming are simply enormous! Imagine that a large group of people needs to be divided into three subgroups. One way to do this is to ask them to pay for the first, second, third. That is, the first person belongs to the first group, the second to the second, the third to the third, the fourth to the first again, and so on. You can use modulo division to perform the same operation. Let's number the same three groups from scratch. Here's how to do it: If you take an index and divide it modulo the maximum value, the resulting result will never be greater than or equal to that value. Try this principle to return a keyword to the beginning! Only instead of sorting by group you need the index of the keyword so you can the correct letter to offset without going over the key length. Since we are automating some tests of your code, the program should behave as shown below: jharvard@appliance (~/Dropbox/pset2): ./vigenere bacon Meet me at the park at eleven am Negh zf av huf pcfx bt gzrwep oz How else can you test the program besides manually computing the ciphertext? We are kind: for this we wrote the program devigenere . It takes one and only one command line argument (keyword), and its job is to take ciphertext as input and return plaintext. Run it: ~cs50/pset2/devigenere k Where k is the keyword. If you want to check the correctness of your program using check50, run: check50 2014.fall.pset2.vigenere vigenere.c And if you want to evaluate our vigenere implementation, type: ~cs50/pset2/vigenere

How to validate your code and get marks

Attention! If it is important for you to check only the correctness of tasks, then use cs50check. If you want to get grades on the edx platform, follow the procedure described below. Keep in mind, this procedure uses the same cs50check to check tasks. The only difference is that it remembers the results and calculates the overall score.

1. Login to CS50 IDE
2. Near the top left corner of the CS50 IDE , where its file browser is located (not in the terminal window), right-click on your initials.c file located in the pset2 directory and click Download . You should see that the browser has loaded initials.c .
3. Repeat for caesar.c .
4. Repeat for vigenere.c .
5. In a separate window or tab, log in to CS50 Submit
6. Click on the Submit icon in the upper left corner of the screen.
7. In the list of folders on the left, click on the Problem Set 2 directory , then click on the Upload New Submission button . It's on the right.
8. On the screen that appears, click on the Add files ... button. A window for selecting files from your computer will open.
9. Navigate to the folder where you keep initials.c . It's most likely located in your Downloads folder or wherever your browser puts files by default. When you find initials.c , click on it once to select it, then click Open.
10. Click Add files again.
11. Find caesar.c and open it.
12. Do the same for the vigenere.c file .
13. Click Start upload. Your files will be uploaded to CS50 servers .
14. On the screen that appears, you should see the No File Selected window . If you move your mouse cursor to the left, you will see a list of downloaded files. To confirm, click on each of them. If you are unsure about something, you can re-upload the files by repeating the same steps. You can do this as many times as you like until the end of 2016.