The basic number-theoretic facts presented in Subsection 7.1.3 will be needed in this and the subsequent sections. In particular, recall the multiplicative group from Example 7.3 and Euler's function. The arithmetics in remainder class rings will be explained at the end of this chapter, see Problem 7-1.

Figure 7.7 shows the Diffie-Hellman secret-key agreement protocol, which is based on exponentiation with base and modulus , where is a prime number and is a primitive root of . A *primitive root of a number*
is any element such that for each with . A primitive root of generates the entire group , i.e., . Recall that for any prime number the group has order . has exactly primitive roots, see also Exercise 7.2-1.

**Example 7.5 **Consider . Since , we have , and the two primitive roots of are and . Both and generate all of , since:

Not every number has a primitive root; is the smallest such example. It is known that a number has a primitive root if and only if either is from , or has the form or for some odd prime number .

**Definition 7.12 **
**(Discrete logarithm)**
*Let be a prime number, and let be a primitive root of . The modular exponential function with base
and modulus
is the function that maps from to , and is defined by . Its inverse function is called the discrete logarithm, and maps for fixed and the value to . We write .*

The protocol given in Figure 7.7 works, since (in the arithmetics modulo )

so Alice indeed computes the same key as Bob. Computing this key is not hard, since modular exponentiation can be performed efficiently using the square-and-multiply method from algorithm *
Square-and-Multiply
*.

Erich, however, has a hard time when he attempts to determine their key, since the discrete logarithm is considered to be a hard problem. That is why the modular exponential function is a candidate of a *one-way function*, a function that is easy to compute but hard to invert. Note that it is not known whether or not one-way functions indeed exist; this is one of the most challenging open research questions in cryptography. The security of many cryptosystems rests on the assumption that one-way functions indeed exist.

*
Square-and-Multiply(
)
*

```
1
is the modulus, is the base, and is the exponent 2 determine the binary expansion of the exponent , where 3 compute successively , where , using that 4 compute in the arithmetics modulo 5 as soon as a factor in the product and are determined,
can be deleted and need not be stored 6
```**
**`RETURN`

Why can the modular exponential function be computed efficiently? Naively performed, this computation may require many multiplications, depending on the size of the exponent . However, using algorithm *
Square-and-Multiply
* there is no need to perform multiplications as in the naive approach; no more than multiplications suffice. The square-and-multiply algorithm thus speeds modular exponentiation up by an exponential factor.

Note that in the arithmetics modulo , we have

Thus, the algorithm *
Square-and-Multiply
* is correct.

**Example 7.6 **[Square-and-Multiply in the Diffie-Hellman Protocol] Alice and Bob have chosen the prime number and the primitive root of . Alice picks the secret number . In order to send her public number to Bob, Alice wishes to compute . The binary expansion of the exponent is . Alice successively computes the values:

Then, she computes . Note that Alice does not have to multiply times but merely performs four squarings and one multiplication to determine .

Suppose that Bob has chosen the secret exponent . By the same method, he can compute his part of the key, . Now, Alice and Bob determine their joint secret key according to the Diffie-Hellman protocol from Figure 7.7; see Exercise 7.2-2.

Note that the protocol is far from being secure in this case, since the prime number and the secret exponents and are much too small. This toy example was chosen just to explain how the protocol works. In practice, and should have at least bits each.

If Erich was listening very careful, he knows the values , , , and after Alice and Bob have executed the protocol. His aim is to determine their joint secret key . This problem is known as the *Diffie-Hellman problem*. If Erich were able to determine and efficiently, he could compute the key just like Alice and Bob and thus would have solved the Diffie-Hellman problem. Thus, this problem is no harder than the problem of computing discrete logarithms. The converse question of whether or not the Diffie-Hellman problem is *at least* as hard as solving the discrete logarithm (i.e., whether or not the two problems are equally hard) is still just an unproven conjecture. As many other cryptographic protocols, the Diffie-Hellman protocol currently has no proof of security.

However, since up to date neither the discrete logarithm nor the Diffie-Hellman problem can be solved efficiently, this direct attack is not a practical threat. On the other hand, there do exist other, indirect attacks in which the key is determined not immediately from the values and communicated in the Diffie-Hellman protocol. For example, Diffie-Hellman is vulnerable by the “*man-in-the-middle*” attack. Unlike the *passive* attack described above, this attack is *active*, since the attacker Erich aims at actively altering the protocol to his own advantage. He is the “man in the middle” between Alice and Bob, and he intercepts Alice's message to Bob and Bob's message to Alice. Instead of and , he forwards his own values to Bob and to Alice, where the private numbers and were chosen by Erich. Now, if Alice computes her key , which she falsely presumes to share with Bob, in fact is a key for future communications with Erich, who determines the same key by computing (in the arithmetics modulo )

Similarly, Erich can share a key with Bob, who has not the slightest idea that he in fact communicates with Erich. This raised the issue of *authentication*, which we will deal with in more detail later in Section 7.5 about zero-knowledge protocols.

**Exercises**

7.2-1 *a.* How many primitive roots do and have?

*b.* Determine all primitive roots of and , and prove that they indeed are primitive roots.

*c.* Show that every primitive root of and of , respectively, generates all of and .

7.2-2 *a.* Determine Bob's number from Example 7.6 using the algorithm *
Square-and-Multiply
*.

*b.* For and from Example 7.6, determine the joint secret key of Alice and Bob according to the Diffie-Hellman protocol from Figure 7.7.