14 Diffie-Hellman Key Agreement

14.1 Cyclic Groups

Definition 14.1 Let д ∈ Zn∗ . Define hдin = {дi % n | i ∈ Z}, the set of all powers of д reduced mod n. Then д
is called a generator of hдin , and hдin is called the cyclic group generated by д mod n.
If hдin = Zn∗ , then we say that д is a primitive root mod n.
The definition allows the generator д to be raised to a negative integer. Since д ∈ Zn∗ ,
it is guaranteed that д has a multiplicative inverse mod n, which we can call д−1 . Then д−i
def
can be defined as д−i = (д−1 )i . All of the usual laws of exponents hold with respect to
this definition of negative exponents.
Example Taking n = 13, we have:
h1i13 = {1}
h2i13 = {1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7} = Z∗13
h3i13 = {1, 3, 9}
Thus 2 is a primitive root modulo 13. Each of the groups {1}, Z∗13 , {1, 3, 9} is a cyclic group
under multiplication mod 13.
A cyclic group may have more than one generator, for example:
h3i13 = h9i13 = {1, 3, 9}
Similarly, there are four primitive roots modulo 13 (equivalently, Z∗13 has four different gen-
erators); they are 2, 6, 7, and 11.
Not every integer has a primitive root. For example, there is no primitive root modulo
15. However, when p is a prime, there is always a primitive root modulo p (and so Zp∗ is a
cyclic group).

Let us write G = hдi = {дi | i ∈ Z} to denote an unspecified cyclic group generated by

д. The defining property of G is that each of its elements can be written as a power of д.
From this we can conclude that:
I Any cyclic group is closed under multiplication. That is, take any X , Y ∈ G; then
it must be possible to write X = дx and Y = дy for some integers x, y. Using the
multiplication operation of G, the product is XY = дx +y , which is also in G.
I Any cyclic group is closed under inverses. Take any X ∈ G; then it must be possible
to write X = дx for some integer x. We can then see that д−x ∈ G by definition, and
д−x X = д−x +x = д0 is the identity element. So X has a multiplicative inverse (д−x )
in G.
These facts demonstrate that G is indeed a group in the terminology of abstract algebra.

© Copyright Mike Rosulek. Creative Commons BY-NC-SA 4.0. Latest version at joyofcryptography.com.
 Draft: January 3, 2021 CHAPTER 14. DIFFIE-HELLMAN KEY AGREEMENT

Discrete Logarithms
It is typically easy to compute the value of дx in a cyclic group, given д and x. For ex-
ample, when using a cyclic group of the form Zn∗ , we can easily compute the modular
exponentiation дx % n using repeated squaring.
The inverse operation in a cyclic group is called the discrete logarithm problem:
Definition 14.2 The discrete logarithm problem is: given X ∈ hдi, determine a number x such that дx = X .
(Discrete Log) Here the exponentiation is with respect to the multiplication operation in G = hдi.

The discrete logarithm problem is conjectured to be hard (that is, no polynomial-time

algorithm exists for the problem) in certain kinds of cyclic groups.

14.2 Diffie-Hellman Key Agreement

Key agreement refers to the problem of establishing a private channel using public com-
munication. Suppose Alice & Bob have never spoken before and have no shared secrets.
By exchanging public messages (i.e., that can be seen by any external observer), they would
like to establish a secret that is known only to the two of them.
The Diffie-Hellman protocol is such a key-agreement protocol, and it was the first
published instance of public-key cryptography:
Construction 14.3 Both parties agree (publicly) on a cyclic group G with generator д. Let n = |G|. All exponen-
(Diffie-Hellman) tiations are with respect to the group operation in G.
1. Alice chooses a ← Zn . She sends A = дa to Bob.

2. Bob chooses b ← Zn . He sends B = дb to Alice.

3. Bob locally outputs K := Ab . Alice locally outputs K := B a .

Alice Bob
a ← Zn A = дa

B = дb b ← Zn

return B a return Ab

By substituting and applying standard rules of exponents, we see that both parties
output a common value, namely K = дab ∈ G.

Defining Security for Key Agreement

Executing a key agreement protocol leaves two artifacts behind. First, we have the col-
lection of messages that are exchanged between the two parties. We call this collection a
transcript. We envision two parties executing a key agreement protocol in the presence
of an eavesdropper, and hence we imagine that the transcript is public. Second, we have
the key that is output by the parties, which is private.

255
 Draft: January 3, 2021 CHAPTER 14. DIFFIE-HELLMAN KEY AGREEMENT

To define security of key agreement, we would like to require that the transcript leaks
no (useful) information to the eavesdropper about the key. There are a few ways to ap-
proach the definition:

I We could require that it is hard to compute the key given the transcript. However,
this turns out to be a rather weak definition. For example, it does not rule out the
possibility that an eavesdropper could guess the first half of the bits of the key.

I We could require that the key is pseudorandom given the transcript. This is a better
definition, and the one we use. To formalize this idea, we define two libraries. In both
libraries the adversary / calling program can obtain the transcript of an execution
of the key agreement protocol. In one library the adversary obtains the key that
resulted from the protocol execution, while in the other library the adversary obtains
a totally unrelated key (chosen uniformly from the set Σ.K of possible keys).

Definition 14.4 Let Σ be a key-agreement protocol. We write Σ.K for the keyspace of the protocol (i.e., the
(KA security) set of possible keys it produces). We write (t, K) ← execprot(Σ) to denote the process of
executing the protocol between two honest parties, where t denotes the resulting transcript, and
K is resulting key. Note that this process is randomized, and that K is presumably correlated
to t.
Σ
We say that Σ is secure if Lka-real ∼ Σ , where:
∼ Lka-rand
Σ
Lka-rand
Σ
Lka-real
qery():
qery():
(t, K) ← execprot(Σ)
(t, K) ← execprot(Σ)
K 0 ← Σ.K
return (t, K)
return (t, K 0)

14.3 Decisional Diffie-Hellman Problem

The Diffie Hellman protocol is parameterized by the choice of cyclic group G (and genera-
tor д). Transcripts in the protocol consist of (дa , дb ), where a and b are chosen uniformly.
The key corresponding to such a transcript is дab . The set of possible keys is the cyclic
group G.
Let us substitute the details of the Diffie-Hellman protocol into the KA security li-
braries. After simplifying, we see that the security of the Diffie Hellman protocol is equiv-
alent to the following statement:

Ldh-real
G
Ldh-rand
G

qery(): ∼
∼ qery():
a, b ← Zn a, b, c ← Zn
return (дa , дb , дab ) return (дa , дb , дc )

We have renamed the libraries to Ldh-real and Ldh-rand . In Ldh-real the response to qery
corresponds to a DHKA transcript (дa , дb ) along with the corresponding “correct” key

256
 Draft: January 3, 2021 CHAPTER 14. DIFFIE-HELLMAN KEY AGREEMENT

дab . The response in Ldh-rand corresponds to a DHKA transcript along with a completely
independent random key дc .
Definition 14.5 The decisional Diffie-Hellman (DDH) assumption in a cyclic group G is that Ldh-real
G ∼
∼
(DDH) Ldh-rand (libraries defined above).
G

Since we have defined the DDH assumption by simply renaming the security definition
for DHKA, we immediately have:
Claim 14.6 The DHKA protocol is a secure KA protocol if and only if the DDH assumption is true for
the choice of G used in the protocol.

For Which Groups does the DDH Assumption Hold?

So far our only example of a cyclic group is Zp∗ , where p is a prime. Although many
textbooks describe DHKA in terms of this cyclic group, it is not a good choice because the
DDH assumption is demonstrably false in Zp∗ . To see why, we introduce a new concept:
p−1
Claim 14.7 If p is a prime and X = дx ∈ Zp∗ , then X 2 ≡p (−1)x .
(Euler criterion)
Note that (−1)x is 1 if x is even and −1 if x is odd. So, while in general it is hard to
determine x given дx , Euler’s criterion says that it is possible to determine the parity of x
(i.e., whether x is even or odd) given дx .
To see how these observations lead to an attack against the Diffie-Hellman protocol,
consider the following attack:
A:
(A, B, C) ← qery()
? p−1
return 1 ≡p C 2

Roughly speaking, the adversary returns true whenever C can be written as д raised to
an even exponent. When linked to Ldh-real , C = дab where a and b are chosen uniformly.
Hence ab will be even with probability 3/4. When linked to Ldh-rand , C = дc for an indepen-
dent random c. So c is even only with probability 1/2. Hence the adversary distinguishes
the libraries with advantage 1/4.
Concretely, with this choice of group, the key дab will never be uniformly distributed.
See the exercises for a slightly better attack which correlates the key to the transcript.

Quadratic Residues. Several better choices of cyclic groups have been proposed in the
literature. Arguably the simplest one is based on the following definition:
Definition 14.8 A number X ∈ Zn∗ is a quadratic residue modulo n if there exists some integer Y such that
Y 2 ≡n X . That is, if X can be obtained by squaring a number mod n. Let QRn∗ ⊆ Zn∗ denote
the set of quadratic residues mod n.

For our purposes it is enough to know that, when p is prime, QRp∗ is a cyclic group with
(p − 1)/2 elements (see the exercises). When both p and (p − 1)/2 are prime, we call p a
safe prime (and call (p − 1)/2 a Sophie Germain prime). To the best of our knowledge the
DDH assumption is true in QRp∗ when p is a safe prime.

257
Draft: January 3, 2021 CHAPTER 14. DIFFIE-HELLMAN KEY AGREEMENT

Exercises
14.1. Let p be an odd prime, as usual. Recall that QRp∗ is the set of quadratic residues mod p
— that is, QRp∗ = {x ∈ Zp∗ | ∃y : x ≡p y 2 }. Show that if д is a primitive root of Zp∗ then
hд2 i = QRp∗ .
Note: This means that дa ∈ QRp∗ if and only if a is even — and in particular, the choice of
generator д doesn’t matter.

14.2. Suppose N = pq where p and q are distinct primes. Show that |QR∗N | = |QRp∗ | · |QRq∗ |.
Chinese remainder theorem.
Hint:

14.3. Suppose you are given X ∈ hдi. You are allowed to choose any X 0 , X and learn the
discrete log of X 0 (with respect to base д). Show that you can use this ability to learn the
discrete log of X .

14.4. Let hдi be a cyclic group with n elements and generator д. Show that for all integers a, it
is true that дa = дa%n .
Note: As a result, hдi is isomorphic to the additive group Zn .

14.5. Let д be a primitive root of Zn∗ . Recall that Zn∗ has ϕ(n) elements. Show that дa is a primitive
root of Zn∗ if and only if gcd(a, ϕ(n)) = 1.
Note: It follows that, for every n, there are either 0 or ϕ(ϕ(n)) primitive roots mod n.

14.6. Let hдi be a cyclic group with n elements. Show that for all x, y ∈ hдi, it is true that
x n = yn .
Every x ∈ hдi can be written as x = дa for some appropriate a. What is (дa )n ?
Hint:

14.7. (a) Prove the following variant

√ of Lemma 4.10: Suppose you fix a value x ∈ ZN . Then
when sampling q = 2N values r 1 , . . . , r q uniformly from ZN , with probability at
least 0.6 there exist i , j with r i ≡N r j + x.
(b) Let д be a primitive root of Zp∗ (for some prime p). Consider the problem of computing
the discrete log of X ∈ Zp∗ with respect to д — that is, finding x such that X ≡p дx .
Argue that if one can find integers r and s such that дr ≡p X ·дs then one can compute
the discrete log of X .
√
(c) Combine the above two observations to describe a O( p)-time algorithm for the dis-
crete logarithm problem in Zp∗ .

14.8. In an execution of DHKA, the eavesdropper observes the following values:

p = 461733370363 A = 114088419126
д=2 B = 276312808197

What will be Alice & Bob’s shared key?

14.9. Explain what is wrong in the following argument:

258
Draft: January 3, 2021 CHAPTER 14. DIFFIE-HELLMAN KEY AGREEMENT

In Diffie-Hellman key agreement, Alice sends A = дa and Bob sends B = дb . Their

shared key is дab . To break the scheme, the eavesdropper can simply compute
A · B = (дa )(дb ) = дab .

14.10. Let G be a cyclic group with n elements and generator д. Consider the following algorithm:

rand(A, B, C):
r, s, t ← Zn
A0 := At дr
B 0 := Bдs
C 0 := C t B r Ast дr s
return (A0, B 0, C 0)

Let DH = {(дa , дb , дab ) ∈ G3 | a, b, ∈ Zn }.

(a) Suppose (A, B, C) ∈ DH . Show that the output distribution of rand(A, B, C) is the
uniform distribution over DH
(b) Suppose (A, B, C) < DH . Show that the output distribution of rand(A, B, C) is the
uniform distribution over G3 .
? (c) Consider the problem of determining whether a given triple (A, B, C) is in the set DH .
Suppose you have an algorithm A that solves this problem on average slightly better
than chance. That is:

Pr[A(A, B, C) = 1] > 0.51 when (A, B, C) chosen uniformly in DH

Pr[A(A, B, C) = 0] > 0.51 when (A, B, C) chosen uniformly in G3

The algorithm A does not seem very useful if you have a particular triple (A, B, C) and
you really want to know whether it is in DH . You might have one of the triples for
which A gives the wrong answer, and there’s no real way to know.
Show how to construct a randomized algorithm A 0 such that: for every (A, B, C) ∈ G3 :
?
h i
Pr A 0(A, B, C) = [(A, B, C) ∈ DH ] > 0.99

Here the input A, B, C is fixed and the probability is over the internal randomness in
A 0. So on every possible input, A 0 gives a very reliable answer.

to-do better attack against Zp∗ instantiation of DHKA

259