Groups and Diffie-Hellman

A small detour in cryptography

This article is a bit of an oddball—on the one hand, it is a continuation of my series on group theory. The last lecture was on the notion of isomorphism.

When are Two Groups the Same Group?

On the other hand, this is meant to be a (largely) standalone post, detailing how group theory can be a useful tool for reasoning about cryptography. So, if you haven’t been following the larger series, don’t worry too much: we’ll try to get you up to speed. You really just need to know what a group is—if you need a refresher, you can look at the very first post in the series.

Where are Groups? What are Groups? Why are Groups?

The cryptographical task that we will try to tackle is this: how can another person and I share private information over a public channel? Let’s go with a slightly toy example (I will explain at the end why you would want something a little different for this in reality): let’s say that I want to make some sort of transaction online—for concreteness, let’s say that I want to buy the book Introduction to Mathematical Logic by Mendelson from Amazon. I want to be able to send Amazon my financial information so that they can withdraw the funds from my bank account. I also want to send them my address so that they know where to ship it. However, I absolutely do not want anyone else to be able to see any of that information.

If Amazon and I had some sort of private communication channel, this would be easy. Unfortunately, I can’t afford a personal fiber-optic cable running from my house to Amazon HQ, and I have been cautioned that roving packs of bears to discourage anyone approaching the cable to mess with it might not actually be legal. So, instead, I am forced to send all of my messages over the Internet, where anyone can read them.¹

That in itself need not be a problem. If Amazon and I had some kind of secret key—a password of some kind—then we could use it to encode our messages such that only we could decode them. But I don’t think I have ever met anyone who works for Amazon. And, to be frank, I have no desire to drive over to Amazon HQ to get a secret key from them—that would completely defeat the point of ordering a book online. So, the question is: how can we communicate with one another over a public channel and thereby produce secret keys that no one else knows?

On the face of it, this may seem impossible. It is not! This was first established by James H. Ellis, Clifford Cocks, and Malcolm J. Williamson in 1969—however, since they were working in secret for British intelligence, credit is often given to Diffie and Hellman, who published the first paper on the subject in 1976.

Photograph of Whitfield Diffie by Wikimedia user Duncan.Hull, shared under the CC BY-SA 4.0 license. I don’t know if he is always so immaculately dressed, but the one time I met him at a conference, he certainly was.

Very abstractly, the way that the Diffie-Hellman key exchange protocol works is that the two participants—named Alice and Bob, for historical reasons—both create a key using some information that they keep private. Then, they send each other their keys. Finally, they combine the two keys together, using the information that they kept private to do it. The end result is that they both have a common secret key.

Okay, but how do you actually do that? The secret ingredient is the discrete logarithm problem.²

The regular logarithm problem is this: if I am given a real number r and told to find b such that r=a^b for some given a>0, how can I do that? This is what the logarithm does: b=log_a(r). There are plenty of algorithms for quickly computing logarithms, so this is a very feasible problem even when r, a, and b are quite large.

The discrete logarithm problem is this: if I am given an element g of a group G and told to find an integer n such that g=hⁿ (that is, h multiplied by itself n times), how can I do that? …This is much harder.

Let me give an example. I might start with the group GL(2, ℝ) (that is, the collection of invertible 2×2 real matrices) and take an element

\(h=\begin{pmatrix} 1 &1 \\ 1 & 0 \end{pmatrix}.\)

I then compute

\(\begin{align*} h^2&=\begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix} \\ h^3&=\begin{pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix} \\ h^4&=\begin{pmatrix} 5 & 3 \\ 3 & 1 \end{pmatrix} \\ g:=h^5&=\begin{pmatrix} 8 & 5 \\ 5 & 3 \end{pmatrix} \end{align*}\)

and I send this last matrix g to my friend Alex. I then ask Alex to figure out the n such that g=hⁿ.

Can Alex do that? Well, n=5 is small enough that he should be able to determine it just by brute force. What if I were to send along the matrix

\(g= \begin{pmatrix} 20365011074 & 12586269025 \\ 12586269025 & 7778742049 \\ \end{pmatrix}?\)

Can Alex (or the reader) figure out what n is for this example? This is trickier, but it is possible to do. (There are a couple of reasonable approaches. Those who are stuck are welcome to ask for hints in the comments.)

What we will want is a group that satisfies the following properties:

1. Given an element h of the group, it should be easy to compute hⁿ even for very large n³.

2. The discrete logarithm problem should be hard: that is, given h and g=hⁿ, it should take a long time to compute n, in general.

It is far from obvious that even one such group exists. We’ll return to that later—for now, take it as given that there is such a group. We can now explain how the Diffie-Hellman key exchange works, step-by-step.

1. Alice and Bob choose a group G with the above two properties, and a base element h. This is done completely publicly.

2. Alice chooses a large integer m at random; Bob chooses a large integer n at random. They do not share this.

3. Alice computes a=h^m and sends it to Bob; Bob computes b=hⁿ and sends it to Alice. This is public.

4. Alice computes b^m=(hⁿ)^m=h^nm—this is her private key; Bob computes aⁿ=(h^m)ⁿ=h^mn—this is his private key.

Observe that, at the end, both Alice and Bob have the same private key h^mn, which they can use to communicate with each other. But if someone (called Eve, also for historical reasons) is listening in to their communication, they cannot work out what this private key is. Why?

Eve knows a and b, but to compute h^mn, she needs to determine either m or n⁴, and for that, she needs to solve the discrete logarithm problem. Per our assumption, this will take her a very long time.⁵

So that’s it… except that I still haven’t given you an example of a group that satisfies the desired properties! Let’s try to build one. We’ll start with something almost maximally simple: the integers modulo N.

If you missed the last set of notes, for any integer N≥2, ℤ/Nℤ denotes the collection {0, 1, 2,… N−1}, with the rule that if we add two elements together and get something that is too large, we subtract by multiples of N until we get back to the desired place. This is how arithmetic works on a clock: we add together hours by subtracting 12 if they go over. Thus, if it is 4 o’clock now, in 9 hours it will be 4+9=13=13−12=1 o’clock.

This group is cyclic: there exists an element g, called a generator, such that every other element is of the form gⁿ. In this case, we could take g=1⁶, since

\(\begin{align*} g^0 &= 0 \\ g^1 &= 1 \\ g^2 &= 1 + 1 = 2 \\ g^3 &= 1 + 1 + 1 = 3\\ &\vdots \\ g^{N-1} &= 1+1+\ldots+1=N-1. \end{align*}\)

Remember: gⁿ means that we are applying the group operation n times with g. In this case, the operation is addition.

However, if we were to use g=1, the discrete logarithm problem would be trivially easy, since the power n and the element gⁿ are the same! So this is unusable.

Perhaps, we could switch to a different generator? After all, 1 isn’t the only possible choice. For example, 3 is a generator for ℤ/7ℤ since

\(\begin{align*} g^0 &= 0 \\ g^1 &= 3 \\ g^2 &= 3 + 3 = 6 \\ g^3 &= 6 + 3 = 2 \\ g^4 &= 2 + 3 = 5 \\ g^5 &= 5 + 3 = 1 \\ g^6 &= 1 + 3 = 4. \end{align*}\)

We still go through the whole group, just in a different order. In general, an element g is a generator of ℤ/Nℤ if and only if it is coprime with N—that is, their largest common factor is 1. We’ll prove this in a minute.

So, here’s how we might update our scheme. Let’s take a large integer N—say,

132169022476074213628073181268002790966934499515294506175269227084753197010308342510617195217740154889982274549903613006045791204991797842802377748564320138582677961709468815250621624258855578855517809028855944711783670919742827454916233879324532242975156857011396808988418328787863093638716516710112158547969.

And we’ll choose some random integer g that is coprime with N—in this case, we could use

75930395193476526623976683112168924223129883638360229644403020165261773865063415161988251795642457933176586032066569480514731032236981897873212657040072000020472359781461629259325912924689890857592946715651185200475579838034374666375224381737249729717967672080852142553512397047611228420082142559014342150957.

(You may well ask how on Earth I know that they are coprime. We’ll get to this in a second.)

Now, if I choose m randomly and compute g^m, it is much less obvious what m is we if we don’t already know. For example, if

m=52606559220074264007722128547173448656546287874443364894952628989352364824380186242668493342951321663144694360568814954405788307593499570019227245675247611430447619037403263919872425765240047061076524410556999643860570213432592370030564173400636318449803080247262711751706766220121993341664474449430609360957

then

g^m=126991081320938267205839338191849521814362217735174735430402859043456883542763593268725210662042688243032220230656742944360666624262843579489270243153445426727294311594720947989481767049684777289626753117782357767165098999394241807285611945170751155896623436321656235131192347708598143356198512856852881287063.

(This computation is very easy: you just need to multiply g and m and then take the remainder when dividing by N. I wouldn’t want to do it by hand, but a computer will do it in less than a millisecond.) This just looks like a random assortment of digits! Have we found an example of a group where the discrete logarithm problem is hard?

Unfortunately, no, and the reason why is a pretty old piece of number theory: namely, Bézout’s identity⁷ This says that given any two integers a and b, one can find integers x and y such that

\(ax+by=f,\)

where f is the greatest common factor of a and b. Moreover, this can be done completely constructively and quite quickly using the extended Euclidean algorithm. So, first of all, this is how we can tell whether two integers are coprime or not; second, if we are given g and a=gⁿ, what we can do is to first compute x and y such that

\(gx+Ny=1.\)

this is possible since g and N are coprime. Then, multiply both sides by a. We get

\(gax+Nay=a,\)

or

\(gax=a-Nay.\)

But that is just to say that g^ax=a, once you expand out what that means. (Remember: in ℤ/Nℤ, we can simply reduce by multiples of N.) We have computed the logarithm—it is ax!

Curses! This is trickier than it may first appear. But there is a light in the darkness: the failure of this naive attempt has demonstrated a path forward.

Consider the set (ℤ/Nℤ)^×, the collection of elements in ℤ/Nℤ that are coprime with N. What Bézout’s identity tells us is that for any such element a, we can find integers x, y such that ax+Ny=1. But this is just to say that x is the inverse of a in (ℤ/Nℤ)^×, with respect to multiplication (subject to the same rule that we can add/subtract multiples of N without issue). Since it is fairly straightforward to check that multiplication gives an associative operation on (ℤ/Nℤ)^×, and it is clear that 1 is the identity, we can therefore conclude that (ℤ/Nℤ)^× is a group!

What does this group look like? Well, that depends on what N is. For example, when N=11, this group is comparatively easy to understand: 1, 2, …, 10 are all coprime with 11, so there are exactly 9 elements. Furthermore, this group is cyclic! You can check that every element is a power of 2, although they go around the elements in (ℤ/11ℤ)^× in a somewhat chaotic way.

The powers of 2 inside (ℤ/11ℤ)^×.

On the other hand, (ℤ/12ℤ)^× is extremely different. It only has 4 elements: 1, 5, 7, 11. And it isn’t at all cyclic, because each of these elements squares to the identity.

An analogous diagram for (ℤ/12ℤ)^×. Two nodes are connected by a blue arrow if one can get the other by multiplying by 5; two nodes are connected by an orange arrow if one can get the other by multiplying by 11.

If we want a group for which there is a chance that the discrete logarithm problem is hard, it should be more like (ℤ/11ℤ)^× than (ℤ/12ℤ)^×, for a couple of reasons. First, we want to maximize the number of elements in the group: if there are too few, it will be easy to go through all possibilities. Secondly, we want there to be an element g such that the smallest n>0 such that gⁿ=1 is pretty large—otherwise, again, it will be too easy to go through all possibilities and find the logarithm that way.

Here’s the amazing thing: as long as p is prime, (ℤ/pℤ)^× will have p-1 elements and will be cyclic. The first fact is immediate; the second is decidedly non-trivial! But it actually gets even better: there are algorithmic ways in which you can produce the large primes p together with the generators g of (ℤ/pℤ)^×, and on modern hardware, this can be done in less than a second. So, using a bit of Python that I wrote myself, I was able to determine that

p=132169022476074213628073181268002790966934499515294506175269227084753197010308342510617195217740154889982274549903613006045791204991797842802377748564320138582677961709468815250621624258855578855517809028855944711783670919742827454916233879324532242975156857011396808988418328787863093638716516710112158547969

is a prime and

g=75930395193476526623976683112168924223129883638360229644403020165261773865063415161988251795642457933176586032066569480514731032236981897873212657040072000020472359781461629259325912924689890857592946715651185200475579838034374666375224381737249729717967672080852142553512397047611228420082142559014342150957

is a generator of (ℤ/pℤ)^×.

How was I able to do it? That’s a much harder question: I personally use this and the fact that (ℤ/pℤ)^× is cyclic as the culmination of a course on elementary number theory.⁸ I will eventually write up my notes from the number theory courses I taught; in the meantime, I will ask that the reader accept this as a black box. (Or you can look up proofs that (ℤ/pℤ)^× is cyclic—it isn’t like there is a shortage of resources on the Internet.)

In any case, what we can now do is to choose a random integer 2≤n≤p-2 and compute gⁿ in (ℤ/pℤ)^×. This can be done very quickly thanks to fast modular exponentiation. But then, as far as we know, there is no fast way to determine n if you only know g and gⁿ—the discrete logarithm problem is conjectured to be difficult for (ℤ/pℤ)^×. Certainly, you aren’t going to make any headway doing this via brute force: since we chose our prime to be on the order of 2¹⁰²⁴≈10³⁰⁸, even if you were able to check each exponent in a tenth of a millisecond, it would still take you over 10²⁹⁶ years to go through all of the possibilities. If you (somewhat optimistically) assume that Moore’s law will mean that the time it takes to do this operation will halve every two years, it will still take almost 2000 years.

This is the most common way that the Diffie-Hellman key exchange is implemented in the modern day.

---

Having described the Diffie-Hellman key exchange, what are our takeaways?

First, we might ask why we need to get group theory mixed up in this at all: I could have just started with (ℤ/pℤ)^× without ever taking about groups at all. This is true, but we would miss some nice benefits:

1. Starting with groups means that we don’t need to get bogged down with the details too early: we can see the big picture first, and then start working out how to make it workable.

2. Because we started with an abstract, group-theoretic viewpoint, we aren’t married to the group (ℤ/pℤ)^×—we could easily replace it with something else. While Diffie-Hellman is most commonly implemented with this group, it is also sometimes implemented using elliptic curves. But that just amounts to switching out one group for another.

3. From a cryptographic point of view, having the ability to swap out groups is useful, especially since we lack a proof that the discrete logarithm problem is difficult for any particular group. If, tomorrow, someone discovers a fast algorithm to compute the logarithm over (ℤ/pℤ)^×, all is not lost: we simply look for a different group where this problem is not solved yet, and switch to that.

Secondly, if you have been following the group theory notes, you might notice that there is something a little strange here. We said that (ℤ/pℤ)^× has p-1 elements and that it is cyclic—that means it is isomorphic to ℤ/(p-1)ℤ. But we showed that the discrete logarithm problem is trivially easy for the latter—if these are “the same” group, how can this problem be difficult for (ℤ/pℤ)^×?

The explanation is that (ℤ/pℤ)^× and ℤ/(p-1)ℤ are the same as groups. But when we ask about the difficulty of the discrete logarithm problem, we are asking about additional structure beyond what they are like as groups: we want to know how the elements of these groups are represented in bits, and what are the algorithms for multiplying elements together.

“Okay,” you might say. “But we still have an isomorphism between these two groups. Why can’t I use this isomorphism to turn elements in (ℤ/pℤ)^× into elements in ℤ/(p-1)ℤ, solve the discrete logarithm problem in the setting where it is easy, and then use the isomorphism to move everything back into (ℤ/pℤ)^×?”

You can! But, how quickly can you compute what the image of a random element in (ℤ/pℤ)^× is inside of ℤ/(p-1)ℤ? We don’t know of any fast way to do it! You can do it by brute force, but that will take you over a thousand years.

The big picture is this: group isomorphisms preserve group properties. Isomorphic groups are guaranteed to be the same when considered as groups; they might be very different if you ask about other types of properties.

One final note before I end this post: while the Diffie-Hellman protocol is a fundamental building block in cryptography, in practice you likely don’t want to use it in quite the way that I described—i.e., you don’t want to use it to directly contact Amazon to buy your book. This is because the pure Diffie-Hellman protocol is susceptible to man-in-the-middle attacks: if someone intercepted my messages to Amazon in the very beginning, and pretended to be me to Amazon and Amazon to me, they would become privy to all of our private correspondence. To make this workable, you need additional protocols to verify that you are actually talking to your desired party. And for the specific application mentioned, you most likely want to use something called RSA, because Amazon has many clients, and RSA gives a way for them to publish a public key that anyone can use to contact them securely. However, there are plenty of similar applications where Diffie-Hellman is used instead.

1. With how ubiquitous cryptographic protection is, it can be easy to miss, but sending a message over the Internet is a bit like crowd surfing: your message is split up into little packets, all of which are passed along by a series of routers that no one entity owns or controls.

2. Okay, okay: this is a lie-to-children. In reality, you need the closely related Diffie-Hellman problem. I’ll discuss the difference in a second.

3. I’m not going to be too precise about what I mean by “large”, or “quickly”, for that matter. Usually, this is stated formally by asking that there is a polynomial-time algorithm.

4. Actually, this is an interesting problem: are we sure that there is no other way to determine h^mn? Nobody knows of one, but technically, this is a separate problem, known as the Diffie-Hellman problem, alluded to earlier. If you can solve the discrete logarithm problem, you can definitely solve the Diffie-Hellman problem, but it is theoretically possible that the Diffie-Hellman problem is solvable even if the discrete logarithm problem isn’t.

5. Yes, given enough time and computing power, Eve will eventually decode Alice and Bob’s messages. This is true of all modern cryptography. The goal is to make it so that this decoding process will take decades, centuries, or millennia, depending on the importance of the data.

6. This is one place where using “1” to mean the group identity can be a little confusing. For this group, the identity is 0, and 1 is a different element entirely.

7. Although, Bézout isn’t the one who came up with this identity for integers—he worked on the case of polynomials. For integers, it was already implicit in Euclid’s Elements; a constructive version via the extended Euclidean algorithm was found by Indian mathematician Aryabhata around the 5th or 6th century CE.

8. I believe the proof of quadratic reciprocity is more common, but I have good reasons for my choice. While quadratic reciprocity is beautiful, it is less immediately useful, and the proof is much harder to motivate—Gauss came up with eight different proofs for it, and one can guess that it was because he felt dissatisfied with each one.