I will be writing a series of posts that will introduce the necessary background of cryptography in a (hopefully) understandable way to anyone. The goal of these posts will be to lead an interactive online classroom discussion covering a wide-range of topics: basic group theory, prime groups, elliptic curves, public-private key cryptography schemes (Diffie-Helman, Elliptic Curve Cryptography, etc.), digital signing algorithms, quantum-resistant algorithms, shared secrets, and ring cryptography.

The goal is to utilize the Steem blockchain and the current Steemit interface to discover (via your participation!) a novel way for teaching by experts to experts and non-experts alike via the internet in an open and free manner, while compensating both teachers for their domain specific knowledge and students for good questions, interactive discussions, and answers.

These next few weeks will serve as my own template for this interactive learning experiment. Feel free to modify / adjust this if you would like to hold your own classes.

I hope you will participate as we all can learn together. Do not be shy jumping into any of my interactive lessons late while the course is in session. There will be ample opportunity for anyone to catch up or to follow along as they wish.

What Is a Mathematical Group?

The development of THEORETICAL and ABSTRACT MATHEMATICS is done by observing common patterns and then codifying the base structure in an axiomatical framework.

Group theory is fundamental to understanding and applying cryptography and understanding cryptographic schemes.

In the context of group theory, observation of the integers, real numbers, subsets of these, as well as symmetries and reflections of regular n-gons gave way to the axioms of a group.

So what are the common properties that each of these seemingly different objects possesses?

The first to note is that there is always some type of operation. In the case of the integers or real numbers, one can consider addition or multiplication. When studying the group properties of regular n-gons, one can think of the operations as a combination of rotations about the center or mirror reflections across some axis of the regular n-gon.

Consider the simplest regular n-gon, i.e. an equilateral triangle, with vertices labeled in a widdershins fashion.

A symmetry action is moving an object in such a way where you can lay it back on top of itself perfectly. Often, mathematicians will label vertices of an n-gon to be able to describe which symmetrical action occurred.

Notice that if we ignore the labelling on the vertices and rotate the triangle by 120 degrees (360 / 3 = 120) or apply a reflection across some axis, the we are looking at an equilateral triangle in the same position under some symmetrical action.

If instead we rotate the equilateral triangle by 90 degrees, we see that this is not a symmetrical action. We cannot take the triangle and lay it on top of its original form.

So what does the symmetry of this equilateral triangle mean in terms of a group? We need to first define some other notions of a group. Objects of a group are called elements. In this case, each of the 6 different possible triangles under some symmetry action are elements of this group.

Now, when you have elements in a group, you have some type of operation associated to the elements, whereas if you input two elements of a group G, you output another element of that same group G. This binary operation (due to having two inputs) is therefore said to be closed (since the output belong to the same set of all possible inputs).

Group Definition

A set G is a group under the operation, +, if and only if the following are true :

1. There exists an identity element, e, such that for every element g in G, e + g = g and g + e = g (identity).
2. If g1, g2 are in G, then g1 + g2 = g3 is also in G (closed).
3. If g1, g2, and g3 are in G, then (g1 + g2) + g3 = g1 + (g2 + g3) (association).
4. If g1 is in G, then there exists a unique element (-g1) such that g1 + (-g1) = e and (-g1) + g1 = e (inverse).

Unique Identity

It turns out that the identity element is unique.

Suppose G is any group with the identity e_1. Suppose another element e_2, different from e_1, satisfies the identity requirements.

Then, e_1*e_2 = e_1. But, also, e_1*e_2 = e_2 and then we have e_1 = e_2, which is a contradiction. Thus, our assumption that e_2 be different than e_1 is false, and we have uniqueness.

Additive Notation Versus Multiplicative Notation

Since groups only have one operation, one can equivalently use any symbol to denote the operation. Often, the symbols chosen were + and *, as these have natural meanings when we consider different groups.

Natural Additive Groups

1. The set of integers. 0 plays the role of the identity element. Remember from grade school when 0 + x = x + 0 = x for all x? That comes from group theory!

2. The set of integers modulo a number k. Modulo is a remainder function and is most commonly denoted with %. If we ask what is the the remainder of 42 mod 5, the result is 2. Mathematically, this is written as 42 mod 5 = 2 or 42 % 5 = 2. An example of a group is the set of integers modulo 6. If we take the set {0,1,2,3,4,5} and consider the standard addition operation, and perform modulo arithmetic on any value that is not in the set 0...5, we obtain a group. The inverses of 0,1,2,3,4,5 are 0,5,4,3,2,1, respectively, i.e. 2 + 4 = 0 (mod 6). Don't believe me? Try it out and see that all of the axioms are satisfied.

3. The set of real numbers. Once more, 0 plays the role of the identity element. 0 + x = x + 0 = x for all x that is a real number. And -x is the inverse of x. If you add two real numbers together, the output will always be a real number. And associativity holds. Thus, all axioms are satisfied, and so the real numbers under addition are a group.

4. Integers of a multiple k. For example, k = 2, all the even integers. Or perhaps all integers of 55. We see that a and b are a multiple of k, then a = ck and b = dk for some c and some d. But then, a + b = ck + dk = (c + d)k. So, at the least, we see that we have closure. What is the identity in this group? Hint: we've seen it before. Do you see how this element is a multiple of any integer k?

Natural Multiplicative Groups

1. Integers without 0, (Z)^*.
2. Rational Numbers without 0, (Q)^*.
3. Real numbers without 0, (R)^*.
4. Integers modulo n without 0, (Z/nZ)^* or (Z_n)^*.

In all these cases, the identity element is 1. Recall from grade school that 1*x = x*1 = x for all x.

A special group used extensively in cryptographic systems is the set of integers modulo a prime number without 0. We will discuss these special cyclic groups in a later post.

Abelian Groups

Abelian groups are groups that have an additional property that make them special. This property is known as commutativity and for historical reasons is also termed abelianity. (This comes from often denoting the operation as multiplication (x) and then using concatenation to denote multiplication, so as to not have to write the additional symbol. Often, elements in a group were given names such as a and b, and so a new element would be called ab. From there, abelian was formed.)

Non-abelian Groups

Non-abelian groups are those which do not have commutavity. A simple example of a non-commutative group is by considering the symmetries of the square as a group. I will refer to the wiki page on groups that gives this example. For more info check the following link: https://en.wikipedia.org/wiki/Group_(mathematics)#Second_example:_a_symmetry_group.

Other Topics of Interests With Group Theory

Unfortunately, some of these topics do not fall into the purview of having to understand all the details behind cryptography. However, they are still interesting in their own right and are often more than tangentially related. Here is a non-complete list.

1. Subgroups
2. Normal Groups
3. Normal Subgroups
4. p-Sylow Groups
5. Group Actions
6. The Center of Group Actions
7. The Monster Group
8. Group Orbits

We will discuss some of these topics as necessary, unless there is significant interest by the community.

Conclusion

This concludes the introduction to group theory. We give the definition of a group and some standard examples. The important bits to understand is that there is fundamentally no difference between an additive group or a multiplicative group. Fundamentally, it is a matter of notation. For instance, if I were to write a + a = 2a in terms of additive notation, then the equivalent representation in multiplicative notation is a^2. This distinction will be important when we consider the group of points on an elliptic curve (additive group) versus a group of prime order in multiplicative notation.

Questions, anyone?