Everything you need to know about Groups

mathematics crypto

Groups

Groups are actually one of the first important algebraic structures, and their study was motivated by the problem of finding the formula for the root of a polynomial in terms of their coefficients. Later, mathematians turned to investigate the set of permutations of roots of a given polynomial. Eventually, Evariste Galois, founder of Group Theory, reducted the study of algebraic equations to the study of permutation groups.

Groups, and other finer structures are one of the building blocks of public-key cryptography.

Definition: A group is a set G, together with a given binary operation \(\circ\). The group and the binary operation \(\circ\) satisfy the following properties:

  1. The group operation \(\circ\) is closed i.e. for all \(a, b \in G\), it holds that \(a \circ b = c \in G\).
  2. The group operation \(\circ\) is associative i.e. \(a \circ (b \circ c) = (a \circ b) \circ c\) for all \(a, b, c \in G\).
  3. There is an element \(1 \in G\), called the identity element, such that \(a \circ 1 = 1 \circ a = a\) for all \(a \in G\).
  4. For each \(a \in G\), there exists an element \(a^{-1} \in G\), called the inverse of \(a\) such that \(a \circ a^{-1} = a^{-1} \circ a = 1\)

It is recommended to write a group as \((G, \circ)\) where \(\circ\) is the binary operation of the group. Note: Groups can be both finite and infinite. In modern cryptography, we are almost always dealing with finite-groups

Abelian Groups

Defintion: A group \((G, \circ)\) is abelian if it also satisfies the commutative property i.e. for all \(a, b \in G\), \(a \circ b = b \circ a\)

\(\mathbb{Z}^{*}_{n}\) is an abelian group that is used in cryptographic schemes such as Diffie-Hellman Key Exchange, Elgamal Encryption, Digital Signatures, etc.

Theorem: The set \(\mathbb{Z}^{*}_{n}\) that consists of all integers \(i = 0, 1, ..., n-1\) for which the \(gcd(i, n) = 1\) forms an abelian group under the binary operation multiplicaiton modulo \(n\). The identity element, of course, is 1.

Cyclic Groups

Before we can fully understand cyclic groups, it will be helpful to brush up on other relevant definitions.

Definition: A group \((G, \circ)\) is finite if it has a finite number of elements. The number of elements present in the group is also referred to as the cardinality or the order of the group. It is denoted as \(|G|\)

Order of an Element

Definition: The order of an element \(a\) of a group \((G, \circ)\) is the smallest positive integer \(k\) such that

\[a^{k} = a \circ a \circ a \circ ... \circ a = 1\]

Finally,

Definition: A group \((G, \circ)\) which contains an element \(a\) with order equal to \(|G|\) is said to be cyclic. The elements with maximum order i.e. equal to \(|G|\) are called primitive elements or generators.

A cyclic group, along with the generator, offers interesting properties. One of those properties is that every element of the cyclic group can be generated by just raising \(a\) to various powers within the group.

Okay, so we know what a cyclic finite group is, but how to we create one? Luckily, here's a sweet little theorem.

Theorem: If \(p\) is prime, then \((\mathbb{Z}^{*}_{p}, \circ)\) is an abelian finite group where \(\circ\) is multiplication mod \(p\) binary operation.

According to the above theorem, we can create an abelian cyclic group per prime number! For instance, \(Z^{*}_{13}\) will be finite cyclic group and all the elements, together with the operation \(*\) will hold all the group properties. Finite groups over a prime \(p\) are so important and useful that almost every modern brower has a built in cyrptosystem over \(Z^{*}_{p}\).