AEP 1: Encrypting messages with binary

--- tags: mth225, 225-spr22, aep --- # AEP 1: Encrypting messages with binary ## Overview In this AEP, you will learn about a way of **encrypting** a message --- encoding it so that only the sender and the intended recipient can read it --- that uses base 2 representations of integers and a special operation on binary integers known as **XOR**. :::warning **Deadline**: This AEP should be submitted on or before **Sunday, May 29 at 11:59pm ET**. If you need an extension on this deadline, contact the professor and explain why you need the extension, and when you plan on turning in the work. ::: ## Background We keep secrets from each other all the time. Those secrets aren't necessarily incriminating or bad; for example, our credit card numbers, social security numbers, and browsing histories are all information that we'd rather not have leaked into the public eye. To keep that information secret in a digital form, we use **encryption**. Encryption refers to *any process that transforms information into a format that is readable only to the owner of that information and the people or machines who the owner decides should see it*. When encrypted information is sent, the recipient turns it back into a readable format by **decrypting** it. Both encryption and decryption use a **key**, which is a piece of information (a number, a code phrase, etc.) that, like a physical key, is used to lock and unlock the information being sent. This AEP is about a method of encryption and decryption that was very common in the early days of digital communications, and which (unfortunately, as you'll see) is still used in some places today. It involves transforming human-readable messages into binary integers, then using a binary string as a key to encrypt it, via a special operation called **XOR**. In this AEP you'll learn how to encrypt and decrypt using this **XOR cipher**, and play the role of an adversary by breaking an intercepted message encrypted using the XOR cipher. Here's a description of how the XOR cipher works. First, the cipher involves the **XOR** operation. This is an operation, denoted `xor`, that is similar to our logical operators from class. The `xor` works on single bits as follows: - `0 xor 0 = 0` - `1 xor 0 = 1` - `0 xor 1 = 1` - `1 xor 1 = 0` `Xor` is like regular binary addition except for the last line --- **we don't ever carry a 1**. Ordinary addition would say `1 + 1 = 10` but here, `1 xor 1` is just `0`. So *`xor`-ing two bits together always leads to just a single bit*. We can therefore `xor` *strings* of bits together, just by `xor`-ing the individual bits in corresponding positions. For example: - `10 xor 11 = 01` (because you `xor` the two bits in the left position and the two in the right position) - `1011 xor 1111 = 0100` - `10110001 xor 01010101 = 11100100` Now we can describe how the cipher works: 1. Start with a message, in regular text, to send. This is called the **plaintext**. For this AEP, *assume that messages only involve capital English letters --- no lower-case letters, punctuation marks, numbers or other symbols*. 2. Take each letter in the plaintext and convert it to a number between **65** representing "A", and **90** representing "Z". For example the letter "M" is assigned the number 77. 3. Then convert each of those integers to their binary representation using an 8-bit format. For example, the letter "M" was the decimal number 77 which in 8-bit binary is `01001101`. Here's a table (taken from [this website](https://www.ascii-code.com/)) that has this information already computed in it. ![](https://i.imgur.com/3Jx9qrm.png) 4. Now choose a random 8-bit binary integer to use as your key. *Share this with the person or machine you want to receive your message*. 6. (**Encryption stage**) Your plaintext message is currently a sequence of 8-bit strings. **Take each one, one at a time, and `xor` it with the key.** Do this for each "letter" in the message. *The result is the encrypted version of the message*. Send it off to your recipient. 8. (**Decryption stage**) When the recipient gets the message, they have the key you sent them (it's the same key as the one you used to encrypt). The recipient breaks the message into 8-bit blocks. Then, they take each block one at a time and `xor` the encrypted block with the same key that was used to encrypt. 9. Now take each 8-bit block, convert back to a decimal number, and then convert back into a letter (reversing the process in steps 2 and 3). If everything is done correctly, the recipient will have the original message in the end. :::info **Example** 1. Alice is sending Bob the message `RUN`. 2. She converts the message into decimals: `82 85 78`. 3. She then converts each of those into 8-bit binary: `01010010 01010101 01001110`. 4. Alice randomly selects the 8-bit string `11000011` to use as the key. (You could use [a random bit generator](https://catonmat.net/tools/generate-random-bits), or flip a coin 8 times, etc.) She shares this key with Bob. 5. To **encrypt**, Alice `xor`'s the the key with each of the blocks above: - `01010010 xor 11000011 = 10010001` - `01010101 xor 11000011 = 10010110` - `01001110 xor 11000011 = 10001101` Alice sends Bob the message: `10010001 10010110 10001101`. Notice, a person intercepting this message would just see a string of seemingly-random bits. 6. Bob receives this message. To **decrypt**, he `xor`'s each block of the message with the key that Alice shared with him: - `10010001 xor 11000011 = 01010010` - `10010110 xor 11000011 = 01010101` - `10001101 xor 11000011 = 01001110` 7. Bob converts each of the resulting blocks to base 10: `82 85 78`. 8. Then finally Bob changes each of those back into letters: `RUN`. ::: ## Tasks for this AEP 1. Make up a short (8 characters or less) message in English and a key, and encrypt the message using the `XOR` cipher. Show each step of the process (through Step 5 shown above). 2. Go to the Miro board that's been set up for this AEP, found at https://miro.com/app/board/uXjVO0Dzmu8=/?share_link_id=345627684661. There, you'll post your name and your encrypted message (in binary) on a sticky note. **Don't post your key!** 3. Find one other person who has posted their message on the board. Email them and ask them for the key. When they reply, decrypt the message that they posted. Show all your steps here in your writeup. (You're playing the role of "Bob" in this task; the other person is "Alice".) If you are the first person to post on the board, you can proceed with the rest of this assignment while you wait for someone else to post. 5. As you just experienced, when "Bob" `xor`'s the encrypted binary with the key, he should get the binary that Alice generated *before* encrypting. So, the process of taking a binary string, `xor`-ing with the key, then `xor`-ing *again* with the key, gets you back to the unencrypted binary. **Explain why this will always be the case.** Do not just use examples, because examples aren't enough to prove a statement is always true! You might look at some examples to get you started, but your explanation should be free of specific choices of keys and messages. Use only the properties of binary and the `xor` operation -- and use plenty of English (remember you are giving an *explanation*). 6. For the final task, you'll be playing the role of **Eve**, the evil eavesdropper who is spying on Alice and Bob. On the Miro board, Alice has left a rather long encrypted message for Bob, in the box shaded green. You don't know the key, because Alice was smart enough not to post it. But you suspect that the binary string `10001111` in the ciphertext was originally the letter `E` in the plaintext, since `E` is the most commonly occurring letter in the alphabet and this string `10001111` happens three times, which is more common than any of the other strings. Using this assumption, find the key to the cipher, and decrypt the message (all the way back to English); and then fully explain what you did. Then write a short paragraph that talks about why the `XOR` cipher can't really be considered as a "secure" way to encrypt data, based on this task. ## Expectations and Grading Criteria AEPs are graded using the "EMRN" rubric found in the syllabus. Make sure you review the [Standards for Assessments in MTH 225](/KoT83ezHRYO3DqPyXMMMag) document before you submit any work, so you're fully aware of the expectations for the different marks. In particular: - All work needs to be shown *and* your thought processes clearly expressed in all of the tasks of the assignment. The results also need to be correct. You are not just doing math; you are explaining things to a reader, so a mix of math and English is needed. - All the information needed for an "outsider" to understand your work needs to be self-contained within the work. For example, you need to clearly state the message and the key in Task 1. **The reader should not have to do any work to fill in gaps.** In addition to the general requirements for marks of E and M, on this assignment an E or M requires the following: - Task 4 needs to be a general explanation that explains why the decryption step *always* works. Do not just give additional examples illustrating that decryption works. - In Task 5, state clearly what the key is and what the original message was, and fully and clearly explain your thought processes so that an "outsider" could replicate your steps on a new intercepted message. The explanation needs also to use the information provided --- if you can break the code some other way, then you can provide that as separate information, but your main solution should use the fact that `E` encrypted to `10001111`. Please note, it is the case with all AEP's that **your grade is primarily based on your explanations and writing, and only secondarily on the precision and correctness of your computations.** Correct computations with insufficient explanation will need to be revised and may receive an "N" grade. A grade of "E" is given if all of the above expectations are met, and the work is of superior quality in terms of the clarity of explanations and work, appearance of the writeup, and precision of the mathematics. ## Submitting your work **AEP submissions must be typewritten and saved as either a PDF or MS Word file. No part of your submission may involve handwriting; work that is submitted that contains handwriting will be graded N and returned without feedback.** This includes electronic handwritten docments, for example using a stylus and a note-taking app. To type up your work, you can use MS Word or Google Docs (both of which have equation editors for mathematical notation) or any other computer-based math typesetting tool. Just make sure you save your work as a Word document or PDF (no `.odt`, `.rtf`, or other file extensions are allowed). When you have your work typed up, double-check it for neatness, correctness, and clarity. Then simply submit your document on Blackboard, in the **AEP** area, in the **AEP 1** assignment. ## Getting Help You **may** ask me (Talbert) for help on this assignment in the form of **specific mathematical or technical questions, or clarifying questions about the instructions**. If I cannot answer a question because it would give too much away, I'll tell you so. However please note: **I will not "look over your work" before you submit it to give you feedback on the overall submission**. I have made the expectations clear, so just follow those directions and submit your best work, and you'll be allowed to revise it if needed. For AEPs, the syllabus policy on collaboration is: >**No collaboration is allowed at all** — with other people, or with print or electronic sources other than your textbook, the video playlist, or your notes. In task 3, you are allowed to email another student to ask for their key. Otherwise, you are expected to abide by the policy above. **You can ask technology related questions to anyone at any time**. For example if you need help figuring out how to type up your work, there are no restrictions on that.