7.2 Groups

Groups are the most basic mathematical structure in which public-key cryptography can take place. So, let’s plunge right into the math and explain the properties of a so-called abelian group.

Let M be a nonempty set, and let ⋆ be an operation on M, which means ⋆ is a function M × M → M, which maps pairs of elements of M to elements of M. The pair (M,⋆) is called an abelian group 𝔾 if the following properties hold:

• (G1) ⋆ is an associative operation that means for all cases of a,b, and c ∈ M, we have
   

• (G2) In M exists a neutral element e with the property that for all cases of a ∈ M,
   

• (G3) For all cases of a ∈ M exists an inverse element a−1 ∈ M with the property a−1 ⋆ a = a ⋆ a−1 = e.
• (G4) ⋆ is a commutative operation, which means for all cases of a,b ∈ M, we have

The number of elements of M is called the order of the group 𝔾. Note that property (G4) is not strictly necessary for the pair of (M,⋆) to be a group. However, we will need this commutativity property later so that Diffie and Hellman can do their magical key exchange.

7.2.1 Examples of groups

Natural examples of abelian groups that immediately spring to mind are the following:

• The integer numbers ℤ with + as a commutative operation, 0 as a neutral element, and (−a) acting as an inverse element for a ∈ℤ
• The rational numbers ℚ∗ = ℚ∖{0} with ⋅ as a commutative operation, 1 as a neutral element, and a−1 = 1∕a as inverse elements

If you need an example of a non-abelian group, take M as the set of invertible matrices with real entries and n rows and n columns, with ⋅ (matrix multiplication) as the operation. The fancy name for this group is GLn(ℝ), or general linear group. Here, we can take the (n,n) identity matrix I as a neutral element and inverse matrices as inverse elements. But as you probably know, matrix multiplication is associative but not commutative.

However, we are not restricted to infinite sets to get an abelian group. Groups with a finite number of elements are called finite groups. An important example of a finite group is M = {0,1}, with ⊕ as an operation. Recall from Chapter 4, Encryption and Decryption, that ⊕ is defined as the exclusive OR operation, so we have 0 ⊕ 0 = 0,0 ⊕ 1 = 1,1 ⊕ 0 = 1, and 1 ⊕ 1 = 0. From this, we can see immediately that 0 is the neutral element, 0 is inverse to 0, 1 is inverse to 1, and ⊕ is commutative. The associativity of ⊕ can also easily be checked. We can go even smaller and take M = {1} and ⋅ as an operation. Naturally, this group is too small to be interesting.

However, these two small examples can be generalized to larger, but still finite, sets. Let M = {0,1,…,n − 1} and ⋆ = addition modulo n, which means for a,b ∈ M we set a ⋆ b = (a + b) mod n. This corresponds to our earlier example with n = 2. In a more general case, the neutral element is still 0, but the inverse element of a is given by (−a) = n − a, and it can be easily checked that addition modulo n is associative and commutative.

Can we again remove 0 from M and get an abelian group with the operation ⋆ = multiplication modulo n? Not always. If we take n = 10, for example, we won’t be able to find an inverse element to a = 2. Moreover, 2 ⋆ 5 = (2 ⋅ 5) mod 10 = 0, which is not an element of M, so ⋅ is not even an operation on M. This happens for all elements a that are divisors of n, so the solution is to make n a prime number: n = p. The resulting group, consisting of the set M = {1,2,…,p− 1} and the operation ⋆ being multiplication modulo p, is called 𝔽p∗. The reason for this symbolism will become apparent later when we discuss finite fields. As an example, the following table shows the multiplication table for 𝔽5∗:

⋅ mod 5	1	2	3	4
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

 Table 7.1: Multiplication table for 𝔽5∗

Using the ⋆ – operation within a group, we can formulate the discrete logarithm problem, which lies at the heart of the Diffie-Hellman protocol.