Who knows me knows that one of the topics I am most passionate about is cryptography. For this reason it was not a matter of if but of when, I would have written an article about it. Since forever however you cannot start abruptly, and this article serves exactly this, to prepare the field. No, not the Galois one, that will come later. So in this post we will lay the foundations of modular arithmetic and Galois fields, which are the supporting pillars of all modern cryptography. Small spoiler: there will be a few numbers. Nothing unmanageable, but if you do not like mathematics, deal with it.
My Numbers Spin
As anticipated in this first paragraph we introduce a fundamental little block: modular arithmetic. I know that when you see numbers it is you who spins, but the title as we will see fits the topic. Modular arithmetic is that branch of mathematics that studies the properties and the relations between integers, through the concepts of congruence and modulus. What?! You ask when two numbers \(a\) and \(b\) are congruent modulo \(n\) ? Well when \(b\) is the remainder of the division between \(a\) and \(n\). This relation is written as follows:
Formula 1. Base Form of Congruence
Yes, written like this it looks like some abstract thing but in reality it is very simple and with a few examples it becomes clear immediately. Suppose we have \(a=5\) and \(n=3\). The division \(\frac{5}{3}\) has result \(1\) with remainder \(2\), therefore the congruence is true
So, in modular arithmetic, writing
or writing
is completely equivalent. With this logic this congruence is also true:
since \(\frac{6}{3}\) has result \(2\) with remainder \(0\).
Now, I know it is not the most fun but you can indulge yourselves by writing all the congruences you want. In fact they are just relations between numbers. And do not make the mistake of thinking they are useless, in reality you use them more often than you might imagine.
A simple example is reading the time. Every time you look at a clock, you are unknowingly working \(\pmod{24}\). When the day ends, you do not keep counting the hours beyond 24, you start again. So 25 becomes 1, 27 becomes 3, and so on until the end of your days. Each "round" of the clock is a modular operation.
Since \(b\) is a remainder, it goes without saying that it can never be negative, but will always be between \(0\) and \(n-1\). If you get a remainder below zero you have made a mistake: too good to go shopping, have a “negative remainder” and see the cashier giving you money. Unfortunately it does not work like this, neither in supermarkets, nor in modular arithmetic. This characteristic leads to a fundamental property: modular arithmetic is cyclic. Once the modulus is exceeded, numbers wrap around themselves starting the count again from 0. And even if it seems like a property with no real purpose, all modern cryptography is based exactly on this.
One Rule To Rule Them
Solving a congruence is very simple. Suppose you have the following relation:
What the equation is asking you is to find the remainder of the division of \(a\) by \(n\). To solve it you follow three very simple steps:
-
You compute:
$$ z = \left\lfloor \frac{a}{n} \right\rfloor $$ -
You compute:
$$ y = n \cdot z $$ -
You compute:
$$ x = a - y $$
These three simple steps handle both congruences with positive values and those with negative values:
-
Case 1:
$$ x \equiv 13 \pmod{5} \\ z = \left\lfloor \frac{13}{5} \right\rfloor = \left\lfloor 2.6 \right\rfloor = 2 \\ y = 5 \cdot 2 = 10 \\ x = 13 - 10 = 3 $$and indeed
$$ 13 \equiv 3 \pmod{5} $$ -
Case 2:
$$ x \equiv -3 \pmod{5} \\ z = \left\lfloor \frac{-3}{5} \right\rfloor = \left\lfloor -0.6 \right\rfloor = -1 \\ y = 5 \cdot -1 = -5 \\ x = -3 - (-5) = 2 $$from which
$$ -3 \equiv 2 \pmod{5} $$
The positive case is very intuitive, unlike the negative one which seems made up out of nowhere, right? No! That one also makes sense. If you are looking at the clock and it is exactly midnight, modularly speaking it is:
And if I asked you: "what time was it one hour ago?" mathematically it would be:
But you, with your extraordinary ability to conceive time, would answer:
(of the previous day).
Yes, Even Fractions
We have seen positive numbers and negative numbers, but it does not end here. Just because remainders are always integers, it does not mean that modular arithmetic is not able to handle divisions. If negative numbers seemed strange to you, modular fractions are no less. The matter here becomes a little more elaborate in fact, given the equation
so that the result exists the condition must hold:
where the \(GCD\) is nothing more than the greatest common divisor. When it holds the numbers are said to be coprime with each other and we can solve divisions. The matter certainly does not end here, because in order to solve it is necessary to apply the algorithm of extended Euclid and find the coefficients of Bézout identity. Without going too much into detail let us see an example, just to show you that I am not talking nonsense. Suppose we have to solve:
That they are coprime does not need to be proven so we start immediately by applying the extended Euclidean algorithm which allows us to write:
and in this equality, the \(x\) is exactly the solution we are looking for.
Making the proper substitutions we have:
This one we can also solve mentally, in fact by setting \(x=-2\) and \(y=1\), we make the equality true. So the solution is \(x=-2\), but by now we know that in modular arithmetic negative numbers disgust us, so bringing it back to positive values we have:
So in our initial equation we have:
What we have done in practice is find a multiplicative inverse, that is, we have found a number (the \(5\)) such that, multiplied by a second one (the \(3\)), and reduced modulo (of \(7\)) gives remainder \(1\). This is easy in everyday mathematics, for example the multiplicative inverse of \(3\) is \(\frac{1}{3}\). But modular arithmetic lives in a world of its own and the inverse of \(3\pmod{7}\) is \(5\).
Knowing the multiplicative inverse, you can also solve equations. Suppose we have:
If you were to calculate the multiplicative inverse of \(2\pmod{17}\) you would see that it is \(9\), so we can write:
These are simple examples, but very explanatory of how the calculation of the inverse works in modular arithmetic. You can obviously make more complex examples but they fall outside my purpose of giving an overview of these concepts.
Now that we have become familiar let us take a step back. Earlier I wrote that it is necessary that the numbers be coprime. Well I lied, at least partly. Even if a bit tricky, there are ways to solve cases in which for a congruence it results
Without going too much into the subject it is enough for you to know this:
- If \(GCD(a, n) = d > 1\) the congruence is solvable if and only if \(d \mid b\) (that is, \(d\) divides \(b\) giving an integer result).
- If \(d \mid b\) we have more than one solution for the congruence (exactly \(d\)).
To give you some examples:
-
Possible case example
$$ 4x \equiv 8 \pmod{12} $$We have that \(GCD(4, 12) = 4\) and since \(4\) divides \(8\) we have 4 solutions which are
$$ x=2, 5, 8, 11 $$Even if I have omitted the procedure because out of scope, try it to believe it.
-
Impossible case example:
$$ 4x \equiv 1 \pmod{12} $$We have that \(GCD(4, 12) = 4\) and since \(4\) does not divide \(1\) we have no solutions.
Obviously this is not all, you can also solve quadratic equations, systems of equations, etc. But these are all topics that fall outside the purpose of a general overview, if you want to explore further I recommend taking a look at the book listed in the references.
Not All Fields Come To Harm
Modular arithmetic is a very powerful tool. By combining it with the use of prime numbers, you get the basis for many cryptographic algorithms: RSA, Diffie-Hellman, El Gamal and so on. It allowed us to play with numbers, remainders, cyclicity and we had fun, but when the going gets tough the tough get going and some cryptographic algorithms, without naming names (elliptic curves), break our balls. They say: "All these remainders are no longer enough for us!". Elliptic curves are greedy, they want more elements. And this is where the infamous fields come into play. Not just any fields, but finite fields, but let us proceed step by step.
What is a field... A field is nothing more than a set of elements which allow the operations of addition and multiplication that satisfy some requirements:
- Closure: by adding and/or multiplying the elements of the field, we obtain an element in the field. Suppose we have a field \(\mathbb{A}\) and two elements \(a, \, b \neq 0 \, \in \mathbb{A}\), then having a closed field means that \(a + b \in \mathbb{A}\) and \(a \cdot b \in \mathbb{A}\).
- Abelian Group: the operations of addition and multiplication must have the neutral element, their inverse and must satisfy the associative, commutative and distributive properties.
This in plain words means that, given the field \(\mathbb{A}\), \(a, \, b, \, c \in \mathbb{A}\) and \(a, \, b, \, c \neq 0\):
- The term \(0\) exists which allows us to write \(a + 0 = a\) (neutral element of addition).
- The term \(1\) exists which allows us to write \(a \cdot 1 = a\) (neutral element of multiplication).
- The term \(-a\) exists which allows us to write \(a - a = 0\) (inverse of addition).
- The term \(a^{-1}\) exists which allows us to write \(a \cdot a^{-1} = 1\) with the exception of \(0\) (inverse of multiplication).
- \(a + b = b + a\) and \((a + b) + c = a + (b + c)\) (commutative and associative properties of addition).
- \(a \cdot b = b \cdot a\) and \((a \cdot b) \cdot c = a \cdot (b \cdot c)\) (commutative and associative properties of multiplication).
- \(a \cdot (b + c) = a \cdot b + a \cdot c\) (distributive property)
It seems like a big list of stuff but if you read carefully everything is quite simple. There are no strange properties, in fact they are all things learned in elementary school. An example of a field is something you actually use every day, the set of real numbers \(\mathbb{R}\). Take any two real numbers and consider the listed points one by one. You will see that all of them are satisfied. The same cannot be said, for example, for the set of natural numbers \(\mathbb{N}\). Natural numbers (depending on the convention, with or without zero) are all positive integers \({0, \, 1, \, 2, \, \dots}\), therefore they cannot include a negative number and consequently the additive inverse element is missing (just to give an example, since other properties are not satisfied as well).
Prairies And Little Gardens
If you have made it this far, congratulations, now you know what a field is. That said, when is a field defined as finite? Nothing more intuitive. When it has a finite set of elements. When you can count the elements of the field knowing that sooner or later the count ends. So not only must it satisfy the previously defined points, but it must also have a finite number of elements. So \(\mathbb{R}\) is indeed a field, but it is not a finite field because it contains an infinite number of elements. If it is conceptually simple to know what a finite field is, building one is not so immediate. Or at least it is not if you want to make elliptic curves happy (yes I am aware that I have mentioned them twice but have not said what they are, it is enough for you to know that they are algebraic curves used in cryptography, maybe one day I will talk about them). So let us proceed step by step. We know what a finite field is, well finite field is a different name to indicate a Galois field. They are exactly the same thing and
Before proceeding with the rest however, I want to make a small tribute to the great Évariste Galois, from whose name Galois fields are derived. He was a great mathematician who died at the tender age of 20. At that age I used to get drunk at university parties, he invented a branch of abstract algebra. But at least I made it past 20 (only because duels to the death no longer exist). But let us get back to us...
In reality, in the previous paragraph we started to see finite fields, but it is not enough, we need to add something. Let us go back to good old modular arithmetic considering the base form, and let us suppose we take a prime number as the value of \(n\) (that prime numbers are those numbers divisible only by 1 and by themselves does not need to be said, right?!). Considering \(n=5\) we have:
From the previous paragraph you should know that all the possible remainders are in the set
Let us go and check the conditions one by one:
-
Closure:
Let us consider the addition operation and take, for example, the values \(4\) and \(3\) (but it is valid for all, trust me)
$$ 4 + 3 = 7 \equiv 2 \pmod{5} $$that is, writing \(7 \pmod{5}\) is equivalent to writing \(2 \pmod{5}\), so we are back in the set \(\mathbb I\). With multiplication we obtain the same thing:
$$ 4 \cdot 3 = 12 \equiv 2 \pmod{5} $$we are still inside \(\mathbb{I}\). -
Neutral element of addition:
Let us consider the addition operation and take, for example, the value \(4\) (but here too it is valid for all, trust me)
$$ 4 + 0 = 4 \equiv 4 \pmod{5} $$This also checks out, great.
-
Neutral element of multiplication:
Let us consider the multiplication operation and take, for example, the value \(4\) (but here too it is valid for all, trust me)
$$ 4 \cdot 1 = 4 \equiv 4 \pmod{5} $$This also checks out, yu-hu.
-
Additive inverse:
Let us consider the addition operation and take, for example, the value \(4\) (same story). The additive inverse is \(-4\), but by now you know how to handle negative values right?! So skipping the steps we write:
$$ -4 \equiv 1 \pmod{5} $$therefore the additive inverse of \(4\) is \(1\). In fact:
$$ 1 + 4 = 5 \equiv 0 \pmod{5} $$This also checks out, yay.
-
Multiplicative inverse: here I will not go through the steps but let us reflect on the set \(\mathbb I - \{ 0 \}\). Once we remove \(0\) which by definition has no inverse, every element of \(\mathbb I\) is coprime with \(5\) since the latter is a prime number. And earlier I clearly wrote that if the numbers are coprime, the inverse exists. So we are certain that for every element of \(\mathbb I - \{ 0 \}\) we have an inverse and consequently we can also check off this point.
-
Well guys, I would be a bit fed up. The last three are variants of additions and multiplications, if you feel like it take paper and pen and do them, otherwise trust me that those also check out.
We have therefore shown that if \(n\) is a prime number, the set of remainders forms a Galois field and its formal notation is \(GF(p)\) or \(\mathbb{F}_p\) where \(p\) is the chosen prime number.
Let us see why, if \(p\) were not prime, we could not have a Galois field. Let us consider the case \(p=8\), we have that the set of remainders is:
Let us take one of the remainders, \(b=2\), and look for its multiplicative inverse. To do this we must write the congruence:
From which:
Checking the divisibility we have that \(2 \nmid 1\), and we can conclude that \(2 \pmod{8}\) has no multiplicative inverse, and this violates one of the required properties of fields.
From The Little Garden To The Plantation
We have seen that \(p\) must be prime in order to define a Galois field. But what if I told you that instead you can define fields of the type \(\mathbb{F}_8\)? No, I am not crazy. It can be done, but in a slightly different way than before. First of all let us start by saying that the argument of the field cannot be just any number, but must be a power of a prime number. So why can \(\mathbb{F}_8\) exist? Because we can write \(8=2^3\), that is, \(8\) as a power of the prime number \(2\).
Even if it is not so, let us suppose you are asking yourself why it is useful to do this. In the previous paragraph we saw that to obtain a Galois field it is necessary to have a prime number \(p\), and the field \(\mathbb{F}_p\) will have exactly \(p\) elements:
This is a bit limiting, don't you think? If we wanted a very large Galois field but with small primes? For example with \(2\)? This would allow us to have all the numerical terms in \(\{0, \, 1\}\) but with a number of elements greater than two. This would allow us not only to obtain a field with many more elements, but also to work with values that are extremely easy to handle: by restricting ourselves to \(0\) and \(1\), the operations become naturally efficient for computers to represent and execute, resulting in significant performance benefits. No it is not witchcraft. It can be done and it is very useful to do it, because it allows us to have numbers of low value, but in very large fields (which increases the security of the infamous elliptic curves). Ok, but how? If the numbers are those what do we use to increase the cardinality of the field? The answer is: polynomials. Polynomials act as building blocks: they combine the values of \(\mathbb{F}_p\) into more complex structures, allowing us to create many more elements without introducing new numbers, but simply new combinations of the same coefficients. Therefore, given a prime number \(p\) and given an exponent \(m\), we can define thanks to polynomials a field \(\mathbb{F}_{p^m}\) of \(p^m\) elements, whose numerical terms are in \(\{ 0, \, \dots, \, p - 1 \}\).
Considering the case \(\mathbb{F}_{2^3}\), let us see step by step (or rather, by degrees), how to proceed:
-
Degree \(m=0\): This case is simple, we must take the polynomials of degree \(0\) which are in fact just the coefficients. Since we are in \(p=2\), the coefficients are
$$ \{0, \, 1 \} $$ -
Degree \(m=1\): In this case we take all the polynomials of degree at most \(1\). The family of these is given by
$$ q(x) = ax + b $$since the coefficients must be in \(\{0, \, 1 \}\), we have that these polynomials are:
$$ \{x, \, x + 1 \} $$In fact if:
- \(a=0, \, b=0\) \(\Rightarrow q(x)=0\). Already considered previously.
- \(a=0, \, b=1\) \(\Rightarrow q(x)=1\). Already considered previously.
- \(a=1, \, b=0\) \(\Rightarrow q(x)=x\).
- \(a=1, \, b=1\) \(\Rightarrow q(x)=x + 1\).
There cannot be polynomials of degree \(1\) such as \(2x\) because working, in this case, with \(\pmod{2}\) we have that
$$ 2 \equiv 0 \pmod{2} \Rightarrow 2x \equiv 0 \pmod{2} $$which we already considered in the case \(m=0\).
-
Degree \(m=2\): Similarly to before, we take all the polynomials of degree at most \(2\) whose coefficients are in \(\{0, \, 1 \}\). The family of these is given by
$$ q(x) = ax^2 + bx + c $$So, expanding, and ignoring all those already considered previously we have:
$$ \{x^2, \, x^2 + 1, \, x^2 + x, \, x^2 + x + 1 \} $$ -
Degree \(m=3\): Eh, here the situation changes. Let us start by saying that working in \(m=3\) we must not go beyond. These polynomials will not be part of the field, but will define the modulus of the field. When we look for the polynomials of maximum degree with respect to the field, we must make sure they are irreducible, that is, that they cannot be written as a product of polynomials among those listed so far. The polynomials are of the family
$$ q(x) = ax^3 + bx^2 + cx + d $$In total there are \(8\) polynomials, but the irreducible ones are only two:
$$ \{x^3 + x + 1, \, x^3 + x^2 + 1 \} $$Try as much as you like, you will never manage to write these two polynomials as the product of two polynomials of lower degree. Let us briefly see why we ignore the others. Suppose we have:
$$ q(x) = x^3 + x^2 + x $$We can also write this as:
$$ q(x) = x^3 + x^2 + x = x \cdot (x^2 + x + 1) $$Since it can be written as the product of two polynomials of lower degree, we discard it because it would mean introducing elements that do not have a multiplicative inverse.
We are almost at the end. Now that we have the irreducible polynomials we choose one at will, whichever you prefer (even if I would get myself checked if I preferred one polynomial over another). In this case the fields are said to be isomorphic (same cardinality, same field structure but different irreducible polynomial). Let us suppose we choose the polynomial:
we have found our Galois field \(\mathbb{F}_{8}\) which contains exactly \(8\) elements reduced modulo the chosen polynomial, all coefficients computed \(\pmod{2}\) and which satisfies the properties mentioned above (otherwise it would not be a Galois field):
Let us take two random values and see how, by performing addition and multiplication of the elements in the field, we never leave the field itself. Let us take \(f(x) = x^2 + 1\) and \(g(x) = x + 1\).
-
Addition:
$$ f(x) + g(x) = x^2 + x + 2 $$Since we are in \(\pmod{2}\) we have that
$$ 2 \equiv 0 \pmod{2} $$Therefore we can write
$$ x^2 + x + 2 \equiv x^2 + x \pmod{2} $$that is, it has gone back to being a polynomial belonging to the field defined earlier.
-
Product:
$$ f(x) \cdot g(x) = (x^2 + 1) \cdot (x + 1) = x^3 + x^2 + x + 1 $$Since our irreducible polynomial is \(x^3 + x^2 + 1\) we can write this relation:
$$ x^3 + x^2 + 1 \equiv 0 \pmod{x^3 + x^2 + 1} $$From which
$$ x^3 \equiv -x^2 - 1 \pmod{x^3 + x^2 + 1} $$However I remind you, that in modular arithmetic, negative numbers are not liked but we already know how to bring ourselves back to positive remainders \(\pmod{2}\). Omitting the steps (which you should already know but which you can read here), we have that:
$$ -1 \equiv 1 \pmod{2} $$So we can write this:
$$ -x^2 - 1 \equiv x^2 + 1 \pmod{2} $$from which we can write:
$$ x^3 \equiv x^2 + 1 \pmod{x^3 + x^2 + 1} $$Returning now to the initial polynomial we can write:
$$ x^3 + x^2 + x + 1 \equiv x^2 + 1 + x^2 + x + 1 \equiv 2x^2 + x + 2 \pmod{x^3 + x^2 + 1} $$Since, as already said and repeated, shown and re-shown, we are in \(\pmod{2}\) we have that:
$$ 2x^2 \equiv 0 \pmod{2}, \, 2 \equiv 0 \pmod{2} $$We have therefore reached the conclusion that:
$$ (x^2 + 1) \cdot (x + 1) \equiv x \pmod{x^3 + x^2 + 1} $$and as luck would have it, \(x\) is a polynomial of the Galois field.
For obvious reasons I have shown you only the closure property, but you are completely free to do all your experiments. I am right anyway.
To conclude this paragraph, I invite you to use a reducible polynomial as the modulus of the field. With pen and paper in hand, you will see that there will be at least one element of the field that does not have a multiplicative inverse belonging to the field itself, violating one of the properties.
Conclusions
When I started writing this article I imagined it shorter, much shorter. But this time I did not get carried away, the problem is that, with hindsight, there were many more things to say. You will forgive me if you have not seen more complicated cases of the extended Euclidean algorithm or if I have not shown you the Chinese remainder theorem to solve systems of congruences. Sure now if on a Saturday night you go out with your crush, you cannot say you know how to solve a quadratic congruence, but you can talk about Galois and finite fields. That’s something. In any case even if all these things seem pointless on their own, know that they are the basis of all the operations you perform every day and that you hope are secure. If you feel safe when performing online operations, if you feel protected under the umbrella of RSA, elliptic curves and so on, know that it is thanks to these basic elements, and one day I will talk to you about them. Until then however, do not come to me saying “my password got hacked”, because cryptography is secure, it is the passwords 1234 and hot mom 3km from you that are not. So it is your fault.
Until next time.