[From  http://searchsecurity.techtarget.com/tip/1,289483,sid14_gci876048,00.html ]

NETWORK SECURITY TACTICS
Diffie-Hellman key exchange
Mike Chapple, CISSP
01.23.2003

If you've had any experience choosing a cryptographic algorithm,
you've probably faced a common dilemma at one time or another:
should you use an asymmetric (public key) or symmetric (private key) algorithm?

From a key exchange point-of-view, public key algorithms are much simpler
to administer.
Users may freely share their public keys over insecure transmission channels
without fear of compromising the cryptosystem.
In order for pure private key systems to remain truly secure,
offline key exchange techniques (such as a floppy diskette) must be used.
On the other hand, symmetric algorithms generally operate much faster
than their asymmetric counterparts.

Diffie-Hellman key exchange offers the best of both worlds -- it
uses public key techniques to allow the exchange of
a private encryption key!
Let's take a look at how the protocol works, from the perspective
of Alice and Bob, two users who wish to establish secure communications.
We can assume that Alice and Bob know nothing about each other but
are in contact.
Here are the nine steps of the process:

   1. Communicating in the clear, Alice and Bob agree on two large
      positive integers, n and g, with the stipulation that n is a
      prime number and g is a generator of n.

   2. Alice randomly chooses another large positive integer, XA,
      which is smaller than n. XA will serve as Alice's private key.

   3. Bob similarly chooses his own private key, XB.

   4. Alice computes her public key, YA, using the formula YA = (g^XA) mod n.

   5. Bob similarly computes his public key, YB, using the
      formula YB = (g^XB) mod n.

   6. Alice and Bob exchange public keys over the insecure circuit.

   7. Alice computes the shared secret key, k, using the
      formula k = (YB ^XA) mod n.

   8. Bob computes the same shared secret key, k, using the
      formula k = (YA ^XB) mod n.

   9. Alice and Bob communicate using the symmetric algorithm of their
      choice and the shared secret key, k, which was never transmitted
      over the insecure circuit.

Pretty nifty, eh?
Diffie-Hellman key exchange is actually nothing new.
It's been around since Whitfield Diffie and Martin Hellman published it
in their 1976 paper, "New Directions in Cryptography."
However, the recent surge of interest in cryptography and secure
communications have increased awareness of the protocol.
In fact, you've probably unknowingly used the Diffie-Hellman protocol
on a daily basis.  It's used by popular protocols like SSL and SSH.

About the author
Mike Chapple, CISSP, currently serves as Chief Information Officer of
the Brand Institute, a Miami-based marketing consultancy.
He previously worked as an information security researcher for the U.S.
National Security Agency.
His publishing credits include the TICSA Training Guide from Que Publishing,
the CISSP Study Guide from Sybex and the upcoming SANS GSEC Prep Guide
from John Wiley. He's also the About.com Guide to Databases.

----------------------------------------------

Example:  [ Adapted from "Network Security Essentials" 3rd Ed., by
 William Stallings.  (C)2007 Pearson (Prentice-Hall).  pp. 80-83 ]

Alice and Bob agree to use n=353 as the "big" prime number n, and
g="3" as the generator g, or "primitive root" of n.

Alice (randomly) picks 97 as her private key XA.  She then calculates
her public key YA = (g ** XA) mod n = 3 ** 97 mod 353 = 40.

Meanwhile Bob randomly picks 233 for his private key XB.  He then
calculates his public key YB = (g ** XB) mod n = 3**233 mod 353 = 248.

Alice and Bob exchange public keys YA and YB.

Alice calculates the secret shared key K with:
   K = (YB ** XA) mod n = (248 ** 97) mod 353 = 160.

Bob calculates the same secret shared key K with:
   K = (YA ** XB_ mod n = (40 ** 233) mod 353 = 160.

Note an opponent listening in will only know n, g, YA and YB.
To figure out the shared secret key K the opponent must
solve the reverse problem.  The security relies on the fact that
computing exponents is easy but computing the matching discrete
logarithm is hard.

In this case an attacker would need to find one of the private
keys to comput K.  To find XA, the attacker must solve
(g ** XA) mod n = YA, or (3 ** XA) mod 353 = 40.  By using
a brute-force search of all possible values for XA, the opponent
will eventually find XA=97, and can then compute K.

Obviously you need to pick a very large value for n to have any security!