Diffie Hellman Merkle

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.

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