Mathematical Cryptography

Section 3.3 Diffie-Hellman key exchange

A central issue in cryptography is how to share the private piece of information (the key) that Alice and Bob will use to send each other information. Once Alice and Bob share a key, they can use one of the many, fast methods of symmetric encryption in use (AES, for example). In their 1978 paper “New Directions in Cryptography”, Diffie and Hellman described a method of sharing a secret key that relies on the difficulty of solving the discrete log problem. The method is now known as Diffie-Hellman key exchange.

The basic scheme is as follows: Alice and Bob agree to a large prime number \(p\) and an element \(g \in \F_p\ad\) with large prime order. Alice selects a private key \(a \in \F_p\ad\) and likewise Bob chooses \(b \in \F_p\ad\text{.}\) Alice and Bob respectively compute the quantities \(A = g^a\) and \(B = g^b\text{.}\) Alice and Bob send each other these quantities. On receiving \(B\) from Bob, Alice computes \(k = B^a = g^{ab}\) and Bob computes \(k = A^b = g^{ab}\text{.}\) The quantity \(k\) is the shared key.

Suppose that Eve wants to recover the value of \(k\text{.}\) We assume that she knows \(p, g, A\) and \(B\text{.}\) If she could solve the discrete log problem

for \(x\text{,}\) then she would have \(a\) and thus be able to compute \(k\text{.}\) This is quite difficult if the values of the parameters involved are large enough. But this isn't the problem that she actually needs to solve.

The DHP provides an excellent illustration of the caution that needs to be taken when designing and evaluating a new cryptographic method. We should convince ourselves that the DHP is at least as difficult as the DLP. If Eve can solve the DLP, then she can obviously solve the DHP, since explicitly finding \(a,b\) would allow her to directly compute \(g^{ab}\text{.}\) That is to say, the DHP is at least as difficult as the DLP. (Note that the converse to this question is still unknown.)