File to Submit

Cipher.java

CipherEC.java (Extra Credit, optional)

 

Goal

In this assignment, we will practice implementing subroutines as methods for reusability and readability. We'll implement static methods with a variety of different return types and parameters and see method name overloading in practice.

Some Background

During quarantine, you and your friends have become a bit more privacy-conscious and decide that you want to send each other messages using a secret code to keep your conversations safe from prying eyes (or at least make it slightly harder for people to snoop on you). The friend group has decided that the logical way to do this is using some classical ciphers! In this assignment, we'll implement some methods to facilitate sending and receiving messages.

When sending our messages, we want to convert our plaintext (plain English) messages to ciphertext messages by encrypting (encoding) them with our key. When receiving encrypted ciphertext messages, we want to convert them back to plaintext by decrypting (decoding) them using

the same key*. The point of this encryption is to be able to recover the original plaintext, so using the original key will guarantee that we recover the original plaintext, but using any other key will not allow us to recover the message. The key is essentially our password - we only want people who know this password to be able to access our original message.

*Note: For these classical ciphers, we will use the same key for encryption and decryption. This is called symmetric encryption. Algorithms exist (and are widely used) where the keys used for encryption and decryption are not the same key (usually a public and a private key); the two keys are different but are mathematically linked in a way that generating the keys is easy but recovering a private key, while knowing only the public key, is very difficult. This is called asymmetric encryption. Asymmetric encryption is not relevant to this PA, but if you are interested in this or cryptography in general, you can take classes such as CSE 107 or Math 187.

Some General Notes

Make sure to read the autograder output after you submit to Gradescope. We cannot be lenient regarding information that you can see by reading that output.

Match the method signatures that we provide exactly, otherwise we cannot ensure that the autograder will function correctly.

Do not use any static or instance variables. We cannot ensure that these do not get clobbered during grading. Any variables used should be local only (private static final constants are fine).

Do not import anything.

Do not specify a package for your files. This will cause them to fail to compile.

Do not add any extra classes to your files and do not write code in files that are not specified.

The extra credit file is not required and will not affect your points in the non-EC portions of this assignment. If you choose to implement the EC, you may only use methods from the non-EC portion as they are specified in the writeup (do not use extra methods or classes that are

not specified otherwise your file will not compile - if you need them, rewrite them in the EC file). More details about this are in Part 4.

For the surveys and AI form, make sure you are filling them out and specifying your email address as the one linked with your Gradescope account. If you fill them out after submitting, you can either resubmit to update your score immediately or wait for us to rerun the autograder for everyone after the deadline.

Any late submission will trigger a slip day usage for this assignment. There will be no more exceptions for "accidents," since we cannot determine if it is an actual accident.

 

 

Part 1: Validity Checking

TODO: Methods to Implement for Checking Validity of Inputs

Implement the following methods in the Cipher class of Cipher.java.

 

We want to write some methods to facilitate validity checking for inputs. Invalid inputs can very easily break our programs, so by limiting the

domain of our functions, we can better reason about the correctness and robustness of our programs. Generally, defensive programming calls for this input validation at the beginning of each method, and many methods in the same program will perform some similar checks, which we can

pull out as separate methods.

 

Here, we've pulled out two separate, but very similar, functions that will help us perform validity checking. Both functions have the same name, but this is allowed and is called "method overloading" (see Zybooks chapter 7.5 if you haven't already) because although they have the same name,

their parameters are different (one takes a char and one takes a String) because they are checking this property for different data types.

 

public static boolean isLowerCase(char letter)

 

Check if the input char is a valid lowercase letter. Return true for valid and false for invalid.

Valid lowercase letters are chars from 'a' to 'z', inclusive on both ends (i.e., a char is valid here if it has an ASCII value in the range [97, 122]).

 

public static boolean isLowerCase(String str)

 

Check if the input String is a valid lowercase String. Return true for valid and false for invalid.

Valid lowercase Strings are those that are not null and do not contain any invalid chars as defined by isLowerCase(char letter). Note that this means that the empty string ("") is valid.

 

 

Part 2: Caesar Shifting

Caesar Shift (or Caesar Cipher) is a classical monoalphabetic substitution cipher. As the name "substitution cipher" suggests, it works by

substituting each letter in the plaintext with a different letter for the ciphertext. These substitutions are permutations (a bijective mapping of the set of letters into itself), meaning that each letter is mapped to a single letter and each letter is mapped to by a single letter.

Caesar Shifts are special substitution ciphers because the order of the letters stays the same, the permutation is just a rotation of the alphabet (which means there are only 26 different possible shifts). Here, a rotation means that we start with a list of the 26 letters in alphabetical order from 'a'-'z', with 'a' on the far left and 'z' on the far right, and every time we rotate (right) by one, we remove the right-most letter and insert it at the far left. Rotating left is the same, but removing from the far left and inserting at the far right.

Caesar Cipher encryption is typically referenced in the context of transforming an entire String, but for our purposes, we will only encrypt a single letter so that we can use these methods to implement a slightly more secure encryption algorithm in the next part of the assignment.

 

There are many equivalent formulations that can be used to reason about Caesar Shifts. We'll present three below, but you are free to implement it however makes the most sense to you.

 

Caesar Shift Formulation 1

To use a Caesar Shift, we have two parallel lists, both starting from 'a' at the far left to 'z' at the far right. The first list represents the letter in

plaintext and the second list represents the letter in ciphertext. The key for this cipher represents which letter in the second list lines up with the 'a' in the first list. All other letters will line up according to whatever rotations are needed to line up 'a' with the key.

The above graphic shows the mapping when the key is 'x'. Follow the arrows to encrypt and reverse the arrows to decrypt. Thus, when the key is 'x', 'e' will encrypt to 'b' and 'c' will decrypt to 'f'.

 

Caesar Shift Formulation 2

Each letter of the alphabet can be mapped to an integer, as shown below. This mapping follows the alphabetical ordering, mapping 'a' to 0 and 'z' to 25.

 

Letter

a b c d e f g h i j k l m n o p q r s t u v w x y z

Integer value

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

 

 

We can therefore reason about letters as if we are reasoning about integers. Thus, encrypting using a Caesar Shift is equivalent to addition (of the plaintext and the key) modulo 26. Decrypting is equivalent to subtraction (of the key from the plaintext) modulo 26. In Java, we can use the % operator to do the mod operation, but note that for Java, the result of an expression a%b is not necessarily non-negative (it will depend on the sign of the operand), so it is not exactly the modulo from math (which requires the remainder to be non-negative).

 

Caesar Shift Formulation 3

Similar to the first formulation, we can think of a Caesar Shift as two lists, initially with both lined up with 'a' matching to 'a'. We can think of the first list as the one we look for the input (either plainttext or ciphertext, depending on if we're encrypting or decrypting) in. We can then think of

the second list as what our input maps to. Then, like in the second formulation, we can think of each key as mapping to an integer. For encrypting, we will rotate the second list to the right by the key amount. For decrypting, we will rotate the second list to the left by the key amount. Then, for either operation, simply look for the input in the first list and get the appropriate element in the second list.

Note that this formulation is essentially the same idea as the first formulation, except that instead of querying our input in one of the two lists

depending on the method and rotating the second list every time, this formulation queries all inputs from the first list and rotates the second list in a different direction depending on the method (and note that rotating the second list in one direction is the same as rotating the first list in the other direction).

 

TODO: Methods to Implement for Caesar Shift

Implement the following methods in the Cipher class of Cipher.java.

 

For this portion of the assignment, we will implement methods to encrypt (encode) and to decrypt (decode) a (single-char) message. Note, possibly for your own testing purposes, that caesarShiftEncode(caesarShiftDecode(ciphertext, key), key)==ciphertext and

caesarShiftDecode(caesarShiftEncode(plaintext, key), key)==plaintext. We'll also note that Caesar Shift, as we have defined it, can only work for letters. For simplicity, we'll define it as being only for lowercase letters - for chars that are not lowercase letters, we will not attempt to make any substitution in either direction.

 

public static char caesarShiftEncode(char plaintext, char key)

 

Return the result of encoding the input plaintext with the key key using the Caesar Shift algorithm described above.

If either of plaintext or key is invalid (i.e., not lower case as defined in Part 1), return whatever is the value of plaintext without applying the Caesar Shift.

 

public static char caesarShiftDecode(char ciphertext, char key)

 

Return the result of decoding the input ciphertext with the key key using the Caesar Shift algorithm described above.

If either of ciphertext or key is invalid (i.e., not lower case as defined in Part 1), return whatever is the value of ciphertext without applying the Caesar Shift.

 

 

Part 3: Vigenère Cipher

The Vigenère Cipher is another classical cipher which (slightly) improves on the idea for the Caesar Shift. Obviously, the Caesar Shift is incredibly weak, since there are only 26 possible keys - an adversary could simply try every possible key. Vigenère Cipher improves on this by expanding the keyspace. Instead of having a single char as the key, Vigenère Cipher uses an entire String as the key.

Earlier, we noted that the Caesar Shift would typically be in the context of encoding/decoding an entire String - doing so would just be putting the method we implemented inside of a loop. However, this obviously does not solve the issue, it exacerbates the problem because attackers can easily look for whole words. However, what if the letters of the message String were not encoded with the same Caesar Shift key? That's the approach that the Vigenère Cipher takes.

The key of the Vigenère Cipher is essentially a list of Caesar Shift keys that we will use sequentially. If the key is a String of 3 letters, we will keep looping through these 3 letters until we have encoded the entire message.

In the following examples, the plaintext "paulcao" and key "cse" leads to the ciphertext "rsynueq" (we've included the integer mappings if you prefer that formulation).

 

Observe that the key "cse" is repeated until we have a Caesar Shift key for each letter. You are encouraged to use your caesarShiftEncode() and caesarShiftDecode() methods as subroutines for this portion. This of course requires that caesarShiftEncode() and caesarShiftDecode() are correct - we'll make the results for all the autograder tests for those two methods visible on Gradescope, but it is up to you to ensure that your methods are functionally correct in all cases.

 

TODO: Methods to Implement for Vigenère Cipher

Implement the following methods in the Cipher class of Cipher.java.

 

Again, note that that ciphertext.equals(vigenereEncode(vigenereDecode(ciphertext, key), key)) and

plaintext.equals(vigenereDecode(vigenereEncode(plaintext, key), key)) will be true (unless plaintext, ciphertext, or key is invalid). We'll use a simple rule to determine what messages/keys are allowed: if either the message (plaintext or ciphertext) or the key is null or not lowercase as defined by the isLowerCase(String) method from Part 1, we will not attempt to encrypt or decrypt the message (note that in

general, we would literally follow the Caesar Shift rules so that we could encode messages like "cse 11" to be something like "eug 11" when the key is "c", but for our assignment we will just say that "cse 11" can never be encoded or decoded by our methods). Also note that a key consisting of 0 chars will not work.

 

public static String vigenereEncode(String plaintext, String key)

 

Return the result of encoding the input plaintext with the key key using the Vigenère Cipher algorithm described above.

Return null if at least one input is invalid. A valid plaintext or key may only contain lowercase letters. Note that key cannot be an empty

String but plaintext can be (leading to a ciphertext of "" if the key is valid). Further note that neither of the arguments can be null.

 

public static String vigenereDecode(String ciphertext, String key)

 

Return the result of decoding the input ciphertext with the key key using the Vigenère Cipher algorithm described above.

Return null if at least one input is invalid. A valid ciphertext or key may only contain lowercase letters. Note that key cannot be an empty

String but ciphertext can be (leading to a plaintext of ""if the key is valid). Further note that neither of the arguments can be null.

 

 

Part 4: Vernam Cipher (Extra Credit, 5 pts)

The Vigenère Cipher seems great, we've solved the issue of the attacker being able to try all possible keys, but is it secure? Turns out, it's not secure. The problem with the Vigenère Cipher is that there is periodicity - after a certain point, the key repeats itself. This means that if x is the length of the key, every x letters of the message uses the same key, which leaves openings for attack. It's actually quite easy, when the key is

reasonably short, to simply check every possible period (length of the key) and look at letter distributions to determine the most likely key, but we won't go into that.

You might catch on that the solution is to simply have a very long key - the longer the better. In fact, if the key is at least as long as the message is, there's no repetition (unless the key is not random, as in the Vigenère Cipher). This is exactly the solution! However, this was a time of war and the internet did not exist, it was simply too difficult to share very long keys (the key had to be punched on a tape and given to people who needed to decrypt these messages).

Gilbert Vernam, an engineer at Bell Labs, thought of a clever solution using some elementary properties of numbers. By simply having two short keys, we can combine them in a deterministic way to create a long key. This simple way is to simply repeat each key, like how we did for the Vigenère Cipher, and then use the Vigenère Cipher with one repeated key as the message and the other as the key, giving back the long key. This makes more sense if you think about the shifts as addition and the letters as numbers, we're simply repeating the two vectors of numbers and then adding them up. The key mathematical property is that the repetition of which elements are added up to form elements of the long key begins only after the LCM of the two short key lengths - these two short keys of length a and b produce a long key of length LCM(a,b). If a and b are coprime (they share no common prime factors), then LCM(a,b)=a*b. Thus, with two relatively short pieces of tape, they could simulate one really long piece of tape. After computing the long key, we can then encrypt and decrypt using the Vigenère Cipher algorithm with the long key as the key (note that it is equivalent to simply do the Vigenère algorithm with the first short key as the key, then use the result of this as the message for a second iteration of the Vigenère algorithm with the second short key as the key - this is easy to see using the mathematical formulation).

Below is an example of the computation of the long key.

With key1 "cse" and key2 "sd", we can compute that the long key should have length 6 (LCM(3,2)=6). We repeat each of the short keys to reach this length and then we use the Vigenère Cipher to compute the long key of "uvwfkh".

Below is an example of encryption with the long key.

With key1 "cse" and key2 "sd", we computed the long key "uvwfkh" and used the Vigenère Cipher algorithm.

 

Joseph Mauborgne later proved that this algorithm was not secure (the long key's letters aren't independent), but this cipher was the precursor to the one-time pad, which was later proven to provide perfect secrecy, meaning no information about the plaintext or key is revealed by the ciphertext. The one-time pad is simply a single-use random string of bits (as long as the message) that is used as the key.

 

TODO: Methods to Implement for Vernam Cipher

Implement the following methods in the CipherEC class of CipherEC.java.

 

Again, note that that ciphertext.equals(vernamEncode(vernamDecode(ciphertext, key), key)) and

plaintext.equals(vernamDecode(vernamEncode(plaintext, key), key)) will be true (unless plaintext, ciphertext, or key is invalid). For validity of inputs, we'll follow the same rules as in Part 3.

You might want to use methods you previously wrote in the Cipher class as subroutines. Since those were static methods, they belong to the class, so you can call a method method1() by writing Cipher.method1()*.

* For autograding the methods in this class, we will be using our own implementations of the methods in the Cipher class (but we will only have the methods defined in this writeup, not any extra methods you add), so you can call them and assume them to be correct even if your own implementation is incorrect. However, you should ensure that your own implementations are correct to earn points for those sections. Note that

this means that if you wrote a method called helper() in Cipher, you will not be able to use it in your CipherEC methods - although Gradescope will say that your CipherEC.java file compiles, it will not actually compile with our grader file. Thus, in this case, you should rewrite the method in your CipherEC class.

 

public static int findLCM(int aVal, int bVal)

Return the LCM of aVal and bVal. We will assume that both aVal and bVal are positive integers and that their LCM is not bigger than the maximum int value.

You are free to directly use the code from Zybooks chapter 6.4 (and this is encouraged). Note, there will be no autograder tests for this method, but you will need to have it.

 

public static String computeVernamLongKey(String key1, String key2)

Return the long key computed from the two short keys key1 and key2 based on the algorithm described above.

If either of these short keys is invalid, i.e., either null, not all lowercase as defined in Part 1, or has length 0, return null.

 

public static String vernamEncode(String plaintext, String key1, String key2)

Return the result of encoding the input plaintext with the two short keys key1 and key2 using the Vernam Cipher algorithm described above.

Return null if at least one input is invalid. A valid plaintext may only contain lowercase letters and must be non-null. Valid key1 and

key2 values are non-null, have length greater than 0, and are all lowercase as defined in Part 1. Note that a plaintext of "" is valid (and leads to a ciphertext of "" if the keys are valid).

 

public static String vernamDecode(String ciphertext, String key1, String key2)

 

Return the result of decoding the input ciphertext with the two short keys key1 and key2 using the Vernam Cipher algorithm described above.

Return null if at least one input is invalid. A valid ciphertext may only contain lowercase letters and must be non-null. Valid key1 and

key2 values are non-null, have length greater than 0, and are all lowercase as defined in Part 1. Note that a ciphertext of "" is valid (and leads to a plaintext of "" if the keys are valid).

This assignment has been answered 5 times in private sessions.