Linxz' Blog

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

Home Blog OSCP Journey
18 May 2019

Modular Inverse

Tags: crypto

Introduction

I wasn’t happy with the very brief introduction we did to modular inverse and so I decided that I wanted to create an individual post on the matter, how it works, why we have it and so on. I think this post will be greatly beneficial to anyone who read the last two posts and was slightly confused so I’m aiming to clear all of that confusion up here.

What is Modular Inverse?

In modular based arithmetic we do not actually have a division operation instead it is thought of as multiplicative inverse instead. You’re probably asking yourself why and I will explain that now, there is a little bit of number theory here so non math geeks bare with me and I’ll do my best to explain it simply.

Why can’t we use the division operator?

As we’ve covered already in our Modulo post, performing arithmetic with moduli is actually pretty easy for addition, subtraction and multiplication, all we really do is calculate like normal arithmetic and then reduce the result to the smallest positive remainder by dividing the modulus, an example would be the following:

We covered that quite a lot so I won’t break it down again, if you don’t get this please see my A Not-So-Master Class in Modulo post for further detail. We can often simplify the calculations because for any integer $ a_1, b_1, a_2 \; \text{&} \; b_2 \; \text{if we know that} \; a_1 \equiv b_1 \bmod m \; \text{and} \; a_2 \equiv b_2 \bmod m $ then the following always holds:

However, this is not always this simple for division because division is not defined for every number meaning it’s not always possible to perform division in modular arithmetic. Take the number 0 for example, like in normal arithmetic division by zero is not defined so 0 cannot be the divisor. The problem is that the multiples of the modulus are congruent to 0. As an example $ {-12, -6, 6, 12} $ are all congruent to 0 with a modulus of 6. So not only is $4 \mid 0$ not allowed but neither would $4 \mid 12$ be allowed with a modulus of 6.

We also know that division is defined through multiplication but we run into problems trying to extend this into modular arithmetic. Let’s say we’re working with $\bmod 6$ and we want to compute $4 \mid 5$ what we need to find here is $x$ such that $5 \cdot x \equiv 4 \bmod 6$ well, the only thing that would satisfy this is 2. That’s because we only can go as high as 5 since our modulus is 6 thus the equation is $4 \mid 5 \equiv 2 \bmod 6$ what if we wanted to compute $4 \mid 2 \equiv x \bmod 6$ on it’s face value it seems quite easy we can just do $2 \cdot 2 \equiv 4 \bmod 6$ but, there is actually another possibility we can do $2 \cdot 5 \equiv 4 \bmod 6$ so look, division is not uniquely defined because we have two numbers that we can multiply by 2 to give 4 and again in this case division would not be allowed.

So when is division defined?

It’s quite simple - when the multiplicative inverse exists! As we covered before the inverse of an integer $a$ under a modulus $m$ exists if $a$ and $m$ are coprime. If you’re unsure what this means it is when the only positive integer which divides both $a$ & $m$ is 1.

Closing Notes

As mentioned before, we will cover the Euclidean algorithm later on in the series, this allows us to decide whether two numbers are coprime for now, we will keep it there. That was quite a lot of number theory so I suggest you do further reading if you’re still confused, I did my best to explain it based off a math paper I read a while back so if you still think this was too much math for you to understand perhaps try something like Khan Academy as they do have a good course on modular arithmetic and all the little details.

I realise that my scheduled post was Cryptanalysis but with me starting the OSCP soon and being dissatisfied with my lack of explanation of multiplicative inverse I thought I’d make this post instead and then come back to the cryptanalysis stuff when I have more time. Especially because the cryptanalysis stuff is going to be a lot of writing, a lot of detail and will have code samples so it’s quite some work and I want to ensure the posts I make are the best they can be (hence me back tracking a little into modular arithmetic) anyway, as always thanks for reading and I’ll see you in the next post!