Diffie-Hellman

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

The Diffie-Hellman key agreement protocol (also called exponential key agreement) was developed by Whitfield Diffie and Martin Hellman in 1976 and published in the ground-breaking paper "New Directions in Cryptography." The protocol allows two users to exchange a secret key over an insecure medium without any prior secrets.

U.S. Patent 4,200,770, now expired, describes the algorithm and credits Hellman, Diffie, and Merkle as inventors.

The Algorithm

• First the hosts must get the "Diffie-Hellman parameters". A prime number, 'p' (larger than 2) and "base", 'g', an integer that is smaller than 'p'. They can either be hard coded or fetched from a server.

• The hosts each secretly generate a private number called 'x', which is less than "p - 1".

• The hosts next generate the public keys, 'y'. They are created with the function:

y = g^x % p

• The two host now exchange the public keys ('y') and the exchanged numbers are converted into a secret key, 'z'.

z = y^x % p

'z' can now be used as the key for whatever encryption method is used to transfer information between the two hosts. Mathematically, the two hosts should have generated the same value for 'z'.

z = (g^x % p)^x' % p = (g^x' % p)^x % 

All of these numbers are positve integers

x^y	means: x is raised to the y power
x%y	means: x is divided by y and the remainder is returned 

References

• What is Diffie-Hellman?
• Diffie-Hellman Method For Key Agreement - Copyright (c) 1997 Benjamin Levy

External Links

• A Review of the Diffie-Hellman Algorithm and its Use in Secure Internet Protocols