Often called the Diffie-Hellman key exchange protocol, it should more accurately be called a key-negotiation protocol. It uses an insecure channel to agree a secret key with another party. Diffie has suggested it should be called Diffie-Hellman-Merkle.
See also
http://en.wikipedia.org/wiki/Diffie-Hellman
It works like this. Over the insecure channel
AliceAndBob agree a base,
s and a modulus
m. The modulus should be a sodding enormous prime, and there are a few technical things to avoid. All calculations are understood to be done modulo
m.
Then Alice chooses a secret number
a and computes
A=s^a, and Bob chooses a secret number
b and computes
B=s^b. These are then sent to each other.
Alice receives
B and computes
k1 = B^a and Bob receives
A and computes
k2 = A^b. Magically,
k1==k2 and that can be used as a key for a "normal" crypto system such as IDEA, Blowfish or whatever.
In summary:
- Alice and Bob agree s and m
- Alice chooses a and computes A=s^a
- Bob chooses b and computes B=s^b.
- Alice receives B and computes k = B^a
- Bob receives A and computes k = A^b
- k is used as the key in a symmetric cipher.
This works because the
DiscreteLogarithmProblem seems to be hard, and because
-
- k1 = B^a
-
- = (s^b)^a
-
- = s^(b*a)
-
- = s^(a*b)
-
- = (s^a)^b
-
- = A^b
-
- = k2,
all arithmetic being done modulo
m.
This is, of course, prone to the "man-in-the-middle" attack, where someone sits in the middle and to each pretends to be the other.
CategoryCryptography CategoryMath