caesar - CS50 Walkthroughs 2019

Summary

The script outlines a Caesar cipher program that encrypts text by shifting letters using a provided key. It explains the process of taking command-line arguments for the key, ensuring its validity, and converting it to an integer. The program prompts for plain text, then shifts each alphabetic character by the key while preserving case and non-alphabetic characters. ASCII values and modulo operations are utilized to achieve the wrap-around effect for the alphabet. The script provides a step-by-step guide on implementing the cipher in C, including handling strings, character checks, and encryption logic.

Takeaways

• 🔑 The task is to create a program that encrypts text by shifting each letter by a specified key.
• 🖥️ The program will prompt the user for a key, receive plaintext, and then produce the corresponding ciphertext.
• 🔠 The encryption shifts letters forward in the alphabet by the key value, wrapping around if necessary (e.g., 'Z' shifted by 2 becomes 'B').
• 🔄 The program must preserve the case of each letter and leave non-alphabetic characters unchanged.
• 🧮 The key is provided as a command-line argument, which must be validated to ensure it is numeric and that only one argument is given.
• 🔍 If the user inputs invalid arguments, the program should display a usage message guiding the correct input format.
• 🔡 Alphabetic characters are identified using functions like isalpha, isupper, and islower, and are then shifted based on their ASCII values.
• 🔁 The formula to wrap around the alphabet after shifting involves using the modulo operation (mod 26) to ensure continuity.
• 📏 The program calculates the alphabetical index for each character, applies the shift, and then converts it back to the correct case.
• 🚀 The final step involves processing the entire plaintext string character by character, applying the shift, and then printing the resulting ciphertext.

Q & A

What is the main task of the Caesar program described in the script?

The main task of the Caesar program is to encipher or encrypt text by shifting all the letters in the text by a certain key amount, creating a ciphertext.

How does the Caesar cipher work with the alphabet?

The Caesar cipher works by shifting each letter in the plaintext by a fixed number of positions (the key) in the alphabet. If the shift goes beyond 'Z', it wraps around to the beginning of the alphabet.

What is the significance of preserving case when using the Caesar cipher?

Preserving case is important because it ensures that uppercase letters remain uppercase and lowercase letters remain lowercase in the ciphertext, maintaining the original style of the plaintext.

How does the script handle non-alphabetic characters in the plaintext?

Non-alphabetic characters such as spaces, numbers, or punctuation marks are not changed during the encryption process; they remain the same in the ciphertext.

What is the purpose of the command line argument in the Caesar program?

The command line argument is used to provide the key for the Caesar cipher, which determines the number of positions each letter in the plaintext will be shifted.

How can the program ensure that only a single, numeric command line argument is provided?

The program checks the number of arguments (argc) and verifies that the argument contains only digit characters. It uses functions like 'isalpha' to check for non-numeric characters.

What is the role of the 'argv' array in the main function of a C program?

The 'argv' array holds the command line arguments provided by the user when running the program. Each element of the array represents a separate argument.

How does the script explain the conversion of a string to an integer in C?

The script suggests using a function like 'atoi' (declared in stdlib.h) to convert a string containing a number into an actual integer value.

What functions are mentioned in the script to check if a character is alphabetic, uppercase, or lowercase?

The script mentions 'isalpha', 'isupper', and 'islower' as functions to check if a character is alphabetic, uppercase, or lowercase, respectively.

How can the ASCII values of characters be manipulated to implement the Caesar cipher?

By treating characters as their corresponding ASCII values, you can perform arithmetic operations to shift the characters. Using modulo 26 ensures the wrap-around effect when shifting past 'Z'.

What is the formula used to convert plaintext into ciphertext in the Caesar cipher?

The formula to convert plaintext into ciphertext is to take the ASCII value of the character, add the key, and then take the result modulo 26, which ensures the wrap-around within the alphabet.

How can you determine the length of the plaintext string in C?

The 'strlen' function can be used to determine the length of a string in C, which is useful for iterating through all characters in the plaintext for encryption.

Outlines

00:00

🔐 Introduction to Caesar Cipher

Brian introduces the Caesar Cipher, a method of encryption that involves shifting the letters of the alphabet by a fixed number, known as the key. The program's objective is to get the key from the user, prompt for plain text, shift the letters to create cipher text, and print the result. The process is demonstrated with examples, such as shifting 'A' by 2 to get 'C', and wrapping around the alphabet for letters like 'Y' and 'Z'. The importance of preserving case and leaving non-alphabetic characters unchanged is emphasized.

05:01

📝 Handling Command Line Arguments

The script explains how to access command line arguments in a C program using 'argc' for the count of arguments and 'argv' for the arguments themselves. It details the process of validating that a single numeric argument is provided, suggesting usage messages for incorrect inputs. The need to convert the string argument into an integer using a function like A2I from standard lib.h is also discussed.

10:03

🔄 Enciphering Characters and ASCII Values

This section delves into the technical aspects of enciphering individual characters. It covers the use of functions like 'isalpha', 'isupper', and 'islower' to determine character types and the ASCII values associated with each letter. The process of shifting characters while preserving case and wrapping around the alphabet is explained using a formula that involves adding the key and taking the result modulo 26. The concept of converting between ASCII and an alphabetical index is introduced to facilitate the shift and wrap-around.

🔠 Implementing the Caesar Cipher Program

Brian concludes the script by outlining the steps to implement the Caesar Cipher in a program. This includes getting the key, prompting for plaintext, enciphering each alphabetic character using the established formula, and handling non-alphabetic characters by leaving them unchanged. The use of string functions like 'get_string' for input and 'strlen' for determining string length is mentioned. The summary emphasizes the iterative process of applying the cipher to each character in the plaintext to produce the final ciphertext.

Keywords

💡Caesar Cipher

The Caesar Cipher is a type of substitution cipher where each letter in the plaintext is shifted a certain number of places down or up the alphabet. It is named after Julius Caesar, who reportedly used it to communicate with his generals. In the video, the Caesar Cipher is the central theme, with the script explaining how to implement a program that performs this encryption technique.

💡Shift

In the context of the Caesar Cipher, a 'shift' refers to the number of positions each letter in the plaintext is moved along the alphabet to create the ciphertext. The script describes how shifting letters by a key amount results in the encrypted message, with examples such as shifting 'A' by 2 to get 'C'.

💡Plaintext

Plaintext is the original message or text before encryption. The script mentions that the program will prompt the user to type in some plaintext, which will then be enciphered using the Caesar Cipher method to produce the ciphertext.

💡Ciphertext

Ciphertext is the result of encrypting the plaintext using a specific encryption algorithm. In the script, after the plaintext is shifted by the key, the output is referred to as the ciphertext, such as 'CDE' being the ciphertext for the plaintext 'ABC' with a shift key of 2.

💡Key

The 'key' in the Caesar Cipher is the number of positions each letter is shifted in the alphabet. The script explains that the program will first get the key as a command-line argument and then use this key to shift the letters of the plaintext to create the ciphertext.

💡Command Line Arguments

Command line arguments are the parameters provided to a program when it is executed from the command line. The script details how the Caesar Cipher program uses command line arguments to receive the key for the cipher, with examples of how to access these arguments using 'argc' and 'argv' in a C program.

💡ASCII

ASCII is a character encoding standard used to represent text in computers, with each character assigned a unique number. The script discusses ASCII values in the context of shifting letters while preserving the wrap-around effect of the alphabet, such as converting 'Z' to 'A' after a shift.

💡Modulo Operation

The modulo operation finds the remainder of a division between two numbers. In the script, the modulo 26 operation is used to implement the wrap-around of the alphabet in the Caesar Cipher, ensuring that shifting 'Z' by 1 results in 'A', due to 26 % 26 being 0.

💡Alphabetical Index

An alphabetical index is a mapping of letters to numbers, where 'A' is 0, 'B' is 1, and so on. The script uses the concept of an alphabetical index to explain how to convert ASCII characters to their corresponding index before applying the shift in the Caesar Cipher.

💡Preservation of Case

The script mentions that the Caesar Cipher program preserves the case of the letters in the plaintext. This means that if a letter is uppercase in the original message, it remains uppercase in the ciphertext, and the same applies to lowercase letters.

💡Non-Alphabetic Characters

The script specifies that non-alphabetic characters such as spaces, numbers, and punctuation marks do not change during the encryption process. They remain the same in both the plaintext and the ciphertext, ensuring that only alphabetic characters are shifted.

Highlights

Introduction to the Caesar cipher encryption technique involving a shift of alphabetic characters.

The program prompts the user for a key to determine the shift amount for the cipher.

User is asked to input plain text which will be encrypted using the Caesar cipher method.

Explanation of how to handle the wrap-around of letters beyond 'Z' or 'z' using modulo operation.

Demonstration of how non-alphabetic characters remain unchanged in the cipher text.

Preservation of character case (upper or lower) in the cipher text.

Use of command line arguments to input the key for the Caesar cipher.

Validation of command line arguments to ensure they contain only numeric characters.

Conversion of the command line argument string to an integer for the cipher key.

Prompting the user for plain text input to be encrypted.

Description of how to encipher a single character in the plain text.

Utilization of ASCII values for shifting alphabetic characters while preserving case.

Application of the modulo operation to achieve alphabetic wrap-around in the cipher.

Conversion of ASCII characters to an alphabetical index for cipher shifting.

Reversion from the alphabetical index back to ASCII after cipher shifting.

Iterating through each character of the plain text to apply the cipher shift.

Use of string functions like 'strlen' to determine the length of the plain text.

Final encryption of the entire plain text and printing of the resulting cipher text.

Summary of the Caesar cipher program's process from key input to cipher text output.

Transcripts

BRIAN: In Caesar, your task is going to be to encipher or encrypt

some text by shifting all of the letters in that text by a certain amount.

What your program is ultimately going to do is it's first going to get the key--

the amount that we should shift each character by.

Then we're going to prompt the user to type in some plain text.

Then we're going to encipher that plain text

by shifting all the letters by the key.

And finally, we're going to print out the resulting cipher text.

What does this look like?

Well, if the key is 2, then for any plaintext character,

we're going to shift that character by 2 letters in the alphabet.

So if we had a plain text capital A, that

would become the ciphertext capital C, because we're shifting it

by 2 letters from the alphabet.

B would become D. C would become E. So on and so forth up,

until X would become Z.

And then when we get to Y, if we were to shift Y by 2 characters,

we would go past the boundary of the alphabet.

So what we'll instead want to do is wrap around to the beginning of the alphabet

so that Y becomes A when we shift it by 2,

and Z becomes B when we shift it by 2.

What does this mean for how your program should actually work?

Well, if we were to run ./caesar and then provide, a command line argument,

the number 2--

meaning we'd want to use 2 as the key, shifting everything by 2--

and we were to type in the plain text ABC,

then your program should print out the ciphertext CDE--

the same as the plain text, but with every character shifted by 2 letters.

If we were to instead run ./caesar2 and provide the plain text of "hello,"

for example, --

then the ciphertext should be this J-G-N-N-Q,

which is each of the letters in "hello" shifted by 2 letters.

Let's take a look at one last example.

If I were to run ./caesar with a key of 2 ans input a plaintext of "This is

CS50," then the ciphertext should look like this.

And there are a couple of things to note here.

One is that we're preserving case.

If a character is an uppercase letter in the plaintext,

then it's also an uppercase letter in the ciphertext.

And likewise, a character that's a lowercase letter in the plaintext

is also a lowercase letter in the ciphertext.

And any character that's not an alphabetical character at all--

so things like spaces or numbers or punctuation marks--

those don't change.

The spaces stay spaces.

The 50 stays 50.

The exclamation point stays an exclamation point.

Only the alphabetic characters are changing.

So let's go through each of the steps of the caesar program

to figure out how you can actually write the code to do this.

The first thing you'll want your program to do is to get the key--

get the amount that we should shift each of the individual letters by.

How is your program going to do that?

Well, remember that your program is going to take the key as a command line

argument, meaning that when the user is running your program,

they're going to run your program as something like ./caesar,

followed by a number representing the key of how many characters to shift

each of the letters by.

How do you access those command line arguments?

Well, recall that in a C program your main function can take arguments.

It can take an argument called argc, which

is going to represent the argument count-- the number of command line

arguments-- and also an array of strings,

called argv, representing each of those command line arguments.

So for example, if I were to run ./caesar2 and then the number 3

as the key, argc would be 2.

I typed in two things--

./caesar2 and 3.

And argv is going to be the actual array of strings

representing those arguments.

And recall that when you have an array, you

can access an individual element of that array using square bracket notation.

So argv[0] is going to be the first string in the argv array--

which, in this case, is ./caesar2--

and argv[1] is going to be the second thing in that argv array--

which, in this case, is the string 3.

So that's how we might access the key.

Now, when we get the key, you'll want to ensure that only a single command line

argument is provided, and that that argument contains only digit

characters before you actually take that argument and convert it to an integer.

What I mean by that is that if the user runs ./caesar, and then 2 and then 8,

providing more command line arguments that's expected, your program,

rather than doing anything else, should just print out a usage message

reminding the user that in order to run the Caesar program,

they should run ./caesar2, followed by a key.

And you should do this anytime they don't use the correct number of command

line arguments.

But even if they have the correct number of command line arguments,

that argument might not be entirely numeric.

If the user runs something like ./caesar20x,

where the command line argument is not entirely numeric,

you should also display a usage message reminding the user that they need

to run ./caesar, followed by a valid key.

How do you check if the key is valid?

Well, you'll probably want to take that command line argument

and check each of the individual characters

in that string to make sure the character is a digit.

And you might want to think about what functions

might be helpful for checking if an individual character is or is not

a digit.

Once you've checked to make sure that the command line arguments are correct,

the last thing you'll need to do here is actually take the command line argument

and convert it into an integer.

Notice that argv[1] right now, representing the key,

is not the number 3, but the string "three."

Recall that in C, every variable has a type.

Some variables are ints, and other variables are strings, for example.

And here, argv[1] is the string "three," rather than the integer 3--

which we'll probably want to use in case we need to do some math with that

number, for example.

So what we'll need to do is convert the string into an into an integer.

To do this, you can use the A2I function,

declared in standard lib.h, that takes a string, like the string 3,

and converts it into the number 3, for example.

So that function might be helpful for making sure

that your key is in fact an integer.

After you've gotten the key, the next step

is to prompt the user to type in the plaintext.

To do that, you can use a call to get string,

asking the user to type in what plaintext they want to encrypt.

Once you've gotten that plaintext, the next step

is going to be to encipher that plaintext, shifting all of the letters

by the key to get the ciphertext result.

But before we talk about how to encipher the entire plaintext,

let's just talk about how to encipher one particular character.

How are we going to do that?

Well, there are a couple of cases that we might want to consider.

If the character is an alphabetic character, like an uppercase letter

or a lowercase letter, for example, then we'll

want to shift that plaintext character by the key,

making sure to preserve the case.

If it was originally an uppercase letter,

it should stay in uppercase letter, for example.

Of course, if the character is not alphabetic-- for example,

if it's a space or a punctuation mark or a digit--

then you can leave the character as is.

Nothing actually needs to change there.

But how do you know if a character is an alphabetic character

or an uppercase character or a lowercase character?

Well, it turns out, there are a number of functions that you

can use that might be helpful here.

Functions like is alpha, is upper, and is lower.

Is alpha is a function that takes a character

and returns a Boolean value, true or false,

depending on whether or not that character is alphabetic.

And likewise, is upper checks to see if the character is uppercase

and is lower checks to see if a character is lowercase.

If we call is alpha, is upper, and is lower on capital A,

for example, is alpha of capital A is true.

It is an alphabetic character.

Is upper of capital A is also true because capital A

is an uppercase letter.

And is lower of capital A is false because capital A is not

a lowercase letter.

And so that can help you to figure out, given a particular character,

is it an uppercase character or is it a lowercase character?

And every character, uppercase and lowercase, has an ASCII value.

Recall that ASCII is just a mapping from characters to numbers

that represent them, where we've decided that capital A is represented

by the number 65, capital B is represented by the number 66,

so on and so forth.

And lowercase letters have a mapping as well.

Lowercase a is represented by the number 97, lowercase b by the number

98, lowercase c by 99, so on and so forth.

And you can treat any individual character

as equivalent to the number that represents it.

So what does that mean in code?

Well, it means that if I have a character in a variable called

c that I set equal to the character A--

capital A-- and I print out that character using %c to mean I want

to substitute a character into this string, then what gets printed out,

as you might expect, is the character A. But this character A is really just

the number 65 inside of my computer, and I can treat this character like

the number 65.

And like any number, I can do math with it, adding or subtracting

numbers from it, for example.

So I can take capital A and add 1 to it, for example.

Capital A is represented by 65.

65 plus 1 is 66.

So if I print out the character corresponding

to the number 66, what's ultimately going to be printed out

is the character B because B in ASCII is represented by the number 66.

But what happens if I try to take a character like the character capital Z

and shift that by one?

If I take the ASCII value corresponding to the letter Z and add 1 to it,

I don't get the ASCII value corresponding

to capital A. I get something that's outside of the range of all

of the capital letters.

What I'd really like to happen here is that once I

try to shift past the letter Z, I want to wrap around back

to the beginning of the alphabet, back to the letter A. But how do I do that?

Well, to do this, we can take advantage of a formula.

And here's the formula that we're going to use to convert

the plaintext into the ciphertext.

It looks a little bit complicated, but we'll break it down piece by piece.

c sub i here represents the ith character of the ciphertext.

How do we determine what the ith character of the ciphertext is?

Well, we're going to start by taking the ith character of the plaintext

and we're going to add k to it, where k is the key.

And we're going to take that whole result and take it modulo 26.

This %26 means we're going to take the remainder when we take this whole value

and divide it by 26.

Why does this work?

Well, for sake of example, let's say that a is represented by the number 0,

b is represented by the number 1, c is represented by 2, so on and so forth,

up until z, represented by the number 25.

So how might I go about taking the character z

and shifting it by 1, using this formula?

Well, here is the formula.

And the plaintext character I want to shift

is the character z, which is here represented by the number 25.

And I want to shift it by the key k, which in this case is 1.

So I have 25 plus 1, which is the number 26, and 26--

mod 26-- is what's the remainder when I divide 26 by 26?

Well, the remainder is just 0, so I'm left with 0, which

corresponds to a in the above chart.

The result is that I'm able to take a character,

shift it by a certain amount.

And by using modulo 26, I'm able to get the remainder when I divide it

by 26, which allows me to loop back around

effectively to the beginning of the alphabet so that z wraps around to a.

And this mapping of a to 0, b to 1, c to 2, et cetera,

you can call an alphabetical index.

Where I might say that a's alphabetical index is 0,

b's alphabetical index is 1, c's alphabetical index is 2, and so forth.

But of course, in our computer, we don't use the alphabetical index

to represent each character.

We use ASCII, where A is 65 and B is 66 and C is 67,

and so we can't directly apply this formula.

So what do we need to do in order to take an ASCII character

and shift it by a certain amount, while still preserving

this wrap-around effect of going from the end of the alphabet back

to the beginning?

Well, here's what we might try to do.

We might first convert an ASCII character to its alphabetical index

so that capital A becomes the number 0, for example,

and capital B becomes the number 1.

And you might want to think about what math you could do to make that work.

Once you have an alphabetical index, you can shift that alphabetical index

using the formula, adding the key and taking the result mod

26 to get the new character's alphabetical index.

And finally, you can take the resulting alphabetical index

and convert that back into ASCII, so that 0

becomes A, 1 becomes B, so on and so forth,

being sure to preserve the case--

uppercase letters should remain uppercase,

lowercase letters should remain lowercase.

And that will allow you to encipher one alphabetic character.

If it's alphabetic, you'll want to shift it to its alphabetic index,

then shift it using the formula, then convert the result back to ASCII.

But how, then, instead of enciphering just a single character,

do you encipher all of the characters that are in the plaintext?

Well, recall that the plaintext is really just a string.

And when you have a string, you can access individual characters by using

array-like notation, where I can say text[0] will get me the first character

of the string text, which in this case is capital T. Likewise,

text[1] is lowercase h, text[2] is lowercase i, so on and so forth.

And I can use this notation to access any

of the characters inside of the string.

How do I know how many characters are in the string?

Well, there's another function called strlen, short for string length,

that will take a string and tell you how many characters are in it.

In this case, 12.

So by combining this, knowing the length of the string,

knowing how to access an individual character in the string,

and knowing how to encipher an individual character in the string,

you should be able to implement this Caesar program by first figuring out

what the key is, then getting the plaintext,

then enciphering that plaintext by shifting all the alphabetic characters,

and printing the result. My name is Brian and this was Caesar.