Linxz' Blog

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

Home Blog OSCP Journey
18 February 2019

Rings

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

Ah, math, math, math I know how much all of you love math! And in light of that, today we’re going to talk about Rings - you might be sat in your chair after reading my last blog posts thinking “Linxz, you’ve taught us all this math and not shown any application or why it’s important, I’m sure you’re just teasing us” and you’re entitled to think that - but I promise, after this post you’re going to see why I explained all of this math to you and then you’ll understand how we actually use the math. Trust me, last math post! (for now…)

Rings

So, Rings! What are they? What do they do? Why are we learning about this? Well, I’ll answer all these questions now just slow down and give me a chance.

You’ve probably seen the phrase “Groups, Rings & Fields” before, these are all algebraic structures that are quite important in abstract algebra, today we’re only going to cover Rings but in the future we will cover the rest of these structures in some detail as they’re quite important later on.

The most basic ring we have in math is $\mathbb{Z}$ this is a ring of integers ranging from ${0, \cdots, m-1}$. This is the ring we will focus on today, in later posts we will see other rings. A ring has three operations, add, subtract, multiply and sometimes divide (more on that later). This is different to a group as a group only has two operations.

Note: The above ring is the simplest ring that we have in math, it runs all numbers from 0 to m-1.

Ring Properties

There are a lot of important properties in regards to rings that we will now discuss, don’t worry if you don’t understand any of these, we will most likely come back to rings but for now I’ll go over the most important properties.

$\bullet$ We can add and multiply any two numbers and the result is always in the ring i.e - a ring is said to be closed. This closure of the ring is assured by the modulo operator.

$\bullet$ Addition and multiplication are associative e.g $a + (b + c) = (a + b) + c$ and $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ for all $a, b, c \in \mathbb{Z}_m$ This means that it doesn’t matter in which sequence you perform the operations.

$\bullet$ There is the neutral element 0 with respect to addition, i.e, for every element $a ∈ \mathbb{Z}_m$ it holds that $a + 0 ≡ a \, \bmod \, m$

$\bullet$ For any element a in the ring, there is always the negative element $-a$ such that $a + (-a) ≡ 0 \, \bmod \, m$ i.e, the additive inverse always exists. We use the previously mentioned neutral element to define the inverse.

$\bullet$ There is the neutral element 1 with respect to multiplication, i.e, for every element $a \in \mathbb{Z}_m$ it holds that $a \cdot 1 ≡ a \, \bmod \, m$.

$\bullet$ The multiplicative inverse exists only for some elements. Let $a \in \mathbb{Z}_m$, the inverse $a^{-1}$ is defined such that: $ a \cdot a^{-1} \equiv 1 \, \bmod \, m $

If an inverse exists for $a$ we can divide by this element since $b \vert a \equiv b \cdot a^{-1} \, \bmod \, m$

Note: We typically find the inverse using the Euclidean algorithm which we’ll cover at a later date. For now we’ll show you a much easier way using Greatest Common Divisor (GCD)

$\bullet$ An element $a \in \mathbb{Z}$ has a multiplicative inverse $a^{-1}$ if $gcd(a,m) = 1$ i.e the largest integer that divides both numbers $\text{a}$ and $\text{m}$. The fact that two numbers have a gcd of 1 is important in number theory, if $gcd(a,m) = 1$ then $\text{a}$ and $\text{m}$ are said to be relatively prime or coprime.

Let’s look at an example and check for the multiplicative inverse of $15$ in $\mathbb{Z_{26}}$ since $gcd(15, 26) = 1$ the inverse must exist! On the other hand $gcd(14, 26) = 2 \neq 1$.

The final ring property we’re going to discuss is that distributive law holds. His means that $a \cdot (b+c) = (a \cdot b) + (a \cdot c)$ for all $a, b,c \in \mathbb{Z}_m$ what this means is that we can say the ring $\mathbb{Z}_m$ is the set of integers ${0, 1, 2, \cdots, m-1}$ in which we can add, subtract, multiply and sometimes divide. The ring $\mathbb{Z}_m$ is very important to modern public-key cryptography in practice the integers involved here have a length of 150-4096 bits.

Conclusion

Don’t worry if you don’t understand much of the maths here, the main thing we will need to know about for the next few posts are coprimes, this is very important and you’re going to see why in the next post when we cover historical ciphers. However, if you’re really stuck feel free to contact me or do some extra reading on rings because it will really come up a lot in your crypto career! Or, whatever you use this for :p

Final Note

I’d like to apologise for not making a post in a while, I’ve been very, very busy and not had time to sit down and write however I should hopefully be back on track soon. I will note that I have the next two posts pretty much nearly finished so the gaps in between this post & the next one should not be too long. Once again, my apologies for the delay hopefully I can get back on track again. Shit happens though, right? :D