Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

10.4 Diffie-Hellman Key Exchange

An important problem in cryptography is how to establish keys for use in cryptographic protocols such as DES or AES, especially when the two parties are widely separated. Public key methods such as RSA provide one solution. In the present section, we describe a different method, due to Diffie and Hellman, whose security is very closely related to the difficulty of computing discrete logarithms.

There are several technical implementation issues related to any key distribution scheme. Some of these are discussed in Chapter 15. In the present section, we restrict ourselves to the basic Diffie-Hellman algorithm. For more discussion of some security concerns about implementations of the Diffie-Hellman protocol, see [Adrian et al.].

Here is how Alice and Bob establish a private key $K$ $K$ . All of their communications in the following algorithm are over public channels.

Either Alice or Bob selects a large prime number $p$ $p$ for which the discrete logarithm problem is hard and a primitive root $α (mod p)$ $α (mod p)$ . Both $p$ $p$ and $α$ $α$ can be made public.
Alice chooses a secret random $x$ $x$ with $1 \leq x \leq p - 2$ $1 \leq x \leq p - 2$ , and Bob selects a secret random $y$ $y$ with $1 \leq y \leq p - 2$ $1 \leq y \leq p - 2$ .
Alice sends $α^{x} (mod p)$ $α^{x} (mod p)$ to Bob, and Bob sends $α^{y} (mod p)$ $α^{y} (mod p)$ to Alice.
Using the messages that they each have received, they can each calculate the session key $K$ $K$ . Alice calculates $K$ $K$ by $K \equiv (α^{y})^{x} (mod p)$ $K \equiv (α^{y})^{x} (mod p)$ , and Bob calculates $K$ $K$ by $K \equiv (α^{x})^{y} (mod p)$ $K \equiv (α^{x})^{y} (mod p)$ .

There is no reason that Alice and Bob need to use all of $K$ $K$ as their key for their communications. Now that they have the same number $K$ $K$ , they can use some prearranged procedure to produce a key. For example, they could use the middle 56 bits of $K$ $K$ to obtain a DES key.

Suppose Eve listens to all the communications between Alice and Bob. She will know $α^{x}$ $α^{x}$ and $α^{y}$ $α^{y}$ . If she can compute discrete logs, then she can find the discrete log of $α^{x}$ $α^{x}$ to obtain $x$ $x$ . Then she raises $α^{y}$ $α^{y}$ to the power $x$ $x$ to obtain $α^{x y} \equiv K$ $α^{x y} \equiv K$ . Once Eve has $K$ $K$ , she can use the same procedure as Alice and Bob to extract a communication key. Therefore, if Eve can compute discrete logs, she can break the system.

However, Eve does not necessarily need to compute $x$ $x$ or $y$ $y$ to find $K$ $K$ . What she needs to do is solve the following:

Computational Diffie-Hellman Problem: Let $p$ $p$ be prime and let $α$ $α$ be a primitive root mod $p$ $p$ . Given $α^{x} (mod p)$ $α^{x} (mod p)$ and $α^{y} (mod p)$ $α^{y} (mod p)$ , find $α^{x y} (mod p)$ $α^{x y} (mod p)$ .

It is not known whether or not this problem is easier than computing discrete logs. The reasoning above shows that it is no harder than computing discrete logs. A related problem is the following:

Decision Diffie-Hellman Problem: Let $p$ $p$ be prime and let $α$ $α$ be a primitive root mod $p$ $p$ . Given $α^{x} (mod p)$ $α^{x} (mod p)$ and $α^{y} (mod p)$ $α^{y} (mod p)$ , and $c \equiv 0 (mod p)$ $c \equiv 0 (mod p)$ , decide whether or not $c \equiv α^{x y} (mod p)$ $c \equiv α^{x y} (mod p)$ .

In other words, if Eve claims that she has found $c$ $c$ with $c \equiv α^{x y} (mod p)$ $c \equiv α^{x y} (mod p)$ , and offers to sell you this information, can you decide whether or not she is telling the truth? Of course, if you can solve the computational Diffie-Hellman problem, then you simply compute $α^{x y} (mod p)$ $α^{x y} (mod p)$ and check whether it is $c$ $c$ (and then you can ignore Eve’s offer).

Conversely, does a method for solving the decision Diffie-Hellman problem yield a solution to the computational Diffie-Hellman problem? This is not known at present. One obvious method is to choose many values of $c$ $c$ and check each value until one equals $α^{x y} (mod p)$ $α^{x y} (mod p)$ . But this brute force method takes at least as long as computing discrete logarithms by brute force, so is impractical. There are situations involving elliptic curves, analogous to the present setup, where a fast solution is known for the decision Diffie-Hellman problem but no practical solution is known for the computational Diffie-Hellman problem (see Exercise 8 in Chapter 22).

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for 10.4 Diffie-Hellman Key Exchange

Create new playlist

Sign In

Sign Up

Table of Contents for
10.4 Diffie-Hellman Key Exchange