Chapter 14: Diffie-Hellman Key Agreement

 Return to Table of Contents

14.1: Cyclic Groups

Definition 14.1

Let g ∈ ℤ^∗_n. Define ⟨g⟩n = {gⁱ % n| i ∈ ℤ}, the set of all powers of g reduced mod n. Then g is called a generator of ⟨g⟩_n, and ⟨g⟩_n is called the cyclic group generated by g mod n.

If ⟨g⟩_n = ℤ^∗_n , then we say that g is a primitive root mod n.

The definition allows the generator g to be raised to a negative integer. Since g ∈ ℤ^∗_n, it is guaranteed that g has a multiplicative inverse mod n, which we can call g⁻¹. Then g⁻ⁱ can be defined as g⁻ⁱ ≝ (g⁻¹)i. All of the usual laws of exponents hold with respect to this definition of negative exponents.

Example

Taking n = 13, we have:

Thus 2 is a primitive root modulo 13. Each of the groups {1}, ℤ^∗₁₃, {1,3,9} is a cyclic group under multiplication mod 13.

A cyclic group may have more than one generator, for example:

Similarly, there are four primitive roots modulo 13 (equivalently, ℤ^∗₁₃ has four different generators); 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 ℤ^∗_p is a cyclic group).

Let us write ? = ⟨g⟩ = {gⁱ | i ∈ ℤ} to denote an unspecified cyclic group generated by g. The defining property of ? is that each of its elements can be written as a power of g. From this we can conclude that:

• Any cyclic group is closed under multiplication. That is, take any X,Y ∈ ?; then it must be possible to write X = g^x and Y = g^y for some integers x,y. Using the multiplication operation of ?, the product is XY = g^x+y, which is also in ?.
• Any cyclic group is closed under inverses. Take any X ∈ ?; then it must be possible to write X = g^x for some integer x. We can then see that g^−x ∈ ? by definition, and g^−xX = g^−x+x = g⁰ is the identity element. So X has a multiplicative inverse (g^−x) in ?.

These facts demonstrate that ? is indeed a group in the terminology of abstract algebra.

Discrete Logarithms

It is typically easy to compute the value of g^x in a cyclic group, given g and x. For example, when using a cyclic group of the form ℤ^∗_n, we can easily compute the modular exponentiation g^x % n using repeated squaring.

The inverse operation in a cyclic group is called the discrete logarithm problem

Definition 14.2: Discrete Log

The discrete logarithm problem is: given X ∈ ⟨g⟩, determine a number x such that g^x = X. Here the exponentiation is with respect to the multiplication operation in ? = ⟨g⟩.

The discrete logarithm problem is conjectured to 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 communication. 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: Diffie-Hellman

Both parties agree (publicly) on a cyclic group ? with generator g. Let n = |?|. All exponentiations are with respect to the group operation in ?.

1. Alice chooses a ← ℤ_n. She sends A = g^a to Bob.
2. Bob chooses b ← ℤ_n. He sends B = g^b to Alice.
3. Bob locally outputs K := A^b. Alice locally outputs K := B^a .

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

Defining Security for Key Agreement

Executing a key agreement protocol leaves two artifacts behind. First, we have the collection 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.

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 approach the definition:

• 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.
• 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 the resulted from the protocol execution, while in the other library the adversary obtains a totally unrelated key (chosen uniformly from the set Σ.? of possible keys).

Definition 14.4: KA Security

Let Σ be a key-agreement protocol. We write Σ.? for the keyspace of the protocol (i.e., the 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 ℒ^Σ_ka-real ≋ ℒ^Σ_ka-rand, where:

14.3: Decisional Diffie-Hellman Problem

The Diffie-Hellman protocol is parameterized by the choice of cyclic group ? (and generator g). Transcripts in the protocol consist of (g^a,g^b), where a and b are chosen uniformly. The key corresponding to such a transcript is g^ab. The set of possible keys is the cyclic group ?.

Let us substitute the details of the Diffie-Hellman protocol into the KA security libraries. After simplifying, we see that the security of the Diffie-Hellman protocol is equivalent to the following statement:

We have renamed the libraries to ℒ_dh-real and ℒ_dh-rand. In ℒ_dh-real the response to QUERY corresponds to a DHKA transcript (g^a,g^b) along with the corresponding “correct” key g^ab. The response in ℒ_dh-real corresponds to a DHKA transcript along with a completely independent random key g^c.

Definition 14.5: DDH

The decisional Diffie-Hellman (DDH) assumption in a cyclic group ? is that ℒ^?_dh-real ≋ ℒ^?_dh-rand (libraries defined above).

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 ? used in the protocol.

For Which Groups does the DDH Assumption Hold?

So far our only example of a cyclic group is ℤ^∗_p, 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 ℤ^∗_p. To see why, we introduce a new concept:

Claim 14.7: 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 g^x, Euler’s criterion says that it is possible to determine the parity of x (i.e., whether x is even or odd) given g^x.

To see how these observations lead to an attack against the Diffie Hellman protocol, consider the following attack:

Roughly speaking, the adversary returns true whenever C can be written as g raised to an even exponent. When linked to ℒ_dh-real, C = g^ab where a and b are chosen uniformly. Hence ab will be even with probability 3/4. When linked to ℒ_dh-rand, C = g^c for an independent 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 g^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 ∈ ℤ^∗_n is a quadratic residue modulo n if there exists some integer Y such that Y² ≡_n X. That is, if X can be obtained by squaring a number mod n. Let ℚℝ^∗_n ⊆ ℤ^∗_n denote the set of quadratic residues mod n.

For our purposes it is enough to know that, when p is prime, ℚℝ^∗_p 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 ℚℝ^∗_p when p is a safe prime.

Exercises

14.1: Let p be an odd prime, as usual. Recall that ℚℝ^∗_p is the set of quadratic residues mod p— that is, ℚℝ^∗_p = {x ∈ ℤ^∗_p| ∃y : x ≡_p y²}. Show that if g is a primitive root of ℤ^∗_p then ⟨g²⟩ = ℚℝ^∗_p.

Note: This means that g^a ∈ ℚℝ^∗_p if and only if a is even — and in particular, the choice of generator g doesn’t matter.

14.2: Suppose N = pq where p and q are distinct primes. Show that |ℚℝ^∗_N| = |ℚℝ^∗_p| · |ℚℝ^∗_q|.

Hint: Chinese remainder theorem.

14.3: Suppose you are given X ∈ ⟨g⟩. You are allowed to choose any X’ ≠ X and learn the discrete log of X’. (with respect to base g). Show that you can use this ability to learn the discrete log of X.

14.4: Let ⟨g⟩ be a cyclic group with n elements and generator g. Show that for all integers a, it is true that g^a = g^a%n.

Note: As a result, ⟨g⟩ is isomorphic to the additive group ℤ_n.

14.5: Let g be a primitive root of ℤ^∗_n. Recall that ℤ^∗_n has ϕ(n) elements. Show that g^a is a primitive root of ℤ^∗_n 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 ⟨g⟩ be a cyclic group with n elements. Show that for all x,y ∈ ⟨g⟩, it is true that xⁿ = yⁿ.

Hint: every x ∈ ⟨g⟩ can be written as x = g^a for some appropriate a. What is (g^a)ⁿ?

14.7: (a). Prove the following variant of Lemma 4.8: Suppose you fix a value x ∈ ℤ_N. Then when sampling q = √2N values r₁,. . . ,r_q uniformly from ℤ_N, with probability at least 0.6 there exist i ≠ j with r_i ≡_N r_j + x.

Hint: This is extremely similar to Exercise 4.7

(b). Let g be a primitive root of ℤ^∗_p (for some prime p). Consider the problem of computing the discrete log of X ∈ ℤ^∗_p with respect to g — that is, finding x such that X ≡_p g^x. Argue that if one can find integers r and s such that g^r ≡_p X · g^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 discrete logarithm problem in ℤ^∗_p.

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

What will be Alice & Bob’s shared key?

14.9: Explain what is wrong in the following argument:

In Diffie-Hellman key agreement, Alice sends A = g^a and Bob sends B = g^b. Their shared key is g^ab. To break the scheme, the eavesdropper can simply compute A · B = (g^a)(g^b) = g^ab.

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

Let DH = {(g^a,g^b,g^ab ) ∈ ?³ | a,b,∈ ℤ_n}.

(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 ?³.

(c). Consider the problem of determining whether a given triple (A,B,C) is in the set DH. Suppose you have an algorithm ? that solves this problem on average slightly better than chance. That is:

The algorithm ? 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 ? gives the wrong answer, and there’s no real way to know.

Show how to construct a randomized algorithm ?’ such that: for every (A,B,C) ∈ ?³:

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