5.5: Diffie-Helman Key Exchange

$\newcommand{\NN}{\mathbb N}$
$\newcommand{\RR}{\mathbb R}$
$\newcommand{\QQ}{\mathbb Q}$
$\newcommand{\ZZ}{\mathbb Z}$
$\newcommand{\Cc}{\mathcal C}$
$\newcommand{\Dd}{\mathcal D}$
$\newcommand{\Ee}{\mathcal E}$
$\newcommand{\Ff}{\mathcal F}$
$\newcommand{\Kk}{\mathcal K}$
$\newcommand{\Mm}{\mathcal M}$
$\newcommand{\Pp}{\mathcal P}$
$\newcommand{\ind}{\operatorname{ind}}$
$\newcommand{\ord}{\operatorname{ord}}$

About a year before the RSA cryptosystem was invented, Whitfield Diffie and Martin Hellman published New directions in cryptography [DH76], the first full description of a working public key cryptosystem in the open scientific literature.¹ They defined in this paper something which has since been named after them:

Definition: Diffie-Hellman Key Exchange

The following protocol is called Diffie-Hellman key exchange [DHKE]:

1. Alice and Bob agree upon a large prime $p$ and a primitive root $r\in(\ZZ/p\ZZ)^*$ and publish both.
2. Alice chooses an $\alpha\in\ZZ$ satisfying $1\le\alpha\le p-1$, computes $A=r^\alpha\pmod{p}$, keeps $\alpha$ secret, but publishes $A$.
3. Bob chooses a $\beta\in\ZZ$ satisfying $1\le\beta\le p-1$, computes $B=r^\beta\pmod{p}$, keeps $\beta$ secret, and publishes $B$.
4. Alice gets the public value $B$ and computes $S=B^\alpha$.
5. Bob gets $A$ and computes the same value $S=A^\beta$.
6. Both Alice and Bob use the shared secret $S$ for future communications encrypted with some symmetric cryptosystem upon which they had previously agreed.

The value $S$ which both Alice and Bob have [but Eve does not] is called their shared key or shared secret.

Here is a graphical representation:

Diffie-Hellman Key Exchange:

Alice	on public network	Bob
	pick a prime $p$
	find a primitive root $r$
pick $\alpha$, compute		pick $\beta$, compute
$A=r^\alpha\pmod{p}$		$B=r^\beta\pmod{p}$
publish $A$	$\rightarrowtail A$ $B\leftarrowtail$	publish $B$
get $B$, compute		get $A$, compute
$S=B^\alpha\pmod{p}$		$S=A^\beta\pmod{p}$
$\Longleftarrow===================== \text{assymteric crypto with key } S =====================\Longrightarrow$

Proposition $\PageIndex{1}$

When Alice and Bob follow the DHKE protocol, they both compute the same shared key; i.e., DHKE works.

Proof

There’s very little to check here: using the notation of the definition and, in the very middle, the commutativity of multiplication, we have $$B^\alpha = \left(r^\beta\right)^\alpha = r^{\beta\cdot\alpha} = r^{\alpha\cdot\beta} = \left(r^\alpha\right)^\beta = A^\beta\ .$$ The left end of this equality is the $S$ that Alice computes, while the right end is the one that Bob computes, and they are the same.

Example $\PageIndex{1}$

Alice and Bob agree in open, public discussion to use the prime $p=617$ and its primitive root $r=17$.

Alice privately chooses her secret value $\alpha=19$ and sends the value $$A=17^{19}\equiv385\pmod{617}$$ to Bob by insecure e-mail. (All unencrypted e-mail is insecure, of course.)

Bob chooses his secret value $\beta=13$ and sends the value $$B=17^{13}\equiv227\pmod{617}$$ to Alice by insecure e-mail.

Alice computes the shared secret $$S=B^{\alpha}=227^{19}\equiv127\pmod{617}\ .$$

Bob computes the same shared secret instead by $$S=A^{\beta}=385^{13}\equiv127\pmod{617}\ .$$

They then can use this value to do symmetric crypto for the rest of this communication.

What about the practicality of DHKE? As was discussed in Section 4.4, finding a the [large] prime $p$ (we continue using the notation in Definition of Diffie-Hellman Key Exchange) is computationally feasible, as are the several modular exponentiations in the DHKE protocol. There remains the question of finding the primitive root $r$.

One way is to avoid searching for $r$ more than once. After one prime $p$ and an associated primitive root $r$ for $p$ are found, each user can choose their secret (Alice’s $\alpha$ and Bob’s $\beta$), without overlap or conflict. This is the approach suggested in some Internet standards, see, e.g., [HC] and [LK08].

Another, more mathematical, strategy is based on the following definition, which we give because of its independent mathematical interest and the amazing life of its namesake.

Definition: Sophie Germain Prime

A prime $p$ with the property that $2p+1$ is also a prime is called a Sophie Germain prime.

It is not known how many Sophie Germain primes there are, although it is conjectured that there are an infinite number. In fact, there are precise conjectures on the asymptotic density of such primes, as well as algorithmic techniques to generate them efficiently; see [Sho09].

The first seventeen Sophie Germain primes are

$$2,\ 3,\ 5,\ 11,\ 23,\ 29,\ 41,\ 53,\ 83,\ 89,\ 113,\ 131,\ 173,\ 179,\ 191,\ 233,\ 239 \nonumber$$

The sequence of all Sophie Germain primes is sequence A005384 at the On-Line Encyclopedia of Integer Sequences, oeis.org.

The largest known Sophie Germain prime, at the time of this writing, is

$18543637900515\times2^{666667}-1$

discovered in $2012$ by Philipp Bliedung and a large distributed network of computers.

The reader is asked to investigate the usefulness of Sophie Germain primes in DHKE is explored in the exercises, below.

As mentioned in the last section 5.4, DHKE depends for its security on modular exponentiation be a one-way function: feasible to compute forwards (by fast modular exponentiation) but infeasible to computer backwards (which is an index).

If discrete logs could be computed by a feasible algorithm, then Eve could completely break the security of DHKE. Starting with the public values of $A$ and $B$, she would compute $\alpha=\ind_r(A)$ and $\beta=\ind_r(B)$. She could then compute $S$ as either $B^\alpha$, $A^\beta$, or, directly, as $r^{\alpha\cdot\beta}$. Having $S$, she could decrypt all of Alice and Bob’s communications as they go by.

Actually, it is not necessary for Eve to be able to compute discrete logs, as long as she can solve a specific computation problem.

Definition: Diffie-Hellman Problem

The Diffie-Hellman problem [DHP] consists of the following question: Given

• a prime $p$,
• a primitive root $r\in(\ZZ/p\ZZ)^*$, and
• two elements $a,b\in(\ZZ/p\ZZ)^*$ which are known to be of the form $a=r^x$ and $b=r^y$ for $x,y\in\NN$, although the $x$ and $y$ are not known

compute

• $r^{xy}$ .

An efficient way to compute discrete logs would of course result in a solution of the Diffie-Hellman problem, but it is not known if there might be a solution of the DHP which is does not consist of a full-blown algorithm to compute discrete logs. Since this question is open as of this writing, it makes sense to make the most precise statement: breaking DHKE amounts of solving the DHP, which is not feasible on a classical computer².

DHKE is one of the most widely used cryptologic protocols on the Internet. It is part of SSL, TLS, SSH, IPsec, and many VPNs, among others.

Exercise $\PageIndex{1}$

1. Suppose you had an efficient algorithm to generate large Sophie Germain primes. Describe how you would use this to do the initial choice of public parameters for DHKE – go through all of the set-up stages of this protocol, and explain how each can be done feasibly, based on either past discussions of calculations we can do feasibly or on new ideas you develop here.

2. The number $p=11717$ is prime, and $r=103$ is a primitive root of this $p$. Playing the role of Alice, your instructor computed $A=5123$.

Please play the role of Bob and do what is necessary to establish a shared key with your instructor: you compute $S$ as in DHKE, and send your $B$ by e-mail so that your instructor can also compute $S$. Then await further instructions by return e-mail, encrypted with the shared secret.

You may need to perform calculations that are hard to do on a hand calculator. If you have access to, and are familiar with, some computer system like Octave, Matlab, or Mathematica, you should be able to do the calculations that way. Otherwise, you might try using your favorite search engine on the phrase “fast modular exponentiation applet”, or using wolframalpha.com.

3. Spell out in precise, mathematical detail all of the steps which would be used in a man-in-the-middle attack against DHKE.

Notes

1. Although in fact, some workable public key crypto had been invented earlier within the US/UK intelligence community, and not shared with the public. Since quite early in the Cold War, there have been mathematical theorems and proofs held in secret by large governments.

2. As is the case with factoring, there is a known algorithm for a quantum computer which solves the DHP efficiently, see [Sho94].