Casual Physics Enjoyer

A Simple Group Theoretic Introduction

The goal of cryptography is to have two agents sharing a coded secret over some public channel. This secret has to be secure, which means that eavesdroppers shouldn’t be able to figure out what the secret is, even if they had the coded version. Most encryption algorithms rely on a key that needs to be known by two parties and kept secret. For now, let’s say that this secret is s, a number. Methods for secure messaging of this secret key are called Key exchanges. A simple yet classically secure way to do this is the Diffie-Hellman protocol. It is a protocol that uses simple group theory to encode secretes for us and is widely applicable to different mathematical groups.

Cyclic Groups

The first step is to take any mathematical group that is cyclic. As I’ve explained in previous posts, a group is a mathematical object with some elements. In this case, let’s assume that we only have a finite number of these elements. We also have a binary operation that allows us to ‘add’ two elements together in a group. In the bullet points below, the following conditions are some conditions that mathematicians use to decide if something is a group formally.

• There exists a group identity, which we will call e, where e ∈ G such that for all g ∈ G, combining the identity with any other element satisfies e · g = g · e = g. In plain English, this means that a group needs to contain a ‘do nothing’ transformation and that this transformation is unique.

• We require that for every symmetry transformation in the group, there needs to exist a unique group inverse for all g ∈ G. If we denote this inverse by the symbol g’, we require that g’· g = g · g’ = e

• Associativity means that we don’t care about the order in which we multiply things in the group. So, for all g1, g2, g3 ∈ G, we have that g1 · (g2 · g3) = (g1 · g2) · g3

In addition, a cyclic group is a group where every element can be expressed as a repeated group addition of a single, unique element to itself. When we add this element enough times, it becomes the identity. Think of this like clock arithmetic — the set of numbers mod n under addition itself a cyclic group. The single element which generates the whole group is called the generator.

Ordinary Diffie-Hellman

The goal of Diffie-Hellman is to allow two agents to share a secret key between them that no one else knows. If we have two agents, Alice and Bob, we can each give them a private key called a and b. They can pick a publicly known group G. Assuming that this group is cyclic, it has a generator.

Suppose they wanted to both pass each other a generated secret key. In the first step, Alice multiplies the generator a times and then passes it to Bob. Then, Bob multiplies this value by itself b times to obtain g^(ab), the secret key. After this, he gives Alice g^b, and then Alice multiplies this value. In this scenario, both a and b are

The cyclic group generated by a prime number is the set of numbers mod p, where multiplication is the group operation. This group itself is cyclic, and the proof of this uses Fermat’s Little theorem to prove the existence of a single generator. If G is such a group, then it is hard for an attacker to compute a, and hence what the secret key is. In the next post, I’ll talk about the asymptotic complexity of trying to break Diffie-Hellman.

Elliptic Curves

Diffie-Hellman permits any type of cyclic group to be used. So, we could even use the group of points on an elliptic curve. It is not at all obvious why points on an elliptic curve should form a group, and I’ll try to explain why in this section. Take your favourite field F — it could be the real numbers, complex numbers, or the multiplicative group of integers mod p. An elliptic curve is a set of points in two dimensions, which satisfy the following equation

Suppose we have two points, A and B on the elliptic curve. To add these points up, we draw a line between these points to get another, third point, and then reflect this in the x-axis. The resulting point is what we call A+B. To get A+A, we take the tangent line at the point A in the curve, see where it intersects with the elliptic curve and then reflect it once again in the x-axis.

Treating this as a cyclic group, we can apply the Diffie-Hellman procedure to come up with a secure key exchange. There are several attacks known to break Diffie-Hellman. One of these attacks is the Pollard Rho algorithm.

Vulnerabilities

It turns out that Diffie-Hellman can be broken by a quantum computer! In the next post, I’ll go over how we can use isogenies to to defend against quantum computer attacks.

References

[1] https://csclub.uwaterloo.ca/~dburbani/work/friendlysidh.pdf

[2] https://en.wikipedia.org/wiki/Diffie–Hellman_key_exchange