Group-based cryptography

In this blog post I will discuss the mathematical concept of a group, and I’ll give an example of an actual cryptosystem based on groups. I’ll try to keep the mathematical jargon to a minimum, and give illustrative examples where possible.

Group theory 101

A group is a very general mathematical structure defined as follows. Let G be a set, and let • be a binary operation on G—basically a function which takes two elements of G and gives an element of G back, like addition or multiplication on the integers. We say that (G, •) is a group if the following conditions are satisfied:

  1. Associativity: For every x, y and z in G, (xy) • z = x • (yz).
  2. Identity element: There is a unique e in G (called the identity element of G) such that for every x in G, xe = x.
  3. Inverse elements: For every x in G, there is a unique y in G (called the inverse of x) such that xy = e.

If I’ve lost you with all of the symbols and jargon, a concrete example might be illuminating. Consider the set of integers Z and the binary operation +. We know that if we add three integers together, it doesn’t matter which addition we do first. For example, if we’re computing 1 + 2 + 5, we could first compute 1 + 2 = 3 and then 3 + 5 = 8, or we could first compute 2 + 5 = 7 and then 1 + 7 = 8. This is associativity. The identity element is 0 (add it to any number and you get that number back), and so the inverse of any integer is simply its negative: 4 + (-4) = 0. We may conclude that (Z, +) is a group, since it satisfies all the group conditions. In fact, groups originated as an abstraction of numerical arithmetic.

Another example of a group, and one very important for cryptography, is the multiplicative group of integers modulo p, denoted (Z_p, ·). This is essentially the set of numbers {1, 2, …, p – 1} furnished with the usual · operation, but where the result “wraps around” if it is bigger than p – 1. For example, in Z_5 we would have 2 · 4 = 8 = 3 and 4 · 4 = 16 = 1. Associativity is inherited from the usual integer multiplication. The identity element is clearly 1. It is not clear why every element of Z_p has an inverse, but this is a standard result from elementary number theory. Using Z_5 as an example again, we see that 1 · 1 = 1, 2 · 3 = 6 = 1 and 4 · 4 = 1, so each element has an inverse.

Before continuing to the next section, we define exponentiation for groups. Let G be a group and let x be an element of G. We define x^n = xx • … • x (n times) for any positive integer n. We extend this to all integers by letting x^0 = e and letting x^(-n) be the inverse of x^n. You may check that the familiar exponentiation laws then hold (i.e. x^mx^n = x^(m + n) and (x^m)^n = x^(mn)).

The discrete logarithm problem

Now that we have the basics of group theory down, we may define the discrete logarithm problem for groups, which reads as follows. Let G be a group with some element x and let n be an integer. Given the group elements x and x^n, determine the value of the exponent n. This is analogous to finding the logarithm to the base x of x^n. In the group Z, this is trivial: if you have x and x^n = x + x + … + x (n times) = nx, then you can find n by simple division. However, in Z_p, the problem becomes harder. No polynomial-time algorithms are known for solving discrete logarithms in Z_p (but some sub-exponential algorithms are known). In other groups, the state-of-the-art algorithms can solve discrete logarithms only in exponential time.

The Diffie-Hellman problem

The Diffie-Hellman problem is a slightly easier version of the discrete logarithm problem defined as follows. Let G be a group with some element x, and let m and n be integers. Now given the group elements x, x^m and x^n, we wish to find x^(mn). Clearly, if the discrete logarithm problem may be solved efficiently for G, then we may compute m and n efficiently, and thus compute x^(mn). However, there might be some clever method of combining x^m and x^n to form x^(mn) without first computing their exponents. This is why we say that Diffie-Hellman is an easier problem. For Z_p, no such method is known, as is true for many other groups, so that these two problems are actually equivalent in practice.

The Diffie-Hellman key exchange

We are now ready to define a group-based cryptosystem, called the Diffie-Hellman key exchange, which will be the conclusion of this post. Assume we have three parties: Alice, Bob and Eve. Alice and Bob wish to agree on some secret value, in such a way that if Eve were to eavesdrop on all of their communications, she would not be able to figure out what this value is. They will do so as follows. First, they agree on a very large group G in which the Diffie-Hellman problem is hard, and they pick some element x in G. Now, Alice computes a large random integer a, and Bob similarly computes b. They keep these values to themselves, but they tell each other the values of x^a and x^b. Now, Alice has the values a and x^b at her disposal, so she may compute (x^b)^a = x^(ab). Similarly, Bob my compute x^(ab) using b and x^a. Eve only knows the values of x, x^a and x^b. Should she wish to compute x^(ab), she will have to solve the Diffie-Hellman problem, which we assumed to be hard in G. Thus, Alice and Bob have succeeded in agreeing on a secret value.

, ,

No comments yet.

Leave a comment

Leave a Reply