Under the Hood: Mod Cryptog

Sometimes the outtakes are the best part of a movie.

As anyone who's taught a Mathalicious lesson knows, we structure our lessons in acts (see Dan Meyer, This American Life, playwrights, etc.). The goal is to create a narrative that flows so naturally that it seems almost effortless, as though the conversation existed already and we just wrote it down. In some cases it feels like this--like we're not so much writing math lessons as conducting them (as in "conduit")--but in other cases lessons go through a lot of massaging and work behind-the-scenes.

We'll be releasing a lesson on cryptography soon in which students use modular mathematics (think "clock" arithmetic, where 17:00 = 5:00 MOD 12) to encrypt and decode secret messages.  To help give a peak under the Mathalicious hood, we hope you enjoy the following.

A huge shout-out to Professor Janet Beissinger @ the University of Illinois at Chicago for her generous explanation.  It's nice to get schooled every now and then!

-----------------------------------------------------------------

Good morning, Professors Pless and Beissinger:

I'm writing a lesson on cryptography and had a quick question for you.  I found your interaction on the UIC site and would be grateful for your help. My question has to do with how to decrypt multiplicative ciphers.

For instance, imagine someone uses the multiplicative cipher x3.  If A = 1...

  1. L = 12     x3 = 36 = 10 mod 26 = J
  2. Y = 25     x3 = 75 = 23 mod 26 = W

All good so far.  When students decrypt this:

  1. J = 10     +26 = 36          36/3 = 12 = L (correct)
  2. W = 23   +26 = 49          49/3 = 16.33 = not possible
  3. W = 23   +26(2) = 75     75/3 = 25 = Y (correct)

I assume your computer algorithm is set to something like, "If N/(int N) > 1, N + 26 --> N" (i.e. that it checks that the result is an integer and, if not, "rewinds" the wheel another 26 spaces), but I'm concerned that this may throw students for a loop given the grade-level target.  With a multiplicative cipher, is there any way around this second step?

Thanks for your help.

Karim

#############

Hello,

We find the topic of decrypting multiplicative ciphers very interesting because it brings up the notion of a multiplicative inverse in modular arithmetic. You can decrypt multiplicative ciphers with inverses. In regular arithmetic, if you multiply by 3, then you can undo that multiplication by multiplying by the inverse, which is 1/3. This is something students know or at least we want them to know in middle school.

As you point out, 1/3 does not exist when we work mod 26. But it turns out other numbers act as inverses mod 26. In the example you gave, if you multiply by 3, then multiplying by 9 and reducing mod 26 will give you back what you started with: Try Y = 25 from your example: 25 x 3 = 75 = 23 mod 26.

Now to decrypt, multiply by 9: 23 x 9 = 207 = 25 mod 26, which is what you started with.

In regular arithmetic, 3 and 1/3 are inverses because their product is 1. The same holds for modular inverses: 3 and 9 are inverses because their product is 3 x 9 = 27 = 1 mod 26.

I don't know how deeply you want to go into this in your curriculum, but in our Cryptoclub curriculum, we have middle grade students find the inverses of the numbers that have them (the numbers that are relatively prime* to 26) and then use these to decrypt.

Your method would work too, but what I like about exploring inverses is that it builds on what they are learning in their work with Real Numbers: that to undo multiplication by a number, you can multiply by the inverse of the number.

We are currently working on a new website (cryptoclub.org) which will have tutorials about this. But for now, the only thing we have published is in our book The Cryptoclub: Using Mathematics to Make and Break Secret Codes--you can find details on the old Cryptoclub website: http://cryptoclub.math.uic.edu/about/aboutbook.htm.

I am glad to hear you are putting some cryptography into your material. It is a great application of the math students learn in middle school and they find the topic of secret codes very engaging.

Good luck,
Janet

-----------------------------------------------------------------

*Relatively prime numbers (also called "co-prime") are numbers that don't share any common factors other than 1. For instance, 4 and 26 are not relatively prime to one another since they both share 2 as a factor, but 3 and 26 are.

The reason the cipher has to be relatively prime to 26 is that, if it's not, multiple letters will "map" to the same letter, making the code impossible to crack. As an example, imagine you used a cipher of x2. In this case, M would map to 26, since 13 x 2 = 26, and would be encoded as Z. At the same time, Z would become 26 x 2 = 52, or 26 mod 26. In other words, Z would also be encoded as Z. When you try to decrypt the message, then, you'll have no way of knowing whether the encoded Z should be decoded as Z or M!

By requiring that the cipher be relatively prime to 26, it ensures that letters don't "land" on the same letter when they're encoded. (Another option would be to use a prime number of characters. Instead of only using the 26 letters, you could include the punctuation symbols ?.!, leaving you with 29 characters...and everything will be relatively prime to that! To help keep the focus on inverse operations, we may end up doing this. Dunno. Thoughts?)


4 thoughts on “Under the Hood: Mod Cryptog”

Leave a Reply

Your email address will not be published. Required fields are marked *