Discrete Math - Day 35

Today we expanded the idea of a cipher function to be a linear function. When a cipher function has the form C(x) = mx + b (mod 26), the cipher function is called an affine cipher.

In order to use an affine cipher, values must take values modulo 26. I explained to students that the process of modular arithmetic makes things easier. The best part is that since the class used remainders while working through the Euclidean algorithm, they were already familiar with the idea of using remainders.

The process of applying an affine cipher involves these steps:

1. Encode your message using a=>0, b=>1,..., y=>24, z=>25
2. Apply your cipher function C(x) = mx + b
3. Find C(x) mod 26 by dividing C(x) by 26 and finding the remainder
4. The remainder becomes your digital ciphertext
5. Convert your digital ciphertext to ciphertext by converting the remainder to the corresponding letter

For example, let's use C(x) = 3x + 7 and the plaintext "Hello." 

The digital plaintext for hello is 07 04 11 11 14. Applying the cipher to each of these values produces the values 28 19 40 40 49. Taking each of these values mod 26 yields digital cipher text of 02 19 14 14 23. Decoding this to ciphertext produces "ctoox."

Students were asked to pick values for the slope and intercept of a linear equation that they could use as a cipher function. I instructed them to use smaller values since this exercise was to help them get a better sense of how the process works and what the results are when ciphering a message using an affine cipher.

While there were a few questions, most students picked up on the idea and were able to cipher the message "Hello World." For the most part, students started the process and wanted to verify that they were proceeding ahead properly. The other questions arose when they had to determine the result modulo 26. Once they understood they were finding the remainder after division by 26 they were able to proceed on.

The next step in the process was for students to swap cipher messages and to see if they could determine what values were used by their classmate to create their affine cipher. Before doing this, I briefly touched on the idea of how to find an inverse to a linear equation.

If C(x) is our cipher function and D(x) is our decipher function, we must have D(C(x)) = C(D(x)) = x, that is, C(x) and D(x) are inverse functions. Since C(x) is an affine cipher, C(x) = mx + b for some integer values m and b. Therefore C(D(x)) = mD(x) + b = x, which means that D(x) = (x-b)/m.

Students attempted to break the code of their classmates knowing that the plaintext message was "Hello World." They struggled with breaking the code since we are not dealing with a simple inverse but an inverse modulo 26. This makes find the inverse values much more difficult.

We discussed the issues with ciphering and deciphering. Students had no issues with ciphering but found the deciphering piece impossible. I pointed out the complexities of finding the inverse modulo 26 made this task difficult.

Students need to understand how modular arithmetic works and different properties and characteristics they can use when working with values modulo 26 or modulo any other integer value.

This will be the next area of investigation for the class.

Visit the class summary for a student's perspective and to view the lesson slides.