Linxz' Blog

Still trying to think of something witty, I will let you know once I get something...

Home Blog OSCP Journey
30 January 2019

A Not-So-Master Class in Modulo

Tags: crypto

Disclaimer

I am not a Cryptographer, I am not a Cryptography student, Cryptology is not my discipline. Please note that there is no guarantee that everything in this series of blog posts is/will be correct, I cannot be held accountable for you implementing a poor crypto system because you decided to do no further reading than my posts. Crypto is a very hard discipline, it takes years & years to get it right. Just keep this in mind when reading my posts, thanks! With that said, I will do my absolute best to ensure that every post is 100% accurate!

Introduction

In Cryptography, modulo is pretty much everywhere, it is an incredibly powerful mathematical function yet all it does is compute the remainder after the division of one number by another - so how does it work? And, why do we use it? Today we’re going to answer these questions so that you understand how modulo works before we dive into cryptosystems that take advantage of modulo which by the way, is quite a lot.

Modular Arithmetic Introduction

So, let us first look at modular arithmetic or “Modular Computation” (Arithmetic is a fancy word for computation). In Cryptography our goal is to work in Finite sets, not always but most of the time we aim to do computation in Finite sets. You may be wondering, what is a Finite set? Well, to answer that question we can give a very, very simple example - a clock is a finite set which is why you will often see modular arithmetic visualised in a clock as using a clock or even just a circle makes it very simple to visualise a finite set!

Now that we have established we can visualise this in a clock, let’s do a very simple visualisation exercise of some modular arithmetic using some small numbers and a circle/clock face.

Clock

As you can see above, there is our clock, now let me show you why it is nice to visualise modular arithmetic in a clock/circle like this. So, if I asked you to do 12+20 in normal mathematics you would tell me the answer is 32 and you’d be correct, but let’s imagine if we did 12+20 on the clock, well, there is no 32 hour in a 12/24 hour clock - so how would we do this? Well, we would start at 12 and we’d go round the clock by 20 hours the hour we land on would be the new time in our case the new time would be 8 o’clock.

Clock +20

You see how simple that is? Let’s take a look at the actual calculation for this so we can say - how many times does 24 go into 32? It goes once with a remainder of 8 which would leave us with the below. Another way of doing this would be 32-24 = 8 which would also give us the below result. You could also do this with other numbers if you wanted to play around with it a little more however we will not look at any more examples here as this is very basic grade 4 maths.

Note: the ≡ symbol is the “equivalence” symbol it is not an equals sign. It means “identical or equivalent to”.

Modulo Function Formal Definition

Now that we’ve covered a very basic introduction to the modulo function using a modular arithmetic example lets look at a formal definition of this function in a little bit more detail. Now I realise the below looks a little bit confusing so we shall break it down a little bit more for you so that you can understand simply what it says.

So here we are saying let a, r, and m be elements in the set Z and m has to be a positive integer i.e not negative or zero. See? That’s not so bad, is it? :D You might be thinking, “what is the Z for? And it is a great question! And basically the reason we’re using Z is because in mathematics we use the letter Z to represent a set of integers - we won’t talk about this in further detail, however you can always read up on number sets more if you’re interested. So, for example our set Z could look a little something like the below and later we will see other sets using specific numbers to give you a better idea of what a set could look like.

So, we can write this as a is congruent (equivalent to) r modulo m this is known as Congruence Modulo where m is called the “modulus” number. I don’t want to get heavy into number theory but basically if we say that two numbers a and r have the property that their difference a-r is integrally divisible by a number m then they are said to be “congruent modulo m” which we can write mathematically as.

If we wanted to write the above explanation in a mathematical notation we would write it as the below. It means exactly the same thing however it is a quick way of writing the definition of congruence modulo.

Note: the | symbol is another mathematical notation for divide, we will use this over / throughout the course of the blog series. So try to remember that in-case you get confused on what | means in future posts!

The above if statement is very important and you must, must, must remember this throughout your cryptographic life and now I’ll move into why it is important to remember this if clause and we’ll get into some nice mathematics examples/discussions! :D

Example

Now we’re going to look at a very basic example. So, here goes. Let’s say that:

Now, if you look back at the first part of our definition we said that $ a ≡ r mod m $ so we can write what we know so far as:

What we need to do is work out how many times 9 goes into 13, which as I’m sure you know is one time - which leaves us with a remainder of 4 which we can write as: $ 13 ≡ 4 mod 9 $ And now we want to check whether this fits our if statement in the definition that we wrote down earlier in order to do this check we can do $ 13-4 = 9 $ Now we need to check whether our a minus r is divisible by m which in our case is 9, so basically - is 9 divisible by 9? And of course, it is so that fits our definition perfectly.

Computing The Remainder

Now that we’ve looked at a very basic example of using this function I want to show you something which is a problem when doing this, now some of you might already know what I am about to talk about and if you do that is great - but for those that don’t, I’d pay attention because this is not something that is totally obvious and it’s very important.

Now for computation of the remainder we typically are given $ a, m ∈ Z $ meaning we compute our a and then our m and using these two numbers we need to compute our r which we can write this with the following notation below.

Note: q is the symbol for the quotient function, this is essentially just a fancy way of saying “how many times”.

So remember we need to compute how many times our m fits into r and thus we use the quotient function to denote that. Simple, right? So now we’re going to look at another example because I want to show you about this “problem” I mentioned earlier.

Example

So, how many times does 9 go into 42? Well, it goes 4 times, right? Which leaves us with a remainder of 6 because $ 4 \cdot 9 = 36 $ and then $ 36 + 6 = 42 $ pretty easy, right? Now let’s check whether this fits our definition so we’ll check this by doing.

So we do 42-6 = 36 then we check is 9 divisible by 36 which of course it is so that’s correct and it fits the definition. And now I’ll show you the “problem” we might experience. So we know that we can have a remainder of 6, but what if we can have a different remainder and it still fit our definition? In other words, what if the remainder is not unique? Spoiler: the remainder is not unique.

You might be thinking, so our $ r = 15 $ here? And yes, you’re right in this case r is equal to 15. Remember how I just told you the remainder is not unique? Yeah… It’s not. Let’s see if this calculation fits our definition shall we?

As you can see, this fits our definition to because 9 is divisible by 27 so there are many remainders that we can have as it’s not unique, and now I’m going to show you another example which is even worse!

Now we can check this by doing $ 42 – 3 $ (two minus make a positive) so we actually write

Does 9 divide 45 and yes it does again and now I expect all of you to be thinking - oh… :D As I spoiled at the start of the post, the remainder is not unique. However,this runs much deeper than what we’ve shown here with this example, i.e this is not just a coincidence and it moves us onto our next topic which is equivalence classes, what they are and what they mean for us which we will talk about in the next post.

Closing Notes

As we’ve covered quite a lot of maths today I’m going to close this post here and in the next post we will get into equivalence classes, after that we’ll start getting into historic cipher systems and you’ll finally see why I’m making such a big deal of this modulo function.

Thank you for reading! See you next time! :D