Groups and Diffie-Hellman - by Senia Sheydvasser

The Deranged Mathematician

SubscribeSign in

Groups and Diffie-Hellman<br>A small detour in cryptography

Senia Sheydvasser<br>Jun 03, 2026

12

11

Share

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?<br>Senia Sheydvasser<br>May 27

Read full story

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?<br>Senia Sheydvasser<br>May 6

Read full story

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.<br>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.1<br>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?<br>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.<br>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.<br>Okay, but how do you actually do that? The secret ingredient is the discrete logarithm problem.2<br>The regular logarithm problem is this: if I am given a real number r and told to find b such that r=ab for some given a>0, how can I do that? This is what the logarithm does: b=loga(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.<br>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=hn (that is, h multiplied by itself n times), how can I do that? …This is much harder.<br>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<br>\(h=\begin{pmatrix} 1 &1 \\ 1 & 0 \end{pmatrix}.\)

I then compute<br>\(\begin{align*}<br>h^2&=\begin{pmatrix} 2 & 1 \\ 1 & 0 \end{pmatrix} \\<br>h^3&=\begin{pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix} \\<br>h^4&=\begin{pmatrix} 5 & 3 \\ 3 & 1 \end{pmatrix} \\<br>g:=h^5&=\begin{pmatrix} 8 & 5 \\ 5 & 3 \end{pmatrix}<br>\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=hn.<br>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<br>\(g=<br>\begin{pmatrix}<br>20365011074 & 12586269025 \\<br>12586269025 & 7778742049 \\<br>\end{pmatrix}?\)

Can Alex (or the...