Blog » Mathematics for Cryptography – Introduction to Group Theory

# Mathematics for Cryptography – Introduction to Group Theory

I’m planning to do a set of posts on the mathematics used in cryptography and so I will be covering topics such as group theory, number theory, modular arithmetic, polynomials and eventually elliptic curves. This is the first post in the series which will give a very basic introduction to group theory and groups.

## What is Group Theory?

Group theory is a branch of mathematics in the area of abstract algebra that studies the symmetries that recur throughout mathematics. A group is a very abstract concept and a generalisation of some other algebraic types such as rings and fields which I will explain more in a future post. It turns out that the patterns and laws described by group theory show up in number theory, algebraic equations and geometry. Most importantly cryptography relies on group theory and finite fields for primitives such as the Diffie-Hellman key exchange, RSA encryption and also for zero knowledge proofs.

So what is a group?

## Definition of a Group

A group is defined as a set with a binary operation that satisfies a few properties; closure, associativity, identity and invert-ability. A set is just a collection of elements and the binary operation is not yet defined. It could be addition or multiplication but the definition of a group is more abstract than that and so it could also be geometric rotations over a shape for example.

In the sample code below I define a Rust trait `Group` which models a group. It takes a type `T` which must implement the `Operation` marker trait. The comments describe the properties which much be satisfied by the group. I represent the binary operation as ‘.’ in the comments which is implemented by the `apply` method which takes two elements and returns another element. The `identity` method should return the identity element for the group and the `inverse` method should return the inverse of the given element.

``````/// A group is a set and a binary operation (denoted by '.') which satisfies the following properties:
/// Closure - a . b = c where a, b, and c are in the set
/// Associativity - a . (b . c) = (a . b) . c
/// Identity - a . I = a
/// Inverse - a . a^-1 = I
pub trait Group<T: Operation, E> {
/// The binary operation which takes elements e1 and e2 of type E and returns the result
fn apply(&self, e1: E, e2: E) -> E;

/// Returns the identity element
fn identity(&self) -> E;

/// Returns the inverse of element e
fn inverse(&self, e: E) -> E;
}``````

## Definition of an Abelian Group

An abelian group is a group that also supports the commutativity property (in addition to the other group properties) which basically means the binary operation can be applied in any order to the elements a and b and the result will be the same. I define it here as a marker trait for completeness which extends the `Group` trait even though no additional methods are required.

``````/// A type which supports commutativity in addition to the standard group properties:
/// Commutativity - a . b = b . a
pub trait AbelianGroup<T: Operation, E>: Group<T, E> {}``````

## Definition of a Monoid

A monoid is similar to a group except that elements may not have an inverse and it only supports the associativity and identity properties. It once again is a very abstract concept having a set and a binary operation. I define the `Monoid` trait below with an `apply` and `identity` method but no inverse method. I will be using this type later when defining a trait for a ring in a future post.

``````/// A monoid is a set and a binary operation (denoted by '.') which satisfies the following properties:
/// Associativity - a . (b . c) = (a . b) . c
/// Identity - a . I = a
pub trait Monoid<T: Operation, E> {
/// The binary operation which takes elements e1 and e2 of type E and returns the result
fn apply(&self, e1: E, e2: E) -> E;

/// Returns the identity element
fn identity(&self) -> E;
}``````

## Example Operations

Next I define the `Operation` marker trait and implement `Addition` and `Multiplication` types to be used as markers. This is required so that a type can implement the trait over multiple operations. For example we might want to implement the `Group` trait under both `Addition` and `Multiplcation`.

``````/// Marks the Monoid and Group traits with a type
pub trait Operation {}
pub struct Multiplication;
impl Operation for Multiplication {}``````

## Example of a Group

Finally here is a very simple example of a group, the set of integers under addition. In mathematics the set of integers is defined as the whole numbers, positive and negative, including zero. With addition the set of integers forms a group because all the group properties are for-filled. The identity element is zero and the inverse is the negation of the given element. We also implement the `AbelianGroup` trait for our new `AdditiveIntegers` type because integer addition is commutative. You can check for yourself to verify that each of the group properties are for-filled with this implementation.

``````/// Integers under addition form a group where plus (+) is the group operation, zero is the identity
/// and negation (-) can be used to get the inverse of an element

fn apply(&self, a: i32, b: i32) -> i32 {
a + b
}

fn identity(&self) -> i32 {
0
}

fn inverse(&self, a: i32) -> i32 {
-a
}
}

// Integers under addition supports commutativity

Next we test out the code by creating a new instance of the `AdditiveIntegers` group. Then we test each of the methods to confirm that they each work as expected and for-fill the required properties, closure, associativity, identity, invert-ability and commutativity.

``````#[cfg(test)]
mod tests {

use super::*;

#[test]

let a: i32 = 10;
let b: i32 = 20;
let c: i32 = 30;

// Closure - a . b = c where a, b, and c are in the set
let result: i32 = group.apply(a, b);
assert_eq!(c, result); // result is an integer so in the set

// Associativity - a . (b . c) = (a . b) . c
assert_eq!(group.apply(a, group.apply(b, c)),
group.apply(group.apply(a , b), c));

// Identity - a . I = a
assert_eq!(group.apply(a, group.identity()), a);

// Inverse - a . a^-1 = I
assert_eq!(group.apply(a, group.inverse(a)), group.identity());

// Commutativity - a . b = b . a
assert_eq!(group.apply(a, b), group.apply(b, a));
}

}``````

## Conclusion

This post introduced group theory and explained the definition of a group, abelian group and monoid. We then created an example group, the integers over addition and showed an example usage. Future posts will cover topics such as rings and fields which will help explain why I’ve created these group types and will further explain these group theory concepts.