TOPICS
Search

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 g and p, where p is large (typically at least 512 bits) and g is a primitive root modulo p. (In practice, it is a good idea to choose p such that (p-1)/2 is also prime.) The numbers g and p need not be kept secret from other users. Now Alice chooses a large random number a as her private key and Bob similarly chooses a large number b. Alice then computes A=g^a (mod p), which she sends to Bob, and Bob computes B=g^b (mod p), which he sends to Alice.

Now both Alice and Bob compute their shared key K=g^(ab) (mod p), which Alice computes as

 K=B^a (mod p)=(g^b)^a (mod p)

and Bob computes as

 K=A^b (mod p)=(g^a)^b (mod p).

Alice and Bob can now use their shared key K 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 K=g^(ab) (mod p) knowing only g, p, A=g^a (mod p) and B=g^b (mod p).

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


See also

Cryptography, Public-Key Cryptography, RSA Encryption

This entry contributed by David Terr

Explore with Wolfram|Alpha

References

Diffie, W. and Hellman, M. "New Directions in Cryptography." IEEE Trans. Info. Th. 22, 644-654, 1976.Hershey, J. E. Cryptography Demystified. New York: McGraw-Hill, pp. 162-166, 2003.Schneier, B Applied Cryptography: Protocols, Algorithms, and Source Code in C, 2nd ed. New York: Wiley, pp. 513-516, 1996.

Referenced on Wolfram|Alpha

Diffie-Hellman Protocol

Cite this as:

Terr, David. "Diffie-Hellman Protocol." From MathWorld--A Wolfram Web Resource, created by Eric W. Weisstein. https://mathworld.wolfram.com/Diffie-HellmanProtocol.html

Subject classifications