In this series, I will start exploring modern cryptography, starting with its mathematical foundation, Finite Groups, Fields.
What is a group?
A group is nothing more than a collection of elements together with an operation. Let's call this collection of elements G and the operation ❍. Together they form a group, (G, ❍) if they satisfy the following properties:
- for every two elements, a, b which are in the set G, the result of a ❍ b = c is still in the set
- for all a, b, c in the set G, (a ❍ b) ❍ c = a ❍ (b ❍ c)
- there exists an element in G, let's call it e, the identity, such that a ❍ e = a for all a in G.
- for every element a, there exists element b, called an inverse, such that a ❍ b = e
There are many ways in which one may classify these groups, but for the purpose of this post, divide groups into two categories, namely finite groups and infinite groups. A group is finite, or infinite, depending on the set of elements G. Hence, if G is finite, the group is finite and conversely if G is infinite, the group is infinite. we can also classify group operations into two categories, additive and multiplicative. After all this theory, let's shed more light on the topic with some examples.
Examples
Let's take the set of integer numbers, Z={-3, -2, -1, 0, 1, 2, 3, ...} together with addition, +. This I claim is a group. A quick check through the properties will make this clear. If we add two integers we get an integer, addition is associative, 0 is the identity and for every a in Z we have -a as the inverse. It is very important how we choose our operation. If we take the same set Z, but we change our operation to multiplication, we don't get a group anymore, because the last property of a group is not true. Other examples of infinite groups include the real numbers, R, without 0, together with multiplication or the entirety of the reals with the operation of addition.
Finite Groups
As I said earlier, finite groups are just groups where the set of elements is finite. The most trivial example of a finite group is {0, 1} together with modulo 2 addition. What is modulo 2 addition? Is just like normal addition, but we take the result and divide it by 2. The remainder of this division, which is either 0 or 1 is our result. So, for example, 1 + 1 = 0 😊
An important class of finite groups, for cryptography as well, are these "groups of remainders" with their clock, or modular arithmetic. Now let's define two important properties of groups. We call a group order, the number of elements in a group. An element in a group, a, also has an order, an integer, let's call it n, and it's the number such that a ❍ n = e, where e is the identity. for finite groups, all elements have an order, which is also finite. There is a strong correlation between group order and element order, given by Lagrange's theorem, which is a little beyond the scope of this article. Another important thing to mention is that, for every prime number p, there is a finite group of order p.
What is a field
Understanding fields is heavily reliant on understanding groups. A field is a set of elements, F, together with two operations, one additive, +, and a multiplicative one, ✕. They form a field, (F, +, ✕) if (F, +) is a group and (F-{0}, ✕) is a group, where F-{0} is the set F without the additive identity element. Also, we must have, for every a, b, c in F, a ✕ (b + c) = a ✕ b + a ✕ c and (b+c) ✕ a = b ✕ a + c ✕ a. This is called distributive of operation ✕ in regards to +. An important field, and one we are very familiar, is the field of real numbers. The reals, together with classical addition and multiplication form a field.
An important class of fields, are finite fields, which, like finite groups, are just fields where F is finite. We will concentrate on prime fields ( fields of prime order), which we introduced in the previous section, when we discussed groups of prime order together with their modular arithmetic. We can extend our discussion to fields of order q = p^n, where p is a prime and n is a positive integer, in another post perhaps.
Modular Field Arithmetic
We know modular field arithmetic since the fifth grade. Let's consider a prime number p and the set of numbers {0, 1, 2, ..., p-1} together with addition and multiplication modulo p. This is a field. Let's take the example of {0, 1, 2, 3, 4, 5, 6}. Addition is pretty straight forward, if we add any to numbers in the set we get another from the set. For example, 6+5 = 11 = 4 (mod 7). We can do multiplication as well, 3 ✕ 4 = 12 = 5. We could multiply our field numbers with other bigger integers, for example, 30 ✕ 2 = 60 = 4. This is equivalent to doing a mod operation on 30 before multiplying: 30 = 2 (mod 7) and 2✕ 2 = 4. Exponentiation works just as expected. For example. 2^7 = 128 = 2. A perhaps more challenging task would b finding a multiplicative inverse. For example, given 2 from the above set we must find the integer, a, such that 2 ✕ a = 1. This is done using the Extended Euclidean Algorithm. For small fields such as the one in our example, we can "brute force" the solution. Hence, we find that 2✕ 4 = 1 (mod 7)
Conclusion
In this article, I have tried to give an introduction to maths I find relevant when studying cryptography. I have tried to make this accessible to the more non technical folks out there, and probably failed miserably. There are lots more to be said about fields and operations on fields, all things which have real world applications in modern cryptosystems. Stuff like the RSA, DSA rely on computationally complex problems to solve, like integer factorization and the discrete logarithm problem. Understanding why these are hard problems and much more, relies on understanding the maths, or at least part of the maths. I hope I have given you a glimpse into this.
Sources
Bits and pieces from my bachelor thesis
Wiki
Pixabey Thumbnail