An Intro to Modulus Arithmetic

So I decided to take a break from Simon Singh’s book which I mentioned in my last two posts to take a look at some practical applications of modern cryptography in Cristof Paar and Jan Pelzl’s Understanding Cryptography: A Textbook for Students and Practitioners. The book is surprisingly informative and so far easy to read, even though it deals with a set of mathematics and code that I haven’t worked with.

The book starts of general enough, with a condensed introduction to cryptography and cryptanalysis. The authors give a brief overview the state of modern cryptography and the avenues an interested party can take to crack the codes being utilized today. One that I had briefly heard of before and would be interested in researching more about later is a side channel attack, where an attacker uses the system’s physical properties to circumvent the encryption by gleaming a little about the process. This can include anything from tapping the actual processor to read the electrical currents flowing through, to analyzing the sounds a keyboard makes when a user types in their keyphrase. Interesting as this is, it isn’t what I wanted to post about today, modulus arithmetic is.

Modulus arithmetic is more commonly known as remainder arithmetic or “clock arithmetic.” In code, the modulus operator is signified by the “%” symbol and when applied to two numbers X and Y will simply give the remainder of the two when X is divided by Y.

As Paar and Pelzl explain, even in early¬†caesar¬†cipher’s, all cipher text is created out of a finite set of objects. Modulus math can be used to tell us where in the set of numbers a digit/character lays after being ciphered and deciphered. What’s more, modulus arithmetic has certain fascinating properties, such as equivalency sets.

Now equivalency sets took me a while to understand completely since the concept was a bit foreign to me. Take for example 12 % 9… for the most part the answer we see and use is 3. But according to modulus arithmetic, there is an equivalency set made up of all other numbers that would also have the same remainder, that is {…, -6, 3, 12, 21, … }. This equivalency allows us to do some math with the other numbers in the set which can be very useful as we get more involved in public key cryptography.

More to come soon!