Chapter 14: Diffie-Hellman Key Agreement

14.1: Cyclic Groups

Definition 14.1

Let g ∈ ℤn. Define ⟨g⟩n = {gi % 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.

Ifgn = ℤ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−1. Then g−i can be defined as g−i ≝ (g−1)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}, ℤ13, {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,13 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⟩ = {gi | 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 = gx and Y = gy for some integers x,y. Using the multiplication operation of ?, the product is XY = gx+y, which is also in ?.
• Any cyclic group is closed under inverses. Take any X ∈ ?; then it must be possible to write X = gx for some integer x. We can then see that gx ∈ ? by definition, and gxX = gx+x = g0 is the identity element. So X has a multiplicative inverse (gx) 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 gx 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 gx % 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 gx = 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 = ga to Bob.
2. Bob chooses b ← ℤn. He sends B = gb to Alice.
3. Bob locally outputs K := Ab. Alice locally outputs K := Ba .

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

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 (ga,gb), where a and b are chosen uniformly. The key corresponding to such a transcript is gab. 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 (ga,gb) along with the corresponding “correct” key gab. The response in ℒdh-real corresponds to a DHKA transcript along with a completely independent random key gc.

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

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 = gab where a and b are chosen uniformly. Hence ab will be even with probability 3/4. When linked to ℒdh-rand, C = gc 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 gab will never be uniformly distributed. See the exercises for a slightly better attack which correlates the key to the transcript.

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 Y2n 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 : xp y2}. Show that if g is a primitive root of ℤp then ⟨g2⟩ = ℚℝp.

Note: This means that ga ∈ ℚℝ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 ga = ga%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 ga 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 xn = yn.

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

14.7: (a). Prove the following variant of Lemma 4.8: Suppose you fix a value x ∈ ℤN. Then when sampling q = √2N values r1,. . . ,rq uniformly from ℤN, with probability at least 0.6 there exist ij with riN rj + x.

HintThis 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 Xp gx. Argue that if one can find integers r and s such that grp X · gs 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 = ga and Bob sends B = gb. Their shared key is gab. To break the scheme, the eavesdropper can simply compute A · B = (ga)(gb) = gab.

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

Let DH = {(ga,gb,gab ) ∈ ?3 | 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 ?3.

(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) ∈ ?3:

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.