HW 2: xor Cipher

Submission Details

Due: 2/11

Submit via Gradescope:

2 files in total

• xor_cipher.py

• A PDF that contains your self-assessment & reflection

• Log in to Coding Rooms

• Navigate to the Assignment of HW 2: xor Cipher

• Work through each part of the homework and use Coding Rooms to develop your code. You may want to refer back to the Variable & Function Worksheet as you go!

• When you're ready to submit, download the 1 file for Gradescope.

• Review the solutions to perform a self-assessment and write your reflection.

  • You may write up your self-assessment and reflection in whatever format is most comfortable for you (written on paper, typed in a Word or Google Doc, etc.), but you must convert it to a PDF before submitting. Please ask if you need help with this!

  • Submit the PDF to Gradescope and name it SelfAssessmentReflection.pdf.

Secure communication has been a challenge since before the age of computers. There are many schemes for doing so in existence, but we will focus on ciphers in this homework. In particular, we'll use an xor cipher to encrypt the letters of a message and a subsequent Caeser cipher to make it a little more exciting.

We will also use a divide-and-conquer approach to tackle the problem and take the opportunity to practice with defining and invoking functions.

Here is an overview of how our encryption scheme works:

1. The user will enter a message that they'd like encrypted.

2. The user will enter a single key for locking the message. This key is required to unlock the message.

3. Every character (in the message plus the single key character) will be converted to a byte:

   • Take the ASCII code for the character

   • Convert it to a binary number

   • Pad it with enough 0s to make it 8 bits long

4. Use the xor cipher to lock or encrypt a single character by computing the xor of that character's byte representation and the key's byte representation.

   • Given two bytes to xor, divide both bytes in half, obtaining two pairs of nibbles.

   • Given two nibbles to xor, divide both nibbles in half, obtaining two pairs of crumbs.

   • Given two crumbs to xor, divide both crumbs in half, obtaining two pairs of bits.

   • Given a pair of bits, convert each to a boolean and use the built-in xor operator to compute the xor.

5. Use a Caesar cipher to shift each character by a particular amount.

   • Without this, we won't be able to "see" some of the characters, as the xor can result in very small Unicode values that do not represent display characters.

This may seem like a large task to undertake, but the homework will walk you through step by step. The goals are for you to:

• practice writing function definitions from pseudocode (a description that is close to code, but not exact Python code)

• practice type-hinting and using mypy to make sure types are consistent

• practice the iterative process of writing a little code, running your program and debugging

  • use function "stubs" to allow the invocation of a function that has not been correctly implemented yet

Remember that we always want to check that the development environment is properly set up!

• Log in to Coding Rooms

• Navigate to the Assignment of HW 2: xor Cipher

• Confirm that you can run the xor_cipher.py script.

• There is some starting code that you should Run, which will:

  • Prompt you to input a key in the console.

  • Type a single letter and hit return.

  • Prompt you to input a message in the console.

    • Type a message and hit return.

  • You'll see an encrypted version (just with the shift cipher) print out.

  • Prompt you to input a message in the console.

    • You can copy-paste the encrypted message and hit return.

  • You'll see the decrypted version (just with the shift cipher) print out.

For this homework, we will specify a design for you; we will tell you what functions to break the problem into and how to implement each.

• In this part, we'll specify each function's expectations for interaction and behavior at a high level.

• You will write the corresponding function declarations.

• You will also write a stub for the function body so that your code will run without errors (but with incorrect behavior)

You'll notice the script is separated into 3 general parts:

1. At the top is some code provided to you to implement the encryption approach for a message. It uses the map function to apply the xor cipher over each letter in the message, followed by the shift (Caesar) cipher over each letter. This is done for encryption and decryption (which "unshifts").

   • You do not need to modify this code.

   • You can read the comments to understand it, but you would not be expected to generate this code on your own.

2. In the middle is an area denoted by comments for where you will be working to define functions that work on applying the xor cipher on a single letter.

################## YOUR FUNCTION DEFINITIONS GO HERE #########################

# There is a little here to start you off from the walkthrough on the homework page

def xorLetter( letter : str, key : str ) -> str:

""" Given a single letter and a key (a single character also),

convert both to bytes representing the binary number of their Unicode

values, xor those bytes and convert the resulting byte back to

a character using the Unicode value represented by the binary

number. """

# You'll need to replace this "stub" with a correct implementation

return letter # as a placeholder, just return the given letter

#### KEEP YOUR FUNCTION DEFINITIONS ABOVE HERE #####

3. At the bottom is the main function and code for running the program.

   • You do not need to modify this.

   • You can read the comments to understand it, but you would not be expected to generate this code on your own.

For each of the following, write:

1. The function declaration with a docstring style comment

2. A stub body returning a placeholder value of the correct type

3. Check your types using mypy

4. Run your code in Python and make sure no bugs have snuck in!

• Be careful of indentation!

You might notice that the provided code invokes a function xorLetter, which is the primary function for the xor cipher. The specification is given below, and we have already provided the solution for you as an example.

1. Write the declaration and stub for a function called xorLetter that:

   • expects two parameters named letter of type str and key of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given a single letter and a key (a single character also), convert both to bytes representing the binary number of their Unicode values, xor those bytes and convert the resulting byte back to a character using the Unicode value represented by the binary number.

   • has a stub body that returns the passed letter as a placeholder
     
     To help you get started, the solution for this function is already in the script in lines 40 - 48.

To apply the xor cipher to a single character, we'll need some conversion functions to go between characters, bytes (represented as strings of "0" and "1" characters of length 8) and booleans (True/False). We'll stick to the convention that a 0 bit corresponds to False and a 1 to True.

1. Write the declaration and stub for a function called charToByte that:

   • expects one parameter named c of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given a single character c, convert it to a byte that is the binary number of the character's Unicode value.

   • has a stub body that returns the placeholder value "00000000"

2. Write the declaration and stub for a function called byteToChar that:

   • expects one parameter named b of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given a byte (string of length 8 of 0s and 1s), convert to the character using the Unicode value represented by the byte interpreted as a binary number.

   • has a stub body that returns the placeholder value "a"

3. Write the declaration and stub for a function called strToBool that:

   • expects one parameter named strVal of type str

   • returns a bool

   • has a docstring comment to indicate the behavior:
     Given a "0" or a "1", convert to False or True and return that boolean value.

   • has a stub body that returns the placeholder value True

4. Write the declaration and stub for a function called boolToStr that:

   • expects one parameter named boolVal of type bool

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given False or True, convert to "0" or "1" and return that string value.

   • has a stub body that returns the placeholder value "0"

The xor will ultimately applied bit by bit. Given a byte of 8 bits, we'll take this opportunity to practice a divide-and-conquer scheme. We'll continuously divide our problem in half, conquer each half and merge the solutions back together. When given a byte, we'll divide into two nibbles; given a nibble, we'll divide into two crumbs; given a crumb, we'll divide into two bits. The bits are "trivial" to solve, and we can apply the built-in boolean xor ^ operator. Each "level" of this divide-and-conquer scheme will have a function; in the next part, we'll see how invoking the subsequent level's function helps us solve the current level. For now, don't think too hard about how the divide-and-conquer scheme works; we're focused on its structure here.

Note: there are many (more efficient) ways of doing this, but we are practicing functions and this idea of divide-and-conquer!

1. Write the declaration and stub for a function called xorByte that:

   • expects two parameters named byteA of type str and byteB of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given two bytes, each a string of length 8 of 0s and 1s, compute the (bitwise) xor and return the resulting byte as a string.

   • has a stub body that returns the placeholder value "00000000"

2. Write the declaration and stub for a function called xorNibble that:

   • expects two parameters named nibbleA of type str and nibbleB of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given two nibbles, each a string of length 4 of 0s and 1s, compute the (bitwise) xor and return the resulting nibble as a string.

   • has a stub body that returns the placeholder value "0000"

3. Write the declaration and stub for a function called xorCrumb that:

   • expects two parameters named crumbA of type str and crumbB of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given two crumbs, each a string of length 2 of 0s and 1s, compute the (bitwise) xor and return the resulting crumb as a string.

   • has a stub body that returns the placeholder value "00"

4. Write the declaration and stub for a function called xorBit that:

   • expects two parameters named bitA of type str and bitB of type str

   • returns a str

   • has a docstring comment to indicate the behavior:
     Given two bits, each a string of length 1 that is either "0" or "1", compute the xor and return the resulting bit as a string.

   • has a stub body that returns the placeholder value "0"

At this point, you should have stub definitions for each of the 9 functions required to apply an xorCipher to a single letter. In this part, you'll implement each function, testing as you go to check for any bugs you've introduced.

For each function, we have given you the pseudocode for how to implement the expected behavior.

1. Replace the stub body of the function with the pseudocode (already formatted as comments).

2. For each numbered pseudocode instruction, write the line of Python code that implements it.

3. Check your types using mypy

4. Run your code in Python and make sure no bugs have snuck in!

Some notes

• You do not need to follow the order that is given here. I tend to follow what's called a "top-down" design, which is what you see here.

• No matter the order you choose, you can use the power of abstraction.

• You can invoke a function you haven't yet implemented the correct behavior for. Sometimes this is called "wishful thinking" where we assume the function is already working properly. Since we have stub definitions for our entire design, we will be able to run our code while focusing (using abstract to "zoom in") on a particular task. We know that later we will get those functions working properly.

Tips

• Be careful of indentation!

• Be as rested as possible - little mistakes, like a typo, can create bugs that are sometimes very hard to spot!

• If you get stuck, peek at the solutions, especially during the initial stages as you're getting used to the process. The solutions are separated into different files for each function so that you can focus on one at a time.

• Leave time to get help. Another pair of eyes can often spot little bugs, while talking through the task can help identify gaps in your understanding or clarify material.

  • You have peers, mentors, instructors, drop-in and office hours precisely for this reason!

# First phase: get the bytes for each representing the

# binary number of their Unicode values

# 1. invoke the function charToByte on letter to obtain the byte

# and assign it to a variable letterByte of type str

# 2. invoke the function charToByte on key to obtain the byte

# and assign it to a variable keyByte of type str

# Second phase: xor the bytes

# 3. invoke the function xorByte on the letterByte and keyByte

# to obtain the xor of the bytes

# and assign it to a variable xoredByte of type str

# Third phase: convert the byte back to a character using Unicode

# 4. invoke the function byteToChar on xoredByte to obtain

# the character whose Unicode value is represented by the byte in binary

# and assign it to a variable cipheredChar of type str

# 5. return the cipheredChar

One of the lines below is implemented for you, since we haven't discussed what a method is and how to ask a string to invoke a method.

# 1. invoke the ord function on c to obtain the Unicode value (in decimal)

# and assign it to a variable called code of type int

# 2. invoke the bin function on code to obtain it in binary

# (as a string starting with 0b)

# and assign it to a variable called binaryNumber of type str

# 3. since the binaryNumber representation starts with the two characters 0b

# slice the string to only keep the characters from index 2 to the end

# and assign the slice to the variable binaryNumber

# 4. since the binaryNumber may not have length 8,

# use the zfill method to pad it from the left with 0s

# and assign it to a variable called byte of type str

byte:str = binaryNumber.zfill(8)

# 5. return the byte

# 1. invoke the int function on the parameters b and 2

# to get the decimal number represented by the byte

# and assign it to a variable called decimalValue of type int

# 2. invoke the chr function on decimalValue

# to convert back to a character using Unicode/ASCII

# and assign it to a variable called c of type str

# 3. return the character c

# 1. invoke the int function on strVal to obtain a numeric 0 or 1

# and assign it to a variable called numVal of type int

# 2. invoke the bool function on numVal to obtain True or False

# and assign it to a variable called boolVal of type bool

# 3. return the converted boolVal

# 1. invoke the int function on boolVal to obtain a numeric 0 or 1

# and assign it to a variable called numVal of type int

# 2. invoke the str function on numVal to obtain "0" or "1"

# and assign it to a variable called strVal of type str

# 3. return the converted strVal

1. slice byteA to extract the first 4 characters/bits

# and assign the value to a variable called nibbleA0 of type str

# 2. slice byteA to extract the last 4 characters/bits

# and assign the value to a variable called nibbleA1 of type str

# 3. slice byteB to extract the first 4 characters/bits

# and assign the value to a variable called nibbleB0 of type str

# 4. slice byteB to extract the last 4 characters/bits

# and assign the value to a variable called nibbleB1 of type str

# 5. invoke the function xorNibble on nibbleA0 and nibbleB0

# to compute the xor of the first 4 bits

# and assign the value to a variable called xoredNibble0 of type str

# 6. invoke the function xorNibble on nibbleA1 and nibbleB1

# to compute the xor of the last 4 bits

# and assign the value to a variable called xoredNibble1 of type str

# 7. concatenate the two nibbles xoredNibble0 and xoredNibble1 to obtain a byte

# and assign it to a variable called xoredByte of type str

# 8. return the xoredByte

# 1. slice nibbleA to extract the first 2 characters/bits

# and assign the value to a variable called crumbA0 of type str

# 2. slice nibbleA to extract the last 2 characters/bits

# and assign the value to a variable called crumbA1 of type str

# 3. slice nibbleB to extract the first 2 characters/bits

# and assign the value to a variable called crumbB0 of type str

# 4. slice nibbleB to extract the last 2 characters/bits

# and assign the value to a variable called crumbB1 of type str

# 5. invoke the function xorCrumb on crumbA0 and crumbB0

# to compute the xor of the first 2 bits

# and assign the value to a variable called xoredCrumb0 of type str

# 6. invoke the function xorCrumb on crumbA1 and crumbB1

# to compute the xor of the last 2 bits

# and assign the value to a variable called xoredCrumb1 of type str

# 7. concatenate the two crumbs xoredCrumb0 and xoredCrumb1 to obtain a nibble

# and assign it to a variable called xoredNibble of type str

# 8. return the xoredNibble

# 1. access index 0 of crumbA to extract the first character/bit

# and assign the value to a variable called bitA0 of type str

# 2. access index 1 of crumbA to extract the last character/bit

# and assign the value to a variable called bitA1 of type str

# 3. access index 0 of crumbB to extract the first character/bit

# and assign the value to a variable called bitB0 of type str

# 4. access index 1 of crumbB to extract the last character/bit

# and assign the value to a variable called bitB1 of type str

# 5. invoke the function xorBit on bitA0 and bitB0

# to compute the xor of the first bit

# and assign the value to a variable called xoredBit0 of type str

# 6. invoke the function xorBit on bitA1 and bitB1

# to compute the xor of the last bit

# and assign the value to a variable called xoredBit1 of type str

# 7. concatenate the two bits xoredBit0 and xoredBit1 to obtain a crumb

# and assign it to a variable called xoredCrumb of type str

# 8. return the xoredCrumb

# 1. invoke the strToBool function to

# convert the string version of bitA to a bool

# and assign it to a variable called boolA of type bool

# 2. invoke the strToBool function to

# convert the string version of bitB to a bool

# and assign it to a variable called boolB of type bool

# 3. compute the xor using the ^ operator on boolA and boolB

# and assign it to a variable called AxorB of type bool

# 4. invoke the boolToStr function on AxorB to

# convert the bool False or True to the bit "0" or "1"

# and assign it to a variabled called xorBit of type str

# 5. return the resulting xorBit

Whew! You made it and hopefully have a fully functional program!!!

• You can play around now and run the program to encrypt different messages. As you do, feel free to post encrypted messages on the HW 2 forum for others to decrypt!

• Be sure to submit on Gradescope