Diffie-Hellman Protocol

The Diffie-Hellman protocol is a method for two computer users to generate a shared private key with which they can then exchange information across an insecure channel. Let the users be named Alice and Bob. First, they agree on two prime numbers and , where is large (typically at least 512 bits) and is a primitive root modulo . (In practice, it is a good idea to choose such that is also prime.) The numbers and need not be kept secret from other users. Now Alice chooses a large random number as her private key and Bob similarly chooses a large number . Alice then computes , which she sends to Bob, and Bob computes , which he sends to Alice.

Now both Alice and Bob compute their shared key , which Alice computes as

and Bob computes as

Alice and Bob can now use their shared key to exchange information without worrying about other users obtaining this information. In order for a potential eavesdropper (Eve) to do so, she would first need to obtain knowing only , , and .

This can be done by computing from or from . This is the discrete logarithm problem, which is computationally infeasible for large . Computing the discrete logarithm of a number modulo takes roughly the same amount of time as factoring the product of two primes the same size as , which is what the security of the RSA cryptosystem relies on. Thus, the Diffie-Hellman protocol is roughly as secure as RSA.

Wolfram Web Resources